src/libFLAC/bitreader.c

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