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