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