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