change license verbiage to Xiph's
[flac.git] / src / libFLAC / bitbuffer.c
1 /* libFLAC - Free Lossless Audio Codec library
2  * Copyright (C) 2000,2001,2002,2003  Josh Coalson
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * - Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *
11  * - Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution.
14  *
15  * - Neither the name of the Xiph.org Foundation nor the names of its
16  * contributors may be used to endorse or promote products derived from
17  * this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 #include <stdlib.h> /* for malloc() */
33 #include <string.h> /* for memcpy(), memset() */
34 #include "private/bitbuffer.h"
35 #include "private/bitmath.h"
36 #include "private/crc.h"
37 #include "FLAC/assert.h"
38
39 /*
40  * Along the way you will see two versions of some functions, selected
41  * by a FLAC__NO_MANUAL_INLINING macro.  One is the simplified, more
42  * readable, and slow version, and the other is the same function
43  * where crucial parts have been manually inlined and are much faster.
44  *
45  */
46
47 /*
48  * This should be at least twice as large as the largest number of blurbs
49  * required to represent any 'number' (in any encoding) you are going to
50  * read.  With FLAC this is on the order of maybe a few hundred bits.
51  * If the buffer is smaller than that, the decoder won't be able to read
52  * in a whole number that is in a variable length encoding (e.g. Rice).
53  *
54  * The number we are actually using here is based on what would be the
55  * approximate maximum size of a verbatim frame at the default block size,
56  * for CD audio (4096 sample * 4 bytes per sample), plus some wiggle room.
57  * 32kbytes sounds reasonable.  For kicks we subtract out 64 bytes for any
58  * alignment or malloc overhead.
59  *
60  * Increase this number to decrease the number of read callbacks, at the
61  * expense of using more memory.  Or decrease for the reverse effect,
62  * keeping in mind the limit from the first paragraph.
63  */
64 static const unsigned FLAC__BITBUFFER_DEFAULT_CAPACITY = ((65536 - 64) * 8) / FLAC__BITS_PER_BLURB; /* blurbs */
65
66 #if FLAC__BITS_PER_BLURB == 8
67 #define FLAC__BITS_PER_BLURB_LOG2 3
68 #define FLAC__BYTES_PER_BLURB 1
69 #define FLAC__BLURB_ALL_ONES ((FLAC__byte)0xff)
70 #define FLAC__BLURB_TOP_BIT_ONE ((FLAC__byte)0x80)
71 #define BLURB_BIT_TO_MASK(b) (((FLAC__blurb)'\x80') >> (b))
72 #define CRC16_UPDATE_BLURB(bb, blurb, crc) FLAC__CRC16_UPDATE((blurb), (crc));
73 #elif FLAC__BITS_PER_BLURB == 32
74 #define FLAC__BITS_PER_BLURB_LOG2 5
75 #define FLAC__BYTES_PER_BLURB 4
76 #define FLAC__BLURB_ALL_ONES ((FLAC__uint32)0xffffffff)
77 #define FLAC__BLURB_TOP_BIT_ONE ((FLAC__uint32)0x80000000)
78 #define BLURB_BIT_TO_MASK(b) (((FLAC__blurb)0x80000000) >> (b))
79 #define CRC16_UPDATE_BLURB(bb, blurb, crc) crc16_update_blurb((bb), (blurb));
80 #else
81 /* ERROR, only sizes of 8 and 32 are supported */
82 #endif
83
84 #define FLAC__BLURBS_TO_BITS(blurbs) ((blurbs) << FLAC__BITS_PER_BLURB_LOG2)
85
86 #ifdef min
87 #undef min
88 #endif
89 #define min(x,y) ((x)<(y)?(x):(y))
90 #ifdef max
91 #undef max
92 #endif
93 #define max(x,y) ((x)>(y)?(x):(y))
94
95 #ifndef FLaC__INLINE
96 #define FLaC__INLINE
97 #endif
98
99 struct FLAC__BitBuffer {
100         FLAC__blurb *buffer;
101         unsigned capacity; /* in blurbs */
102         unsigned blurbs, bits;
103         unsigned total_bits; /* must always == FLAC__BITS_PER_BLURB*blurbs+bits */
104         unsigned consumed_blurbs, consumed_bits;
105         unsigned total_consumed_bits; /* must always == FLAC__BITS_PER_BLURB*consumed_blurbs+consumed_bits */
106         FLAC__uint16 read_crc16;
107 #if FLAC__BITS_PER_BLURB == 32
108         unsigned crc16_align;
109 #endif
110         FLAC__blurb save_head, save_tail;
111 };
112
113 #if FLAC__BITS_PER_BLURB == 32
114 static void crc16_update_blurb(FLAC__BitBuffer *bb, FLAC__blurb blurb)
115 {
116         if(bb->crc16_align == 0) {
117                 FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
118                 FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
119                 FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
120                 FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
121         }
122         else if(bb->crc16_align == 8) {
123                 FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
124                 FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
125                 FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
126         }
127         else if(bb->crc16_align == 16) {
128                 FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
129                 FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
130         }
131         else if(bb->crc16_align == 24) {
132                 FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
133         }
134         bb->crc16_align = 0;
135 }
136 #endif
137
138 /*
139  * WATCHOUT: The current implentation is not friendly to shrinking, i.e. it
140  * does not shift left what is consumed, it just chops off the end, whether
141  * there is unconsumed data there or not.  This is OK because currently we
142  * never shrink the buffer, but if this ever changes, we'll have to do some
143  * fixups here.
144  */
145 static FLAC__bool bitbuffer_resize_(FLAC__BitBuffer *bb, unsigned new_capacity)
146 {
147         FLAC__blurb *new_buffer;
148
149         FLAC__ASSERT(0 != bb);
150         FLAC__ASSERT(0 != bb->buffer);
151
152         if(bb->capacity == new_capacity)
153                 return true;
154
155         new_buffer = (FLAC__blurb*)calloc(new_capacity, sizeof(FLAC__blurb));
156         if(new_buffer == 0)
157                 return false;
158         memcpy(new_buffer, bb->buffer, sizeof(FLAC__blurb)*min(bb->blurbs+(bb->bits?1:0), new_capacity));
159         if(new_capacity < bb->blurbs+(bb->bits?1:0)) {
160                 bb->blurbs = new_capacity;
161                 bb->bits = 0;
162                 bb->total_bits = FLAC__BLURBS_TO_BITS(new_capacity);
163         }
164         if(new_capacity < bb->consumed_blurbs+(bb->consumed_bits?1:0)) {
165                 bb->consumed_blurbs = new_capacity;
166                 bb->consumed_bits = 0;
167                 bb->total_consumed_bits = FLAC__BLURBS_TO_BITS(new_capacity);
168         }
169         free(bb->buffer); /* we've already asserted above that (0 != bb->buffer) */
170         bb->buffer = new_buffer;
171         bb->capacity = new_capacity;
172         return true;
173 }
174
175 static FLAC__bool bitbuffer_grow_(FLAC__BitBuffer *bb, unsigned min_blurbs_to_add)
176 {
177         unsigned new_capacity;
178
179         FLAC__ASSERT(min_blurbs_to_add > 0);
180
181         new_capacity = max(bb->capacity * 2, bb->capacity + min_blurbs_to_add);
182         return bitbuffer_resize_(bb, new_capacity);
183 }
184
185 static FLAC__bool bitbuffer_ensure_size_(FLAC__BitBuffer *bb, unsigned bits_to_add)
186 {
187         FLAC__ASSERT(0 != bb);
188         FLAC__ASSERT(0 != bb->buffer);
189
190         if(FLAC__BLURBS_TO_BITS(bb->capacity) < bb->total_bits + bits_to_add)
191                 return bitbuffer_grow_(bb, (bits_to_add >> FLAC__BITS_PER_BLURB_LOG2) + 2);
192         else
193                 return true;
194 }
195
196 static FLAC__bool bitbuffer_read_from_client_(FLAC__BitBuffer *bb, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
197 {
198         unsigned bytes;
199         FLAC__byte *target;
200
201         /* first shift the unconsumed buffer data toward the front as much as possible */
202         if(bb->total_consumed_bits >= FLAC__BITS_PER_BLURB) {
203                 unsigned l = 0, r = bb->consumed_blurbs, r_end = bb->blurbs + (bb->bits? 1:0);
204                 for( ; r < r_end; l++, r++)
205                         bb->buffer[l] = bb->buffer[r];
206                 for( ; l < r_end; l++)
207                         bb->buffer[l] = 0;
208                 bb->blurbs -= bb->consumed_blurbs;
209                 bb->total_bits -= FLAC__BLURBS_TO_BITS(bb->consumed_blurbs);
210                 bb->consumed_blurbs = 0;
211                 bb->total_consumed_bits = bb->consumed_bits;
212         }
213
214         /* grow if we need to */
215         if(bb->capacity <= 1) {
216                 if(!bitbuffer_resize_(bb, 16))
217                         return false;
218         }
219
220         /* set the target for reading, taking into account blurb alignment */
221 #if FLAC__BITS_PER_BLURB == 8
222         /* blurb == byte, so no gyrations necessary: */
223         target = bb->buffer + bb->blurbs;
224         bytes = bb->capacity - bb->blurbs;
225 #elif FLAC__BITS_PER_BLURB == 32
226         /* @@@ WATCHOUT: code currently only works for big-endian: */
227         FLAC__ASSERT((bb->bits & 7) == 0);
228         target = (FLAC__byte*)(bb->buffer + bb->blurbs) + (bb->bits >> 3);
229         bytes = ((bb->capacity - bb->blurbs) << 2) - (bb->bits >> 3); /* i.e. (bb->capacity - bb->blurbs) * FLAC__BYTES_PER_BLURB - (bb->bits / 8) */
230 #else
231         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
232 #endif
233
234         /* finally, read in some data */
235         if(!read_callback(target, &bytes, client_data))
236                 return false;
237
238         /* now we have to handle partial blurb cases: */
239 #if FLAC__BITS_PER_BLURB == 8
240         /* blurb == byte, so no gyrations necessary: */
241         bb->blurbs += bytes;
242         bb->total_bits += FLAC__BLURBS_TO_BITS(bytes);
243 #elif FLAC__BITS_PER_BLURB == 32
244         /* @@@ WATCHOUT: code currently only works for big-endian: */
245         {
246                 const unsigned aligned_bytes = (bb->bits >> 3) + bytes;
247                 bb->blurbs += (aligned_bytes >> 2); /* i.e. aligned_bytes / FLAC__BYTES_PER_BLURB */
248                 bb->bits = (aligned_bytes & 3u) << 3; /* i.e. (aligned_bytes % FLAC__BYTES_PER_BLURB) * 8 */
249                 bb->total_bits += (bytes << 3);
250         }
251 #else
252         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
253 #endif
254         return true;
255 }
256
257 /***********************************************************************
258  *
259  * Class constructor/destructor
260  *
261  ***********************************************************************/
262
263 FLAC__BitBuffer *FLAC__bitbuffer_new()
264 {
265         FLAC__BitBuffer *bb = (FLAC__BitBuffer*)calloc(1, sizeof(FLAC__BitBuffer));
266
267         /* calloc() implies:
268                 memset(bb, 0, sizeof(FLAC__BitBuffer));
269                 bb->buffer = 0;
270                 bb->capacity = 0;
271                 bb->blurbs = bb->bits = bb->total_bits = 0;
272                 bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
273         */
274         return bb;
275 }
276
277 void FLAC__bitbuffer_delete(FLAC__BitBuffer *bb)
278 {
279         FLAC__ASSERT(0 != bb);
280
281         FLAC__bitbuffer_free(bb);
282         free(bb);
283 }
284
285 /***********************************************************************
286  *
287  * Public class methods
288  *
289  ***********************************************************************/
290
291 FLAC__bool FLAC__bitbuffer_init(FLAC__BitBuffer *bb)
292 {
293         FLAC__ASSERT(0 != bb);
294
295         bb->buffer = 0;
296         bb->capacity = 0;
297         bb->blurbs = bb->bits = bb->total_bits = 0;
298         bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
299
300         return FLAC__bitbuffer_clear(bb);
301 }
302
303 FLAC__bool FLAC__bitbuffer_init_from(FLAC__BitBuffer *bb, const FLAC__byte buffer[], unsigned bytes)
304 {
305         FLAC__ASSERT(0 != bb);
306         FLAC__ASSERT(bytes > 0);
307
308         if(!FLAC__bitbuffer_init(bb))
309                 return false;
310
311         if(!bitbuffer_ensure_size_(bb, bytes << 3))
312                 return false;
313
314         FLAC__ASSERT(0 != buffer);
315         /* @@@ WATCHOUT: code currently only works for 8-bits-per-blurb inclusive-or big-endian: */
316         memcpy((FLAC__byte*)bb->buffer, buffer, sizeof(FLAC__byte)*bytes);
317         bb->blurbs = bytes / FLAC__BYTES_PER_BLURB;
318         bb->bits = (bytes % FLAC__BYTES_PER_BLURB) << 3;
319         bb->total_bits = bytes << 3;
320         return true;
321 }
322
323 FLAC__bool FLAC__bitbuffer_concatenate_aligned(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
324 {
325         unsigned bits_to_add = src->total_bits - src->total_consumed_bits;
326
327         FLAC__ASSERT(0 != dest);
328         FLAC__ASSERT(0 != src);
329
330         if(bits_to_add == 0)
331                 return true;
332         if(dest->bits != src->consumed_bits)
333                 return false;
334         if(!bitbuffer_ensure_size_(dest, bits_to_add))
335                 return false;
336         if(dest->bits == 0) {
337                 memcpy(dest->buffer+dest->blurbs, src->buffer+src->consumed_blurbs, sizeof(FLAC__blurb)*(src->blurbs-src->consumed_blurbs + ((src->bits)? 1:0)));
338         }
339         else if(dest->bits + bits_to_add > FLAC__BITS_PER_BLURB) {
340                 dest->buffer[dest->blurbs] <<= (FLAC__BITS_PER_BLURB - dest->bits);
341                 dest->buffer[dest->blurbs] |= (src->buffer[src->consumed_blurbs] & ((1u << (FLAC__BITS_PER_BLURB-dest->bits)) - 1));
342                 memcpy(dest->buffer+dest->blurbs+1, src->buffer+src->consumed_blurbs+1, sizeof(FLAC__blurb)*(src->blurbs-src->consumed_blurbs-1 + ((src->bits)? 1:0)));
343         }
344         else {
345                 dest->buffer[dest->blurbs] <<= bits_to_add;
346                 dest->buffer[dest->blurbs] |= (src->buffer[src->consumed_blurbs] & ((1u << bits_to_add) - 1));
347         }
348         dest->bits = src->bits;
349         dest->total_bits += bits_to_add;
350         dest->blurbs = dest->total_bits / FLAC__BITS_PER_BLURB;
351
352         return true;
353 }
354
355 void FLAC__bitbuffer_free(FLAC__BitBuffer *bb)
356 {
357         FLAC__ASSERT(0 != bb);
358
359         if(0 != bb->buffer)
360                 free(bb->buffer);
361         bb->buffer = 0;
362         bb->capacity = 0;
363         bb->blurbs = bb->bits = bb->total_bits = 0;
364         bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
365 }
366
367 FLAC__bool FLAC__bitbuffer_clear(FLAC__BitBuffer *bb)
368 {
369         if(bb->buffer == 0) {
370                 bb->capacity = FLAC__BITBUFFER_DEFAULT_CAPACITY;
371                 bb->buffer = (FLAC__blurb*)calloc(bb->capacity, sizeof(FLAC__blurb));
372                 if(bb->buffer == 0)
373                         return false;
374         }
375         else {
376                 memset(bb->buffer, 0, bb->blurbs + (bb->bits?1:0));
377         }
378         bb->blurbs = bb->bits = bb->total_bits = 0;
379         bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
380         return true;
381 }
382
383 FLAC__bool FLAC__bitbuffer_clone(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
384 {
385         FLAC__ASSERT(0 != dest);
386         FLAC__ASSERT(0 != dest->buffer);
387         FLAC__ASSERT(0 != src);
388         FLAC__ASSERT(0 != src->buffer);
389
390         if(dest->capacity < src->capacity)
391                 if(!bitbuffer_resize_(dest, src->capacity))
392                         return false;
393         memcpy(dest->buffer, src->buffer, sizeof(FLAC__blurb)*min(src->capacity, src->blurbs+1));
394         dest->blurbs = src->blurbs;
395         dest->bits = src->bits;
396         dest->total_bits = src->total_bits;
397         dest->consumed_blurbs = src->consumed_blurbs;
398         dest->consumed_bits = src->consumed_bits;
399         dest->total_consumed_bits = src->total_consumed_bits;
400         dest->read_crc16 = src->read_crc16;
401         return true;
402 }
403
404 void FLAC__bitbuffer_reset_read_crc16(FLAC__BitBuffer *bb, FLAC__uint16 seed)
405 {
406         FLAC__ASSERT(0 != bb);
407         FLAC__ASSERT(0 != bb->buffer);
408         FLAC__ASSERT((bb->consumed_bits & 7) == 0);
409
410         bb->read_crc16 = seed;
411 #if FLAC__BITS_PER_BLURB == 8
412         /* no need to do anything */
413 #elif FLAC__BITS_PER_BLURB == 32
414         bb->crc16_align = bb->consumed_bits;
415 #else
416         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
417 #endif
418 }
419
420 FLAC__uint16 FLAC__bitbuffer_get_read_crc16(FLAC__BitBuffer *bb)
421 {
422         FLAC__ASSERT(0 != bb);
423         FLAC__ASSERT(0 != bb->buffer);
424         FLAC__ASSERT((bb->bits & 7) == 0);
425         FLAC__ASSERT((bb->consumed_bits & 7) == 0);
426
427 #if FLAC__BITS_PER_BLURB == 8
428         /* no need to do anything */
429 #elif FLAC__BITS_PER_BLURB == 32
430         /*@@@ BUG: even though this probably can't happen with FLAC, need to fix the case where we are called here for the very first blurb and crc16_align is > 0 */
431         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) {
432                 if(bb->consumed_bits == 8) {
433                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
434                         FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
435                 }
436                 else if(bb->consumed_bits == 16) {
437                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
438                         FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
439                         FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
440                 }
441                 else if(bb->consumed_bits == 24) {
442                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
443                         FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
444                         FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
445                         FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
446                 }
447         }
448         else {
449                 if(bb->consumed_bits == 8) {
450                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
451                         FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
452                 }
453                 else if(bb->consumed_bits == 16) {
454                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
455                         FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
456                         FLAC__CRC16_UPDATE((blurb >> (bb->bits-16)) & 0xff, bb->read_crc16);
457                 }
458                 else if(bb->consumed_bits == 24) {
459                         const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
460                         FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
461                         FLAC__CRC16_UPDATE((blurb >> (bb->bits-16)) & 0xff, bb->read_crc16);
462                         FLAC__CRC16_UPDATE((blurb >> (bb->bits-24)) & 0xff, bb->read_crc16);
463                 }
464         }
465         bb->crc16_align = bb->consumed_bits;
466 #else
467         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
468 #endif
469         return bb->read_crc16;
470 }
471
472 FLAC__uint16 FLAC__bitbuffer_get_write_crc16(const FLAC__BitBuffer *bb)
473 {
474         FLAC__ASSERT((bb->bits & 7) == 0); /* assert that we're byte-aligned */
475
476 #if FLAC__BITS_PER_BLURB == 8
477         return FLAC__crc16(bb->buffer, bb->blurbs);
478 #elif FLAC__BITS_PER_BLURB == 32
479         /* @@@ WATCHOUT: code currently only works for big-endian: */
480         return FLAC__crc16((FLAC__byte*)(bb->buffer), (bb->blurbs * FLAC__BYTES_PER_BLURB) + (bb->bits >> 3));
481 #else
482         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
483 #endif
484 }
485
486 FLAC__byte FLAC__bitbuffer_get_write_crc8(const FLAC__BitBuffer *bb)
487 {
488         FLAC__ASSERT(0 != bb);
489         FLAC__ASSERT((bb->bits & 7) == 0); /* assert that we're byte-aligned */
490         FLAC__ASSERT(bb->buffer[0] == 0xff); /* MAGIC NUMBER for the first byte of the sync code */
491 #if FLAC__BITS_PER_BLURB == 8
492         return FLAC__crc8(bb->buffer, bb->blurbs);
493 #elif FLAC__BITS_PER_BLURB == 32
494         /* @@@ WATCHOUT: code currently only works for big-endian: */
495         return FLAC__crc8((FLAC__byte*)(bb->buffer), (bb->blurbs * FLAC__BYTES_PER_BLURB) + (bb->bits >> 3));
496 #else
497         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
498 #endif
499 }
500
501 FLAC__bool FLAC__bitbuffer_is_byte_aligned(const FLAC__BitBuffer *bb)
502 {
503         return ((bb->bits & 7) == 0);
504 }
505
506 FLAC__bool FLAC__bitbuffer_is_consumed_byte_aligned(const FLAC__BitBuffer *bb)
507 {
508         return ((bb->consumed_bits & 7) == 0);
509 }
510
511 unsigned FLAC__bitbuffer_bits_left_for_byte_alignment(const FLAC__BitBuffer *bb)
512 {
513         return 8 - (bb->consumed_bits & 7);
514 }
515
516 unsigned FLAC__bitbuffer_get_input_bytes_unconsumed(const FLAC__BitBuffer *bb)
517 {
518         FLAC__ASSERT((bb->consumed_bits & 7) == 0 && (bb->bits & 7) == 0);
519         return (bb->total_bits - bb->total_consumed_bits) >> 3;
520 }
521
522 void FLAC__bitbuffer_get_buffer(FLAC__BitBuffer *bb, const FLAC__byte **buffer, unsigned *bytes)
523 {
524         FLAC__ASSERT((bb->consumed_bits & 7) == 0 && (bb->bits & 7) == 0);
525 #if FLAC__BITS_PER_BLURB == 8
526         *buffer = bb->buffer + bb->consumed_blurbs;
527         *bytes = bb->blurbs - bb->consumed_blurbs;
528 #elif FLAC__BITS_PER_BLURB == 32
529         /* @@@ WATCHOUT: code currently only works for big-endian: */
530         *buffer = (FLAC__byte*)(bb->buffer + bb->consumed_blurbs) + (bb->consumed_bits >> 3);
531         *bytes = (bb->total_bits - bb->total_consumed_bits) >> 3;
532 #else
533         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
534 #endif
535 }
536
537 void FLAC__bitbuffer_release_buffer(FLAC__BitBuffer *bb)
538 {
539 #if FLAC__BITS_PER_BLURB == 8
540         (void)bb;
541 #elif FLAC__BITS_PER_BLURB == 32
542         /* @@@ WATCHOUT: code currently only works for big-endian: */
543         (void)bb;
544 #else
545         FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
546 #endif
547 }
548
549 FLAC__bool FLAC__bitbuffer_write_zeroes(FLAC__BitBuffer *bb, unsigned bits)
550 {
551         unsigned n;
552
553         FLAC__ASSERT(0 != bb);
554         FLAC__ASSERT(0 != bb->buffer);
555
556         if(bits == 0)
557                 return true;
558         if(!bitbuffer_ensure_size_(bb, bits))
559                 return false;
560         bb->total_bits += bits;
561         while(bits > 0) {
562                 n = min(FLAC__BITS_PER_BLURB - bb->bits, bits);
563                 bb->buffer[bb->blurbs] <<= n;
564                 bits -= n;
565                 bb->bits += n;
566                 if(bb->bits == FLAC__BITS_PER_BLURB) {
567                         bb->blurbs++;
568                         bb->bits = 0;
569                 }
570         }
571         return true;
572 }
573
574 FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_raw_uint32(FLAC__BitBuffer *bb, FLAC__uint32 val, unsigned bits)
575 {
576         unsigned n, k;
577
578         FLAC__ASSERT(0 != bb);
579         FLAC__ASSERT(0 != bb->buffer);
580
581         FLAC__ASSERT(bits <= 32);
582         if(bits == 0)
583                 return true;
584         /* inline the size check so we don't incure a function call unnecessarily */
585         if(FLAC__BLURBS_TO_BITS(bb->capacity) < bb->total_bits + bits) {
586                 if(!bitbuffer_ensure_size_(bb, bits))
587                         return false;
588         }
589
590         /* zero-out unused bits; WATCHOUT: other code relies on this, so this needs to stay */
591         if(bits < 32) /* @@@ gcc seems to require this because the following line causes incorrect results when bits==32; investigate */
592                 val &= (~(0xffffffff << bits)); /* zero-out unused bits */
593
594         bb->total_bits += bits;
595         while(bits > 0) {
596                 n = FLAC__BITS_PER_BLURB - bb->bits;
597                 if(n == FLAC__BITS_PER_BLURB) { /* i.e. bb->bits == 0 */
598                         if(bits < FLAC__BITS_PER_BLURB) {
599                                 bb->buffer[bb->blurbs] = (FLAC__blurb)val;
600                                 bb->bits = bits;
601                                 break;
602                         }
603                         else if(bits == FLAC__BITS_PER_BLURB) {
604                                 bb->buffer[bb->blurbs++] = (FLAC__blurb)val;
605                                 break;
606                         }
607                         else {
608                                 k = bits - FLAC__BITS_PER_BLURB;
609                                 bb->buffer[bb->blurbs++] = (FLAC__blurb)(val >> k);
610                                 /* we know k < 32 so no need to protect against the gcc bug mentioned above */
611                                 val &= (~(0xffffffff << k));
612                                 bits -= FLAC__BITS_PER_BLURB;
613                         }
614                 }
615                 else if(bits <= n) {
616                         bb->buffer[bb->blurbs] <<= bits;
617                         bb->buffer[bb->blurbs] |= val;
618                         if(bits == n) {
619                                 bb->blurbs++;
620                                 bb->bits = 0;
621                         }
622                         else
623                                 bb->bits += bits;
624                         break;
625                 }
626                 else {
627                         k = bits - n;
628                         bb->buffer[bb->blurbs] <<= n;
629                         bb->buffer[bb->blurbs] |= (val >> k);
630                         /* we know n > 0 so k < 32 so no need to protect against the gcc bug mentioned above */
631                         val &= (~(0xffffffff << k));
632                         bits -= n;
633                         bb->blurbs++;
634                         bb->bits = 0;
635                 }
636         }
637
638         return true;
639 }
640
641 FLAC__bool FLAC__bitbuffer_write_raw_int32(FLAC__BitBuffer *bb, FLAC__int32 val, unsigned bits)
642 {
643         return FLAC__bitbuffer_write_raw_uint32(bb, (FLAC__uint32)val, bits);
644 }
645
646 FLAC__bool FLAC__bitbuffer_write_raw_uint64(FLAC__BitBuffer *bb, FLAC__uint64 val, unsigned bits)
647 {
648         static const FLAC__uint64 mask[] = {
649                 0,
650                 0x0000000000000001, 0x0000000000000003, 0x0000000000000007, 0x000000000000000F,
651                 0x000000000000001F, 0x000000000000003F, 0x000000000000007F, 0x00000000000000FF,
652                 0x00000000000001FF, 0x00000000000003FF, 0x00000000000007FF, 0x0000000000000FFF,
653                 0x0000000000001FFF, 0x0000000000003FFF, 0x0000000000007FFF, 0x000000000000FFFF,
654                 0x000000000001FFFF, 0x000000000003FFFF, 0x000000000007FFFF, 0x00000000000FFFFF,
655                 0x00000000001FFFFF, 0x00000000003FFFFF, 0x00000000007FFFFF, 0x0000000000FFFFFF,
656                 0x0000000001FFFFFF, 0x0000000003FFFFFF, 0x0000000007FFFFFF, 0x000000000FFFFFFF,
657                 0x000000001FFFFFFF, 0x000000003FFFFFFF, 0x000000007FFFFFFF, 0x00000000FFFFFFFF,
658                 0x00000001FFFFFFFF, 0x00000003FFFFFFFF, 0x00000007FFFFFFFF, 0x0000000FFFFFFFFF,
659                 0x0000001FFFFFFFFF, 0x0000003FFFFFFFFF, 0x0000007FFFFFFFFF, 0x000000FFFFFFFFFF,
660                 0x000001FFFFFFFFFF, 0x000003FFFFFFFFFF, 0x000007FFFFFFFFFF, 0x00000FFFFFFFFFFF,
661                 0x00001FFFFFFFFFFF, 0x00003FFFFFFFFFFF, 0x00007FFFFFFFFFFF, 0x0000FFFFFFFFFFFF,
662                 0x0001FFFFFFFFFFFF, 0x0003FFFFFFFFFFFF, 0x0007FFFFFFFFFFFF, 0x000FFFFFFFFFFFFF,
663                 0x001FFFFFFFFFFFFF, 0x003FFFFFFFFFFFFF, 0x007FFFFFFFFFFFFF, 0x00FFFFFFFFFFFFFF,
664                 0x01FFFFFFFFFFFFFF, 0x03FFFFFFFFFFFFFF, 0x07FFFFFFFFFFFFFF, 0x0FFFFFFFFFFFFFFF,
665                 0x1FFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF
666         };
667         unsigned n, k;
668
669         FLAC__ASSERT(0 != bb);
670         FLAC__ASSERT(0 != bb->buffer);
671
672         FLAC__ASSERT(bits <= 64);
673         if(bits == 0)
674                 return true;
675         if(!bitbuffer_ensure_size_(bb, bits))
676                 return false;
677         val &= mask[bits];
678         bb->total_bits += bits;
679         while(bits > 0) {
680                 if(bb->bits == 0) {
681                         if(bits < FLAC__BITS_PER_BLURB) {
682                                 bb->buffer[bb->blurbs] = (FLAC__blurb)val;
683                                 bb->bits = bits;
684                                 break;
685                         }
686                         else if(bits == FLAC__BITS_PER_BLURB) {
687                                 bb->buffer[bb->blurbs++] = (FLAC__blurb)val;
688                                 break;
689                         }
690                         else {
691                                 k = bits - FLAC__BITS_PER_BLURB;
692                                 bb->buffer[bb->blurbs++] = (FLAC__blurb)(val >> k);
693                                 /* we know k < 64 so no need to protect against the gcc bug mentioned above */
694                                 val &= (~(0xffffffffffffffff << k));
695                                 bits -= FLAC__BITS_PER_BLURB;
696                         }
697                 }
698                 else {
699                         n = min(FLAC__BITS_PER_BLURB - bb->bits, bits);
700                         k = bits - n;
701                         bb->buffer[bb->blurbs] <<= n;
702                         bb->buffer[bb->blurbs] |= (val >> k);
703                         /* we know n > 0 so k < 64 so no need to protect against the gcc bug mentioned above */
704                         val &= (~(0xffffffffffffffff << k));
705                         bits -= n;
706                         bb->bits += n;
707                         if(bb->bits == FLAC__BITS_PER_BLURB) {
708                                 bb->blurbs++;
709                                 bb->bits = 0;
710                         }
711                 }
712         }
713
714         return true;
715 }
716
717 #if 0 /* UNUSED */
718 FLAC__bool FLAC__bitbuffer_write_raw_int64(FLAC__BitBuffer *bb, FLAC__int64 val, unsigned bits)
719 {
720         return FLAC__bitbuffer_write_raw_uint64(bb, (FLAC__uint64)val, bits);
721 }
722 #endif
723
724 FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_raw_uint32_little_endian(FLAC__BitBuffer *bb, FLAC__uint32 val)
725 {
726         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
727
728         /* NOTE: we rely on the fact that FLAC__bitbuffer_write_raw_uint32() masks out the unused bits */
729         if(!FLAC__bitbuffer_write_raw_uint32(bb, val, 8))
730                 return false;
731         if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>8, 8))
732                 return false;
733         if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>16, 8))
734                 return false;
735         if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>24, 8))
736                 return false;
737
738         return true;
739 }
740
741 FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_byte_block(FLAC__BitBuffer *bb, const FLAC__byte vals[], unsigned nvals)
742 {
743         unsigned i;
744
745         /* this could be faster but currently we don't need it to be */
746         for(i = 0; i < nvals; i++) {
747                 if(!FLAC__bitbuffer_write_raw_uint32(bb, (FLAC__uint32)(vals[i]), 8))
748                         return false;
749         }
750
751         return true;
752 }
753
754 FLAC__bool FLAC__bitbuffer_write_unary_unsigned(FLAC__BitBuffer *bb, unsigned val)
755 {
756         if(val < 32)
757                 return FLAC__bitbuffer_write_raw_uint32(bb, 1, ++val);
758         else if(val < 64)
759                 return FLAC__bitbuffer_write_raw_uint64(bb, 1, ++val);
760         else {
761                 if(!FLAC__bitbuffer_write_zeroes(bb, val))
762                         return false;
763                 return FLAC__bitbuffer_write_raw_uint32(bb, 1, 1);
764         }
765 }
766
767 unsigned FLAC__bitbuffer_rice_bits(int val, unsigned parameter)
768 {
769         unsigned msbs, uval;
770
771         /* fold signed to unsigned */
772         if(val < 0)
773                 /* equivalent to
774                  *     (unsigned)(((--val) << 1) - 1);
775                  * but without the overflow problem at MININT
776                  */
777                 uval = (unsigned)(((-(++val)) << 1) + 1);
778         else
779                 uval = (unsigned)(val << 1);
780
781         msbs = uval >> parameter;
782
783         return 1 + parameter + msbs;
784 }
785
786 #if 0 /* UNUSED */
787 unsigned FLAC__bitbuffer_golomb_bits_signed(int val, unsigned parameter)
788 {
789         unsigned bits, msbs, uval;
790         unsigned k;
791
792         FLAC__ASSERT(parameter > 0);
793
794         /* fold signed to unsigned */
795         if(val < 0)
796                 /* equivalent to
797                  *     (unsigned)(((--val) << 1) - 1);
798                  * but without the overflow problem at MININT
799                  */
800                 uval = (unsigned)(((-(++val)) << 1) + 1);
801         else
802                 uval = (unsigned)(val << 1);
803
804         k = FLAC__bitmath_ilog2(parameter);
805         if(parameter == 1u<<k) {
806                 FLAC__ASSERT(k <= 30);
807
808                 msbs = uval >> k;
809                 bits = 1 + k + msbs;
810         }
811         else {
812                 unsigned q, r, d;
813
814                 d = (1 << (k+1)) - parameter;
815                 q = uval / parameter;
816                 r = uval - (q * parameter);
817
818                 bits = 1 + q + k;
819                 if(r >= d)
820                         bits++;
821         }
822         return bits;
823 }
824
825 unsigned FLAC__bitbuffer_golomb_bits_unsigned(unsigned uval, unsigned parameter)
826 {
827         unsigned bits, msbs;
828         unsigned k;
829
830         FLAC__ASSERT(parameter > 0);
831
832         k = FLAC__bitmath_ilog2(parameter);
833         if(parameter == 1u<<k) {
834                 FLAC__ASSERT(k <= 30);
835
836                 msbs = uval >> k;
837                 bits = 1 + k + msbs;
838         }
839         else {
840                 unsigned q, r, d;
841
842                 d = (1 << (k+1)) - parameter;
843                 q = uval / parameter;
844                 r = uval - (q * parameter);
845
846                 bits = 1 + q + k;
847                 if(r >= d)
848                         bits++;
849         }
850         return bits;
851 }
852 #endif /* UNUSED */
853
854 #ifdef FLAC__SYMMETRIC_RICE
855 FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
856 {
857         unsigned total_bits, interesting_bits, msbs;
858         FLAC__uint32 pattern;
859
860         FLAC__ASSERT(0 != bb);
861         FLAC__ASSERT(0 != bb->buffer);
862         FLAC__ASSERT(parameter <= 31);
863
864         /* init pattern with the unary end bit and the sign bit */
865         if(val < 0) {
866                 pattern = 3;
867                 val = -val;
868         }
869         else
870                 pattern = 2;
871
872         msbs = val >> parameter;
873         interesting_bits = 2 + parameter;
874         total_bits = interesting_bits + msbs;
875         pattern <<= parameter;
876         pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */
877
878         if(total_bits <= 32) {
879                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
880                         return false;
881         }
882         else {
883                 /* write the unary MSBs */
884                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
885                         return false;
886                 /* write the unary end bit, the sign bit, and binary LSBs */
887                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
888                         return false;
889         }
890         return true;
891 }
892
893 #if 0 /* UNUSED */
894 FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, FLAC__bool *overflow)
895 {
896         unsigned total_bits, interesting_bits, msbs;
897         FLAC__uint32 pattern;
898
899         FLAC__ASSERT(0 != bb);
900         FLAC__ASSERT(0 != bb->buffer);
901         FLAC__ASSERT(parameter <= 31);
902
903         *overflow = false;
904
905         /* init pattern with the unary end bit and the sign bit */
906         if(val < 0) {
907                 pattern = 3;
908                 val = -val;
909         }
910         else
911                 pattern = 2;
912
913         msbs = val >> parameter;
914         interesting_bits = 2 + parameter;
915         total_bits = interesting_bits + msbs;
916         pattern <<= parameter;
917         pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */
918
919         if(total_bits <= 32) {
920                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
921                         return false;
922         }
923         else if(total_bits > max_bits) {
924                 *overflow = true;
925                 return true;
926         }
927         else {
928                 /* write the unary MSBs */
929                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
930                         return false;
931                 /* write the unary end bit, the sign bit, and binary LSBs */
932                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
933                         return false;
934         }
935         return true;
936 }
937 #endif /* UNUSED */
938
939 FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed_escape(FLAC__BitBuffer *bb, int val, unsigned parameter)
940 {
941         unsigned total_bits, val_bits;
942         FLAC__uint32 pattern;
943
944         FLAC__ASSERT(0 != bb);
945         FLAC__ASSERT(0 != bb->buffer);
946         FLAC__ASSERT(parameter <= 31);
947
948         val_bits = FLAC__bitmath_silog2(val);
949         total_bits = 2 + parameter + 5 + val_bits;
950
951         if(total_bits <= 32) {
952                 pattern = 3;
953                 pattern <<= (parameter + 5);
954                 pattern |= val_bits;
955                 pattern <<= val_bits;
956                 pattern |= (val & ((1 << val_bits) - 1));
957                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
958                         return false;
959         }
960         else {
961                 /* write the '-0' escape code first */
962                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 3u << parameter, 2+parameter))
963                         return false;
964                 /* write the length */
965                 if(!FLAC__bitbuffer_write_raw_uint32(bb, val_bits, 5))
966                         return false;
967                 /* write the value */
968                 if(!FLAC__bitbuffer_write_raw_int32(bb, val, val_bits))
969                         return false;
970         }
971         return true;
972 }
973 #endif /* ifdef FLAC__SYMMETRIC_RICE */
974
975 FLAC__bool FLAC__bitbuffer_write_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
976 {
977         unsigned total_bits, interesting_bits, msbs, uval;
978         FLAC__uint32 pattern;
979
980         FLAC__ASSERT(0 != bb);
981         FLAC__ASSERT(0 != bb->buffer);
982         FLAC__ASSERT(parameter <= 30);
983
984         /* fold signed to unsigned */
985         if(val < 0)
986                 /* equivalent to
987                  *     (unsigned)(((--val) << 1) - 1);
988                  * but without the overflow problem at MININT
989                  */
990                 uval = (unsigned)(((-(++val)) << 1) + 1);
991         else
992                 uval = (unsigned)(val << 1);
993
994         msbs = uval >> parameter;
995         interesting_bits = 1 + parameter;
996         total_bits = interesting_bits + msbs;
997         pattern = 1 << parameter; /* the unary end bit */
998         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
999
1000         if(total_bits <= 32) {
1001                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1002                         return false;
1003         }
1004         else {
1005                 /* write the unary MSBs */
1006                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
1007                         return false;
1008                 /* write the unary end bit and binary LSBs */
1009                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
1010                         return false;
1011         }
1012         return true;
1013 }
1014
1015 #if 0 /* UNUSED */
1016 FLAC__bool FLAC__bitbuffer_write_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, FLAC__bool *overflow)
1017 {
1018         unsigned total_bits, interesting_bits, msbs, uval;
1019         FLAC__uint32 pattern;
1020
1021         FLAC__ASSERT(0 != bb);
1022         FLAC__ASSERT(0 != bb->buffer);
1023         FLAC__ASSERT(parameter <= 30);
1024
1025         *overflow = false;
1026
1027         /* fold signed to unsigned */
1028         if(val < 0)
1029                 /* equivalent to
1030                  *     (unsigned)(((--val) << 1) - 1);
1031                  * but without the overflow problem at MININT
1032                  */
1033                 uval = (unsigned)(((-(++val)) << 1) + 1);
1034         else
1035                 uval = (unsigned)(val << 1);
1036
1037         msbs = uval >> parameter;
1038         interesting_bits = 1 + parameter;
1039         total_bits = interesting_bits + msbs;
1040         pattern = 1 << parameter; /* the unary end bit */
1041         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
1042
1043         if(total_bits <= 32) {
1044                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1045                         return false;
1046         }
1047         else if(total_bits > max_bits) {
1048                 *overflow = true;
1049                 return true;
1050         }
1051         else {
1052                 /* write the unary MSBs */
1053                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
1054                         return false;
1055                 /* write the unary end bit and binary LSBs */
1056                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
1057                         return false;
1058         }
1059         return true;
1060 }
1061 #endif /* UNUSED */
1062
1063 #if 0 /* UNUSED */
1064 FLAC__bool FLAC__bitbuffer_write_golomb_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
1065 {
1066         unsigned total_bits, msbs, uval;
1067         unsigned k;
1068
1069         FLAC__ASSERT(0 != bb);
1070         FLAC__ASSERT(0 != bb->buffer);
1071         FLAC__ASSERT(parameter > 0);
1072
1073         /* fold signed to unsigned */
1074         if(val < 0)
1075                 /* equivalent to
1076                  *     (unsigned)(((--val) << 1) - 1);
1077                  * but without the overflow problem at MININT
1078                  */
1079                 uval = (unsigned)(((-(++val)) << 1) + 1);
1080         else
1081                 uval = (unsigned)(val << 1);
1082
1083         k = FLAC__bitmath_ilog2(parameter);
1084         if(parameter == 1u<<k) {
1085                 unsigned pattern;
1086
1087                 FLAC__ASSERT(k <= 30);
1088
1089                 msbs = uval >> k;
1090                 total_bits = 1 + k + msbs;
1091                 pattern = 1 << k; /* the unary end bit */
1092                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
1093
1094                 if(total_bits <= 32) {
1095                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1096                                 return false;
1097                 }
1098                 else {
1099                         /* write the unary MSBs */
1100                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
1101                                 return false;
1102                         /* write the unary end bit and binary LSBs */
1103                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
1104                                 return false;
1105                 }
1106         }
1107         else {
1108                 unsigned q, r, d;
1109
1110                 d = (1 << (k+1)) - parameter;
1111                 q = uval / parameter;
1112                 r = uval - (q * parameter);
1113                 /* write the unary MSBs */
1114                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
1115                         return false;
1116                 /* write the unary end bit */
1117                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
1118                         return false;
1119                 /* write the binary LSBs */
1120                 if(r >= d) {
1121                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
1122                                 return false;
1123                 }
1124                 else {
1125                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
1126                                 return false;
1127                 }
1128         }
1129         return true;
1130 }
1131
1132 FLAC__bool FLAC__bitbuffer_write_golomb_unsigned(FLAC__BitBuffer *bb, unsigned uval, unsigned parameter)
1133 {
1134         unsigned total_bits, msbs;
1135         unsigned k;
1136
1137         FLAC__ASSERT(0 != bb);
1138         FLAC__ASSERT(0 != bb->buffer);
1139         FLAC__ASSERT(parameter > 0);
1140
1141         k = FLAC__bitmath_ilog2(parameter);
1142         if(parameter == 1u<<k) {
1143                 unsigned pattern;
1144
1145                 FLAC__ASSERT(k <= 30);
1146
1147                 msbs = uval >> k;
1148                 total_bits = 1 + k + msbs;
1149                 pattern = 1 << k; /* the unary end bit */
1150                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
1151
1152                 if(total_bits <= 32) {
1153                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1154                                 return false;
1155                 }
1156                 else {
1157                         /* write the unary MSBs */
1158                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
1159                                 return false;
1160                         /* write the unary end bit and binary LSBs */
1161                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
1162                                 return false;
1163                 }
1164         }
1165         else {
1166                 unsigned q, r, d;
1167
1168                 d = (1 << (k+1)) - parameter;
1169                 q = uval / parameter;
1170                 r = uval - (q * parameter);
1171                 /* write the unary MSBs */
1172                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
1173                         return false;
1174                 /* write the unary end bit */
1175                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
1176                         return false;
1177                 /* write the binary LSBs */
1178                 if(r >= d) {
1179                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
1180                                 return false;
1181                 }
1182                 else {
1183                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
1184                                 return false;
1185                 }
1186         }
1187         return true;
1188 }
1189 #endif /* UNUSED */
1190
1191 FLAC__bool FLAC__bitbuffer_write_utf8_uint32(FLAC__BitBuffer *bb, FLAC__uint32 val)
1192 {
1193         FLAC__bool ok = 1;
1194
1195         FLAC__ASSERT(0 != bb);
1196         FLAC__ASSERT(0 != bb->buffer);
1197
1198         FLAC__ASSERT(!(val & 0x80000000)); /* this version only handles 31 bits */
1199
1200         if(val < 0x80) {
1201                 return FLAC__bitbuffer_write_raw_uint32(bb, val, 8);
1202         }
1203         else if(val < 0x800) {
1204                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (val>>6), 8);
1205                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
1206         }
1207         else if(val < 0x10000) {
1208                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (val>>12), 8);
1209                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
1210                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
1211         }
1212         else if(val < 0x200000) {
1213                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (val>>18), 8);
1214                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
1215                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
1216                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
1217         }
1218         else if(val < 0x4000000) {
1219                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (val>>24), 8);
1220                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
1221                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
1222                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
1223                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
1224         }
1225         else {
1226                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (val>>30), 8);
1227                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>24)&0x3F), 8);
1228                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
1229                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
1230                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
1231                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
1232         }
1233
1234         return ok;
1235 }
1236
1237 FLAC__bool FLAC__bitbuffer_write_utf8_uint64(FLAC__BitBuffer *bb, FLAC__uint64 val)
1238 {
1239         FLAC__bool ok = 1;
1240
1241         FLAC__ASSERT(0 != bb);
1242         FLAC__ASSERT(0 != bb->buffer);
1243
1244         FLAC__ASSERT(!(val & 0xFFFFFFF000000000)); /* this version only handles 36 bits */
1245
1246         if(val < 0x80) {
1247                 return FLAC__bitbuffer_write_raw_uint32(bb, (FLAC__uint32)val, 8);
1248         }
1249         else if(val < 0x800) {
1250                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (FLAC__uint32)(val>>6), 8);
1251                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1252         }
1253         else if(val < 0x10000) {
1254                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (FLAC__uint32)(val>>12), 8);
1255                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
1256                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1257         }
1258         else if(val < 0x200000) {
1259                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (FLAC__uint32)(val>>18), 8);
1260                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
1261                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
1262                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1263         }
1264         else if(val < 0x4000000) {
1265                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (FLAC__uint32)(val>>24), 8);
1266                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
1267                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
1268                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
1269                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1270         }
1271         else if(val < 0x80000000) {
1272                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (FLAC__uint32)(val>>30), 8);
1273                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
1274                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
1275                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
1276                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
1277                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1278         }
1279         else {
1280                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFE, 8);
1281                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>30)&0x3F), 8);
1282                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
1283                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
1284                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
1285                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
1286                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (FLAC__uint32)(val&0x3F), 8);
1287         }
1288
1289         return ok;
1290 }
1291
1292 FLAC__bool FLAC__bitbuffer_zero_pad_to_byte_boundary(FLAC__BitBuffer *bb)
1293 {
1294         /* 0-pad to byte boundary */
1295         if(bb->bits & 7u)
1296                 return FLAC__bitbuffer_write_zeroes(bb, 8 - (bb->bits & 7u));
1297         else
1298                 return true;
1299 }
1300
1301 FLAC__bool FLAC__bitbuffer_peek_bit(FLAC__BitBuffer *bb, unsigned *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1302 {
1303         /* to avoid a drastic speed penalty we don't:
1304         FLAC__ASSERT(0 != bb);
1305         FLAC__ASSERT(0 != bb->buffer);
1306         FLAC__ASSERT(bb->bits == 0);
1307         */
1308
1309         while(1) {
1310                 if(bb->total_consumed_bits < bb->total_bits) {
1311                         *val = (bb->buffer[bb->consumed_blurbs] & BLURB_BIT_TO_MASK(bb->consumed_bits))? 1 : 0;
1312                         return true;
1313                 }
1314                 else {
1315                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1316                                 return false;
1317                 }
1318         }
1319 }
1320
1321 FLAC__bool FLAC__bitbuffer_read_bit(FLAC__BitBuffer *bb, unsigned *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1322 {
1323         /* to avoid a drastic speed penalty we don't:
1324         FLAC__ASSERT(0 != bb);
1325         FLAC__ASSERT(0 != bb->buffer);
1326         FLAC__ASSERT(bb->bits == 0);
1327         */
1328
1329         while(1) {
1330                 if(bb->total_consumed_bits < bb->total_bits) {
1331                         *val = (bb->buffer[bb->consumed_blurbs] & BLURB_BIT_TO_MASK(bb->consumed_bits))? 1 : 0;
1332                         bb->consumed_bits++;
1333                         if(bb->consumed_bits == FLAC__BITS_PER_BLURB) {
1334                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1335                                 bb->consumed_blurbs++;
1336                                 bb->consumed_bits = 0;
1337                         }
1338                         bb->total_consumed_bits++;
1339                         return true;
1340                 }
1341                 else {
1342                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1343                                 return false;
1344                 }
1345         }
1346 }
1347
1348 FLAC__bool FLAC__bitbuffer_read_bit_to_uint32(FLAC__BitBuffer *bb, FLAC__uint32 *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1349 {
1350         /* to avoid a drastic speed penalty we don't:
1351         FLAC__ASSERT(0 != bb);
1352         FLAC__ASSERT(0 != bb->buffer);
1353         FLAC__ASSERT(bb->bits == 0);
1354         */
1355
1356         while(1) {
1357                 if(bb->total_consumed_bits < bb->total_bits) {
1358                         *val <<= 1;
1359                         *val |= (bb->buffer[bb->consumed_blurbs] & BLURB_BIT_TO_MASK(bb->consumed_bits))? 1 : 0;
1360                         bb->consumed_bits++;
1361                         if(bb->consumed_bits == FLAC__BITS_PER_BLURB) {
1362                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1363                                 bb->consumed_blurbs++;
1364                                 bb->consumed_bits = 0;
1365                         }
1366                         bb->total_consumed_bits++;
1367                         return true;
1368                 }
1369                 else {
1370                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1371                                 return false;
1372                 }
1373         }
1374 }
1375
1376 FLAC__bool FLAC__bitbuffer_read_bit_to_uint64(FLAC__BitBuffer *bb, FLAC__uint64 *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1377 {
1378         /* to avoid a drastic speed penalty we don't:
1379         FLAC__ASSERT(0 != bb);
1380         FLAC__ASSERT(0 != bb->buffer);
1381         FLAC__ASSERT(bb->bits == 0);
1382         */
1383
1384         while(1) {
1385                 if(bb->total_consumed_bits < bb->total_bits) {
1386                         *val <<= 1;
1387                         *val |= (bb->buffer[bb->consumed_blurbs] & BLURB_BIT_TO_MASK(bb->consumed_bits))? 1 : 0;
1388                         bb->consumed_bits++;
1389                         if(bb->consumed_bits == FLAC__BITS_PER_BLURB) {
1390                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1391                                 bb->consumed_blurbs++;
1392                                 bb->consumed_bits = 0;
1393                         }
1394                         bb->total_consumed_bits++;
1395                         return true;
1396                 }
1397                 else {
1398                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1399                                 return false;
1400                 }
1401         }
1402 }
1403
1404 FLaC__INLINE FLAC__bool FLAC__bitbuffer_read_raw_uint32(FLAC__BitBuffer *bb, FLAC__uint32 *val, const unsigned bits, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1405 #ifdef FLAC__NO_MANUAL_INLINING
1406 {
1407         unsigned i;
1408
1409         FLAC__ASSERT(0 != bb);
1410         FLAC__ASSERT(0 != bb->buffer);
1411
1412         FLAC__ASSERT(bits <= 32);
1413
1414         *val = 0;
1415         for(i = 0; i < bits; i++) {
1416                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, val, read_callback, client_data))
1417                         return false;
1418         }
1419         return true;
1420 }
1421 #else
1422 {
1423         unsigned i, bits_ = bits;
1424         FLAC__uint32 v = 0;
1425
1426         FLAC__ASSERT(0 != bb);
1427         FLAC__ASSERT(0 != bb->buffer);
1428
1429         FLAC__ASSERT(bits <= 32);
1430         FLAC__ASSERT((bb->capacity*FLAC__BITS_PER_BLURB) * 2 >= bits);
1431
1432         if(bits == 0) {
1433                 *val = 0;
1434                 return true;
1435         }
1436
1437         while(bb->total_consumed_bits + bits > bb->total_bits) {
1438                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1439                         return false;
1440         }
1441 #if FLAC__BITS_PER_BLURB > 8
1442         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) { /*@@@ comment on why this is here*/
1443 #endif
1444                 if(bb->consumed_bits) {
1445                         i = FLAC__BITS_PER_BLURB - bb->consumed_bits;
1446                         if(i <= bits_) {
1447                                 v = bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits);
1448                                 bits_ -= i;
1449                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1450                                 bb->consumed_blurbs++;
1451                                 bb->consumed_bits = 0;
1452                                 /* we hold off updating bb->total_consumed_bits until the end */
1453                         }
1454                         else {
1455                                 *val = (bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits)) >> (i-bits_);
1456                                 bb->consumed_bits += bits_;
1457                                 bb->total_consumed_bits += bits_;
1458                                 return true;
1459                         }
1460                 }
1461 #if FLAC__BITS_PER_BLURB == 32
1462                 /* note that we know bits_ cannot be > 32 because of previous assertions */
1463                 if(bits_ == FLAC__BITS_PER_BLURB) {
1464                         v = bb->buffer[bb->consumed_blurbs];
1465                         CRC16_UPDATE_BLURB(bb, v, bb->read_crc16);
1466                         bb->consumed_blurbs++;
1467                         /* bb->consumed_bits is already 0 */
1468                         bb->total_consumed_bits += bits;
1469                         *val = v;
1470                         return true;
1471                 }
1472 #else
1473                 while(bits_ >= FLAC__BITS_PER_BLURB) {
1474                         v <<= FLAC__BITS_PER_BLURB;
1475                         v |= bb->buffer[bb->consumed_blurbs];
1476                         bits_ -= FLAC__BITS_PER_BLURB;
1477                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1478                         bb->consumed_blurbs++;
1479                         /* bb->consumed_bits is already 0 */
1480                         /* we hold off updating bb->total_consumed_bits until the end */
1481                 }
1482 #endif
1483                 if(bits_ > 0) {
1484                         v <<= bits_;
1485                         v |= (bb->buffer[bb->consumed_blurbs] >> (FLAC__BITS_PER_BLURB-bits_));
1486                         bb->consumed_bits = bits_;
1487                         /* we hold off updating bb->total_consumed_bits until the end */
1488                 }
1489                 bb->total_consumed_bits += bits;
1490                 *val = v;
1491 #if FLAC__BITS_PER_BLURB > 8
1492         }
1493         else {
1494                 *val = 0;
1495                 for(i = 0; i < bits; i++) {
1496                         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, val, read_callback, client_data))
1497                                 return false;
1498                 }
1499         }
1500 #endif
1501         return true;
1502 }
1503 #endif
1504
1505 FLAC__bool FLAC__bitbuffer_read_raw_int32(FLAC__BitBuffer *bb, FLAC__int32 *val, const unsigned bits, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1506 #ifdef FLAC__NO_MANUAL_INLINING
1507 {
1508         unsigned i;
1509         FLAC__uint32 v;
1510
1511         FLAC__ASSERT(0 != bb);
1512         FLAC__ASSERT(0 != bb->buffer);
1513
1514         FLAC__ASSERT(bits <= 32);
1515
1516         if(bits == 0) {
1517                 *val = 0;
1518                 return true;
1519         }
1520
1521         v = 0;
1522         for(i = 0; i < bits; i++) {
1523                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &v, read_callback, client_data))
1524                         return false;
1525         }
1526
1527         /* fix the sign */
1528         i = 32 - bits;
1529         if(i) {
1530                 v <<= i;
1531                 *val = (FLAC__int32)v;
1532                 *val >>= i;
1533         }
1534         else
1535                 *val = (FLAC__int32)v;
1536
1537         return true;
1538 }
1539 #else
1540 {
1541         unsigned i, bits_ = bits;
1542         FLAC__uint32 v = 0;
1543
1544         FLAC__ASSERT(0 != bb);
1545         FLAC__ASSERT(0 != bb->buffer);
1546
1547         FLAC__ASSERT(bits <= 32);
1548         FLAC__ASSERT((bb->capacity*FLAC__BITS_PER_BLURB) * 2 >= bits);
1549
1550         if(bits == 0) {
1551                 *val = 0;
1552                 return true;
1553         }
1554
1555         while(bb->total_consumed_bits + bits > bb->total_bits) {
1556                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1557                         return false;
1558         }
1559 #if FLAC__BITS_PER_BLURB > 8
1560         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) { /*@@@ comment on why this is here*/
1561 #endif
1562                 if(bb->consumed_bits) {
1563                         i = FLAC__BITS_PER_BLURB - bb->consumed_bits;
1564                         if(i <= bits_) {
1565                                 v = bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits);
1566                                 bits_ -= i;
1567                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1568                                 bb->consumed_blurbs++;
1569                                 bb->consumed_bits = 0;
1570                                 /* we hold off updating bb->total_consumed_bits until the end */
1571                         }
1572                         else {
1573                                 /* bits_ must be < FLAC__BITS_PER_BLURB-1 if we get to here */
1574                                 v = (bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits));
1575                                 v <<= (32-i);
1576                                 *val = (FLAC__int32)v;
1577                                 *val >>= (32-bits_);
1578                                 bb->consumed_bits += bits_;
1579                                 bb->total_consumed_bits += bits_;
1580                                 return true;
1581                         }
1582                 }
1583 #if FLAC__BITS_PER_BLURB == 32
1584                 /* note that we know bits_ cannot be > 32 because of previous assertions */
1585                 if(bits_ == FLAC__BITS_PER_BLURB) {
1586                         v = bb->buffer[bb->consumed_blurbs];
1587                         bits_ = 0;
1588                         CRC16_UPDATE_BLURB(bb, v, bb->read_crc16);
1589                         bb->consumed_blurbs++;
1590                         /* bb->consumed_bits is already 0 */
1591                         /* we hold off updating bb->total_consumed_bits until the end */
1592                 }
1593 #else
1594                 while(bits_ >= FLAC__BITS_PER_BLURB) {
1595                         v <<= FLAC__BITS_PER_BLURB;
1596                         v |= bb->buffer[bb->consumed_blurbs];
1597                         bits_ -= FLAC__BITS_PER_BLURB;
1598                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1599                         bb->consumed_blurbs++;
1600                         /* bb->consumed_bits is already 0 */
1601                         /* we hold off updating bb->total_consumed_bits until the end */
1602                 }
1603 #endif
1604                 if(bits_ > 0) {
1605                         v <<= bits_;
1606                         v |= (bb->buffer[bb->consumed_blurbs] >> (FLAC__BITS_PER_BLURB-bits_));
1607                         bb->consumed_bits = bits_;
1608                         /* we hold off updating bb->total_consumed_bits until the end */
1609                 }
1610                 bb->total_consumed_bits += bits;
1611 #if FLAC__BITS_PER_BLURB > 8
1612         }
1613         else {
1614                 for(i = 0; i < bits; i++) {
1615                         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &v, read_callback, client_data))
1616                                 return false;
1617                 }
1618         }
1619 #endif
1620
1621         /* fix the sign */
1622         i = 32 - bits;
1623         if(i) {
1624                 v <<= i;
1625                 *val = (FLAC__int32)v;
1626                 *val >>= i;
1627         }
1628         else
1629                 *val = (FLAC__int32)v;
1630
1631         return true;
1632 }
1633 #endif
1634
1635 FLAC__bool FLAC__bitbuffer_read_raw_uint64(FLAC__BitBuffer *bb, FLAC__uint64 *val, const unsigned bits, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1636 #ifdef FLAC__NO_MANUAL_INLINING
1637 {
1638         unsigned i;
1639
1640         FLAC__ASSERT(0 != bb);
1641         FLAC__ASSERT(0 != bb->buffer);
1642
1643         FLAC__ASSERT(bits <= 64);
1644
1645         *val = 0;
1646         for(i = 0; i < bits; i++) {
1647                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, val, read_callback, client_data))
1648                         return false;
1649         }
1650         return true;
1651 }
1652 #else
1653 {
1654         unsigned i, bits_ = bits;
1655         FLAC__uint64 v = 0;
1656
1657         FLAC__ASSERT(0 != bb);
1658         FLAC__ASSERT(0 != bb->buffer);
1659
1660         FLAC__ASSERT(bits <= 64);
1661         FLAC__ASSERT((bb->capacity*FLAC__BITS_PER_BLURB) * 2 >= bits);
1662
1663         if(bits == 0) {
1664                 *val = 0;
1665                 return true;
1666         }
1667
1668         while(bb->total_consumed_bits + bits > bb->total_bits) {
1669                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1670                         return false;
1671         }
1672 #if FLAC__BITS_PER_BLURB > 8
1673         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) { /*@@@ comment on why this is here*/
1674 #endif
1675                 if(bb->consumed_bits) {
1676                         i = FLAC__BITS_PER_BLURB - bb->consumed_bits;
1677                         if(i <= bits_) {
1678                                 v = bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits);
1679                                 bits_ -= i;
1680                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1681                                 bb->consumed_blurbs++;
1682                                 bb->consumed_bits = 0;
1683                                 /* we hold off updating bb->total_consumed_bits until the end */
1684                         }
1685                         else {
1686                                 *val = (bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits)) >> (i-bits_);
1687                                 bb->consumed_bits += bits_;
1688                                 bb->total_consumed_bits += bits_;
1689                                 return true;
1690                         }
1691                 }
1692                 while(bits_ >= FLAC__BITS_PER_BLURB) {
1693                         v <<= FLAC__BITS_PER_BLURB;
1694                         v |= bb->buffer[bb->consumed_blurbs];
1695                         bits_ -= FLAC__BITS_PER_BLURB;
1696                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1697                         bb->consumed_blurbs++;
1698                         /* bb->consumed_bits is already 0 */
1699                         /* we hold off updating bb->total_consumed_bits until the end */
1700                 }
1701                 if(bits_ > 0) {
1702                         v <<= bits_;
1703                         v |= (bb->buffer[bb->consumed_blurbs] >> (FLAC__BITS_PER_BLURB-bits_));
1704                         bb->consumed_bits = bits_;
1705                         /* we hold off updating bb->total_consumed_bits until the end */
1706                 }
1707                 bb->total_consumed_bits += bits;
1708                 *val = v;
1709 #if FLAC__BITS_PER_BLURB > 8
1710         }
1711         else {
1712                 *val = 0;
1713                 for(i = 0; i < bits; i++) {
1714                         if(!FLAC__bitbuffer_read_bit_to_uint64(bb, val, read_callback, client_data))
1715                                 return false;
1716                 }
1717         }
1718 #endif
1719         return true;
1720 }
1721 #endif
1722
1723 #if 0 /* UNUSED */
1724 FLAC__bool FLAC__bitbuffer_read_raw_int64(FLAC__BitBuffer *bb, FLAC__int64 *val, const unsigned bits, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1725 #ifdef FLAC__NO_MANUAL_INLINING
1726 {
1727         unsigned i;
1728         FLAC__uint64 v;
1729
1730         FLAC__ASSERT(0 != bb);
1731         FLAC__ASSERT(0 != bb->buffer);
1732
1733         FLAC__ASSERT(bits <= 64);
1734
1735         v = 0;
1736         for(i = 0; i < bits; i++) {
1737                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, &v, read_callback, client_data))
1738                         return false;
1739         }
1740         /* fix the sign */
1741         i = 64 - bits;
1742         if(i) {
1743                 v <<= i;
1744                 *val = (FLAC__int64)v;
1745                 *val >>= i;
1746         }
1747         else
1748                 *val = (FLAC__int64)v;
1749
1750         return true;
1751 }
1752 #else
1753 {
1754         unsigned i, bits_ = bits;
1755         FLAC__uint64 v = 0;
1756
1757         FLAC__ASSERT(0 != bb);
1758         FLAC__ASSERT(0 != bb->buffer);
1759
1760         FLAC__ASSERT(bits <= 64);
1761         FLAC__ASSERT((bb->capacity*FLAC__BITS_PER_BLURB) * 2 >= bits);
1762
1763         if(bits == 0) {
1764                 *val = 0;
1765                 return true;
1766         }
1767
1768         while(bb->total_consumed_bits + bits > bb->total_bits) {
1769                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1770                         return false;
1771         }
1772 #if FLAC__BITS_PER_BLURB > 8
1773         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) { /*@@@ comment on why this is here*/
1774 #endif
1775                 if(bb->consumed_bits) {
1776                         i = FLAC__BITS_PER_BLURB - bb->consumed_bits;
1777                         if(i <= bits_) {
1778                                 v = bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits);
1779                                 bits_ -= i;
1780                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1781                                 bb->consumed_blurbs++;
1782                                 bb->consumed_bits = 0;
1783                                 /* we hold off updating bb->total_consumed_bits until the end */
1784                         }
1785                         else {
1786                                 /* bits_ must be < FLAC__BITS_PER_BLURB-1 if we get to here */
1787                                 v = (bb->buffer[bb->consumed_blurbs] & (FLAC__BLURB_ALL_ONES >> bb->consumed_bits));
1788                                 v <<= (64-i);
1789                                 *val = (FLAC__int64)v;
1790                                 *val >>= (64-bits_);
1791                                 bb->consumed_bits += bits_;
1792                                 bb->total_consumed_bits += bits_;
1793                                 return true;
1794                         }
1795                 }
1796                 while(bits_ >= FLAC__BITS_PER_BLURB) {
1797                         v <<= FLAC__BITS_PER_BLURB;
1798                         v |= bb->buffer[bb->consumed_blurbs];
1799                         bits_ -= FLAC__BITS_PER_BLURB;
1800                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1801                         bb->consumed_blurbs++;
1802                         /* bb->consumed_bits is already 0 */
1803                         /* we hold off updating bb->total_consumed_bits until the end */
1804                 }
1805                 if(bits_ > 0) {
1806                         v <<= bits_;
1807                         v |= (bb->buffer[bb->consumed_blurbs] >> (FLAC__BITS_PER_BLURB-bits_));
1808                         bb->consumed_bits = bits_;
1809                         /* we hold off updating bb->total_consumed_bits until the end */
1810                 }
1811                 bb->total_consumed_bits += bits;
1812 #if FLAC__BITS_PER_BLURB > 8
1813         }
1814         else {
1815                 for(i = 0; i < bits; i++) {
1816                         if(!FLAC__bitbuffer_read_bit_to_uint64(bb, &v, read_callback, client_data))
1817                                 return false;
1818                 }
1819         }
1820 #endif
1821
1822         /* fix the sign */
1823         i = 64 - bits;
1824         if(i) {
1825                 v <<= i;
1826                 *val = (FLAC__int64)v;
1827                 *val >>= i;
1828         }
1829         else
1830                 *val = (FLAC__int64)v;
1831
1832         return true;
1833 }
1834 #endif
1835 #endif
1836
1837 FLaC__INLINE FLAC__bool FLAC__bitbuffer_read_raw_uint32_little_endian(FLAC__BitBuffer *bb, FLAC__uint32 *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1838 {
1839         FLAC__uint32 x8, x32 = 0;
1840
1841         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
1842
1843         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x32, 8, read_callback, client_data))
1844                 return false;
1845
1846         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x8, 8, read_callback, client_data))
1847                 return false;
1848         x32 |= (x8 << 8);
1849
1850         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x8, 8, read_callback, client_data))
1851                 return false;
1852         x32 |= (x8 << 16);
1853
1854         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x8, 8, read_callback, client_data))
1855                 return false;
1856         x32 |= (x8 << 24);
1857
1858         *val = x32;
1859         return true;
1860 }
1861
1862 FLAC__bool FLAC__bitbuffer_skip_bits_no_crc(FLAC__BitBuffer *bb, unsigned bits, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1863 {
1864         /*
1865          * @@@ a slightly faster implementation is possible but
1866          * probably not that useful since this is only called a
1867          * couple of times in the metadata readers.
1868          */
1869         FLAC__ASSERT(0 != bb);
1870         FLAC__ASSERT(0 != bb->buffer);
1871
1872         if(bits > 0) {
1873                 const unsigned n = bb->consumed_bits & 7;
1874                 unsigned m;
1875                 FLAC__uint32 x;
1876
1877                 if(n != 0) {
1878                         m = min(8-n, bits);
1879                         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, m, read_callback, client_data))
1880                                 return false;
1881                         bits -= m;
1882                 }
1883                 m = bits / 8;
1884                 if(m > 0) {
1885                         if(!FLAC__bitbuffer_read_byte_block_aligned_no_crc(bb, 0, m, read_callback, client_data))
1886                                 return false;
1887                         bits %= 8;
1888                 }
1889                 if(bits > 0) {
1890                         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, bits, read_callback, client_data))
1891                                 return false;
1892                 }
1893         }
1894
1895         return true;
1896 }
1897
1898 FLAC__bool FLAC__bitbuffer_read_byte_block_aligned_no_crc(FLAC__BitBuffer *bb, FLAC__byte *val, unsigned nvals, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1899 {
1900         FLAC__ASSERT(0 != bb);
1901         FLAC__ASSERT(0 != bb->buffer);
1902         FLAC__ASSERT(FLAC__bitbuffer_is_byte_aligned(bb));
1903         FLAC__ASSERT(FLAC__bitbuffer_is_consumed_byte_aligned(bb));
1904 #if FLAC__BITS_PER_BLURB == 8
1905         while(nvals > 0) {
1906                 unsigned chunk = min(nvals, bb->blurbs - bb->consumed_blurbs);
1907                 if(chunk == 0) {
1908                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1909                                 return false;
1910                 }
1911                 else {
1912                         if(0 != val) {
1913                                 memcpy(val, bb->buffer + bb->consumed_blurbs, FLAC__BYTES_PER_BLURB * chunk);
1914                                 val += FLAC__BYTES_PER_BLURB * chunk;
1915                         }
1916                         nvals -= chunk;
1917                         bb->consumed_blurbs += chunk;
1918                         bb->total_consumed_bits = (bb->consumed_blurbs << FLAC__BITS_PER_BLURB_LOG2);
1919                 }
1920         }
1921 #else
1922         @@@ need to write this still
1923         FLAC__ASSERT(0);
1924 #endif
1925
1926         return true;
1927 }
1928
1929 FLaC__INLINE FLAC__bool FLAC__bitbuffer_read_unary_unsigned(FLAC__BitBuffer *bb, unsigned *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1930 #ifdef FLAC__NO_MANUAL_INLINING
1931 {
1932         unsigned bit, val_ = 0;
1933
1934         FLAC__ASSERT(0 != bb);
1935         FLAC__ASSERT(0 != bb->buffer);
1936
1937         while(1) {
1938                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1939                         return false;
1940                 if(bit)
1941                         break;
1942                 else
1943                         val_++;
1944         }
1945         *val = val_;
1946         return true;
1947 }
1948 #else
1949 {
1950         unsigned i, val_ = 0;
1951         unsigned total_blurbs_ = (bb->total_bits + (FLAC__BITS_PER_BLURB-1)) / FLAC__BITS_PER_BLURB;
1952         FLAC__blurb b;
1953
1954         FLAC__ASSERT(0 != bb);
1955         FLAC__ASSERT(0 != bb->buffer);
1956
1957 #if FLAC__BITS_PER_BLURB > 8
1958         if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) { /*@@@ comment on why this is here*/
1959 #endif
1960                 if(bb->consumed_bits) {
1961                         b = bb->buffer[bb->consumed_blurbs] << bb->consumed_bits;
1962                         if(b) {
1963                                 for(i = 0; !(b & FLAC__BLURB_TOP_BIT_ONE); i++)
1964                                         b <<= 1;
1965                                 *val = i;
1966                                 i++;
1967                                 bb->consumed_bits += i;
1968                                 bb->total_consumed_bits += i;
1969                                 if(bb->consumed_bits == FLAC__BITS_PER_BLURB) {
1970                                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1971                                         bb->consumed_blurbs++;
1972                                         bb->consumed_bits = 0;
1973                                 }
1974                                 return true;
1975                         }
1976                         else {
1977                                 val_ = FLAC__BITS_PER_BLURB - bb->consumed_bits;
1978                                 CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
1979                                 bb->consumed_blurbs++;
1980                                 bb->consumed_bits = 0;
1981                                 bb->total_consumed_bits += val_;
1982                         }
1983                 }
1984                 while(1) {
1985                         if(bb->consumed_blurbs >= total_blurbs_) {
1986                                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1987                                         return false;
1988                                 total_blurbs_ = (bb->total_bits + (FLAC__BITS_PER_BLURB-1)) / FLAC__BITS_PER_BLURB;
1989                         }
1990                         b = bb->buffer[bb->consumed_blurbs];
1991                         if(b) {
1992                                 for(i = 0; !(b & FLAC__BLURB_TOP_BIT_ONE); i++)
1993                                         b <<= 1;
1994                                 val_ += i;
1995                                 i++;
1996                                 bb->consumed_bits = i;
1997                                 *val = val_;
1998                                 if(i == FLAC__BITS_PER_BLURB) {
1999                                         CRC16_UPDATE_BLURB(bb, bb->buffer[bb->consumed_blurbs], bb->read_crc16);
2000                                         bb->consumed_blurbs++;
2001                                         bb->consumed_bits = 0;
2002                                 }
2003                                 bb->total_consumed_bits += i;
2004                                 return true;
2005                         }
2006                         else {
2007                                 val_ += FLAC__BITS_PER_BLURB;
2008                                 CRC16_UPDATE_BLURB(bb, 0, bb->read_crc16);
2009                                 bb->consumed_blurbs++;
2010                                 /* bb->consumed_bits is already 0 */
2011                                 bb->total_consumed_bits += FLAC__BITS_PER_BLURB;
2012                         }
2013                 }
2014 #if FLAC__BITS_PER_BLURB > 8
2015         }
2016         else {
2017                 while(1) {
2018                         if(!FLAC__bitbuffer_read_bit(bb, &i, read_callback, client_data))
2019                                 return false;
2020                         if(i)
2021                                 break;
2022                         else
2023                                 val_++;
2024                 }
2025                 *val = val_;
2026                 return true;
2027         }
2028 #endif
2029 }
2030 #endif
2031
2032 #ifdef FLAC__SYMMETRIC_RICE
2033 FLAC__bool FLAC__bitbuffer_read_symmetric_rice_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
2034 {
2035         FLAC__uint32 sign = 0, lsbs = 0, msbs = 0;
2036
2037         FLAC__ASSERT(0 != bb);
2038         FLAC__ASSERT(0 != bb->buffer);
2039         FLAC__ASSERT(parameter <= 31);
2040
2041         /* read the unary MSBs and end bit */
2042         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
2043                 return false;
2044
2045         /* read the sign bit */
2046         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &sign, read_callback, client_data))
2047                 return false;
2048
2049         /* read the binary LSBs */
2050         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
2051                 return false;
2052
2053         /* compose the value */
2054         *val = (msbs << parameter) | lsbs;
2055         if(sign)
2056                 *val = -(*val);
2057
2058         return true;
2059 }
2060 #endif /* ifdef FLAC__SYMMETRIC_RICE */
2061
2062 FLAC__bool FLAC__bitbuffer_read_rice_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
2063 {
2064         FLAC__uint32 lsbs = 0, msbs = 0;
2065         unsigned uval;
2066
2067         FLAC__ASSERT(0 != bb);
2068         FLAC__ASSERT(0 != bb->buffer);
2069         FLAC__ASSERT(parameter <= 31);
2070
2071         /* read the unary MSBs and end bit */
2072         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
2073                 return false;
2074
2075         /* read the binary LSBs */
2076         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
2077                 return false;
2078
2079         /* compose the value */
2080         uval = (msbs << parameter) | lsbs;
2081         if(uval & 1)
2082                 *val = -((int)(uval >> 1)) - 1;
2083         else
2084                 *val = (int)(uval >> 1);
2085
2086         return true;
2087 }
2088
2089 FLAC__bool FLAC__bitbuffer_read_rice_signed_block(FLAC__BitBuffer *bb, int vals[], unsigned nvals, unsigned parameter, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
2090 {
2091         const FLAC__blurb *buffer = bb->buffer;
2092
2093         unsigned i, j, val_i = 0;
2094         unsigned cbits = 0, uval = 0, msbs = 0, lsbs_left = 0;
2095         FLAC__blurb blurb, save_blurb;
2096         unsigned state = 0; /* 0 = getting unary MSBs, 1 = getting binary LSBs */
2097
2098         FLAC__ASSERT(0 != bb);
2099         FLAC__ASSERT(0 != bb->buffer);
2100         FLAC__ASSERT(parameter <= 31);
2101
2102         if(nvals == 0)
2103                 return true;
2104
2105         i = bb->consumed_blurbs;
2106         /*
2107          * We unroll the main loop to take care of partially consumed blurbs here.
2108          */
2109         if(bb->consumed_bits > 0) {
2110                 save_blurb = blurb = buffer[i];
2111                 cbits = bb->consumed_bits;
2112                 blurb <<= cbits;
2113
2114                 while(1) {
2115                         if(state == 0) {
2116                                 if(blurb) {
2117                                         for(j = 0; !(blurb & FLAC__BLURB_TOP_BIT_ONE); j++)
2118                                                 blurb <<= 1;
2119                                         msbs += j;
2120
2121                                         /* dispose of the unary end bit */
2122                                         blurb <<= 1;
2123                                         j++;
2124                                         cbits += j;
2125
2126                                         uval = 0;
2127                                         lsbs_left = parameter;
2128                                         state++;
2129                                         if(cbits == FLAC__BITS_PER_BLURB) {
2130                                                 cbits = 0;
2131                                                 CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2132                                                 break;
2133                                         }
2134                                 }
2135                                 else {
2136                                         msbs += FLAC__BITS_PER_BLURB - cbits;
2137                                         cbits = 0;
2138                                         CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2139                                         break;
2140                                 }
2141                         }
2142                         else {
2143                                 const unsigned available_bits = FLAC__BITS_PER_BLURB - cbits;
2144                                 if(lsbs_left >= available_bits) {
2145                                         uval <<= available_bits;
2146                                         uval |= (blurb >> cbits);
2147                                         cbits = 0;
2148                                         CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2149
2150                                         if(lsbs_left == available_bits) {
2151                                                 /* compose the value */
2152                                                 uval |= (msbs << parameter);
2153                                                 if(uval & 1)
2154                                                         vals[val_i++] = -((int)(uval >> 1)) - 1;
2155                                                 else
2156                                                         vals[val_i++] = (int)(uval >> 1);
2157                                                 if(val_i == nvals)
2158                                                         break;
2159
2160                                                 msbs = 0;
2161                                                 state = 0;
2162                                         }
2163
2164                                         lsbs_left -= available_bits;
2165                                         break;
2166                                 }
2167                                 else {
2168                                         uval <<= lsbs_left;
2169                                         uval |= (blurb >> (FLAC__BITS_PER_BLURB - lsbs_left));
2170                                         blurb <<= lsbs_left;
2171                                         cbits += lsbs_left;
2172
2173                                         /* compose the value */
2174                                         uval |= (msbs << parameter);
2175                                         if(uval & 1)
2176                                                 vals[val_i++] = -((int)(uval >> 1)) - 1;
2177                                         else
2178                                                 vals[val_i++] = (int)(uval >> 1);
2179                                         if(val_i == nvals) {
2180                                                 /* back up one if we exited the for loop because we read all nvals but the end came in the middle of a blurb */
2181                                                 i--;
2182                                                 break;
2183                                         }
2184
2185                                         msbs = 0;
2186                                         state = 0;
2187                                 }
2188                         }
2189                 }
2190                 i++;
2191
2192                 bb->consumed_blurbs = i;
2193                 bb->consumed_bits = cbits;
2194                 bb->total_consumed_bits = (i << FLAC__BITS_PER_BLURB_LOG2) | cbits;
2195         }
2196
2197         /*
2198          * Now that we are blurb-aligned the logic is slightly simpler
2199          */
2200         while(val_i < nvals) {
2201                 for( ; i < bb->blurbs && val_i < nvals; i++) {
2202                         save_blurb = blurb = buffer[i];
2203                         cbits = 0;
2204                         while(1) {
2205                                 if(state == 0) {
2206                                         if(blurb) {
2207                                                 for(j = 0; !(blurb & FLAC__BLURB_TOP_BIT_ONE); j++)
2208                                                         blurb <<= 1;
2209                                                 msbs += j;
2210
2211                                                 /* dispose of the unary end bit */
2212                                                 blurb <<= 1;
2213                                                 j++;
2214                                                 cbits += j;
2215
2216                                                 uval = 0;
2217                                                 lsbs_left = parameter;
2218                                                 state++;
2219                                                 if(cbits == FLAC__BITS_PER_BLURB) {
2220                                                         cbits = 0;
2221                                                         CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2222                                                         break;
2223                                                 }
2224                                         }
2225                                         else {
2226                                                 msbs += FLAC__BITS_PER_BLURB - cbits;
2227                                                 cbits = 0;
2228                                                 CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2229                                                 break;
2230                                         }
2231                                 }
2232                                 else {
2233                                         const unsigned available_bits = FLAC__BITS_PER_BLURB - cbits;
2234                                         if(lsbs_left >= available_bits) {
2235                                                 uval <<= available_bits;
2236                                                 uval |= (blurb >> cbits);
2237                                                 cbits = 0;
2238                                                 CRC16_UPDATE_BLURB(bb, save_blurb, bb->read_crc16);
2239
2240                                                 if(lsbs_left == available_bits) {
2241                                                         /* compose the value */
2242                                                         uval |= (msbs << parameter);
2243                                                         if(uval & 1)
2244                                                                 vals[val_i++] = -((int)(uval >> 1)) - 1;
2245                                                         else
2246                                                                 vals[val_i++] = (int)(uval >> 1);
2247                                                         if(val_i == nvals)
2248                                                                 break;
2249
2250                                                         msbs = 0;
2251                                                         state = 0;
2252                                                 }
2253
2254                                                 lsbs_left -= available_bits;
2255                                                 break;
2256                                         }
2257                                         else {
2258                                                 uval <<= lsbs_left;
2259                                                 uval |= (blurb >> (FLAC__BITS_PER_BLURB - lsbs_left));
2260                                                 blurb <<= lsbs_left;
2261                                                 cbits += lsbs_left;
2262
2263                                                 /* compose the value */
2264                                                 uval |= (msbs << parameter);
2265                                                 if(uval & 1)
2266                                                         vals[val_i++] = -((int)(uval >> 1)) - 1;
2267                                                 else
2268                                                         vals[val_i++] = (int)(uval >> 1);
2269                                                 if(val_i == nvals) {
2270                                                         /* back up one if we exited the for loop because we read all nvals but the end came in the middle of a blurb */
2271                                                         i--;
2272                                                         break;
2273                                                 }
2274
2275                                                 msbs = 0;
2276                                                 state = 0;
2277                                         }
2278                                 }
2279                         }
2280                 }
2281                 bb->consumed_blurbs = i;
2282                 bb->consumed_bits = cbits;
2283                 bb->total_consumed_bits = (i << FLAC__BITS_PER_BLURB_LOG2) | cbits;
2284                 if(val_i < nvals) {
2285                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
2286                                 return false;
2287                         /* these must be zero because we can only get here if we got to the end of the buffer */
2288                         FLAC__ASSERT(bb->consumed_blurbs == 0);
2289                         FLAC__ASSERT(bb->consumed_bits == 0);
2290                         i = 0;
2291                 }
2292         }
2293
2294         return true;
2295 }
2296
2297 #if 0 /* UNUSED */
2298 FLAC__bool FLAC__bitbuffer_read_golomb_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
2299 {
2300         FLAC__uint32 lsbs = 0, msbs = 0;
2301         unsigned bit, uval, k;
2302
2303         FLAC__ASSERT(0 != bb);
2304         FLAC__ASSERT(0 != bb->buffer);
2305
2306         k = FLAC__bitmath_ilog2(parameter);
2307
2308         /* read the unary MSBs and end bit */
2309         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
2310                 return false;
2311
2312         /* read the binary LSBs */
2313         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
2314                 return false;
2315
2316         if(parameter == 1u<<k) {
2317                 /* compose the value */
2318                 uval = (msbs << k) | lsbs;
2319         }
2320         else {
2321                 unsigned d = (1 << (k+1)) - parameter;
2322                 if(lsbs >= d) {
2323                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
2324                                 return false;
2325                         lsbs <<= 1;
2326                         lsbs |= bit;
2327                         lsbs -= d;
2328                 }
2329                 /* compose the value */
2330                 uval = msbs * parameter + lsbs;
2331         }
2332
2333         /* unfold unsigned to signed */
2334         if(uval & 1)
2335                 *val = -((int)(uval >> 1)) - 1;
2336         else
2337                 *val = (int)(uval >> 1);
2338
2339         return true;
2340 }
2341
2342 FLAC__bool FLAC__bitbuffer_read_golomb_unsigned(FLAC__BitBuffer *bb, unsigned *val, unsigned parameter, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
2343 {
2344         FLAC__uint32 lsbs, msbs = 0;
2345         unsigned bit, k;
2346
2347         FLAC__ASSERT(0 != bb);
2348         FLAC__ASSERT(0 != bb->buffer);
2349
2350         k = FLAC__bitmath_ilog2(parameter);
2351
2352         /* read the unary MSBs and end bit */
2353         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
2354                 return false;
2355
2356         /* read the binary LSBs */
2357         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
2358                 return false;
2359
2360         if(parameter == 1u<<k) {
2361                 /* compose the value */
2362                 *val = (msbs << k) | lsbs;
2363         }
2364         else {
2365                 unsigned d = (1 << (k+1)) - parameter;
2366                 if(lsbs >= d) {
2367                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
2368                                 return false;
2369                         lsbs <<= 1;
2370                         lsbs |= bit;
2371                         lsbs -= d;
2372                 }
2373                 /* compose the value */
2374                 *val = msbs * parameter + lsbs;
2375         }
2376
2377         return true;
2378 }
2379 #endif /* UNUSED */
2380
2381 /* on return, if *val == 0xffffffff then the utf-8 sequence was invalid, but the return value will be true */
2382 FLAC__bool FLAC__bitbuffer_read_utf8_uint32(FLAC__BitBuffer *bb, FLAC__uint32 *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data, FLAC__byte *raw, unsigned *rawlen)
2383 {
2384         FLAC__uint32 v = 0;
2385         FLAC__uint32 x;
2386         unsigned i;
2387
2388         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
2389                 return false;
2390         if(raw)
2391                 raw[(*rawlen)++] = (FLAC__byte)x;
2392         if(!(x & 0x80)) { /* 0xxxxxxx */
2393                 v = x;
2394                 i = 0;
2395         }
2396         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
2397                 v = x & 0x1F;
2398                 i = 1;
2399         }
2400         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
2401                 v = x & 0x0F;
2402                 i = 2;
2403         }
2404         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
2405                 v = x & 0x07;
2406                 i = 3;
2407         }
2408         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
2409                 v = x & 0x03;
2410                 i = 4;
2411         }
2412         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
2413                 v = x & 0x01;
2414                 i = 5;
2415         }
2416         else {
2417                 *val = 0xffffffff;
2418                 return true;
2419         }
2420         for( ; i; i--) {
2421                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
2422                         return false;
2423                 if(raw)
2424                         raw[(*rawlen)++] = (FLAC__byte)x;
2425                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
2426                         *val = 0xffffffff;
2427                         return true;
2428                 }
2429                 v <<= 6;
2430                 v |= (x & 0x3F);
2431         }
2432         *val = v;
2433         return true;
2434 }
2435
2436 /* on return, if *val == 0xffffffffffffffff then the utf-8 sequence was invalid, but the return value will be true */
2437 FLAC__bool FLAC__bitbuffer_read_utf8_uint64(FLAC__BitBuffer *bb, FLAC__uint64 *val, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data, FLAC__byte *raw, unsigned *rawlen)
2438 {
2439         FLAC__uint64 v = 0;
2440         FLAC__uint32 x;
2441         unsigned i;
2442
2443         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
2444                 return false;
2445         if(raw)
2446                 raw[(*rawlen)++] = (FLAC__byte)x;
2447         if(!(x & 0x80)) { /* 0xxxxxxx */
2448                 v = x;
2449                 i = 0;
2450         }
2451         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
2452                 v = x & 0x1F;
2453                 i = 1;
2454         }
2455         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
2456                 v = x & 0x0F;
2457                 i = 2;
2458         }
2459         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
2460                 v = x & 0x07;
2461                 i = 3;
2462         }
2463         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
2464                 v = x & 0x03;
2465                 i = 4;
2466         }
2467         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
2468                 v = x & 0x01;
2469                 i = 5;
2470         }
2471         else if(x & 0xFE && !(x & 0x01)) { /* 11111110 */
2472                 v = 0;
2473                 i = 6;
2474         }
2475         else {
2476                 *val = 0xffffffffffffffff;
2477                 return true;
2478         }
2479         for( ; i; i--) {
2480                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
2481                         return false;
2482                 if(raw)
2483                         raw[(*rawlen)++] = (FLAC__byte)x;
2484                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
2485                         *val = 0xffffffffffffffff;
2486                         return true;
2487                 }
2488                 v <<= 6;
2489                 v |= (x & 0x3F);
2490         }
2491         *val = v;
2492         return true;
2493 }
2494
2495 void FLAC__bitbuffer_dump(const FLAC__BitBuffer *bb, FILE *out)
2496 {
2497         unsigned i, j;
2498         if(bb == 0) {
2499                 fprintf(out, "bitbuffer is NULL\n");
2500         }
2501         else {
2502                 fprintf(out, "bitbuffer: capacity=%u blurbs=%u bits=%u total_bits=%u consumed: blurbs=%u, bits=%u, total_bits=%u\n", bb->capacity, bb->blurbs, bb->bits, bb->total_bits, bb->consumed_blurbs, bb->consumed_bits, bb->total_consumed_bits);
2503
2504                 for(i = 0; i < bb->blurbs; i++) {
2505                         fprintf(out, "%08X: ", i);
2506                         for(j = 0; j < FLAC__BITS_PER_BLURB; j++)
2507                                 if(i*FLAC__BITS_PER_BLURB+j < bb->total_consumed_bits)
2508                                         fprintf(out, ".");
2509                                 else
2510                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (FLAC__BITS_PER_BLURB-j-1)) ? 1:0);
2511                         fprintf(out, "\n");
2512                 }
2513                 if(bb->bits > 0) {
2514                         fprintf(out, "%08X: ", i);
2515                         for(j = 0; j < bb->bits; j++)
2516                                 if(i*FLAC__BITS_PER_BLURB+j < bb->total_consumed_bits)
2517                                         fprintf(out, ".");
2518                                 else
2519                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (bb->bits-j-1)) ? 1:0);
2520                         fprintf(out, "\n");
2521                 }
2522         }
2523 }