src/libFLAC/bitreader.c

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