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