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