deps/flac-1.3.2/src/libFLAC/bitreader.c

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