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