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