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