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