src/libFLAC/bitreader.c

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