src/libFLAC/bitbuffer.c

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