src/libFLAC/bitbuffer.c

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