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