src/libFLAC/bitreader.c

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