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