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