temporary commit
[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 static unsigned silog21_(int v)
571 {
572 doit_:
573         if(v == 0) {
574                 return 0;
575         }
576         else if(v > 0) {
577                 unsigned l = 0;
578                 while(v) {
579                         l++;
580                         v >>= 1;
581                 }
582                 return l+1;
583         }
584         else if(v == -1) {
585                 return 2;
586         }
587         else {
588                 v = -(++v);
589                 goto doit_;
590         }
591 }
592
593 bool FLAC__bitbuffer_write_symmetric_rice_signed_escape(FLAC__BitBuffer *bb, int val, unsigned parameter)
594 {
595         unsigned total_bits, val_bits;
596         uint32 pattern;
597 unsigned x;
598
599         assert(bb != 0);
600         assert(bb->buffer != 0);
601         assert(parameter <= 31);
602
603         val_bits = silog21_(val);
604         total_bits = 2 + parameter + 5 + val_bits;
605
606 x=bb->total_bits;
607         if(total_bits <= 32) {
608                 pattern = 3;
609                 pattern <<= (parameter + 5);
610                 pattern |= val_bits;
611                 pattern <<= val_bits;
612                 pattern |= (val & ((1 << val_bits) - 1));
613                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
614                         return false;
615         }
616         else {
617                 /* write the '-0' escape code first */
618                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 3u << parameter, 2+parameter))
619                         return false;
620                 /* write the length */
621                 if(!FLAC__bitbuffer_write_raw_uint32(bb, val_bits, 5))
622                         return false;
623                 /* write the value */
624                 if(!FLAC__bitbuffer_write_raw_int32(bb, val, val_bits))
625                         return false;
626         }
627 fprintf(stderr,"wrote %u bits\n",bb->total_bits-x);
628         return true;
629 }
630
631 bool FLAC__bitbuffer_write_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
632 {
633         unsigned total_bits, interesting_bits, msbs, uval;
634         uint32 pattern;
635
636         assert(bb != 0);
637         assert(bb->buffer != 0);
638         assert(parameter <= 30);
639
640         /* convert signed to unsigned */
641         if(val < 0)
642                 /* equivalent to
643                  *     (unsigned)(((--val) << 1) - 1);
644                  * but without the overflow problem at -MAXINT
645                  */
646                 uval = (unsigned)(((-(++val)) << 1) + 1);
647         else
648                 uval = (unsigned)(val << 1);
649
650         msbs = uval >> parameter;
651         interesting_bits = 1 + parameter;
652         total_bits = interesting_bits + msbs;
653         pattern = 1 << parameter; /* the unary end bit */
654         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
655
656         if(total_bits <= 32) {
657                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
658                         return false;
659         }
660         else {
661                 /* write the unary MSBs */
662                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
663                         return false;
664                 /* write the unary end bit and binary LSBs */
665                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
666                         return false;
667         }
668         return true;
669 }
670
671 bool FLAC__bitbuffer_write_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, bool *overflow)
672 {
673         unsigned total_bits, interesting_bits, msbs, uval;
674         uint32 pattern;
675
676         assert(bb != 0);
677         assert(bb->buffer != 0);
678         assert(parameter <= 30);
679
680         *overflow = false;
681
682         /* convert signed to unsigned */
683         if(val < 0)
684                 /* equivalent to
685                  *     (unsigned)(((--val) << 1) - 1);
686                  * but without the overflow problem at -MAXINT
687                  */
688                 uval = (unsigned)(((-(++val)) << 1) + 1);
689         else
690                 uval = (unsigned)(val << 1);
691
692         msbs = uval >> parameter;
693         interesting_bits = 1 + parameter;
694         total_bits = interesting_bits + msbs;
695         pattern = 1 << parameter; /* the unary end bit */
696         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
697
698         if(total_bits <= 32) {
699                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
700                         return false;
701         }
702         else if(total_bits > max_bits) {
703                 *overflow = true;
704                 return true;
705         }
706         else {
707                 /* write the unary MSBs */
708                 if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
709                         return false;
710                 /* write the unary end bit and binary LSBs */
711                 if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
712                         return false;
713         }
714         return true;
715 }
716
717 bool FLAC__bitbuffer_write_golomb_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
718 {
719         unsigned total_bits, msbs, uval;
720         unsigned k;
721
722         assert(bb != 0);
723         assert(bb->buffer != 0);
724         assert(parameter > 0);
725
726         /* convert signed to unsigned */
727         if(val < 0)
728                 /* equivalent to
729                  *     (unsigned)(((--val) << 1) - 1);
730                  * but without the overflow problem at -MAXINT
731                  */
732                 uval = (unsigned)(((-(++val)) << 1) + 1);
733         else
734                 uval = (unsigned)(val << 1);
735
736         k = ilog2_(parameter);
737         if(parameter == 1u<<k) {
738                 unsigned pattern;
739
740                 assert(k <= 30);
741
742                 msbs = uval >> k;
743                 total_bits = 1 + k + msbs;
744                 pattern = 1 << k; /* the unary end bit */
745                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
746
747                 if(total_bits <= 32) {
748                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
749                                 return false;
750                 }
751                 else {
752                         /* write the unary MSBs */
753                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
754                                 return false;
755                         /* write the unary end bit and binary LSBs */
756                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
757                                 return false;
758                 }
759         }
760         else {
761                 unsigned q, r, d;
762
763                 d = (1 << (k+1)) - parameter;
764                 q = uval / parameter;
765                 r = uval - (q * parameter);
766                 /* write the unary MSBs */
767                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
768                         return false;
769                 /* write the unary end bit */
770                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
771                         return false;
772                 /* write the binary LSBs */
773                 if(r >= d) {
774                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
775                                 return false;
776                 }
777                 else {
778                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
779                                 return false;
780                 }
781         }
782         return true;
783 }
784
785 bool FLAC__bitbuffer_write_golomb_unsigned(FLAC__BitBuffer *bb, unsigned uval, unsigned parameter)
786 {
787         unsigned total_bits, msbs;
788         unsigned k;
789
790         assert(bb != 0);
791         assert(bb->buffer != 0);
792         assert(parameter > 0);
793
794         k = ilog2_(parameter);
795         if(parameter == 1u<<k) {
796                 unsigned pattern;
797
798                 assert(k <= 30);
799
800                 msbs = uval >> k;
801                 total_bits = 1 + k + msbs;
802                 pattern = 1 << k; /* the unary end bit */
803                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
804
805                 if(total_bits <= 32) {
806                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
807                                 return false;
808                 }
809                 else {
810                         /* write the unary MSBs */
811                         if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
812                                 return false;
813                         /* write the unary end bit and binary LSBs */
814                         if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
815                                 return false;
816                 }
817         }
818         else {
819                 unsigned q, r, d;
820
821                 d = (1 << (k+1)) - parameter;
822                 q = uval / parameter;
823                 r = uval - (q * parameter);
824                 /* write the unary MSBs */
825                 if(!FLAC__bitbuffer_write_zeroes(bb, q))
826                         return false;
827                 /* write the unary end bit */
828                 if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
829                         return false;
830                 /* write the binary LSBs */
831                 if(r >= d) {
832                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
833                                 return false;
834                 }
835                 else {
836                         if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
837                                 return false;
838                 }
839         }
840         return true;
841 }
842
843 bool FLAC__bitbuffer_write_utf8_uint32(FLAC__BitBuffer *bb, uint32 val)
844 {
845         bool ok = 1;
846
847         assert(bb != 0);
848         assert(bb->buffer != 0);
849
850         assert(!(val & 0x80000000)); /* this version only handles 31 bits */
851
852         if(val < 0x80) {
853                 return FLAC__bitbuffer_write_raw_uint32(bb, val, 8);
854         }
855         else if(val < 0x800) {
856                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (val>>6), 8);
857                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
858         }
859         else if(val < 0x10000) {
860                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (val>>12), 8);
861                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
862                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
863         }
864         else if(val < 0x200000) {
865                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (val>>18), 8);
866                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
867                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
868                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
869         }
870         else if(val < 0x4000000) {
871                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (val>>24), 8);
872                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
873                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
874                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
875                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
876         }
877         else {
878                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (val>>30), 8);
879                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>24)&0x3F), 8);
880                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
881                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
882                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
883                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
884         }
885
886         return ok;
887 }
888
889 bool FLAC__bitbuffer_write_utf8_uint64(FLAC__BitBuffer *bb, uint64 val)
890 {
891         bool ok = 1;
892
893         assert(bb != 0);
894         assert(bb->buffer != 0);
895
896         assert(!(val & 0xFFFFFFF000000000)); /* this version only handles 36 bits */
897
898         if(val < 0x80) {
899                 return FLAC__bitbuffer_write_raw_uint32(bb, (uint32)val, 8);
900         }
901         else if(val < 0x800) {
902                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (uint32)(val>>6), 8);
903                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
904         }
905         else if(val < 0x10000) {
906                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (uint32)(val>>12), 8);
907                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
908                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
909         }
910         else if(val < 0x200000) {
911                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (uint32)(val>>18), 8);
912                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
913                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
914                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
915         }
916         else if(val < 0x4000000) {
917                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (uint32)(val>>24), 8);
918                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
919                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
920                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
921                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
922         }
923         else if(val < 0x80000000) {
924                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (uint32)(val>>30), 8);
925                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>24)&0x3F), 8);
926                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
927                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
928                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
929                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
930         }
931         else {
932                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFE, 8);
933                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>30)&0x3F), 8);
934                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>24)&0x3F), 8);
935                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>18)&0x3F), 8);
936                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>12)&0x3F), 8);
937                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)((val>>6)&0x3F), 8);
938                 ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (uint32)(val&0x3F), 8);
939         }
940
941         return ok;
942 }
943
944 bool FLAC__bitbuffer_zero_pad_to_byte_boundary(FLAC__BitBuffer *bb)
945 {
946         /* 0-pad to byte boundary */
947         if(bb->bits != 0)
948                 return FLAC__bitbuffer_write_zeroes(bb, 8 - bb->bits);
949         else
950                 return true;
951 }
952
953 bool FLAC__bitbuffer_peek_bit(FLAC__BitBuffer *bb, unsigned *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
954 {
955         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
956
957         /* to avoid a drastic speed penalty we don't:
958         assert(bb != 0);
959         assert(bb->buffer != 0);
960         assert(bb->bits == 0);
961         */
962
963 read_bit_:
964         if(bb->total_consumed_bits < bb->total_bits) {
965                 *val = (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
966                 return true;
967         }
968         else {
969                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
970                         return false;
971                 goto read_bit_;
972         }
973 }
974
975 bool FLAC__bitbuffer_read_bit(FLAC__BitBuffer *bb, unsigned *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
976 {
977         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
978
979         /* to avoid a drastic speed penalty we don't:
980         assert(bb != 0);
981         assert(bb->buffer != 0);
982         assert(bb->bits == 0);
983         */
984
985 read_bit_:
986         if(bb->total_consumed_bits < bb->total_bits) {
987                 *val = (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
988                 bb->consumed_bits++;
989                 if(bb->consumed_bits == 8) {
990                         bb->consumed_bytes++;
991                         bb->consumed_bits = 0;
992                 }
993                 bb->total_consumed_bits++;
994                 return true;
995         }
996         else {
997                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
998                         return false;
999                 goto read_bit_;
1000         }
1001 }
1002
1003 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)
1004 {
1005         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
1006
1007         /* to avoid a drastic speed penalty we don't:
1008         assert(bb != 0);
1009         assert(bb->buffer != 0);
1010         assert(bb->bits == 0);
1011         */
1012
1013 read_bit_:
1014         if(bb->total_consumed_bits < bb->total_bits) {
1015                 *val <<= 1;
1016                 *val |= (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
1017                 bb->consumed_bits++;
1018                 if(bb->consumed_bits == 8) {
1019                         bb->consumed_bytes++;
1020                         bb->consumed_bits = 0;
1021                 }
1022                 bb->total_consumed_bits++;
1023                 return true;
1024         }
1025         else {
1026                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1027                         return false;
1028                 goto read_bit_;
1029         }
1030 }
1031
1032 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)
1033 {
1034         static byte mask[] = { 128, 64, 32, 16, 8, 4, 2, 1 };
1035
1036         /* to avoid a drastic speed penalty we don't:
1037         assert(bb != 0);
1038         assert(bb->buffer != 0);
1039         assert(bb->bits == 0);
1040         */
1041
1042 read_bit_:
1043         if(bb->total_consumed_bits < bb->total_bits) {
1044                 *val <<= 1;
1045                 *val |= (bb->buffer[bb->consumed_bytes] & mask[bb->consumed_bits])? 1 : 0;
1046                 bb->consumed_bits++;
1047                 if(bb->consumed_bits == 8) {
1048                         bb->consumed_bytes++;
1049                         bb->consumed_bits = 0;
1050                 }
1051                 bb->total_consumed_bits++;
1052                 return true;
1053         }
1054         else {
1055                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1056                         return false;
1057                 goto read_bit_;
1058         }
1059 }
1060
1061 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)
1062 {
1063         unsigned i;
1064
1065         assert(bb != 0);
1066         assert(bb->buffer != 0);
1067
1068         assert(bits <= 32);
1069
1070         *val = 0;
1071         for(i = 0; i < bits; i++) {
1072                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, val, read_callback, client_data))
1073                         return false;
1074         }
1075         return true;
1076 }
1077
1078 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)
1079 {
1080         unsigned i;
1081         uint32 x;
1082
1083         assert(bb != 0);
1084         assert(bb->buffer != 0);
1085
1086         assert(bits <= 32);
1087
1088         x = 0;
1089         for(i = 0; i < bits; i++) {
1090                 if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &x, read_callback, client_data))
1091                         return false;
1092         }
1093         /* fix the sign */
1094         i = 32 - bits;
1095         if(i) {
1096                 x <<= i;
1097                 *val = (int32)x;
1098                 *val >>= i;
1099         }
1100         else
1101                 *val = (int32)x;
1102
1103         return true;
1104 }
1105
1106 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)
1107 {
1108         unsigned i;
1109
1110         assert(bb != 0);
1111         assert(bb->buffer != 0);
1112
1113         assert(bits <= 64);
1114
1115         *val = 0;
1116         for(i = 0; i < bits; i++) {
1117                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, val, read_callback, client_data))
1118                         return false;
1119         }
1120         return true;
1121 }
1122
1123 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)
1124 {
1125         unsigned i;
1126         uint64 x;
1127
1128         assert(bb != 0);
1129         assert(bb->buffer != 0);
1130
1131         assert(bits <= 64);
1132
1133         x = 0;
1134         for(i = 0; i < bits; i++) {
1135                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, &x, read_callback, client_data))
1136                         return false;
1137         }
1138         /* fix the sign */
1139         i = 64 - bits;
1140         if(i) {
1141                 x <<= i;
1142                 *val = (int64)x;
1143                 *val >>= i;
1144         }
1145         else
1146                 *val = (int64)x;
1147
1148         return true;
1149 }
1150
1151 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)
1152 {
1153         uint32 sign = 0, lsbs = 0, msbs = 0;
1154         unsigned bit;
1155
1156         assert(bb != 0);
1157         assert(bb->buffer != 0);
1158         assert(parameter <= 31);
1159
1160         /* read the unary MSBs and end bit */
1161         while(1) {
1162                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1163                         return false;
1164                 if(bit)
1165                         break;
1166                 else
1167                         msbs++;
1168         }
1169         /* read the sign bit */
1170         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &sign, read_callback, client_data))
1171                 return false;
1172         /* read the binary LSBs */
1173         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1174                 return false;
1175
1176         /* compose the value */
1177         *val = (msbs << parameter) | lsbs;
1178         if(sign)
1179                 *val = -(*val);
1180
1181         return true;
1182 }
1183
1184 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)
1185 {
1186         uint32 lsbs = 0, msbs = 0;
1187         unsigned bit, uval;
1188
1189         assert(bb != 0);
1190         assert(bb->buffer != 0);
1191         assert(parameter <= 31);
1192
1193         /* read the unary MSBs and end bit */
1194         while(1) {
1195                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1196                         return false;
1197                 if(bit)
1198                         break;
1199                 else
1200                         msbs++;
1201         }
1202         /* read the binary LSBs */
1203         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1204                 return false;
1205         /* compose the value */
1206         uval = (msbs << parameter) | lsbs;
1207         if(uval & 1)
1208                 *val = -((int)(uval >> 1)) - 1;
1209         else
1210                 *val = (int)(uval >> 1);
1211
1212         return true;
1213 }
1214
1215 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)
1216 {
1217         uint32 lsbs = 0, msbs = 0;
1218         unsigned bit, uval, k;
1219
1220         assert(bb != 0);
1221         assert(bb->buffer != 0);
1222
1223         k = ilog2_(parameter);
1224
1225         /* read the unary MSBs and end bit */
1226         while(1) {
1227                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1228                         return false;
1229                 if(bit)
1230                         break;
1231                 else
1232                         msbs++;
1233         }
1234         /* read the binary LSBs */
1235         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1236                 return false;
1237
1238         if(parameter == 1u<<k) {
1239                 /* compose the value */
1240                 uval = (msbs << k) | lsbs;
1241         }
1242         else {
1243                 unsigned d = (1 << (k+1)) - parameter;
1244                 if(lsbs >= d) {
1245                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1246                                 return false;
1247                         lsbs <<= 1;
1248                         lsbs |= bit;
1249                         lsbs -= d;
1250                 }
1251                 /* compose the value */
1252                 uval = msbs * parameter + lsbs;
1253         }
1254
1255         /* unfold unsigned to signed */
1256         if(uval & 1)
1257                 *val = -((int)(uval >> 1)) - 1;
1258         else
1259                 *val = (int)(uval >> 1);
1260
1261         return true;
1262 }
1263
1264 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)
1265 {
1266         uint32 lsbs, msbs = 0;
1267         unsigned bit, k;
1268
1269         assert(bb != 0);
1270         assert(bb->buffer != 0);
1271
1272         k = ilog2_(parameter);
1273
1274         /* read the unary MSBs and end bit */
1275         while(1) {
1276                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1277                         return false;
1278                 if(bit)
1279                         break;
1280                 else
1281                         msbs++;
1282         }
1283         /* read the binary LSBs */
1284         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1285                 return false;
1286
1287         if(parameter == 1u<<k) {
1288                 /* compose the value */
1289                 *val = (msbs << k) | lsbs;
1290         }
1291         else {
1292                 unsigned d = (1 << (k+1)) - parameter;
1293                 if(lsbs >= d) {
1294                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1295                                 return false;
1296                         lsbs <<= 1;
1297                         lsbs |= bit;
1298                         lsbs -= d;
1299                 }
1300                 /* compose the value */
1301                 *val = msbs * parameter + lsbs;
1302         }
1303
1304         return true;
1305 }
1306
1307 /* on return, if *val == 0xffffffff then the utf-8 sequence was invalid, but the return value will be true */
1308 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)
1309 {
1310         uint32 v = 0;
1311         uint32 x;
1312         unsigned i;
1313
1314         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1315                 return false;
1316         if(raw)
1317                 raw[(*rawlen)++] = (byte)x;
1318         if(!(x & 0x80)) { /* 0xxxxxxx */
1319                 v = x;
1320                 i = 0;
1321         }
1322         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1323                 v = x & 0x1F;
1324                 i = 1;
1325         }
1326         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1327                 v = x & 0x0F;
1328                 i = 2;
1329         }
1330         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1331                 v = x & 0x07;
1332                 i = 3;
1333         }
1334         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1335                 v = x & 0x03;
1336                 i = 4;
1337         }
1338         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1339                 v = x & 0x01;
1340                 i = 5;
1341         }
1342         else
1343                 goto invalid_;
1344         for( ; i; i--) {
1345                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1346                         return false;
1347                 if(raw)
1348                         raw[(*rawlen)++] = (byte)x;
1349                 if(!(x & 0x80) || (x & 0x40)) /* 10xxxxxx */
1350                         goto invalid_;
1351                 v <<= 6;
1352                 v |= (x & 0x3F);
1353         }
1354         *val = v;
1355         return true;
1356 invalid_:
1357         *val = 0xffffffff;
1358         return true;
1359 }
1360
1361 /* on return, if *val == 0xffffffffffffffff then the utf-8 sequence was invalid, but the return value will be true */
1362 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)
1363 {
1364         uint64 v = 0;
1365         uint32 x;
1366         unsigned i;
1367
1368         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1369                 return false;
1370         if(raw)
1371                 raw[(*rawlen)++] = (byte)x;
1372         if(!(x & 0x80)) { /* 0xxxxxxx */
1373                 v = x;
1374                 i = 0;
1375         }
1376         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1377                 v = x & 0x1F;
1378                 i = 1;
1379         }
1380         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1381                 v = x & 0x0F;
1382                 i = 2;
1383         }
1384         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1385                 v = x & 0x07;
1386                 i = 3;
1387         }
1388         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1389                 v = x & 0x03;
1390                 i = 4;
1391         }
1392         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1393                 v = x & 0x01;
1394                 i = 5;
1395         }
1396         else if(x & 0xFE && !(x & 0x01)) { /* 11111110 */
1397                 v = 0;
1398                 i = 6;
1399         }
1400         else
1401                 goto invalid_;
1402         for( ; i; i--) {
1403                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1404                         return false;
1405                 if(raw)
1406                         raw[(*rawlen)++] = (byte)x;
1407                 if(!(x & 0x80) || (x & 0x40)) /* 10xxxxxx */
1408                         goto invalid_;
1409                 v <<= 6;
1410                 v |= (x & 0x3F);
1411         }
1412         *val = v;
1413         return true;
1414 invalid_:
1415         *val = 0xffffffff;
1416         return true;
1417 }
1418
1419 void FLAC__bitbuffer_dump(const FLAC__BitBuffer *bb, FILE *out)
1420 {
1421         unsigned i, j;
1422         if(bb == 0) {
1423                 fprintf(out, "bitbuffer is NULL\n");
1424         }
1425         else {
1426                 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);
1427                 for(i = 0; i < bb->bytes; i++) {
1428                         fprintf(out, "%08X: ", i);
1429                         for(j = 0; j < 8; j++)
1430                                 if(i*8+j < bb->total_consumed_bits)
1431                                         fprintf(out, ".");
1432                                 else
1433                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (8-j-1)) ? 1:0);
1434                         fprintf(out, "\n");
1435                 }
1436                 if(bb->bits > 0) {
1437                         fprintf(out, "%08X: ", i);
1438                         for(j = 0; j < bb->bits; j++)
1439                                 if(i*8+j < bb->total_consumed_bits)
1440                                         fprintf(out, ".");
1441                                 else
1442                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (bb->bits-j-1)) ? 1:0);
1443                         fprintf(out, "\n");
1444                 }
1445         }
1446 }