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