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