fix bug where gcc gets shifting wrong
[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                         *val = (bb->buffer[bb->consumed_bytes] & (0xff >> bb->consumed_bits)) >> (i-bits_);
1172                         bb->consumed_bits += bits_;
1173                         bb->total_consumed_bits += bits_;
1174                         return true;
1175                 }
1176         }
1177         while(bits_ >= 8) {
1178                 v <<= 8;
1179                 v |= bb->buffer[bb->consumed_bytes];
1180                 bits_ -= 8;
1181                 FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1182                 bb->consumed_bytes++;
1183                 /* bb->consumed_bits is already 0 */
1184                 /* we hold off updating bb->total_consumed_bits until the end */
1185         }
1186         if(bits_ > 0) {
1187                 v <<= bits_;
1188                 v |= (bb->buffer[bb->consumed_bytes] >> (8-bits_));
1189                 bb->consumed_bits = bits_;
1190                 /* we hold off updating bb->total_consumed_bits until the end */
1191         }
1192         bb->total_consumed_bits += bits;
1193
1194         /* fix the sign */
1195         i = 32 - bits;
1196         if(i) {
1197                 v <<= i;
1198                 *val = (int32)v;
1199                 *val >>= i;
1200         }
1201         else
1202                 *val = (int32)v;
1203
1204         return true;
1205 }
1206 #endif
1207
1208 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)
1209 #ifdef FLAC__NO_MANUAL_INLINING
1210 {
1211         unsigned i;
1212
1213         assert(bb != 0);
1214         assert(bb->buffer != 0);
1215
1216         assert(bits <= 64);
1217
1218         *val = 0;
1219         for(i = 0; i < bits; i++) {
1220                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, val, read_callback, client_data))
1221                         return false;
1222         }
1223         return true;
1224 }
1225 #else
1226 {
1227         unsigned i, bits_ = bits;
1228         uint64 v = 0;
1229
1230         assert(bb != 0);
1231         assert(bb->buffer != 0);
1232
1233         assert(bits <= 64);
1234         assert((bb->capacity*8) * 2 >= bits);
1235
1236         while(bb->total_consumed_bits + bits > bb->total_bits) {
1237                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1238                         return false;
1239         }
1240         if(bb->consumed_bits) {
1241                 i = 8 - bb->consumed_bits;
1242                 if(i <= bits_) {
1243                         v = bb->buffer[bb->consumed_bytes] & (0xff >> bb->consumed_bits);
1244                         bits_ -= i;
1245                         FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1246                         bb->consumed_bytes++;
1247                         bb->consumed_bits = 0;
1248                         /* we hold off updating bb->total_consumed_bits until the end */
1249                 }
1250                 else {
1251                         *val = (bb->buffer[bb->consumed_bytes] & (0xff >> bb->consumed_bits)) >> (i-bits_);
1252                         bb->consumed_bits += bits_;
1253                         bb->total_consumed_bits += bits_;
1254                         return true;
1255                 }
1256         }
1257         while(bits_ >= 8) {
1258                 v <<= 8;
1259                 v |= bb->buffer[bb->consumed_bytes];
1260                 bits_ -= 8;
1261                 FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1262                 bb->consumed_bytes++;
1263                 /* bb->consumed_bits is already 0 */
1264                 /* we hold off updating bb->total_consumed_bits until the end */
1265         }
1266         if(bits_ > 0) {
1267                 v <<= bits_;
1268                 v |= (bb->buffer[bb->consumed_bytes] >> (8-bits_));
1269                 bb->consumed_bits = bits_;
1270                 /* we hold off updating bb->total_consumed_bits until the end */
1271         }
1272         bb->total_consumed_bits += bits;
1273         *val = v;
1274         return true;
1275 }
1276 #endif
1277
1278 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)
1279 #ifdef FLAC__NO_MANUAL_INLINING
1280 {
1281         unsigned i;
1282         uint64 v;
1283
1284         assert(bb != 0);
1285         assert(bb->buffer != 0);
1286
1287         assert(bits <= 64);
1288
1289         v = 0;
1290         for(i = 0; i < bits; i++) {
1291                 if(!FLAC__bitbuffer_read_bit_to_uint64(bb, &v, read_callback, client_data))
1292                         return false;
1293         }
1294         /* fix the sign */
1295         i = 64 - bits;
1296         if(i) {
1297                 v <<= i;
1298                 *val = (int64)v;
1299                 *val >>= i;
1300         }
1301         else
1302                 *val = (int64)v;
1303
1304         return true;
1305 }
1306 #else
1307 {
1308         unsigned i, bits_ = bits;
1309         uint64 v = 0;
1310
1311         assert(bb != 0);
1312         assert(bb->buffer != 0);
1313
1314         assert(bits <= 64);
1315         assert((bb->capacity*8) * 2 >= bits);
1316
1317         while(bb->total_consumed_bits + bits > bb->total_bits) {
1318                 if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1319                         return false;
1320         }
1321         if(bb->consumed_bits) {
1322                 i = 8 - bb->consumed_bits;
1323                 if(i <= bits_) {
1324                         v = bb->buffer[bb->consumed_bytes] & (0xff >> bb->consumed_bits);
1325                         bits_ -= i;
1326                         FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1327                         bb->consumed_bytes++;
1328                         bb->consumed_bits = 0;
1329                         /* we hold off updating bb->total_consumed_bits until the end */
1330                 }
1331                 else {
1332                         *val = (bb->buffer[bb->consumed_bytes] & (0xff >> bb->consumed_bits)) >> (i-bits_);
1333                         bb->consumed_bits += bits_;
1334                         bb->total_consumed_bits += bits_;
1335                         return true;
1336                 }
1337         }
1338         while(bits_ >= 8) {
1339                 v <<= 8;
1340                 v |= bb->buffer[bb->consumed_bytes];
1341                 bits_ -= 8;
1342                 FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1343                 bb->consumed_bytes++;
1344                 /* bb->consumed_bits is already 0 */
1345                 /* we hold off updating bb->total_consumed_bits until the end */
1346         }
1347         if(bits_ > 0) {
1348                 v <<= bits_;
1349                 v |= (bb->buffer[bb->consumed_bytes] >> (8-bits_));
1350                 bb->consumed_bits = bits_;
1351                 /* we hold off updating bb->total_consumed_bits until the end */
1352         }
1353         bb->total_consumed_bits += bits;
1354
1355         /* fix the sign */
1356         i = 64 - bits;
1357         if(i) {
1358                 v <<= i;
1359                 *val = (int64)v;
1360                 *val >>= i;
1361         }
1362         else
1363                 *val = (int64)v;
1364
1365         return true;
1366 }
1367 #endif
1368
1369 bool FLAC__bitbuffer_read_unary_unsigned(FLAC__BitBuffer *bb, unsigned *val, bool (*read_callback)(byte buffer[], unsigned *bytes, void *client_data), void *client_data)
1370 #ifdef FLAC__NO_MANUAL_INLINING
1371 {
1372         unsigned bit, val_ = 0;
1373
1374         assert(bb != 0);
1375         assert(bb->buffer != 0);
1376
1377         while(1) {
1378                 if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1379                         return false;
1380                 if(bit)
1381                         break;
1382                 else
1383                         val_++;
1384         }
1385         *val = val_;
1386         return true;
1387 }
1388 #else
1389 {
1390         unsigned i, val_ = 0;
1391         unsigned total_bytes_ = (bb->total_bits + 7) / 8;
1392         byte b;
1393
1394         assert(bb != 0);
1395         assert(bb->buffer != 0);
1396
1397         if(bb->consumed_bits) {
1398                 b = bb->buffer[bb->consumed_bytes] << bb->consumed_bits;
1399                 if(b) {
1400                         for(i = 0; !(b & 0x80); i++)
1401                                 b <<= 1;
1402                         *val = i;
1403                         i++;
1404                         bb->consumed_bits += i;
1405                         bb->total_consumed_bits += i;
1406                         if(bb->consumed_bits == 8) {
1407                                 FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1408                                 bb->consumed_bytes++;
1409                                 bb->consumed_bits = 0;
1410                         }
1411                         return true;
1412                 }
1413                 else {
1414                         val_ = 8 - bb->consumed_bits;
1415                         FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1416                         bb->consumed_bytes++;
1417                         bb->consumed_bits = 0;
1418                         bb->total_consumed_bits += val_;
1419                 }
1420         }
1421         while(1) {
1422                 if(bb->consumed_bytes >= total_bytes_) {
1423                         if(!bitbuffer_read_from_client_(bb, read_callback, client_data))
1424                                 return false;
1425                         total_bytes_ = (bb->total_bits + 7) / 8;
1426                 }
1427                 b = bb->buffer[bb->consumed_bytes];
1428                 if(b) {
1429                         for(i = 0; !(b & 0x80); i++)
1430                                 b <<= 1;
1431                         val_ += i;
1432                         i++;
1433                         bb->consumed_bits = i;
1434                         *val = val_;
1435                         if(i == 8) {
1436                                 FLAC__CRC16_UPDATE(bb->buffer[bb->consumed_bytes], bb->read_crc16);
1437                                 bb->consumed_bytes++;
1438                                 bb->consumed_bits = 0;
1439                         }
1440                         bb->total_consumed_bits += i;
1441                         return true;
1442                 }
1443                 else {
1444                         val_ += 8;
1445                         FLAC__CRC16_UPDATE(0, bb->read_crc16);
1446                         bb->consumed_bytes++;
1447                         /* bb->consumed_bits is already 0 */
1448                         /* we hold off updating bb->total_consumed_bits until the end */
1449                         bb->total_consumed_bits += 8;
1450                 }
1451         }
1452 }
1453 #endif
1454
1455 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)
1456 {
1457         uint32 sign = 0, lsbs = 0, msbs = 0;
1458
1459         assert(bb != 0);
1460         assert(bb->buffer != 0);
1461         assert(parameter <= 31);
1462
1463         /* read the unary MSBs and end bit */
1464         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
1465                 return false;
1466
1467         /* read the sign bit */
1468         if(!FLAC__bitbuffer_read_bit_to_uint32(bb, &sign, read_callback, client_data))
1469                 return false;
1470
1471         /* read the binary LSBs */
1472         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1473                 return false;
1474
1475         /* compose the value */
1476         *val = (msbs << parameter) | lsbs;
1477         if(sign)
1478                 *val = -(*val);
1479
1480         return true;
1481 }
1482
1483 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)
1484 {
1485         uint32 lsbs = 0, msbs = 0;
1486         unsigned uval;
1487
1488         assert(bb != 0);
1489         assert(bb->buffer != 0);
1490         assert(parameter <= 31);
1491
1492         /* read the unary MSBs and end bit */
1493         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
1494                 return false;
1495
1496         /* read the binary LSBs */
1497         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, parameter, read_callback, client_data))
1498                 return false;
1499
1500         /* compose the value */
1501         uval = (msbs << parameter) | lsbs;
1502         if(uval & 1)
1503                 *val = -((int)(uval >> 1)) - 1;
1504         else
1505                 *val = (int)(uval >> 1);
1506
1507         return true;
1508 }
1509
1510 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)
1511 {
1512         uint32 lsbs = 0, msbs = 0;
1513         unsigned bit, uval, k;
1514
1515         assert(bb != 0);
1516         assert(bb->buffer != 0);
1517
1518         k = FLAC__bitmath_ilog2(parameter);
1519
1520         /* read the unary MSBs and end bit */
1521         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
1522                 return false;
1523
1524         /* read the binary LSBs */
1525         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1526                 return false;
1527
1528         if(parameter == 1u<<k) {
1529                 /* compose the value */
1530                 uval = (msbs << k) | lsbs;
1531         }
1532         else {
1533                 unsigned d = (1 << (k+1)) - parameter;
1534                 if(lsbs >= d) {
1535                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1536                                 return false;
1537                         lsbs <<= 1;
1538                         lsbs |= bit;
1539                         lsbs -= d;
1540                 }
1541                 /* compose the value */
1542                 uval = msbs * parameter + lsbs;
1543         }
1544
1545         /* unfold unsigned to signed */
1546         if(uval & 1)
1547                 *val = -((int)(uval >> 1)) - 1;
1548         else
1549                 *val = (int)(uval >> 1);
1550
1551         return true;
1552 }
1553
1554 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)
1555 {
1556         uint32 lsbs, msbs = 0;
1557         unsigned bit, k;
1558
1559         assert(bb != 0);
1560         assert(bb->buffer != 0);
1561
1562         k = FLAC__bitmath_ilog2(parameter);
1563
1564         /* read the unary MSBs and end bit */
1565         if(!FLAC__bitbuffer_read_unary_unsigned(bb, &msbs, read_callback, client_data))
1566                 return false;
1567
1568         /* read the binary LSBs */
1569         if(!FLAC__bitbuffer_read_raw_uint32(bb, &lsbs, k, read_callback, client_data))
1570                 return false;
1571
1572         if(parameter == 1u<<k) {
1573                 /* compose the value */
1574                 *val = (msbs << k) | lsbs;
1575         }
1576         else {
1577                 unsigned d = (1 << (k+1)) - parameter;
1578                 if(lsbs >= d) {
1579                         if(!FLAC__bitbuffer_read_bit(bb, &bit, read_callback, client_data))
1580                                 return false;
1581                         lsbs <<= 1;
1582                         lsbs |= bit;
1583                         lsbs -= d;
1584                 }
1585                 /* compose the value */
1586                 *val = msbs * parameter + lsbs;
1587         }
1588
1589         return true;
1590 }
1591
1592 /* on return, if *val == 0xffffffff then the utf-8 sequence was invalid, but the return value will be true */
1593 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)
1594 {
1595         uint32 v = 0;
1596         uint32 x;
1597         unsigned i;
1598
1599         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1600                 return false;
1601         if(raw)
1602                 raw[(*rawlen)++] = (byte)x;
1603         if(!(x & 0x80)) { /* 0xxxxxxx */
1604                 v = x;
1605                 i = 0;
1606         }
1607         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1608                 v = x & 0x1F;
1609                 i = 1;
1610         }
1611         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1612                 v = x & 0x0F;
1613                 i = 2;
1614         }
1615         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1616                 v = x & 0x07;
1617                 i = 3;
1618         }
1619         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1620                 v = x & 0x03;
1621                 i = 4;
1622         }
1623         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1624                 v = x & 0x01;
1625                 i = 5;
1626         }
1627         else {
1628                 *val = 0xffffffff;
1629                 return true;
1630         }
1631         for( ; i; i--) {
1632                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1633                         return false;
1634                 if(raw)
1635                         raw[(*rawlen)++] = (byte)x;
1636                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
1637                         *val = 0xffffffff;
1638                         return true;
1639                 }
1640                 v <<= 6;
1641                 v |= (x & 0x3F);
1642         }
1643         *val = v;
1644         return true;
1645 }
1646
1647 /* on return, if *val == 0xffffffffffffffff then the utf-8 sequence was invalid, but the return value will be true */
1648 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)
1649 {
1650         uint64 v = 0;
1651         uint32 x;
1652         unsigned i;
1653
1654         if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1655                 return false;
1656         if(raw)
1657                 raw[(*rawlen)++] = (byte)x;
1658         if(!(x & 0x80)) { /* 0xxxxxxx */
1659                 v = x;
1660                 i = 0;
1661         }
1662         else if(x & 0xC0 && !(x & 0x20)) { /* 110xxxxx */
1663                 v = x & 0x1F;
1664                 i = 1;
1665         }
1666         else if(x & 0xE0 && !(x & 0x10)) { /* 1110xxxx */
1667                 v = x & 0x0F;
1668                 i = 2;
1669         }
1670         else if(x & 0xF0 && !(x & 0x08)) { /* 11110xxx */
1671                 v = x & 0x07;
1672                 i = 3;
1673         }
1674         else if(x & 0xF8 && !(x & 0x04)) { /* 111110xx */
1675                 v = x & 0x03;
1676                 i = 4;
1677         }
1678         else if(x & 0xFC && !(x & 0x02)) { /* 1111110x */
1679                 v = x & 0x01;
1680                 i = 5;
1681         }
1682         else if(x & 0xFE && !(x & 0x01)) { /* 11111110 */
1683                 v = 0;
1684                 i = 6;
1685         }
1686         else {
1687                 *val = 0xffffffffffffffff;
1688                 return true;
1689         }
1690         for( ; i; i--) {
1691                 if(!FLAC__bitbuffer_read_raw_uint32(bb, &x, 8, read_callback, client_data))
1692                         return false;
1693                 if(raw)
1694                         raw[(*rawlen)++] = (byte)x;
1695                 if(!(x & 0x80) || (x & 0x40)) { /* 10xxxxxx */
1696                         *val = 0xffffffffffffffff;
1697                         return true;
1698                 }
1699                 v <<= 6;
1700                 v |= (x & 0x3F);
1701         }
1702         *val = v;
1703         return true;
1704 }
1705
1706 void FLAC__bitbuffer_dump(const FLAC__BitBuffer *bb, FILE *out)
1707 {
1708         unsigned i, j;
1709         if(bb == 0) {
1710                 fprintf(out, "bitbuffer is NULL\n");
1711         }
1712         else {
1713                 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);
1714                 for(i = 0; i < bb->bytes; i++) {
1715                         fprintf(out, "%08X: ", i);
1716                         for(j = 0; j < 8; j++)
1717                                 if(i*8+j < bb->total_consumed_bits)
1718                                         fprintf(out, ".");
1719                                 else
1720                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (8-j-1)) ? 1:0);
1721                         fprintf(out, "\n");
1722                 }
1723                 if(bb->bits > 0) {
1724                         fprintf(out, "%08X: ", i);
1725                         for(j = 0; j < bb->bits; j++)
1726                                 if(i*8+j < bb->total_consumed_bits)
1727                                         fprintf(out, ".");
1728                                 else
1729                                         fprintf(out, "%01u", bb->buffer[i] & (1 << (bb->bits-j-1)) ? 1:0);
1730                         fprintf(out, "\n");
1731                 }
1732         }
1733 }