src/libFLAC/bitreader.c

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