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