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