add symmetric rice coding back in
[flac.git] / src / libFLAC / bitbuffer.c
1 /* libFLAC - Free Lossless Audio Codec library
2  * Copyright (C) 2000,2001  Josh Coalson
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA  02111-1307, USA.
18  */
19
20 #include <assert.h>
21 #include <stdlib.h> /* for malloc() */
22 #include <string.h> /* for memcpy(), memset() */
23 #include "private/bitbuffer.h"
24
25 static const unsigned FLAC__BITBUFFER_DEFAULT_CAPACITY = 65536; /* bytes */
26
27 #ifdef min
28 #undef min
29 #endif
30 #define min(x,y) ((x)<(y)?(x):(y))
31 #ifdef max
32 #undef max
33 #endif
34 #define max(x,y) ((x)>(y)?(x):(y))
35
36 static unsigned ilog2_(unsigned v)
37 {
38         unsigned l = 0;
39         assert(v > 0);
40         while(v >>= 1)
41                 l++;
42         return l;
43 }
44
45 static bool bitbuffer_resize_(FLAC__BitBuffer *bb, unsigned new_capacity)
46 {
47         byte *new_buffer;
48
49         assert(bb != 0);
50         assert(bb->buffer != 0);
51
52         if(bb->capacity == new_capacity)
53                 return true;
54
55         new_buffer = (byte*)malloc(sizeof(byte) * new_capacity);
56         if(new_buffer == 0)
57                 return false;
58         memset(new_buffer, 0, new_capacity);
59         memcpy(new_buffer, bb->buffer, sizeof(byte)*min(bb->bytes+(bb->bits?1:0), new_capacity));
60         if(new_capacity < bb->bytes+(bb->bits?1:0)) {
61                 bb->bytes = new_capacity;
62                 bb->bits = 0;
63                 bb->total_bits = (new_capacity<<3);
64         }
65         if(new_capacity < bb->consumed_bytes+(bb->consumed_bits?1:0)) {
66                 bb->consumed_bytes = new_capacity;
67                 bb->consumed_bits = 0;
68                 bb->total_consumed_bits = (new_capacity<<3);
69         }
70         bb->buffer = new_buffer;
71         bb->capacity = new_capacity;
72         return true;
73 }
74
75 static bool bitbuffer_grow_(FLAC__BitBuffer *bb, unsigned min_bytes_to_add)
76 {
77         unsigned new_capacity;
78
79         assert(min_bytes_to_add > 0);
80
81         new_capacity = max(bb->capacity * 4, bb->capacity + min_bytes_to_add);
82         return bitbuffer_resize_(bb, new_capacity);
83 }
84
85 static bool bitbuffer_ensure_size_(FLAC__BitBuffer *bb, unsigned bits_to_add)
86 {
87         assert(bb != 0);
88         assert(bb->buffer != 0);
89         if((bb->capacity<<3) < bb->total_bits + bits_to_add)
90                 return bitbuffer_grow_(bb, (bits_to_add>>3)+2);
91         else
92                 return true;
93 }
94
95 static bool bitbuffer_read_from_client_(FLAC__BitBuffer *bb, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
96 {
97         unsigned bytes;
98
99         /* first shift the unconsumed buffer data toward the front as much as possible */
100         if(bb->total_consumed_bits >= 8) {
101                 unsigned l = 0, r = bb->consumed_bytes, r_end = bb->bytes;
102                 for( ; r < r_end; l++, r++)
103                         bb->buffer[l] = bb->buffer[r];
104                 for( ; l < r_end; l++)
105                         bb->buffer[l] = 0;
106                 bb->bytes -= bb->consumed_bytes;
107                 bb->total_bits -= (bb->consumed_bytes<<3);
108                 bb->consumed_bytes = 0;
109                 bb->total_consumed_bits = bb->consumed_bits;
110         }
111         /* grow if we need to */
112         if(bb->capacity <= 1) {
113                 if(!bitbuffer_resize_(bb, 16))
114                         return false;
115         }
116         /* finally, read in some data; if OK, go back to read_bit_, else fail */
117         bytes = bb->capacity - bb->bytes;
118         if(!read_callback(bb->buffer+bb->bytes, &bytes, client_data))
119                 return false;
120         bb->bytes += bytes;
121         bb->total_bits += (bytes<<3);
122         return true;
123 }
124
125 void FLAC__bitbuffer_init(FLAC__BitBuffer *bb)
126 {
127         assert(bb != 0);
128         bb->buffer = 0;
129         bb->capacity = 0;
130         bb->bytes = bb->bits = bb->total_bits = 0;
131         bb->consumed_bytes = bb->consumed_bits = bb->total_consumed_bits = 0;
132 }
133
134 bool FLAC__bitbuffer_init_from(FLAC__BitBuffer *bb, const byte buffer[], unsigned bytes)
135 {
136         assert(bb != 0);
137         FLAC__bitbuffer_init(bb);
138         if(bytes == 0)
139                 return true;
140         else {
141                 assert(buffer != 0);
142                 bb->buffer = (byte*)malloc(sizeof(byte)*bytes);
143                 if(bb->buffer == 0)
144                         return false;
145                 memcpy(bb->buffer, buffer, sizeof(byte)*bytes);
146                 bb->capacity = bb->bytes = bytes;
147                 bb->bits = 0;
148                 bb->total_bits = (bytes<<3);
149                 bb->consumed_bytes = bb->consumed_bits = bb->total_consumed_bits = 0;
150                 return true;
151         }
152 }
153
154 bool FLAC__bitbuffer_concatenate_aligned(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
155 {
156         static byte mask_[9] = { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
157         unsigned bits_to_add = src->total_bits - src->total_consumed_bits;
158         assert(dest != 0);
159         assert(src != 0);
160
161         if(bits_to_add == 0)
162                 return true;
163         if(dest->bits != src->consumed_bits)
164                 return false;
165         if(!bitbuffer_ensure_size_(dest, bits_to_add))
166                 return false;
167         if(dest->bits == 0) {
168                 memcpy(dest->buffer+dest->bytes, src->buffer+src->consumed_bytes, src->bytes-src->consumed_bytes + ((src->bits)? 1:0));
169         }
170         else if(dest->bits + bits_to_add > 8) {
171                 dest->buffer[dest->bytes] <<= (8 - dest->bits);
172                 dest->buffer[dest->bytes] |= (src->buffer[src->consumed_bytes] & mask_[8-dest->bits]);
173                 memcpy(dest->buffer+dest->bytes+1, src->buffer+src->consumed_bytes+1, src->bytes-src->consumed_bytes-1 + ((src->bits)? 1:0));
174         }
175         else {
176                 dest->buffer[dest->bytes] <<= bits_to_add;
177                 dest->buffer[dest->bytes] |= (src->buffer[src->consumed_bytes] & mask_[bits_to_add]);
178         }
179         dest->bits = src->bits;
180         dest->total_bits += bits_to_add;
181         dest->bytes = dest->total_bits / 8;
182
183         return true;
184 }
185
186 void FLAC__bitbuffer_free(FLAC__BitBuffer *bb)
187 {
188         assert(bb != 0);
189         if(bb->buffer != 0)
190                 free(bb->buffer);
191         bb->buffer = 0;
192         bb->capacity = 0;
193         bb->bytes = bb->bits = bb->total_bits = 0;
194         bb->consumed_bytes = bb->consumed_bits = bb->total_consumed_bits = 0;
195 }
196
197 bool FLAC__bitbuffer_clear(FLAC__BitBuffer *bb)
198 {
199         if(bb->buffer == 0) {
200                 bb->capacity = FLAC__BITBUFFER_DEFAULT_CAPACITY;
201                 bb->buffer = (byte*)malloc(sizeof(byte) * bb->capacity);
202                 if(bb->buffer == 0)
203                         return false;
204                 memset(bb->buffer, 0, bb->capacity);
205         }
206         else {
207                 memset(bb->buffer, 0, bb->bytes + (bb->bits?1:0));
208         }
209         bb->bytes = bb->bits = bb->total_bits = 0;
210         bb->consumed_bytes = bb->consumed_bits = bb->total_consumed_bits = 0;
211         return true;
212 }
213
214 bool FLAC__bitbuffer_clone(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
215 {
216         if(dest->capacity < src->capacity)
217                 if(!bitbuffer_resize_(dest, src->capacity))
218                         return false;
219         memcpy(dest->buffer, src->buffer, sizeof(byte)*min(src->capacity, src->bytes+1));
220         dest->bytes = src->bytes;
221         dest->bits = src->bits;
222         dest->total_bits = src->total_bits;
223         dest->consumed_bytes = src->consumed_bytes;
224         dest->consumed_bits = src->consumed_bits;
225         dest->total_consumed_bits = src->total_consumed_bits;
226         return true;
227 }
228
229 bool FLAC__bitbuffer_write_zeroes(FLAC__BitBuffer *bb, unsigned bits)
230 {
231         unsigned n, k;
232
233         assert(bb != 0);
234         assert(bb->buffer != 0);
235
236         if(bits == 0)
237                 return true;
238         if(!bitbuffer_ensure_size_(bb, bits))
239                 return false;
240         bb->total_bits += bits;
241         while(bits > 0) {
242                 n = min(8 - bb->bits, bits);
243                 k = bits - n;
244                 bb->buffer[bb->bytes] <<= n;
245                 bits -= n;
246                 bb->bits += n;
247                 if(bb->bits == 8) {
248                         bb->bytes++;
249                         bb->bits = 0;
250                 }
251         }
252         return true;
253 }
254
255 bool FLAC__bitbuffer_write_raw_uint32(FLAC__BitBuffer *bb, uint32 val, unsigned bits)
256 {
257         static uint32 mask[] = {
258                 0,
259                 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
260                 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
261                 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
262                 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
263                 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
264                 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
265                 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
266                 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
267         };
268         unsigned n, k;
269
270         assert(bb != 0);
271         assert(bb->buffer != 0);
272
273         assert(bits <= 32);
274         if(bits == 0)
275                 return true;
276         if(!bitbuffer_ensure_size_(bb, bits))
277                 return false;
278         val &= mask[bits];
279         bb->total_bits += bits;
280         while(bits > 0) {
281                 n = 8 - bb->bits;
282                 if(n == 8) { /* i.e. bb->bits == 0 */
283                         if(bits < 8) {
284                                 bb->buffer[bb->bytes] = val;
285                                 bb->bits = bits;
286                                 break;
287                         }
288                         else if(bits == 8) {
289                                 bb->buffer[bb->bytes++] = val;
290                                 break;
291                         }
292                         else {
293                                 k = bits - 8;
294                                 bb->buffer[bb->bytes++] = val >> k;
295                                 val &= (~(0xffffffff << k));
296                                 bits -= 8;
297                         }
298                 }
299                 else if(bits <= n) {
300                         bb->buffer[bb->bytes] <<= bits;
301                         bb->buffer[bb->bytes] |= val;
302                         if(bits == n) {
303                                 bb->bytes++;
304                                 bb->bits = 0;
305                         }
306                         else
307                                 bb->bits += bits;
308                         break;
309                 }
310                 else {
311                         k = bits - n;
312                         bb->buffer[bb->bytes] <<= n;
313                         bb->buffer[bb->bytes] |= (val>>k);
314                         val &= (~(0xffffffff << k));
315                         bits -= n;
316                         bb->bytes++;
317                         bb->bits = 0;
318                 }
319         }
320
321         return true;
322 }
323
324 bool FLAC__bitbuffer_write_raw_int32(FLAC__BitBuffer *bb, int32 val, unsigned bits)
325 {
326         return FLAC__bitbuffer_write_raw_uint32(bb, (uint32)val, bits);
327 }
328
329 bool FLAC__bitbuffer_write_raw_uint64(FLAC__BitBuffer *bb, uint64 val, unsigned bits)
330 {
331         static uint64 mask[] = {
332                 0,
333                 0x0000000000000001, 0x0000000000000003, 0x0000000000000007, 0x000000000000000F,
334                 0x000000000000001F, 0x000000000000003F, 0x000000000000007F, 0x00000000000000FF,
335                 0x00000000000001FF, 0x00000000000003FF, 0x00000000000007FF, 0x0000000000000FFF,
336                 0x0000000000001FFF, 0x0000000000003FFF, 0x0000000000007FFF, 0x000000000000FFFF,
337                 0x000000000001FFFF, 0x000000000003FFFF, 0x000000000007FFFF, 0x00000000000FFFFF,
338                 0x00000000001FFFFF, 0x00000000003FFFFF, 0x00000000007FFFFF, 0x0000000000FFFFFF,
339                 0x0000000001FFFFFF, 0x0000000003FFFFFF, 0x0000000007FFFFFF, 0x000000000FFFFFFF,
340                 0x000000001FFFFFFF, 0x000000003FFFFFFF, 0x000000007FFFFFFF, 0x00000000FFFFFFFF,
341                 0x00000001FFFFFFFF, 0x00000003FFFFFFFF, 0x00000007FFFFFFFF, 0x0000000FFFFFFFFF,
342                 0x0000001FFFFFFFFF, 0x0000003FFFFFFFFF, 0x0000007FFFFFFFFF, 0x000000FFFFFFFFFF,
343                 0x000001FFFFFFFFFF, 0x000003FFFFFFFFFF, 0x000007FFFFFFFFFF, 0x00000FFFFFFFFFFF,
344                 0x00001FFFFFFFFFFF, 0x00003FFFFFFFFFFF, 0x00007FFFFFFFFFFF, 0x0000FFFFFFFFFFFF,
345                 0x0001FFFFFFFFFFFF, 0x0003FFFFFFFFFFFF, 0x0007FFFFFFFFFFFF, 0x000FFFFFFFFFFFFF,
346                 0x001FFFFFFFFFFFFF, 0x003FFFFFFFFFFFFF, 0x007FFFFFFFFFFFFF, 0x00FFFFFFFFFFFFFF,
347                 0x01FFFFFFFFFFFFFF, 0x03FFFFFFFFFFFFFF, 0x07FFFFFFFFFFFFFF, 0x0FFFFFFFFFFFFFFF,
348                 0x1FFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF
349         };
350         unsigned n, k;
351
352         assert(bb != 0);
353         assert(bb->buffer != 0);
354
355         assert(bits <= 64);
356         if(bits == 0)
357                 return true;
358         if(!bitbuffer_ensure_size_(bb, bits))
359                 return false;
360         val &= mask[bits];
361         bb->total_bits += bits;
362         while(bits > 0) {
363                 if(bb->bits == 0) {
364                         if(bits < 8) {
365                                 bb->buffer[bb->bytes] = val;
366                                 bb->bits = bits;
367                                 break;
368                         }
369                         else if(bits == 8) {
370                                 bb->buffer[bb->bytes++] = val;
371                                 break;
372                         }
373                         else {
374                                 k = bits - 8;
375                                 bb->buffer[bb->bytes++] = val >> k;
376                                 val &= (~(0xffffffffffffffff << k));
377                                 bits -= 8;
378                         }
379                 }
380                 else {
381                         n = min(8 - bb->bits, bits);
382                         k = bits - n;
383                         bb->buffer[bb->bytes] <<= n;
384                         bb->buffer[bb->bytes] |= (val>>k);
385                         val &= (~(0xffffffffffffffff << k));
386                         bits -= n;
387                         bb->bits += n;
388                         if(bb->bits == 8) {
389                                 bb->bytes++;
390                                 bb->bits = 0;
391                         }
392                 }
393         }
394
395         return true;
396 }
397
398 bool FLAC__bitbuffer_write_raw_int64(FLAC__BitBuffer *bb, int64 val, unsigned bits)
399 {
400         return FLAC__bitbuffer_write_raw_uint64(bb, (uint64)val, bits);
401 }
402
403 unsigned FLAC__bitbuffer_rice_bits(int val, unsigned parameter)
404 {
405         unsigned msbs, uval;
406
407         /* convert signed to unsigned */
408         if(val < 0)
409                 /* equivalent to
410                  *     (unsigned)(((--val) << 1) - 1);
411                  * but without the overflow problem at -MAXINT
412                  */
413                 uval = (unsigned)(((-(++val)) << 1) + 1);
414         else
415                 uval = (unsigned)(val << 1);
416
417         msbs = uval >> parameter;
418
419         return 1 + parameter + msbs;
420 }
421
422 unsigned FLAC__bitbuffer_golomb_bits_signed(int val, unsigned parameter)
423 {
424         unsigned bits, msbs, uval;
425         unsigned k;
426
427         assert(parameter > 0);
428
429         /* convert signed to unsigned */
430         if(val < 0)
431                 /* equivalent to
432                  *     (unsigned)(((--val) << 1) - 1);
433                  * but without the overflow problem at -MAXINT
434                  */
435                 uval = (unsigned)(((-(++val)) << 1) + 1);
436         else
437                 uval = (unsigned)(val << 1);
438
439         k = ilog2_(parameter);
440         if(parameter == 1u<<k) {
441                 assert(k <= 30);
442
443                 msbs = uval >> k;
444                 bits = 1 + k + msbs;
445         }
446         else {
447                 unsigned q, r, d;
448
449                 d = (1 << (k+1)) - parameter;
450                 q = uval / parameter;
451                 r = uval - (q * parameter);
452
453                 bits = 1 + q + k;
454                 if(r >= d)
455                         bits++;
456         }
457         return bits;
458 }
459
460 unsigned FLAC__bitbuffer_golomb_bits_unsigned(unsigned uval, unsigned parameter)
461 {
462         unsigned bits, msbs;
463         unsigned k;
464
465         assert(parameter > 0);
466
467         k = ilog2_(parameter);
468         if(parameter == 1u<<k) {
469                 assert(k <= 30);
470
471                 msbs = uval >> k;
472                 bits = 1 + k + msbs;
473         }
474         else {
475                 unsigned q, r, d;
476
477                 d = (1 << (k+1)) - parameter;
478                 q = uval / parameter;
479                 r = uval - (q * parameter);
480
481                 bits = 1 + q + k;
482                 if(r >= d)
483                         bits++;
484         }
485         return bits;
486 }
487
488 bool FLAC__bitbuffer_write_symmetric_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
489 {
490         unsigned total_bits, interesting_bits, msbs;
491         uint32 pattern;
492
493         assert(bb != 0);
494         assert(bb->buffer != 0);
495         assert(parameter <= 31);
496
497         /* init pattern with the unary end bit and the sign bit */
498         if(val < 0) {
499                 pattern = 3;
500                 val = -val;
501         }
502         else
503                 pattern = 2;
504
505         msbs = val >> parameter;
506         interesting_bits = 2 + parameter;
507         total_bits = interesting_bits + msbs;
508         pattern <<= parameter;
509         pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */
510
511         if(total_bits <= 32) {
512                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
513                         return false;
514         }
515         else {
516                 /* write the unary MSBs */
517                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
518                         return false;
519                 /* write the unary end bit, the sign bit, and binary LSBs */
520                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
521                         return false;
522         }
523         return true;
524 }
525
526 bool FLAC__bitbuffer_write_symmetric_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, bool *overflow)
527 {
528         unsigned total_bits, interesting_bits, msbs;
529         uint32 pattern;
530
531         assert(bb != 0);
532         assert(bb->buffer != 0);
533         assert(parameter <= 31);
534
535         *overflow = false;
536
537         /* init pattern with the unary end bit and the sign bit */
538         if(val < 0) {
539                 pattern = 3;
540                 val = -val;
541         }
542         else
543                 pattern = 2;
544
545         msbs = val >> parameter;
546         interesting_bits = 2 + parameter;
547         total_bits = interesting_bits + msbs;
548         pattern <<= parameter;
549         pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */
550
551         if(total_bits <= 32) {
552                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
553                         return false;
554         }
555         else if(total_bits > max_bits) {
556                 *overflow = true;
557                 return true;
558         }
559         else {
560                 /* write the unary MSBs */
561                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
562                         return false;
563                 /* write the unary end bit, the sign bit, and binary LSBs */
564                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
565                         return false;
566         }
567         return true;
568 }
569
570 bool FLAC__bitbuffer_write_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
571 {
572         unsigned total_bits, interesting_bits, msbs, uval;
573         uint32 pattern;
574
575         assert(bb != 0);
576         assert(bb->buffer != 0);
577         assert(parameter <= 30);
578
579         /* convert signed to unsigned */
580         if(val < 0)
581                 /* equivalent to
582                  *     (unsigned)(((--val) << 1) - 1);
583                  * but without the overflow problem at -MAXINT
584                  */
585                 uval = (unsigned)(((-(++val)) << 1) + 1);
586         else
587                 uval = (unsigned)(val << 1);
588
589         msbs = uval >> parameter;
590         interesting_bits = 1 + parameter;
591         total_bits = interesting_bits + msbs;
592         pattern = 1 << parameter; /* the unary end bit */
593         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
594
595         if(total_bits <= 32) {
596                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
597                         return false;
598         }
599         else {
600                 /* write the unary MSBs */
601                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
602                         return false;
603                 /* write the unary end bit and binary LSBs */
604                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
605                         return false;
606         }
607         return true;
608 }
609
610 bool FLAC__bitbuffer_write_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, bool *overflow)
611 {
612         unsigned total_bits, interesting_bits, msbs, uval;
613         uint32 pattern;
614
615         assert(bb != 0);
616         assert(bb->buffer != 0);
617         assert(parameter <= 30);
618
619         *overflow = false;
620
621         /* convert signed to unsigned */
622         if(val < 0)
623                 /* equivalent to
624                  *     (unsigned)(((--val) << 1) - 1);
625                  * but without the overflow problem at -MAXINT
626                  */
627                 uval = (unsigned)(((-(++val)) << 1) + 1);
628         else
629                 uval = (unsigned)(val << 1);
630
631         msbs = uval >> parameter;
632         interesting_bits = 1 + parameter;
633         total_bits = interesting_bits + msbs;
634         pattern = 1 << parameter; /* the unary end bit */
635         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
636
637         if(total_bits <= 32) {
638                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
639                         return false;
640         }
641         else if(total_bits > max_bits) {
642                 *overflow = true;
643                 return true;
644         }
645         else {
646                 /* write the unary MSBs */
647                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
648                         return false;
649                 /* write the unary end bit and binary LSBs */
650                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
651                         return false;
652         }
653         return true;
654 }
655
656 bool FLAC__bitbuffer_write_golomb_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
657 {
658         unsigned total_bits, msbs, uval;
659         unsigned k;
660
661         assert(bb != 0);
662         assert(bb->buffer != 0);
663         assert(parameter > 0);
664
665         /* convert signed to unsigned */
666         if(val < 0)
667                 /* equivalent to
668                  *     (unsigned)(((--val) << 1) - 1);
669                  * but without the overflow problem at -MAXINT
670                  */
671                 uval = (unsigned)(((-(++val)) << 1) + 1);
672         else
673                 uval = (unsigned)(val << 1);
674
675         k = ilog2_(parameter);
676         if(parameter == 1u<<k) {
677                 unsigned pattern;
678
679                 assert(k <= 30);
680
681                 msbs = uval >> k;
682                 total_bits = 1 + k + msbs;
683                 pattern = 1 << k; /* the unary end bit */
684                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
685
686                 if(total_bits <= 32) {
687                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
688                                 return false;
689                 }
690                 else {
691                         /* write the unary MSBs */
692                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
693                                 return false;
694                         /* write the unary end bit and binary LSBs */
695                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
696                                 return false;
697                 }
698         }
699         else {
700                 unsigned q, r, d;
701
702                 d = (1 << (k+1)) - parameter;
703                 q = uval / parameter;
704                 r = uval - (q * parameter);
705                 /* write the unary MSBs */
706                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
707                         return false;
708                 /* write the unary end bit */
709                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
710                         return false;
711                 /* write the binary LSBs */
712                 if(r >= d) {
713                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
714                                 return false;
715                 }
716                 else {
717                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
718                                 return false;
719                 }
720         }
721         return true;
722 }
723
724 bool FLAC__bitbuffer_write_golomb_unsigned(FLAC__BitBuffer *bb, unsigned uval, unsigned parameter)
725 {
726         unsigned total_bits, msbs;
727         unsigned k;
728
729         assert(bb != 0);
730         assert(bb->buffer != 0);
731         assert(parameter > 0);
732
733         k = ilog2_(parameter);
734         if(parameter == 1u<<k) {
735                 unsigned pattern;
736
737                 assert(k <= 30);
738
739                 msbs = uval >> k;
740                 total_bits = 1 + k + msbs;
741                 pattern = 1 << k; /* the unary end bit */
742                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
743
744                 if(total_bits <= 32) {
745                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
746                                 return false;
747                 }
748                 else {
749                         /* write the unary MSBs */
750                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
751                                 return false;
752                         /* write the unary end bit and binary LSBs */
753                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
754                                 return false;
755                 }
756         }
757         else {
758                 unsigned q, r, d;
759
760                 d = (1 << (k+1)) - parameter;
761                 q = uval / parameter;
762                 r = uval - (q * parameter);
763                 /* write the unary MSBs */
764                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
765                         return false;
766                 /* write the unary end bit */
767                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
768                         return false;
769                 /* write the binary LSBs */
770                 if(r >= d) {
771                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
772                                 return false;
773                 }
774                 else {
775                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
776                                 return false;
777                 }
778         }
779         return true;
780 }
781
782 bool FLAC__bitbuffer_write_utf8_uint32(FLAC__BitBuffer *bb, uint32 val)
783 {
784         bool ok = 1;
785
786         assert(bb != 0);
787         assert(bb->buffer != 0);
788
789         assert(!(val & 0x80000000)); /* this version only handles 31 bits */
790
791         if(val < 0x80) {
792                 return FLAC__bitbuffer_write_raw_uint32(bb, val, 8);
793         }
794         else if(val < 0x800) {
795                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (val>>6), 8);
796                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
797         }
798         else if(val < 0x10000) {
799                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (val>>12), 8);
800                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
801                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
802         }
803         else if(val < 0x200000) {
804                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (val>>18), 8);
805                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
806                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
807                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
808         }
809         else if(val < 0x4000000) {
810                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (val>>24), 8);
811                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
812                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
813                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
814                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
815         }
816         else {
817                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (val>>30), 8);
818                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>24)&0x3F), 8);
819                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
820                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
821                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
822                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
823         }
824
825         return ok;
826 }
827
828 bool FLAC__bitbuffer_write_utf8_uint64(FLAC__BitBuffer *bb, uint64 val)
829 {
830         bool ok = 1;
831
832         assert(bb != 0);
833         assert(bb->buffer != 0);
834
835         assert(!(val & 0xFFFFFFF000000000)); /* this version only handles 36 bits */
836
837         if(val < 0x80) {
838                 return FLAC__bitbuffer_write_raw_uint32(bb, (uint32)val, 8);
839         }
840         else if(val < 0x800) {
841                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (uint32)(val>>6), 8);
842                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
843         }
844         else if(val < 0x10000) {
845                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (uint32)(val>>12), 8);
846                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
847                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
848         }
849         else if(val < 0x200000) {
850                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (uint32)(val>>18), 8);
851                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
852                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
853                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
854         }
855         else if(val < 0x4000000) {
856                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (uint32)(val>>24), 8);
857                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
858                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
859                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
860                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
861         }
862         else if(val < 0x80000000) {
863                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (uint32)(val>>30), 8);
864                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>24)&0x3F), 8);
865                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
866                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
867                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
868                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
869         }
870         else {
871                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFE, 8);
872                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>30)&0x3F), 8);
873                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>24)&0x3F), 8);
874                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
875                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
876                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
877                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
878         }
879
880         return ok;
881 }
882
883 bool FLAC__bitbuffer_zero_pad_to_byte_boundary(FLAC__BitBuffer *bb)
884 {
885         /* 0-pad to byte boundary */
886         if(bb->bits != 0)
887                 return FLAC__bitbuffer_write_zeroes(bb, 8 - bb->bits);
888         else
889                 return true;
890 }
891
892 bool FLAC__bitbuffer_peek_bit(FLAC__BitBuffer *bb, unsigned *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
893 {
894         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
895
896         /* to avoid a drastic speed penalty we don't:
897         assert(bb != 0);
898         assert(bb->buffer != 0);
899         assert(bb->bits == 0);
900         */
901
902 read_bit_:
903         if(bb->total_consumed_bits < bb->total_bits) {
904                 *val = (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
905                 return true;
906         }
907         else {
908                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
909                         return false;
910                 goto read_bit_;
911         }
912 }
913
914 bool FLAC__bitbuffer_read_bit(FLAC__BitBuffer *bb, unsigned *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
915 {
916         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
917
918         /* to avoid a drastic speed penalty we don't:
919         assert(bb != 0);
920         assert(bb->buffer != 0);
921         assert(bb->bits == 0);
922         */
923
924 read_bit_:
925         if(bb->total_consumed_bits < bb->total_bits) {
926                 *val = (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
927                 bb->consumed_bits++;
928                 if(bb->consumed_bits == 8) {
929                         bb->consumed_bytes++;
930                         bb->consumed_bits = 0;
931                 }
932                 bb->total_consumed_bits++;
933                 return true;
934         }
935         else {
936                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
937                         return false;
938                 goto read_bit_;
939         }
940 }
941
942 bool FLAC__bitbuffer_read_bit_to_uint32(FLAC__BitBuffer *bb, uint32 *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
943 {
944         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
945
946         /* to avoid a drastic speed penalty we don't:
947         assert(bb != 0);
948         assert(bb->buffer != 0);
949         assert(bb->bits == 0);
950         */
951
952 read_bit_:
953         if(bb->total_consumed_bits < bb->total_bits) {
954                 *val <<= 1;
955                 *val |= (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
956                 bb->consumed_bits++;
957                 if(bb->consumed_bits == 8) {
958                         bb->consumed_bytes++;
959                         bb->consumed_bits = 0;
960                 }
961                 bb->total_consumed_bits++;
962                 return true;
963         }
964         else {
965                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
966                         return false;
967                 goto read_bit_;
968         }
969 }
970
971 bool FLAC__bitbuffer_read_bit_to_uint64(FLAC__BitBuffer *bb, uint64 *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
972 {
973         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
974
975         /* to avoid a drastic speed penalty we don't:
976         assert(bb != 0);
977         assert(bb->buffer != 0);
978         assert(bb->bits == 0);
979         */
980
981 read_bit_:
982         if(bb->total_consumed_bits < bb->total_bits) {
983                 *val <<= 1;
984                 *val |= (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
985                 bb->consumed_bits++;
986                 if(bb->consumed_bits == 8) {
987                         bb->consumed_bytes++;
988                         bb->consumed_bits = 0;
989                 }
990                 bb->total_consumed_bits++;
991                 return true;
992         }
993         else {
994                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
995                         return false;
996                 goto read_bit_;
997         }
998 }
999
1000 bool FLAC__bitbuffer_read_raw_uint32(FLAC__BitBuffer *bb, uint32 *val, unsigned bits, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1001 {
1002         unsigned i;
1003
1004         assert(bb != 0);
1005         assert(bb->buffer != 0);
1006
1007         assert(bits <= 32);
1008
1009         *val = 0;
1010         for(i = 0; i < bits; i++) {
1011                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, val, read_callback, client_data))
1012                         return false;
1013         }
1014         return true;
1015 }
1016
1017 bool FLAC__bitbuffer_read_raw_int32(FLAC__BitBuffer *bb, int32 *val, unsigned bits, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1018 {
1019         unsigned i;
1020         uint32 x;
1021
1022         assert(bb != 0);
1023         assert(bb->buffer != 0);
1024
1025         assert(bits <= 32);
1026
1027         x = 0;
1028         for(i = 0; i < bits; i++) {
1029                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &x, read_callback, client_data))
1030                         return false;
1031         }
1032         /* fix the sign */
1033         i = 32 - bits;
1034         if(i) {
1035                 x <<= i;
1036                 *val = (int32)x;
1037                 *val >>= i;
1038         }
1039         else
1040                 *val = (int32)x;
1041
1042         return true;
1043 }
1044
1045 bool FLAC__bitbuffer_read_raw_uint64(FLAC__BitBuffer *bb, uint64 *val, unsigned bits, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1046 {
1047         unsigned i;
1048
1049         assert(bb != 0);
1050         assert(bb->buffer != 0);
1051
1052         assert(bits <= 64);
1053
1054         *val = 0;
1055         for(i = 0; i < bits; i++) {
1056                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, val, read_callback, client_data))
1057                         return false;
1058         }
1059         return true;
1060 }
1061
1062 bool FLAC__bitbuffer_read_raw_int64(FLAC__BitBuffer *bb, int64 *val, unsigned bits, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1063 {
1064         unsigned i;
1065         uint64 x;
1066
1067         assert(bb != 0);
1068         assert(bb->buffer != 0);
1069
1070         assert(bits <= 64);
1071
1072         x = 0;
1073         for(i = 0; i < bits; i++) {
1074                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, &x, read_callback, client_data))
1075                         return false;
1076         }
1077         /* fix the sign */
1078         i = 64 - bits;
1079         if(i) {
1080                 x <<= i;
1081                 *val = (int64)x;
1082                 *val >>= i;
1083         }
1084         else
1085                 *val = (int64)x;
1086
1087         return true;
1088 }
1089
1090 bool FLAC__bitbuffer_read_symmetric_rice_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1091 {
1092         uint32 sign = 0, lsbs = 0, msbs = 0;
1093         unsigned bit;
1094
1095         assert(bb != 0);
1096         assert(bb->buffer != 0);
1097         assert(parameter <= 31);
1098
1099         /* read the unary MSBs and end bit */
1100         while(1) {
1101                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1102                         return false;
1103                 if(bit)
1104                         break;
1105                 else
1106                         msbs++;
1107         }
1108         /* read the sign bit */
1109         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &sign, read_callback, client_data))
1110                 return false;
1111         /* read the binary LSBs */
1112         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1113                 return false;
1114
1115         /* compose the value */
1116         *val = (msbs << parameter) | lsbs;
1117         if(sign)
1118                 *val = -(*val);
1119
1120         return true;
1121 }
1122
1123 bool FLAC__bitbuffer_read_rice_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1124 {
1125         uint32 lsbs = 0, msbs = 0;
1126         unsigned bit, uval;
1127
1128         assert(bb != 0);
1129         assert(bb->buffer != 0);
1130         assert(parameter <= 31);
1131
1132         /* read the unary MSBs and end bit */
1133         while(1) {
1134                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1135                         return false;
1136                 if(bit)
1137                         break;
1138                 else
1139                         msbs++;
1140         }
1141         /* read the binary LSBs */
1142         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1143                 return false;
1144         /* compose the value */
1145         uval = (msbs << parameter) | lsbs;
1146         if(uval & 1)
1147                 *val = -((int)(uval >> 1)) - 1;
1148         else
1149                 *val = (int)(uval >> 1);
1150
1151         return true;
1152 }
1153
1154 bool FLAC__bitbuffer_read_golomb_signed(FLAC__BitBuffer *bb, int *val, unsigned parameter, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1155 {
1156         uint32 lsbs = 0, msbs = 0;
1157         unsigned bit, uval, k;
1158
1159         assert(bb != 0);
1160         assert(bb->buffer != 0);
1161
1162         k = ilog2_(parameter);
1163
1164         /* read the unary MSBs and end bit */
1165         while(1) {
1166                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1167                         return false;
1168                 if(bit)
1169                         break;
1170                 else
1171                         msbs++;
1172         }
1173         /* read the binary LSBs */
1174         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1175                 return false;
1176
1177         if(parameter == 1u<<k) {
1178                 /* compose the value */
1179                 uval = (msbs << k) | lsbs;
1180         }
1181         else {
1182                 unsigned d = (1 << (k+1)) - parameter;
1183                 if(lsbs >= d) {
1184                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1185                                 return false;
1186                         lsbs <<= 1;
1187                         lsbs |= bit;
1188                         lsbs -= d;
1189                 }
1190                 /* compose the value */
1191                 uval = msbs * parameter + lsbs;
1192         }
1193
1194         /* unfold unsigned to signed */
1195         if(uval & 1)
1196                 *val = -((int)(uval >> 1)) - 1;
1197         else
1198                 *val = (int)(uval >> 1);
1199
1200         return true;
1201 }
1202
1203 bool FLAC__bitbuffer_read_golomb_unsigned(FLAC__BitBuffer *bb, unsigned *val, unsigned parameter, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1204 {
1205         uint32 lsbs, msbs = 0;
1206         unsigned bit, k;
1207
1208         assert(bb != 0);
1209         assert(bb->buffer != 0);
1210
1211         k = ilog2_(parameter);
1212
1213         /* read the unary MSBs and end bit */
1214         while(1) {
1215                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1216                         return false;
1217                 if(bit)
1218                         break;
1219                 else
1220                         msbs++;
1221         }
1222         /* read the binary LSBs */
1223         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1224                 return false;
1225
1226         if(parameter == 1u<<k) {
1227                 /* compose the value */
1228                 *val = (msbs << k) | lsbs;
1229         }
1230         else {
1231                 unsigned d = (1 << (k+1)) - parameter;
1232                 if(lsbs >= d) {
1233                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1234                                 return false;
1235                         lsbs <<= 1;
1236                         lsbs |= bit;
1237                         lsbs -= d;
1238                 }
1239                 /* compose the value */
1240                 *val = msbs * parameter + lsbs;
1241         }
1242
1243         return true;
1244 }
1245
1246 /* on return, if *val == 0xffffffff then the utf-8 sequence was invalid, but the return value will be true */
1247 bool FLAC__bitbuffer_read_utf8_uint32(FLAC__BitBuffer *bb, uint32 *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data, byte *raw, unsigned *rawlen)
1248 {
1249         uint32 v = 0;
1250         uint32 x;
1251         unsigned i;
1252
1253         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1254                 return false;
1255         if(raw)
1256                 raw[(*rawlen)++] = (byte)x;
1257         if(!(x & 0x80)) { /* 0xxxxxxx */
1258                 v = x;
1259                 i = 0;
1260         }
1261         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1262                 v = x & 0x1F;
1263                 i = 1;
1264         }
1265         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1266                 v = x & 0x0F;
1267                 i = 2;
1268         }
1269         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1270                 v = x & 0x07;
1271                 i = 3;
1272         }
1273         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1274                 v = x & 0x03;
1275                 i = 4;
1276         }
1277         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1278                 v = x & 0x01;
1279                 i = 5;
1280         }
1281         else
1282                 goto invalid_;
1283         for( ; i; i--) {
1284                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1285                         return false;
1286                 if(raw)
1287                         raw[(*rawlen)++] = (byte)x;
1288                 if(!(x & 0x80) || (x & 0x40)) /* 10xxxxxx */
1289                         goto invalid_;
1290                 v <<= 6;
1291                 v |= (x & 0x3F);
1292         }
1293         *val = v;
1294         return true;
1295 invalid_:
1296         *val = 0xffffffff;
1297         return true;
1298 }
1299
1300 /* on return, if *val == 0xffffffffffffffff then the utf-8 sequence was invalid, but the return value will be true */
1301 bool FLAC__bitbuffer_read_utf8_uint64(FLAC__BitBuffer *bb, uint64 *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data, byte *raw, unsigned *rawlen)
1302 {
1303         uint64 v = 0;
1304         uint32 x;
1305         unsigned i;
1306
1307         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1308                 return false;
1309         if(raw)
1310                 raw[(*rawlen)++] = (byte)x;
1311         if(!(x & 0x80)) { /* 0xxxxxxx */
1312                 v = x;
1313                 i = 0;
1314         }
1315         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1316                 v = x & 0x1F;
1317                 i = 1;
1318         }
1319         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1320                 v = x & 0x0F;
1321                 i = 2;
1322         }
1323         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1324                 v = x & 0x07;
1325                 i = 3;
1326         }
1327         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1328                 v = x & 0x03;
1329                 i = 4;
1330         }
1331         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1332                 v = x & 0x01;
1333                 i = 5;
1334         }
1335         else if(x & 0xFE && !(x & 0x01)) { /* 11111110 */
1336                 v = 0;
1337                 i = 6;
1338         }
1339         else
1340                 goto invalid_;
1341         for( ; i; i--) {
1342                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1343                         return false;
1344                 if(raw)
1345                         raw[(*rawlen)++] = (byte)x;
1346                 if(!(x & 0x80) || (x & 0x40)) /* 10xxxxxx */
1347                         goto invalid_;
1348                 v <<= 6;
1349                 v |= (x & 0x3F);
1350         }
1351         *val = v;
1352         return true;
1353 invalid_:
1354         *val = 0xffffffff;
1355         return true;
1356 }
1357
1358 void FLAC__bitbuffer_dump(const FLAC__BitBuffer *bb, FILE *out)
1359 {
1360         unsigned i, j;
1361         if(bb == 0) {
1362                 fprintf(out, "bitbuffer is NULL\n");
1363         }
1364         else {
1365                 fprintf(out, "bitbuffer: capacity=%u bytes=%u bits=%u total_bits=%u consumed: bytes=%u, bits=%u, total_bits=%u\n", bb->capacity, bb->bytes, bb->bits, bb->total_bits, bb->consumed_bytes, bb->consumed_bits, bb->total_consumed_bits);
1366                 for(i = 0; i < bb->bytes; i++) {
1367                         fprintf(out, "%08X: ", i);
1368                         for(j = 0; j < 8; j++)
1369                                 if(i*8+j < bb->total_consumed_bits)
1370                                         fprintf(out, ".");
1371                                 else
1372                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (8-j-1)) ? 1:0);
1373                         fprintf(out, "\n");
1374                 }
1375                 if(bb->bits > 0) {
1376                         fprintf(out, "%08X: ", i);
1377                         for(j = 0; j < bb->bits; j++)
1378                                 if(i*8+j < bb->total_consumed_bits)
1379                                         fprintf(out, ".");
1380                                 else
1381                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (bb->bits-j-1)) ? 1:0);
1382                         fprintf(out, "\n");
1383                 }
1384         }
1385 }