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