FLAC/src/bitreader.c

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2000-2009  Josh Coalson
   3  * Copyright (C) 2011-2018  Xiph.Org Foundation
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *
  12  * - Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  *
  16  * - Neither the name of the Xiph.org Foundation nor the names of its
  17  * contributors may be used to endorse or promote products derived from
  18  * this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #ifdef HAVE_CONFIG_H
  34 #  include <config.h>
  35 #endif
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include "private/bitmath.h"
  40 #include "private/bitreader.h"
  41 #include "private/crc.h"
  42 #include "private/macros.h"
  43 #include "FLAC/assert.h"
  44 #include "share/compat.h"
  45 #include "share/endswap.h"
  46
  47 /* Things should be fastest when this matches the machine word size */
  48 /* WATCHOUT: if you change this you must also change the following #defines down to COUNT_ZERO_MSBS2 below to match */
  49 /* WATCHOUT: there are a few places where the code will not work unless brword is >= 32 bits wide */
  50 /*           also, some sections currently only have fast versions for 4 or 8 bytes per word */
  51
  52 #if (ENABLE_64_BIT_WORDS == 0)
  53
  54 typedef FLAC__uint32 brword;
  55 #define FLAC__BYTES_PER_WORD 4          /* sizeof brword */
  56 #define FLAC__BITS_PER_WORD 32
  57 #define FLAC__WORD_ALL_ONES ((FLAC__uint32)0xffffffff)
  58 /* SWAP_BE_WORD_TO_HOST swaps bytes in a brword (which is always big-endian) if necessary to match host byte order */
  59 #if WORDS_BIGENDIAN
  60 #define SWAP_BE_WORD_TO_HOST(x) (x)
  61 #else
  62 #define SWAP_BE_WORD_TO_HOST(x) ENDSWAP_32(x)
  63 #endif
  64 /* counts the # of zero MSBs in a word */
  65 #define COUNT_ZERO_MSBS(word) FLAC__clz_uint32(word)
  66 #define COUNT_ZERO_MSBS2(word) FLAC__clz2_uint32(word)
  67
  68 #else
  69
  70 typedef FLAC__uint64 brword;
  71 #define FLAC__BYTES_PER_WORD 8          /* sizeof brword */
  72 #define FLAC__BITS_PER_WORD 64
  73 #define FLAC__WORD_ALL_ONES ((FLAC__uint64)FLAC__U64L(0xffffffffffffffff))
  74 /* SWAP_BE_WORD_TO_HOST swaps bytes in a brword (which is always big-endian) if necessary to match host byte order */
  75 #if WORDS_BIGENDIAN
  76 #define SWAP_BE_WORD_TO_HOST(x) (x)
  77 #else
  78 #define SWAP_BE_WORD_TO_HOST(x) ENDSWAP_64(x)
  79 #endif
  80 /* counts the # of zero MSBs in a word */
  81 #define COUNT_ZERO_MSBS(word) FLAC__clz_uint64(word)
  82 #define COUNT_ZERO_MSBS2(word) FLAC__clz2_uint64(word)
  83
  84 #endif
  85
  86 /*
  87  * This should be at least twice as large as the largest number of words
  88  * required to represent any 'number' (in any encoding) you are going to
  89  * read.  With FLAC this is on the order of maybe a few hundred bits.
  90  * If the buffer is smaller than that, the decoder won't be able to read
  91  * in a whole number that is in a variable length encoding (e.g. Rice).
  92  * But to be practical it should be at least 1K bytes.
  93  *
  94  * Increase this number to decrease the number of read callbacks, at the
  95  * expense of using more memory.  Or decrease for the reverse effect,
  96  * keeping in mind the limit from the first paragraph.  The optimal size
  97  * also depends on the CPU cache size and other factors; some twiddling
  98  * may be necessary to squeeze out the best performance.
  99  */
 100 static const uint32_t FLAC__BITREADER_DEFAULT_CAPACITY = 65536u / FLAC__BITS_PER_WORD; /* in words */
 101
 102 struct FLAC__BitReader {
 103         /* any partially-consumed word at the head will stay right-justified as bits are consumed from the left */
 104         /* any incomplete word at the tail will be left-justified, and bytes from the read callback are added on the right */
 105         brword *buffer;
 106         uint32_t capacity; /* in words */
 107         uint32_t words; /* # of completed words in buffer */
 108         uint32_t bytes; /* # of bytes in incomplete word at buffer[words] */
 109         uint32_t consumed_words; /* #words ... */
 110         uint32_t consumed_bits; /* ... + (#bits of head word) already consumed from the front of buffer */
 111         uint32_t read_crc16; /* the running frame CRC */
 112         uint32_t crc16_offset; /* the number of words in the current buffer that should not be CRC'd */
 113         uint32_t crc16_align; /* the number of bits in the current consumed word that should not be CRC'd */
 114         FLAC__BitReaderReadCallback read_callback;
 115         void *client_data;
 116 };
 117
 118 static inline void crc16_update_word_(FLAC__BitReader *br, brword word)
 119 {
 120         register uint32_t crc = br->read_crc16;
 121
 122         for( ; br->crc16_align < FLAC__BITS_PER_WORD; br->crc16_align += 8)
 123                 crc = FLAC__CRC16_UPDATE((uint32_t)((word >> (FLAC__BITS_PER_WORD-8-br->crc16_align)) & 0xff), crc);
 124
 125         br->read_crc16 = crc;
 126         br->crc16_align = 0;
 127 }
 128
 129 static inline void crc16_update_block_(FLAC__BitReader *br)
 130 {
 131         if(br->consumed_words > br->crc16_offset && br->crc16_align)
 132                 crc16_update_word_(br, br->buffer[br->crc16_offset++]);
 133
 134 #if FLAC__BYTES_PER_WORD == 4
 135         br->read_crc16 = FLAC__crc16_update_words32(br->buffer + br->crc16_offset, br->consumed_words - br->crc16_offset, br->read_crc16);
 136 #elif FLAC__BYTES_PER_WORD == 8
 137         br->read_crc16 = FLAC__crc16_update_words64(br->buffer + br->crc16_offset, br->consumed_words - br->crc16_offset, br->read_crc16);
 138 #else
 139         unsigned i;
 140
 141         for(i = br->crc16_offset; i < br->consumed_words; i++)
 142                 crc16_update_word_(br, br->buffer[i]);
 143 #endif
 144
 145         br->crc16_offset = 0;
 146 }
 147
 148 static FLAC__bool bitreader_read_from_client_(FLAC__BitReader *br)
 149 {
 150         uint32_t start, end;
 151         size_t bytes;
 152         FLAC__byte *target;
 153
 154         /* first shift the unconsumed buffer data toward the front as much as possible */
 155         if(br->consumed_words > 0) {
 156                 crc16_update_block_(br); /* CRC consumed words */
 157
 158                 start = br->consumed_words;
 159                 end = br->words + (br->bytes? 1:0);
 160                 memmove(br->buffer, br->buffer+start, FLAC__BYTES_PER_WORD * (end - start));
 161
 162                 br->words -= start;
 163                 br->consumed_words = 0;
 164         }
 165
 166         /*
 167          * set the target for reading, taking into account word alignment and endianness
 168          */
 169         bytes = (br->capacity - br->words) * FLAC__BYTES_PER_WORD - br->bytes;
 170         if(bytes == 0)
 171                 return false; /* no space left, buffer is too small; see note for FLAC__BITREADER_DEFAULT_CAPACITY  */
 172         target = ((FLAC__byte*)(br->buffer+br->words)) + br->bytes;
 173
 174         /* before reading, if the existing reader looks like this (say brword is 32 bits wide)
 175          *   bitstream :  11 22 33 44 55            br->words=1 br->bytes=1 (partial tail word is left-justified)
 176          *   buffer[BE]:  11 22 33 44 55 ?? ?? ??   (shown laid out as bytes sequentially in memory)
 177          *   buffer[LE]:  44 33 22 11 ?? ?? ?? 55   (?? being don't-care)
 178          *                               ^^-------target, bytes=3
 179          * on LE machines, have to byteswap the odd tail word so nothing is
 180          * overwritten:
 181          */
 182 #if WORDS_BIGENDIAN
 183 #else
 184         if(br->bytes)
 185                 br->buffer[br->words] = SWAP_BE_WORD_TO_HOST(br->buffer[br->words]);
 186 #endif
 187
 188         /* now it looks like:
 189          *   bitstream :  11 22 33 44 55            br->words=1 br->bytes=1
 190          *   buffer[BE]:  11 22 33 44 55 ?? ?? ??
 191          *   buffer[LE]:  44 33 22 11 55 ?? ?? ??
 192          *                               ^^-------target, bytes=3
 193          */
 194
 195         /* read in the data; note that the callback may return a smaller number of bytes */
 196         if(!br->read_callback(target, &bytes, br->client_data))
 197                 return false;
 198
 199         /* after reading bytes 66 77 88 99 AA BB CC DD EE FF from the client:
 200          *   bitstream :  11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF
 201          *   buffer[BE]:  11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF ??
 202          *   buffer[LE]:  44 33 22 11 55 66 77 88 99 AA BB CC DD EE FF ??
 203          * now have to byteswap on LE machines:
 204          */
 205 #if WORDS_BIGENDIAN
 206 #else
 207         end = (br->words*FLAC__BYTES_PER_WORD + br->bytes + (uint32_t)bytes + (FLAC__BYTES_PER_WORD-1)) / FLAC__BYTES_PER_WORD;
 208         for(start = br->words; start < end; start++)
 209                 br->buffer[start] = SWAP_BE_WORD_TO_HOST(br->buffer[start]);
 210 #endif
 211
 212         /* now it looks like:
 213          *   bitstream :  11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF
 214          *   buffer[BE]:  11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF ??
 215          *   buffer[LE]:  44 33 22 11 88 77 66 55 CC BB AA 99 ?? FF EE DD
 216          * finally we'll update the reader values:
 217          */
 218         end = br->words*FLAC__BYTES_PER_WORD + br->bytes + (uint32_t)bytes;
 219         br->words = end / FLAC__BYTES_PER_WORD;
 220         br->bytes = end % FLAC__BYTES_PER_WORD;
 221
 222         return true;
 223 }
 224
 225 /***********************************************************************
 226  *
 227  * Class constructor/destructor
 228  *
 229  ***********************************************************************/
 230
 231 FLAC__BitReader *FLAC__bitreader_new(void)
 232 {
 233         FLAC__BitReader *br = calloc(1, sizeof(FLAC__BitReader));
 234
 235         /* calloc() implies:
 236                 memset(br, 0, sizeof(FLAC__BitReader));
 237                 br->buffer = 0;
 238                 br->capacity = 0;
 239                 br->words = br->bytes = 0;
 240                 br->consumed_words = br->consumed_bits = 0;
 241                 br->read_callback = 0;
 242                 br->client_data = 0;
 243         */
 244         return br;
 245 }
 246
 247 void FLAC__bitreader_delete(FLAC__BitReader *br)
 248 {
 249         FLAC__ASSERT(0 != br);
 250
 251         FLAC__bitreader_free(br);
 252         free(br);
 253 }
 254
 255 /***********************************************************************
 256  *
 257  * Public class methods
 258  *
 259  ***********************************************************************/
 260
 261 FLAC__bool FLAC__bitreader_init(FLAC__BitReader *br, FLAC__BitReaderReadCallback rcb, void *cd)
 262 {
 263         FLAC__ASSERT(0 != br);
 264
 265         br->words = br->bytes = 0;
 266         br->consumed_words = br->consumed_bits = 0;
 267         br->capacity = FLAC__BITREADER_DEFAULT_CAPACITY;
 268         br->buffer = malloc(sizeof(brword) * br->capacity);
 269         if(br->buffer == 0)
 270                 return false;
 271         br->read_callback = rcb;
 272         br->client_data = cd;
 273
 274         return true;
 275 }
 276
 277 void FLAC__bitreader_free(FLAC__BitReader *br)
 278 {
 279         FLAC__ASSERT(0 != br);
 280
 281         if(0 != br->buffer)
 282                 free(br->buffer);
 283         br->buffer = 0;
 284         br->capacity = 0;
 285         br->words = br->bytes = 0;
 286         br->consumed_words = br->consumed_bits = 0;
 287         br->read_callback = 0;
 288         br->client_data = 0;
 289 }
 290
 291 FLAC__bool FLAC__bitreader_clear(FLAC__BitReader *br)
 292 {
 293         br->words = br->bytes = 0;
 294         br->consumed_words = br->consumed_bits = 0;
 295         return true;
 296 }
 297
 298 void FLAC__bitreader_dump(const FLAC__BitReader *br, FILE *out)
 299 {
 300         uint32_t i, j;
 301         if(br == 0) {
 302                 fprintf(out, "bitreader is NULL\n");
 303         }
 304         else {
 305                 fprintf(out, "bitreader: capacity=%u words=%u bytes=%u consumed: words=%u, bits=%u\n", br->capacity, br->words, br->bytes, br->consumed_words, br->consumed_bits);
 306
 307                 for(i = 0; i < br->words; i++) {
 308                         fprintf(out, "%08X: ", i);
 309                         for(j = 0; j < FLAC__BITS_PER_WORD; j++)
 310                                 if(i < br->consumed_words || (i == br->consumed_words && j < br->consumed_bits))
 311                                         fprintf(out, ".");
 312                                 else
 313                                         fprintf(out, "%01d", br->buffer[i] & ((brword)1 << (FLAC__BITS_PER_WORD-j-1)) ? 1:0);
 314                         fprintf(out, "\n");
 315                 }
 316                 if(br->bytes > 0) {
 317                         fprintf(out, "%08X: ", i);
 318                         for(j = 0; j < br->bytes*8; j++)
 319                                 if(i < br->consumed_words || (i == br->consumed_words && j < br->consumed_bits))
 320                                         fprintf(out, ".");
 321                                 else
 322                                         fprintf(out, "%01d", br->buffer[i] & ((brword)1 << (br->bytes*8-j-1)) ? 1:0);
 323                         fprintf(out, "\n");
 324                 }
 325         }
 326 }
 327
 328 void FLAC__bitreader_reset_read_crc16(FLAC__BitReader *br, FLAC__uint16 seed)
 329 {
 330         FLAC__ASSERT(0 != br);
 331         FLAC__ASSERT(0 != br->buffer);
 332         FLAC__ASSERT((br->consumed_bits & 7) == 0);
 333
 334         br->read_crc16 = (uint32_t)seed;
 335         br->crc16_offset = br->consumed_words;
 336         br->crc16_align = br->consumed_bits;
 337 }
 338
 339 FLAC__uint16 FLAC__bitreader_get_read_crc16(FLAC__BitReader *br)
 340 {
 341         FLAC__ASSERT(0 != br);
 342         FLAC__ASSERT(0 != br->buffer);
 343
 344         /* CRC consumed words up to here */
 345         crc16_update_block_(br);
 346
 347         FLAC__ASSERT((br->consumed_bits & 7) == 0);
 348         FLAC__ASSERT(br->crc16_align <= br->consumed_bits);
 349
 350         /* CRC any tail bytes in a partially-consumed word */
 351         if(br->consumed_bits) {
 352                 const brword tail = br->buffer[br->consumed_words];
 353                 for( ; br->crc16_align < br->consumed_bits; br->crc16_align += 8)
 354                         br->read_crc16 = FLAC__CRC16_UPDATE((uint32_t)((tail >> (FLAC__BITS_PER_WORD-8-br->crc16_align)) & 0xff), br->read_crc16);
 355         }
 356         return br->read_crc16;
 357 }
 358
 359 inline FLAC__bool FLAC__bitreader_is_consumed_byte_aligned(const FLAC__BitReader *br)
 360 {
 361         return ((br->consumed_bits & 7) == 0);
 362 }
 363
 364 inline uint32_t FLAC__bitreader_bits_left_for_byte_alignment(const FLAC__BitReader *br)
 365 {
 366         return 8 - (br->consumed_bits & 7);
 367 }
 368
 369 inline uint32_t FLAC__bitreader_get_input_bits_unconsumed(const FLAC__BitReader *br)
 370 {
 371         return (br->words-br->consumed_words)*FLAC__BITS_PER_WORD + br->bytes*8 - br->consumed_bits;
 372 }
 373
 374 FLAC__bool FLAC__bitreader_read_raw_uint32(FLAC__BitReader *br, FLAC__uint32 *val, uint32_t bits)
 375 {
 376         FLAC__ASSERT(0 != br);
 377         FLAC__ASSERT(0 != br->buffer);
 378
 379         FLAC__ASSERT(bits <= 32);
 380         FLAC__ASSERT((br->capacity*FLAC__BITS_PER_WORD) * 2 >= bits);
 381         FLAC__ASSERT(br->consumed_words <= br->words);
 382
 383         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 384         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 385
 386         if(bits == 0) { /* OPT: investigate if this can ever happen, maybe change to assertion */
 387                 *val = 0;
 388                 return true;
 389         }
 390
 391         while((br->words-br->consumed_words)*FLAC__BITS_PER_WORD + br->bytes*8 - br->consumed_bits < bits) {
 392                 if(!bitreader_read_from_client_(br))
 393                         return false;
 394         }
 395         if(br->consumed_words < br->words) { /* if we've not consumed up to a partial tail word... */
 396                 /* OPT: taking out the consumed_bits==0 "else" case below might make things faster if less code allows the compiler to inline this function */
 397                 if(br->consumed_bits) {
 398                         /* this also works when consumed_bits==0, it's just a little slower than necessary for that case */
 399                         const uint32_t n = FLAC__BITS_PER_WORD - br->consumed_bits;
 400                         const brword word = br->buffer[br->consumed_words];
 401                         if(bits < n) {
 402                                 *val = (FLAC__uint32)((word & (FLAC__WORD_ALL_ONES >> br->consumed_bits)) >> (n-bits)); /* The result has <= 32 non-zero bits */
 403                                 br->consumed_bits += bits;
 404                                 return true;
 405                         }
 406                         /* (FLAC__BITS_PER_WORD - br->consumed_bits <= bits) ==> (FLAC__WORD_ALL_ONES >> br->consumed_bits) has no more than 'bits' non-zero bits */
 407                         *val = (FLAC__uint32)(word & (FLAC__WORD_ALL_ONES >> br->consumed_bits));
 408                         bits -= n;
 409                         br->consumed_words++;
 410                         br->consumed_bits = 0;
 411                         if(bits) { /* if there are still bits left to read, there have to be less than 32 so they will all be in the next word */
 412                                 *val <<= bits;
 413                                 *val |= (FLAC__uint32)(br->buffer[br->consumed_words] >> (FLAC__BITS_PER_WORD-bits));
 414                                 br->consumed_bits = bits;
 415                         }
 416                         return true;
 417                 }
 418                 else { /* br->consumed_bits == 0 */
 419                         const brword word = br->buffer[br->consumed_words];
 420                         if(bits < FLAC__BITS_PER_WORD) {
 421                                 *val = (FLAC__uint32)(word >> (FLAC__BITS_PER_WORD-bits));
 422                                 br->consumed_bits = bits;
 423                                 return true;
 424                         }
 425                         /* at this point bits == FLAC__BITS_PER_WORD == 32; because of previous assertions, it can't be larger */
 426                         *val = (FLAC__uint32)word;
 427                         br->consumed_words++;
 428                         return true;
 429                 }
 430         }
 431         else {
 432                 /* in this case we're starting our read at a partial tail word;
 433                  * the reader has guaranteed that we have at least 'bits' bits
 434                  * available to read, which makes this case simpler.
 435                  */
 436                 /* OPT: taking out the consumed_bits==0 "else" case below might make things faster if less code allows the compiler to inline this function */
 437                 if(br->consumed_bits) {
 438                         /* this also works when consumed_bits==0, it's just a little slower than necessary for that case */
 439                         FLAC__ASSERT(br->consumed_bits + bits <= br->bytes*8);
 440                         *val = (FLAC__uint32)((br->buffer[br->consumed_words] & (FLAC__WORD_ALL_ONES >> br->consumed_bits)) >> (FLAC__BITS_PER_WORD-br->consumed_bits-bits));
 441                         br->consumed_bits += bits;
 442                         return true;
 443                 }
 444                 else {
 445                         *val = (FLAC__uint32)(br->buffer[br->consumed_words] >> (FLAC__BITS_PER_WORD-bits));
 446                         br->consumed_bits += bits;
 447                         return true;
 448                 }
 449         }
 450 }
 451
 452 FLAC__bool FLAC__bitreader_read_raw_int32(FLAC__BitReader *br, FLAC__int32 *val, uint32_t bits)
 453 {
 454         FLAC__uint32 uval, mask;
 455         /* OPT: inline raw uint32 code here, or make into a macro if possible in the .h file */
 456         if(!FLAC__bitreader_read_raw_uint32(br, &uval, bits))
 457                 return false;
 458         /* sign-extend *val assuming it is currently bits wide. */
 459         /* From: https://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend */
 460         mask = 1u << (bits - 1);
 461         *val = (uval ^ mask) - mask;
 462         return true;
 463 }
 464
 465 FLAC__bool FLAC__bitreader_read_raw_uint64(FLAC__BitReader *br, FLAC__uint64 *val, uint32_t bits)
 466 {
 467         FLAC__uint32 hi, lo;
 468
 469         if(bits > 32) {
 470                 if(!FLAC__bitreader_read_raw_uint32(br, &hi, bits-32))
 471                         return false;
 472                 if(!FLAC__bitreader_read_raw_uint32(br, &lo, 32))
 473                         return false;
 474                 *val = hi;
 475                 *val <<= 32;
 476                 *val |= lo;
 477         }
 478         else {
 479                 if(!FLAC__bitreader_read_raw_uint32(br, &lo, bits))
 480                         return false;
 481                 *val = lo;
 482         }
 483         return true;
 484 }
 485
 486 inline FLAC__bool FLAC__bitreader_read_uint32_little_endian(FLAC__BitReader *br, FLAC__uint32 *val)
 487 {
 488         FLAC__uint32 x8, x32 = 0;
 489
 490         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
 491
 492         if(!FLAC__bitreader_read_raw_uint32(br, &x32, 8))
 493                 return false;
 494
 495         if(!FLAC__bitreader_read_raw_uint32(br, &x8, 8))
 496                 return false;
 497         x32 |= (x8 << 8);
 498
 499         if(!FLAC__bitreader_read_raw_uint32(br, &x8, 8))
 500                 return false;
 501         x32 |= (x8 << 16);
 502
 503         if(!FLAC__bitreader_read_raw_uint32(br, &x8, 8))
 504                 return false;
 505         x32 |= (x8 << 24);
 506
 507         *val = x32;
 508         return true;
 509 }
 510
 511 FLAC__bool FLAC__bitreader_skip_bits_no_crc(FLAC__BitReader *br, uint32_t bits)
 512 {
 513         /*
 514          * OPT: a faster implementation is possible but probably not that useful
 515          * since this is only called a couple of times in the metadata readers.
 516          */
 517         FLAC__ASSERT(0 != br);
 518         FLAC__ASSERT(0 != br->buffer);
 519
 520         if(bits > 0) {
 521                 const uint32_t n = br->consumed_bits & 7;
 522                 uint32_t m;
 523                 FLAC__uint32 x;
 524
 525                 if(n != 0) {
 526                         m = flac_min(8-n, bits);
 527                         if(!FLAC__bitreader_read_raw_uint32(br, &x, m))
 528                                 return false;
 529                         bits -= m;
 530                 }
 531                 m = bits / 8;
 532                 if(m > 0) {
 533                         if(!FLAC__bitreader_skip_byte_block_aligned_no_crc(br, m))
 534                                 return false;
 535                         bits %= 8;
 536                 }
 537                 if(bits > 0) {
 538                         if(!FLAC__bitreader_read_raw_uint32(br, &x, bits))
 539                                 return false;
 540                 }
 541         }
 542
 543         return true;
 544 }
 545
 546 FLAC__bool FLAC__bitreader_skip_byte_block_aligned_no_crc(FLAC__BitReader *br, uint32_t nvals)
 547 {
 548         FLAC__uint32 x;
 549
 550         FLAC__ASSERT(0 != br);
 551         FLAC__ASSERT(0 != br->buffer);
 552         FLAC__ASSERT(FLAC__bitreader_is_consumed_byte_aligned(br));
 553
 554         /* step 1: skip over partial head word to get word aligned */
 555         while(nvals && br->consumed_bits) { /* i.e. run until we read 'nvals' bytes or we hit the end of the head word */
 556                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
 557                         return false;
 558                 nvals--;
 559         }
 560         if(0 == nvals)
 561                 return true;
 562         /* step 2: skip whole words in chunks */
 563         while(nvals >= FLAC__BYTES_PER_WORD) {
 564                 if(br->consumed_words < br->words) {
 565                         br->consumed_words++;
 566                         nvals -= FLAC__BYTES_PER_WORD;
 567                 }
 568                 else if(!bitreader_read_from_client_(br))
 569                         return false;
 570         }
 571         /* step 3: skip any remainder from partial tail bytes */
 572         while(nvals) {
 573                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
 574                         return false;
 575                 nvals--;
 576         }
 577
 578         return true;
 579 }
 580
 581 FLAC__bool FLAC__bitreader_read_byte_block_aligned_no_crc(FLAC__BitReader *br, FLAC__byte *val, uint32_t nvals)
 582 {
 583         FLAC__uint32 x;
 584
 585         FLAC__ASSERT(0 != br);
 586         FLAC__ASSERT(0 != br->buffer);
 587         FLAC__ASSERT(FLAC__bitreader_is_consumed_byte_aligned(br));
 588
 589         /* step 1: read from partial head word to get word aligned */
 590         while(nvals && br->consumed_bits) { /* i.e. run until we read 'nvals' bytes or we hit the end of the head word */
 591                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
 592                         return false;
 593                 *val++ = (FLAC__byte)x;
 594                 nvals--;
 595         }
 596         if(0 == nvals)
 597                 return true;
 598         /* step 2: read whole words in chunks */
 599         while(nvals >= FLAC__BYTES_PER_WORD) {
 600                 if(br->consumed_words < br->words) {
 601                         const brword word = br->buffer[br->consumed_words++];
 602 #if FLAC__BYTES_PER_WORD == 4
 603                         val[0] = (FLAC__byte)(word >> 24);
 604                         val[1] = (FLAC__byte)(word >> 16);
 605                         val[2] = (FLAC__byte)(word >> 8);
 606                         val[3] = (FLAC__byte)word;
 607 #elif FLAC__BYTES_PER_WORD == 8
 608                         val[0] = (FLAC__byte)(word >> 56);
 609                         val[1] = (FLAC__byte)(word >> 48);
 610                         val[2] = (FLAC__byte)(word >> 40);
 611                         val[3] = (FLAC__byte)(word >> 32);
 612                         val[4] = (FLAC__byte)(word >> 24);
 613                         val[5] = (FLAC__byte)(word >> 16);
 614                         val[6] = (FLAC__byte)(word >> 8);
 615                         val[7] = (FLAC__byte)word;
 616 #else
 617                         for(x = 0; x < FLAC__BYTES_PER_WORD; x++)
 618                                 val[x] = (FLAC__byte)(word >> (8*(FLAC__BYTES_PER_WORD-x-1)));
 619 #endif
 620                         val += FLAC__BYTES_PER_WORD;
 621                         nvals -= FLAC__BYTES_PER_WORD;
 622                 }
 623                 else if(!bitreader_read_from_client_(br))
 624                         return false;
 625         }
 626         /* step 3: read any remainder from partial tail bytes */
 627         while(nvals) {
 628                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
 629                         return false;
 630                 *val++ = (FLAC__byte)x;
 631                 nvals--;
 632         }
 633
 634         return true;
 635 }
 636
 637 FLAC__bool FLAC__bitreader_read_unary_unsigned(FLAC__BitReader *br, uint32_t *val)
 638 #if 0 /* slow but readable version */
 639 {
 640         uint32_t bit;
 641
 642         FLAC__ASSERT(0 != br);
 643         FLAC__ASSERT(0 != br->buffer);
 644
 645         *val = 0;
 646         while(1) {
 647                 if(!FLAC__bitreader_read_bit(br, &bit))
 648                         return false;
 649                 if(bit)
 650                         break;
 651                 else
 652                         *val++;
 653         }
 654         return true;
 655 }
 656 #else
 657 {
 658         uint32_t i;
 659
 660         FLAC__ASSERT(0 != br);
 661         FLAC__ASSERT(0 != br->buffer);
 662
 663         *val = 0;
 664         while(1) {
 665                 while(br->consumed_words < br->words) { /* if we've not consumed up to a partial tail word... */
 666                         brword b = br->buffer[br->consumed_words] << br->consumed_bits;
 667                         if(b) {
 668                                 i = COUNT_ZERO_MSBS(b);
 669                                 *val += i;
 670                                 i++;
 671                                 br->consumed_bits += i;
 672                                 if(br->consumed_bits >= FLAC__BITS_PER_WORD) { /* faster way of testing if(br->consumed_bits == FLAC__BITS_PER_WORD) */
 673                                         br->consumed_words++;
 674                                         br->consumed_bits = 0;
 675                                 }
 676                                 return true;
 677                         }
 678                         else {
 679                                 *val += FLAC__BITS_PER_WORD - br->consumed_bits;
 680                                 br->consumed_words++;
 681                                 br->consumed_bits = 0;
 682                                 /* didn't find stop bit yet, have to keep going... */
 683                         }
 684                 }
 685                 /* at this point we've eaten up all the whole words; have to try
 686                  * reading through any tail bytes before calling the read callback.
 687                  * this is a repeat of the above logic adjusted for the fact we
 688                  * don't have a whole word.  note though if the client is feeding
 689                  * us data a byte at a time (unlikely), br->consumed_bits may not
 690                  * be zero.
 691                  */
 692                 if(br->bytes*8 > br->consumed_bits) {
 693                         const uint32_t end = br->bytes * 8;
 694                         brword b = (br->buffer[br->consumed_words] & (FLAC__WORD_ALL_ONES << (FLAC__BITS_PER_WORD-end))) << br->consumed_bits;
 695                         if(b) {
 696                                 i = COUNT_ZERO_MSBS(b);
 697                                 *val += i;
 698                                 i++;
 699                                 br->consumed_bits += i;
 700                                 FLAC__ASSERT(br->consumed_bits < FLAC__BITS_PER_WORD);
 701                                 return true;
 702                         }
 703                         else {
 704                                 *val += end - br->consumed_bits;
 705                                 br->consumed_bits = end;
 706                                 FLAC__ASSERT(br->consumed_bits < FLAC__BITS_PER_WORD);
 707                                 /* didn't find stop bit yet, have to keep going... */
 708                         }
 709                 }
 710                 if(!bitreader_read_from_client_(br))
 711                         return false;
 712         }
 713 }
 714 #endif
 715
 716 FLAC__bool FLAC__bitreader_read_rice_signed(FLAC__BitReader *br, int *val, uint32_t parameter)
 717 {
 718         FLAC__uint32 lsbs = 0, msbs = 0;
 719         uint32_t uval;
 720
 721         FLAC__ASSERT(0 != br);
 722         FLAC__ASSERT(0 != br->buffer);
 723         FLAC__ASSERT(parameter <= 31);
 724
 725         /* read the unary MSBs and end bit */
 726         if(!FLAC__bitreader_read_unary_unsigned(br, &msbs))
 727                 return false;
 728
 729         /* read the binary LSBs */
 730         if(!FLAC__bitreader_read_raw_uint32(br, &lsbs, parameter))
 731                 return false;
 732
 733         /* compose the value */
 734         uval = (msbs << parameter) | lsbs;
 735         if(uval & 1)
 736                 *val = -((int)(uval >> 1)) - 1;
 737         else
 738                 *val = (int)(uval >> 1);
 739
 740         return true;
 741 }
 742
 743 /* this is by far the most heavily used reader call.  it ain't pretty but it's fast */
 744 FLAC__bool FLAC__bitreader_read_rice_signed_block(FLAC__BitReader *br, int vals[], uint32_t nvals, uint32_t parameter)
 745 {
 746         /* try and get br->consumed_words and br->consumed_bits into register;
 747          * must remember to flush them back to *br before calling other
 748          * bitreader functions that use them, and before returning */
 749         uint32_t cwords, words, lsbs, msbs, x, y;
 750         uint32_t ucbits; /* keep track of the number of unconsumed bits in word */
 751         brword b;
 752         int *val, *end;
 753
 754         FLAC__ASSERT(0 != br);
 755         FLAC__ASSERT(0 != br->buffer);
 756         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 757         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 758         FLAC__ASSERT(parameter < 32);
 759         /* the above two asserts also guarantee that the binary part never straddles more than 2 words, so we don't have to loop to read it */
 760
 761         val = vals;
 762         end = vals + nvals;
 763
 764         if(parameter == 0) {
 765                 while(val < end) {
 766                         /* read the unary MSBs and end bit */
 767                         if(!FLAC__bitreader_read_unary_unsigned(br, &msbs))
 768                                 return false;
 769
 770                         *val++ = (int)(msbs >> 1) ^ -(int)(msbs & 1);
 771                 }
 772
 773                 return true;
 774         }
 775
 776         FLAC__ASSERT(parameter > 0);
 777
 778         cwords = br->consumed_words;
 779         words = br->words;
 780
 781         /* if we've not consumed up to a partial tail word... */
 782         if(cwords >= words) {
 783                 x = 0;
 784                 goto process_tail;
 785         }
 786
 787         ucbits = FLAC__BITS_PER_WORD - br->consumed_bits;
 788         b = br->buffer[cwords] << br->consumed_bits;  /* keep unconsumed bits aligned to left */
 789
 790         while(val < end) {
 791                 /* read the unary MSBs and end bit */
 792                 x = y = COUNT_ZERO_MSBS2(b);
 793                 if(x == FLAC__BITS_PER_WORD) {
 794                         x = ucbits;
 795                         do {
 796                                 /* didn't find stop bit yet, have to keep going... */
 797                                 cwords++;
 798                                 if (cwords >= words)
 799                                         goto incomplete_msbs;
 800                                 b = br->buffer[cwords];
 801                                 y = COUNT_ZERO_MSBS2(b);
 802                                 x += y;
 803                         } while(y == FLAC__BITS_PER_WORD);
 804                 }
 805                 b <<= y;
 806                 b <<= 1; /* account for stop bit */
 807                 ucbits = (ucbits - x - 1) % FLAC__BITS_PER_WORD;
 808                 msbs = x;
 809
 810                 /* read the binary LSBs */
 811                 x = (FLAC__uint32)(b >> (FLAC__BITS_PER_WORD - parameter)); /* parameter < 32, so we can cast to 32-bit uint32_t */
 812                 if(parameter <= ucbits) {
 813                         ucbits -= parameter;
 814                         b <<= parameter;
 815                 } else {
 816                         /* there are still bits left to read, they will all be in the next word */
 817                         cwords++;
 818                         if (cwords >= words)
 819                                 goto incomplete_lsbs;
 820                         b = br->buffer[cwords];
 821                         ucbits += FLAC__BITS_PER_WORD - parameter;
 822                         x |= (FLAC__uint32)(b >> ucbits);
 823                         b <<= FLAC__BITS_PER_WORD - ucbits;
 824                 }
 825                 lsbs = x;
 826
 827                 /* compose the value */
 828                 x = (msbs << parameter) | lsbs;
 829                 *val++ = (int)(x >> 1) ^ -(int)(x & 1);
 830
 831                 continue;
 832
 833                 /* at this point we've eaten up all the whole words */
 834 process_tail:
 835                 do {
 836                         if(0) {
 837 incomplete_msbs:
 838                                 br->consumed_bits = 0;
 839                                 br->consumed_words = cwords;
 840                         }
 841
 842                         /* read the unary MSBs and end bit */
 843                         if(!FLAC__bitreader_read_unary_unsigned(br, &msbs))
 844                                 return false;
 845                         msbs += x;
 846                         x = ucbits = 0;
 847
 848                         if(0) {
 849 incomplete_lsbs:
 850                                 br->consumed_bits = 0;
 851                                 br->consumed_words = cwords;
 852                         }
 853
 854                         /* read the binary LSBs */
 855                         if(!FLAC__bitreader_read_raw_uint32(br, &lsbs, parameter - ucbits))
 856                                 return false;
 857                         lsbs = x | lsbs;
 858
 859                         /* compose the value */
 860                         x = (msbs << parameter) | lsbs;
 861                         *val++ = (int)(x >> 1) ^ -(int)(x & 1);
 862                         x = 0;
 863
 864                         cwords = br->consumed_words;
 865                         words = br->words;
 866                         ucbits = FLAC__BITS_PER_WORD - br->consumed_bits;
 867                         b = br->buffer[cwords] << br->consumed_bits;
 868                 } while(cwords >= words && val < end);
 869         }
 870
 871         if(ucbits == 0 && cwords < words) {
 872                 /* don't leave the head word with no unconsumed bits */
 873                 cwords++;
 874                 ucbits = FLAC__BITS_PER_WORD;
 875         }
 876
 877         br->consumed_bits = FLAC__BITS_PER_WORD - ucbits;
 878         br->consumed_words = cwords;
 879
 880         return true;
 881 }
 882
 883 #if 0 /* UNUSED */
 884 FLAC__bool FLAC__bitreader_read_golomb_signed(FLAC__BitReader *br, int *val, uint32_t parameter)
 885 {
 886         FLAC__uint32 lsbs = 0, msbs = 0;
 887         uint32_t bit, uval, k;
 888
 889         FLAC__ASSERT(0 != br);
 890         FLAC__ASSERT(0 != br->buffer);
 891
 892         k = FLAC__bitmath_ilog2(parameter);
 893
 894         /* read the unary MSBs and end bit */
 895         if(!FLAC__bitreader_read_unary_unsigned(br, &msbs))
 896                 return false;
 897
 898         /* read the binary LSBs */
 899         if(!FLAC__bitreader_read_raw_uint32(br, &lsbs, k))
 900                 return false;
 901
 902         if(parameter == 1u<<k) {
 903                 /* compose the value */
 904                 uval = (msbs << k) | lsbs;
 905         }
 906         else {
 907                 uint32_t d = (1 << (k+1)) - parameter;
 908                 if(lsbs >= d) {
 909                         if(!FLAC__bitreader_read_bit(br, &bit))
 910                                 return false;
 911                         lsbs <<= 1;
 912                         lsbs |= bit;
 913                         lsbs -= d;
 914                 }
 915                 /* compose the value */
 916                 uval = msbs * parameter + lsbs;
 917         }
 918
 919         /* unfold uint32_t to signed */
 920         if(uval & 1)
 921                 *val = -((int)(uval >> 1)) - 1;
 922         else
 923                 *val = (int)(uval >> 1);
 924
 925         return true;
 926 }
 927
 928 FLAC__bool FLAC__bitreader_read_golomb_unsigned(FLAC__BitReader *br, uint32_t *val, uint32_t parameter)
 929 {
 930         FLAC__uint32 lsbs, msbs = 0;
 931         uint32_t bit, k;
 932
 933         FLAC__ASSERT(0 != br);
 934         FLAC__ASSERT(0 != br->buffer);
 935
 936         k = FLAC__bitmath_ilog2(parameter);
 937
 938         /* read the unary MSBs and end bit */
 939         if(!FLAC__bitreader_read_unary_unsigned(br, &msbs))
 940                 return false;
 941
 942         /* read the binary LSBs */
 943         if(!FLAC__bitreader_read_raw_uint32(br, &lsbs, k))
 944                 return false;
 945
 946         if(parameter == 1u<<k) {
 947                 /* compose the value */
 948                 *val = (msbs << k) | lsbs;
 949         }
 950         else {
 951                 uint32_t d = (1 << (k+1)) - parameter;
 952                 if(lsbs >= d) {
 953                         if(!FLAC__bitreader_read_bit(br, &bit))
 954                                 return false;
 955                         lsbs <<= 1;
 956                         lsbs |= bit;
 957                         lsbs -= d;
 958                 }
 959                 /* compose the value */
 960                 *val = msbs * parameter + lsbs;
 961         }
 962
 963         return true;
 964 }
 965 #endif /* UNUSED */
 966
 967 /* on return, if *val == 0xffffffff then the utf-8 sequence was invalid, but the return value will be true */
 968 FLAC__bool FLAC__bitreader_read_utf8_uint32(FLAC__BitReader *br, FLAC__uint32 *val, FLAC__byte *raw, uint32_t *rawlen)
 969 {
 970         FLAC__uint32 v = 0;
 971         FLAC__uint32 x;
 972         uint32_t i;
 973
 974         if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
 975                 return false;
 976         if(raw)
 977                 raw[(*rawlen)++] = (FLAC__byte)x;
 978         if(!(x & 0x80)) { /* 0xxxxxxx */
 979                 v = x;
 980                 i = 0;
 981         }
 982         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
 983                 v = x & 0x1F;
 984                 i = 1;
 985         }
 986         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
 987                 v = x & 0x0F;
 988                 i = 2;
 989         }
 990         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
 991                 v = x & 0x07;
 992                 i = 3;
 993         }
 994         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
 995                 v = x & 0x03;
 996                 i = 4;
 997         }
 998         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
 999                 v = x & 0x01;
1000                 i = 5;
1001         }
1002         else {
1003                 *val = 0xffffffff;
1004                 return true;
1005         }
1006         for( ; i; i--) {
1007                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
1008                         return false;
1009                 if(raw)
1010                         raw[(*rawlen)++] = (FLAC__byte)x;
1011                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
1012                         *val = 0xffffffff;
1013                         return true;
1014                 }
1015                 v <<= 6;
1016                 v |= (x & 0x3F);
1017         }
1018         *val = v;
1019         return true;
1020 }
1021
1022 /* on return, if *val == 0xffffffffffffffff then the utf-8 sequence was invalid, but the return value will be true */
1023 FLAC__bool FLAC__bitreader_read_utf8_uint64(FLAC__BitReader *br, FLAC__uint64 *val, FLAC__byte *raw, uint32_t *rawlen)
1024 {
1025         FLAC__uint64 v = 0;
1026         FLAC__uint32 x;
1027         uint32_t i;
1028
1029         if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
1030                 return false;
1031         if(raw)
1032                 raw[(*rawlen)++] = (FLAC__byte)x;
1033         if(!(x & 0x80)) { /* 0xxxxxxx */
1034                 v = x;
1035                 i = 0;
1036         }
1037         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1038                 v = x & 0x1F;
1039                 i = 1;
1040         }
1041         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1042                 v = x & 0x0F;
1043                 i = 2;
1044         }
1045         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1046                 v = x & 0x07;
1047                 i = 3;
1048         }
1049         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1050                 v = x & 0x03;
1051                 i = 4;
1052         }
1053         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1054                 v = x & 0x01;
1055                 i = 5;
1056         }
1057         else if(x & 0xFE && !(x & 0x01)) { /* 11111110 */
1058                 v = 0;
1059                 i = 6;
1060         }
1061         else {
1062                 *val = FLAC__U64L(0xffffffffffffffff);
1063                 return true;
1064         }
1065         for( ; i; i--) {
1066                 if(!FLAC__bitreader_read_raw_uint32(br, &x, 8))
1067                         return false;
1068                 if(raw)
1069                         raw[(*rawlen)++] = (FLAC__byte)x;
1070                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
1071                         *val = FLAC__U64L(0xffffffffffffffff);
1072                         return true;
1073                 }
1074                 v <<= 6;
1075                 v |= (x & 0x3F);
1076         }
1077         *val = v;
1078         return true;
1079 }
1080
1081 /* These functions are declared inline in this file but are also callable as
1082  * externs from elsewhere.
1083  * According to the C99 spec, section 6.7.4, simply providing a function
1084  * prototype in a header file without 'inline' and making the function inline
1085  * in this file should be sufficient.
1086  * Unfortunately, the Microsoft VS compiler doesn't pick them up externally. To
1087  * fix that we add extern declarations here.
1088  */
1089 extern FLAC__bool FLAC__bitreader_is_consumed_byte_aligned(const FLAC__BitReader *br);
1090 extern uint32_t FLAC__bitreader_bits_left_for_byte_alignment(const FLAC__BitReader *br);
1091 extern uint32_t FLAC__bitreader_get_input_bits_unconsumed(const FLAC__BitReader *br);
1092 extern FLAC__bool FLAC__bitreader_read_uint32_little_endian(FLAC__BitReader *br, FLAC__uint32 *val);