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