src/libFLAC/bitbuffer.c

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