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