src/libFLAC/bitwriter.c

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2000,2001,2002,2003,2004,2005,2006,2007,2008,2009  Josh Coalson
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * - Neither the name of the Xiph.org Foundation nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  26  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  27  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  28  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  29  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #if HAVE_CONFIG_H
  33 #  include <config.h>
  34 #endif
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include "private/bitwriter.h"
  39 #include "private/crc.h"
  40 #include "private/macros.h"
  41 #include "FLAC/assert.h"
  42 #include "share/alloc.h"
  43 #include "share/endswap.h"
  44
  45 /* Things should be fastest when this matches the machine word size */
  46 /* WATCHOUT: if you change this you must also change the following #defines down to SWAP_BE_WORD_TO_HOST below to match */
  47 /* WATCHOUT: there are a few places where the code will not work unless uint32_t is >= 32 bits wide */
  48 #define FLAC__BYTES_PER_WORD 4
  49 #define FLAC__BITS_PER_WORD 32
  50 #define FLAC__WORD_ALL_ONES ((FLAC__uint32)0xffffffff)
  51 /* SWAP_BE_WORD_TO_HOST swaps bytes in a uint32_t (which is always big-endian) if necessary to match host byte order */
  52 #if WORDS_BIGENDIAN
  53 #define SWAP_BE_WORD_TO_HOST(x) (x)
  54 #else
  55 #define SWAP_BE_WORD_TO_HOST(x) ENDSWAP_32(x)
  56 #endif
  57
  58 /*
  59  * The default capacity here doesn't matter too much.  The buffer always grows
  60  * to hold whatever is written to it.  Usually the encoder will stop adding at
  61  * a frame or metadata block, then write that out and clear the buffer for the
  62  * next one.
  63  */
  64 static const unsigned FLAC__BITWRITER_DEFAULT_CAPACITY = 32768u / sizeof(uint32_t); /* size in words */
  65 /* When growing, increment 4K at a time */
  66 static const unsigned FLAC__BITWRITER_DEFAULT_INCREMENT = 4096u / sizeof(uint32_t); /* size in words */
  67
  68 #define FLAC__WORDS_TO_BITS(words) ((words) * FLAC__BITS_PER_WORD)
  69 #define FLAC__TOTAL_BITS(bw) (FLAC__WORDS_TO_BITS((bw)->words) + (bw)->bits)
  70
  71 /* adjust for compilers that can't understand using LLU suffix for uint64_t literals */
  72 #ifdef _MSC_VER
  73 #define FLAC__U64L(x) x
  74 #else
  75 #define FLAC__U64L(x) x##LLU
  76 #endif
  77
  78 struct FLAC__BitWriter {
  79         uint32_t *buffer;
  80         uint32_t accum; /* accumulator; bits are right-justified; when full, accum is appended to buffer */
  81         unsigned capacity; /* capacity of buffer in words */
  82         unsigned words; /* # of complete words in buffer */
  83         unsigned bits; /* # of used bits in accum */
  84 };
  85
  86 /* * WATCHOUT: The current implementation only grows the buffer. */
  87 static FLAC__bool bitwriter_grow_(FLAC__BitWriter *bw, unsigned bits_to_add)
  88 {
  89         unsigned new_capacity;
  90         uint32_t *new_buffer;
  91
  92         FLAC__ASSERT(0 != bw);
  93         FLAC__ASSERT(0 != bw->buffer);
  94
  95         /* calculate total words needed to store 'bits_to_add' additional bits */
  96         new_capacity = bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD);
  97
  98         /* it's possible (due to pessimism in the growth estimation that
  99          * leads to this call) that we don't actually need to grow
 100          */
 101         if(bw->capacity >= new_capacity)
 102                 return true;
 103
 104         /* round up capacity increase to the nearest FLAC__BITWRITER_DEFAULT_INCREMENT */
 105         if((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT)
 106                 new_capacity += FLAC__BITWRITER_DEFAULT_INCREMENT - ((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 107         /* make sure we got everything right */
 108         FLAC__ASSERT(0 == (new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 109         FLAC__ASSERT(new_capacity > bw->capacity);
 110         FLAC__ASSERT(new_capacity >= bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD));
 111
 112         new_buffer = safe_realloc_mul_2op_(bw->buffer, sizeof(uint32_t), /*times*/new_capacity);
 113         if(new_buffer == 0)
 114                 return false;
 115         bw->buffer = new_buffer;
 116         bw->capacity = new_capacity;
 117         return true;
 118 }
 119
 120
 121 /***********************************************************************
 122  *
 123  * Class constructor/destructor
 124  *
 125  ***********************************************************************/
 126
 127 FLAC__BitWriter *FLAC__bitwriter_new(void)
 128 {
 129         FLAC__BitWriter *bw = calloc(1, sizeof(FLAC__BitWriter));
 130         /* note that calloc() sets all members to 0 for us */
 131         return bw;
 132 }
 133
 134 void FLAC__bitwriter_delete(FLAC__BitWriter *bw)
 135 {
 136         FLAC__ASSERT(0 != bw);
 137
 138         FLAC__bitwriter_free(bw);
 139         free(bw);
 140 }
 141
 142 /***********************************************************************
 143  *
 144  * Public class methods
 145  *
 146  ***********************************************************************/
 147
 148 FLAC__bool FLAC__bitwriter_init(FLAC__BitWriter *bw)
 149 {
 150         FLAC__ASSERT(0 != bw);
 151
 152         bw->words = bw->bits = 0;
 153         bw->capacity = FLAC__BITWRITER_DEFAULT_CAPACITY;
 154         bw->buffer = malloc(sizeof(uint32_t) * bw->capacity);
 155         if(bw->buffer == 0)
 156                 return false;
 157
 158         return true;
 159 }
 160
 161 void FLAC__bitwriter_free(FLAC__BitWriter *bw)
 162 {
 163         FLAC__ASSERT(0 != bw);
 164
 165         if(0 != bw->buffer)
 166                 free(bw->buffer);
 167         bw->buffer = 0;
 168         bw->capacity = 0;
 169         bw->words = bw->bits = 0;
 170 }
 171
 172 void FLAC__bitwriter_clear(FLAC__BitWriter *bw)
 173 {
 174         bw->words = bw->bits = 0;
 175 }
 176
 177 void FLAC__bitwriter_dump(const FLAC__BitWriter *bw, FILE *out)
 178 {
 179         unsigned i, j;
 180         if(bw == 0) {
 181                 fprintf(out, "bitwriter is NULL\n");
 182         }
 183         else {
 184                 fprintf(out, "bitwriter: capacity=%u words=%u bits=%u total_bits=%u\n", bw->capacity, bw->words, bw->bits, FLAC__TOTAL_BITS(bw));
 185
 186                 for(i = 0; i < bw->words; i++) {
 187                         fprintf(out, "%08X: ", i);
 188                         for(j = 0; j < FLAC__BITS_PER_WORD; j++)
 189                                 fprintf(out, "%01u", bw->buffer[i] & (1 << (FLAC__BITS_PER_WORD-j-1)) ? 1:0);
 190                         fprintf(out, "\n");
 191                 }
 192                 if(bw->bits > 0) {
 193                         fprintf(out, "%08X: ", i);
 194                         for(j = 0; j < bw->bits; j++)
 195                                 fprintf(out, "%01u", bw->accum & (1 << (bw->bits-j-1)) ? 1:0);
 196                         fprintf(out, "\n");
 197                 }
 198         }
 199 }
 200
 201 FLAC__bool FLAC__bitwriter_get_write_crc16(FLAC__BitWriter *bw, FLAC__uint16 *crc)
 202 {
 203         const FLAC__byte *buffer;
 204         size_t bytes;
 205
 206         FLAC__ASSERT((bw->bits & 7) == 0); /* assert that we're byte-aligned */
 207
 208         if(!FLAC__bitwriter_get_buffer(bw, &buffer, &bytes))
 209                 return false;
 210
 211         *crc = (FLAC__uint16)FLAC__crc16(buffer, bytes);
 212         FLAC__bitwriter_release_buffer(bw);
 213         return true;
 214 }
 215
 216 FLAC__bool FLAC__bitwriter_get_write_crc8(FLAC__BitWriter *bw, FLAC__byte *crc)
 217 {
 218         const FLAC__byte *buffer;
 219         size_t bytes;
 220
 221         FLAC__ASSERT((bw->bits & 7) == 0); /* assert that we're byte-aligned */
 222
 223         if(!FLAC__bitwriter_get_buffer(bw, &buffer, &bytes))
 224                 return false;
 225
 226         *crc = FLAC__crc8(buffer, bytes);
 227         FLAC__bitwriter_release_buffer(bw);
 228         return true;
 229 }
 230
 231 FLAC__bool FLAC__bitwriter_is_byte_aligned(const FLAC__BitWriter *bw)
 232 {
 233         return ((bw->bits & 7) == 0);
 234 }
 235
 236 unsigned FLAC__bitwriter_get_input_bits_unconsumed(const FLAC__BitWriter *bw)
 237 {
 238         return FLAC__TOTAL_BITS(bw);
 239 }
 240
 241 FLAC__bool FLAC__bitwriter_get_buffer(FLAC__BitWriter *bw, const FLAC__byte **buffer, size_t *bytes)
 242 {
 243         FLAC__ASSERT((bw->bits & 7) == 0);
 244         /* double protection */
 245         if(bw->bits & 7)
 246                 return false;
 247         /* if we have bits in the accumulator we have to flush those to the buffer first */
 248         if(bw->bits) {
 249                 FLAC__ASSERT(bw->words <= bw->capacity);
 250                 if(bw->words == bw->capacity && !bitwriter_grow_(bw, FLAC__BITS_PER_WORD))
 251                         return false;
 252                 /* append bits as complete word to buffer, but don't change bw->accum or bw->bits */
 253                 bw->buffer[bw->words] = SWAP_BE_WORD_TO_HOST(bw->accum << (FLAC__BITS_PER_WORD-bw->bits));
 254         }
 255         /* now we can just return what we have */
 256         *buffer = (FLAC__byte*)bw->buffer;
 257         *bytes = (FLAC__BYTES_PER_WORD * bw->words) + (bw->bits >> 3);
 258         return true;
 259 }
 260
 261 void FLAC__bitwriter_release_buffer(FLAC__BitWriter *bw)
 262 {
 263         /* nothing to do.  in the future, strict checking of a 'writer-is-in-
 264          * get-mode' flag could be added everywhere and then cleared here
 265          */
 266         (void)bw;
 267 }
 268
 269 inline FLAC__bool FLAC__bitwriter_write_zeroes(FLAC__BitWriter *bw, unsigned bits)
 270 {
 271         unsigned n;
 272
 273         FLAC__ASSERT(0 != bw);
 274         FLAC__ASSERT(0 != bw->buffer);
 275
 276         if(bits == 0)
 277                 return true;
 278         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 279         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 280                 return false;
 281         /* first part gets to word alignment */
 282         if(bw->bits) {
 283                 n = flac_min(FLAC__BITS_PER_WORD - bw->bits, bits);
 284                 bw->accum <<= n;
 285                 bits -= n;
 286                 bw->bits += n;
 287                 if(bw->bits == FLAC__BITS_PER_WORD) {
 288                         bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 289                         bw->bits = 0;
 290                 }
 291                 else
 292                         return true;
 293         }
 294         /* do whole words */
 295         while(bits >= FLAC__BITS_PER_WORD) {
 296                 bw->buffer[bw->words++] = 0;
 297                 bits -= FLAC__BITS_PER_WORD;
 298         }
 299         /* do any leftovers */
 300         if(bits > 0) {
 301                 bw->accum = 0;
 302                 bw->bits = bits;
 303         }
 304         return true;
 305 }
 306
 307 inline FLAC__bool FLAC__bitwriter_write_raw_uint32(FLAC__BitWriter *bw, FLAC__uint32 val, unsigned bits)
 308 {
 309         register unsigned left;
 310
 311         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 312         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 313
 314         FLAC__ASSERT(0 != bw);
 315         FLAC__ASSERT(0 != bw->buffer);
 316
 317         FLAC__ASSERT(bits <= 32);
 318         if(bits == 0)
 319                 return true;
 320
 321         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 322         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 323                 return false;
 324
 325         left = FLAC__BITS_PER_WORD - bw->bits;
 326         if(bits < left) {
 327                 bw->accum <<= bits;
 328                 bw->accum |= val;
 329                 bw->bits += bits;
 330         }
 331         else if(bw->bits) { /* WATCHOUT: if bw->bits == 0, left==FLAC__BITS_PER_WORD and bw->accum<<=left is a NOP instead of setting to 0 */
 332                 bw->accum <<= left;
 333                 bw->accum |= val >> (bw->bits = bits - left);
 334                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 335                 bw->accum = val;
 336         }
 337         else {
 338                 bw->accum = val;
 339                 bw->bits = 0;
 340                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(val);
 341         }
 342
 343         return true;
 344 }
 345
 346 inline FLAC__bool FLAC__bitwriter_write_raw_int32(FLAC__BitWriter *bw, FLAC__int32 val, unsigned bits)
 347 {
 348         /* zero-out unused bits */
 349         if(bits < 32)
 350                 val &= (~(0xffffffff << bits));
 351
 352         return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, bits);
 353 }
 354
 355 inline FLAC__bool FLAC__bitwriter_write_raw_uint64(FLAC__BitWriter *bw, FLAC__uint64 val, unsigned bits)
 356 {
 357         /* this could be a little faster but it's not used for much */
 358         if(bits > 32) {
 359                 return
 360                         FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)(val>>32), bits-32) &&
 361                         FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, 32);
 362         }
 363         else
 364                 return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, bits);
 365 }
 366
 367 inline FLAC__bool FLAC__bitwriter_write_raw_uint32_little_endian(FLAC__BitWriter *bw, FLAC__uint32 val)
 368 {
 369         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
 370
 371         if(!FLAC__bitwriter_write_raw_uint32(bw, val & 0xff, 8))
 372                 return false;
 373         if(!FLAC__bitwriter_write_raw_uint32(bw, (val>>8) & 0xff, 8))
 374                 return false;
 375         if(!FLAC__bitwriter_write_raw_uint32(bw, (val>>16) & 0xff, 8))
 376                 return false;
 377         if(!FLAC__bitwriter_write_raw_uint32(bw, val>>24, 8))
 378                 return false;
 379
 380         return true;
 381 }
 382
 383 inline FLAC__bool FLAC__bitwriter_write_byte_block(FLAC__BitWriter *bw, const FLAC__byte vals[], unsigned nvals)
 384 {
 385         unsigned i;
 386
 387         /* this could be faster but currently we don't need it to be since it's only used for writing metadata */
 388         for(i = 0; i < nvals; i++) {
 389                 if(!FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)(vals[i]), 8))
 390                         return false;
 391         }
 392
 393         return true;
 394 }
 395
 396 FLAC__bool FLAC__bitwriter_write_unary_unsigned(FLAC__BitWriter *bw, unsigned val)
 397 {
 398         if(val < 32)
 399                 return FLAC__bitwriter_write_raw_uint32(bw, 1, ++val);
 400         else
 401                 return
 402                         FLAC__bitwriter_write_zeroes(bw, val) &&
 403                         FLAC__bitwriter_write_raw_uint32(bw, 1, 1);
 404 }
 405
 406 unsigned FLAC__bitwriter_rice_bits(FLAC__int32 val, unsigned parameter)
 407 {
 408         FLAC__uint32 uval;
 409
 410         FLAC__ASSERT(parameter < sizeof(unsigned)*8);
 411
 412         /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 413         uval = (val<<1) ^ (val>>31);
 414
 415         return 1 + parameter + (uval >> parameter);
 416 }
 417
 418 #if 0 /* UNUSED */
 419 unsigned FLAC__bitwriter_golomb_bits_signed(int val, unsigned parameter)
 420 {
 421         unsigned bits, msbs, uval;
 422         unsigned k;
 423
 424         FLAC__ASSERT(parameter > 0);
 425
 426         /* fold signed to unsigned */
 427         if(val < 0)
 428                 uval = (unsigned)(((-(++val)) << 1) + 1);
 429         else
 430                 uval = (unsigned)(val << 1);
 431
 432         k = FLAC__bitmath_ilog2(parameter);
 433         if(parameter == 1u<<k) {
 434                 FLAC__ASSERT(k <= 30);
 435
 436                 msbs = uval >> k;
 437                 bits = 1 + k + msbs;
 438         }
 439         else {
 440                 unsigned q, r, d;
 441
 442                 d = (1 << (k+1)) - parameter;
 443                 q = uval / parameter;
 444                 r = uval - (q * parameter);
 445
 446                 bits = 1 + q + k;
 447                 if(r >= d)
 448                         bits++;
 449         }
 450         return bits;
 451 }
 452
 453 unsigned FLAC__bitwriter_golomb_bits_unsigned(unsigned uval, unsigned parameter)
 454 {
 455         unsigned bits, msbs;
 456         unsigned k;
 457
 458         FLAC__ASSERT(parameter > 0);
 459
 460         k = FLAC__bitmath_ilog2(parameter);
 461         if(parameter == 1u<<k) {
 462                 FLAC__ASSERT(k <= 30);
 463
 464                 msbs = uval >> k;
 465                 bits = 1 + k + msbs;
 466         }
 467         else {
 468                 unsigned q, r, d;
 469
 470                 d = (1 << (k+1)) - parameter;
 471                 q = uval / parameter;
 472                 r = uval - (q * parameter);
 473
 474                 bits = 1 + q + k;
 475                 if(r >= d)
 476                         bits++;
 477         }
 478         return bits;
 479 }
 480 #endif /* UNUSED */
 481
 482 FLAC__bool FLAC__bitwriter_write_rice_signed(FLAC__BitWriter *bw, FLAC__int32 val, unsigned parameter)
 483 {
 484         unsigned total_bits, interesting_bits, msbs;
 485         FLAC__uint32 uval, pattern;
 486
 487         FLAC__ASSERT(0 != bw);
 488         FLAC__ASSERT(0 != bw->buffer);
 489         FLAC__ASSERT(parameter < 8*sizeof(uval));
 490
 491         /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 492         uval = (val<<1) ^ (val>>31);
 493
 494         msbs = uval >> parameter;
 495         interesting_bits = 1 + parameter;
 496         total_bits = interesting_bits + msbs;
 497         pattern = 1 << parameter; /* the unary end bit */
 498         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
 499
 500         if(total_bits <= 32)
 501                 return FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits);
 502         else
 503                 return
 504                         FLAC__bitwriter_write_zeroes(bw, msbs) && /* write the unary MSBs */
 505                         FLAC__bitwriter_write_raw_uint32(bw, pattern, interesting_bits); /* write the unary end bit and binary LSBs */
 506 }
 507
 508 FLAC__bool FLAC__bitwriter_write_rice_signed_block(FLAC__BitWriter *bw, const FLAC__int32 *vals, unsigned nvals, unsigned parameter)
 509 {
 510         const FLAC__uint32 mask1 = FLAC__WORD_ALL_ONES << parameter; /* we val|=mask1 to set the stop bit above it... */
 511         const FLAC__uint32 mask2 = FLAC__WORD_ALL_ONES >> (31-parameter); /* ...then mask off the bits above the stop bit with val&=mask2*/
 512         FLAC__uint32 uval;
 513         unsigned left;
 514         const unsigned lsbits = 1 + parameter;
 515         unsigned msbits;
 516
 517         FLAC__ASSERT(0 != bw);
 518         FLAC__ASSERT(0 != bw->buffer);
 519         FLAC__ASSERT(parameter < 8*sizeof(uint32_t)-1);
 520         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 521         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 522
 523         while(nvals) {
 524                 /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 525                 uval = (*vals<<1) ^ (*vals>>31);
 526
 527                 msbits = uval >> parameter;
 528
 529 #if 0 /* OPT: can remove this special case if it doesn't make up for the extra compare (doesn't make a statistically significant difference with msvc or gcc/x86) */
 530                 if(bw->bits && bw->bits + msbits + lsbits <= FLAC__BITS_PER_WORD) { /* i.e. if the whole thing fits in the current uint32_t */
 531                         /* ^^^ if bw->bits is 0 then we may have filled the buffer and have no free uint32_t to work in */
 532                         bw->bits = bw->bits + msbits + lsbits;
 533                         uval |= mask1; /* set stop bit */
 534                         uval &= mask2; /* mask off unused top bits */
 535                         /* NOT: bw->accum <<= msbits + lsbits because msbits+lsbits could be 32, then the shift would be a NOP */
 536                         bw->accum <<= msbits;
 537                         bw->accum <<= lsbits;
 538                         bw->accum |= uval;
 539                         if(bw->bits == FLAC__BITS_PER_WORD) {
 540                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 541                                 bw->bits = 0;
 542                                 /* burying the capacity check down here means we have to grow the buffer a little if there are more vals to do */
 543                                 if(bw->capacity <= bw->words && nvals > 1 && !bitwriter_grow_(bw, 1)) {
 544                                         FLAC__ASSERT(bw->capacity == bw->words);
 545                                         return false;
 546                                 }
 547                         }
 548                 }
 549                 else {
 550 #elif 1 /*@@@@@@ OPT: try this version with MSVC6 to see if better, not much difference for gcc-4 */
 551                 if(bw->bits && bw->bits + msbits + lsbits < FLAC__BITS_PER_WORD) { /* i.e. if the whole thing fits in the current uint32_t */
 552                         /* ^^^ if bw->bits is 0 then we may have filled the buffer and have no free uint32_t to work in */
 553                         bw->bits = bw->bits + msbits + lsbits;
 554                         uval |= mask1; /* set stop bit */
 555                         uval &= mask2; /* mask off unused top bits */
 556                         bw->accum <<= msbits + lsbits;
 557                         bw->accum |= uval;
 558                 }
 559                 else {
 560 #endif
 561                         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+msbits+lsbits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 562                         /* OPT: pessimism may cause flurry of false calls to grow_ which eat up all savings before it */
 563                         if(bw->capacity <= bw->words + bw->bits + msbits + 1/*lsbits always fit in 1 uint32_t*/ && !bitwriter_grow_(bw, msbits+lsbits))
 564                                 return false;
 565
 566                         if(msbits) {
 567                                 /* first part gets to word alignment */
 568                                 if(bw->bits) {
 569                                         left = FLAC__BITS_PER_WORD - bw->bits;
 570                                         if(msbits < left) {
 571                                                 bw->accum <<= msbits;
 572                                                 bw->bits += msbits;
 573                                                 goto break1;
 574                                         }
 575                                         else {
 576                                                 bw->accum <<= left;
 577                                                 msbits -= left;
 578                                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 579                                                 bw->bits = 0;
 580                                         }
 581                                 }
 582                                 /* do whole words */
 583                                 while(msbits >= FLAC__BITS_PER_WORD) {
 584                                         bw->buffer[bw->words++] = 0;
 585                                         msbits -= FLAC__BITS_PER_WORD;
 586                                 }
 587                                 /* do any leftovers */
 588                                 if(msbits > 0) {
 589                                         bw->accum = 0;
 590                                         bw->bits = msbits;
 591                                 }
 592                         }
 593 break1:
 594                         uval |= mask1; /* set stop bit */
 595                         uval &= mask2; /* mask off unused top bits */
 596
 597                         left = FLAC__BITS_PER_WORD - bw->bits;
 598                         if(lsbits < left) {
 599                                 bw->accum <<= lsbits;
 600                                 bw->accum |= uval;
 601                                 bw->bits += lsbits;
 602                         }
 603                         else {
 604                                 /* if bw->bits == 0, left==FLAC__BITS_PER_WORD which will always
 605                                  * be > lsbits (because of previous assertions) so it would have
 606                                  * triggered the (lsbits<left) case above.
 607                                  */
 608                                 FLAC__ASSERT(bw->bits);
 609                                 FLAC__ASSERT(left < FLAC__BITS_PER_WORD);
 610                                 bw->accum <<= left;
 611                                 bw->accum |= uval >> (bw->bits = lsbits - left);
 612                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 613                                 bw->accum = uval;
 614                         }
 615 #if 1
 616                 }
 617 #endif
 618                 vals++;
 619                 nvals--;
 620         }
 621         return true;
 622 }
 623
 624 #if 0 /* UNUSED */
 625 FLAC__bool FLAC__bitwriter_write_golomb_signed(FLAC__BitWriter *bw, int val, unsigned parameter)
 626 {
 627         unsigned total_bits, msbs, uval;
 628         unsigned k;
 629
 630         FLAC__ASSERT(0 != bw);
 631         FLAC__ASSERT(0 != bw->buffer);
 632         FLAC__ASSERT(parameter > 0);
 633
 634         /* fold signed to unsigned */
 635         if(val < 0)
 636                 uval = (unsigned)(((-(++val)) << 1) + 1);
 637         else
 638                 uval = (unsigned)(val << 1);
 639
 640         k = FLAC__bitmath_ilog2(parameter);
 641         if(parameter == 1u<<k) {
 642                 unsigned pattern;
 643
 644                 FLAC__ASSERT(k <= 30);
 645
 646                 msbs = uval >> k;
 647                 total_bits = 1 + k + msbs;
 648                 pattern = 1 << k; /* the unary end bit */
 649                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 650
 651                 if(total_bits <= 32) {
 652                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 653                                 return false;
 654                 }
 655                 else {
 656                         /* write the unary MSBs */
 657                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 658                                 return false;
 659                         /* write the unary end bit and binary LSBs */
 660                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 661                                 return false;
 662                 }
 663         }
 664         else {
 665                 unsigned q, r, d;
 666
 667                 d = (1 << (k+1)) - parameter;
 668                 q = uval / parameter;
 669                 r = uval - (q * parameter);
 670                 /* write the unary MSBs */
 671                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 672                         return false;
 673                 /* write the unary end bit */
 674                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 675                         return false;
 676                 /* write the binary LSBs */
 677                 if(r >= d) {
 678                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 679                                 return false;
 680                 }
 681                 else {
 682                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 683                                 return false;
 684                 }
 685         }
 686         return true;
 687 }
 688
 689 FLAC__bool FLAC__bitwriter_write_golomb_unsigned(FLAC__BitWriter *bw, unsigned uval, unsigned parameter)
 690 {
 691         unsigned total_bits, msbs;
 692         unsigned k;
 693
 694         FLAC__ASSERT(0 != bw);
 695         FLAC__ASSERT(0 != bw->buffer);
 696         FLAC__ASSERT(parameter > 0);
 697
 698         k = FLAC__bitmath_ilog2(parameter);
 699         if(parameter == 1u<<k) {
 700                 unsigned pattern;
 701
 702                 FLAC__ASSERT(k <= 30);
 703
 704                 msbs = uval >> k;
 705                 total_bits = 1 + k + msbs;
 706                 pattern = 1 << k; /* the unary end bit */
 707                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 708
 709                 if(total_bits <= 32) {
 710                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 711                                 return false;
 712                 }
 713                 else {
 714                         /* write the unary MSBs */
 715                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 716                                 return false;
 717                         /* write the unary end bit and binary LSBs */
 718                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 719                                 return false;
 720                 }
 721         }
 722         else {
 723                 unsigned q, r, d;
 724
 725                 d = (1 << (k+1)) - parameter;
 726                 q = uval / parameter;
 727                 r = uval - (q * parameter);
 728                 /* write the unary MSBs */
 729                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 730                         return false;
 731                 /* write the unary end bit */
 732                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 733                         return false;
 734                 /* write the binary LSBs */
 735                 if(r >= d) {
 736                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 737                                 return false;
 738                 }
 739                 else {
 740                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 741                                 return false;
 742                 }
 743         }
 744         return true;
 745 }
 746 #endif /* UNUSED */
 747
 748 FLAC__bool FLAC__bitwriter_write_utf8_uint32(FLAC__BitWriter *bw, FLAC__uint32 val)
 749 {
 750         FLAC__bool ok = 1;
 751
 752         FLAC__ASSERT(0 != bw);
 753         FLAC__ASSERT(0 != bw->buffer);
 754
 755         FLAC__ASSERT(!(val & 0x80000000)); /* this version only handles 31 bits */
 756
 757         if(val < 0x80) {
 758                 return FLAC__bitwriter_write_raw_uint32(bw, val, 8);
 759         }
 760         else if(val < 0x800) {
 761                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xC0 | (val>>6), 8);
 762                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 763         }
 764         else if(val < 0x10000) {
 765                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xE0 | (val>>12), 8);
 766                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 767                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 768         }
 769         else if(val < 0x200000) {
 770                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF0 | (val>>18), 8);
 771                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 772                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 773                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 774         }
 775         else if(val < 0x4000000) {
 776                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF8 | (val>>24), 8);
 777                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>18)&0x3F), 8);
 778                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 779                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 780                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 781         }
 782         else {
 783                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFC | (val>>30), 8);
 784                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>24)&0x3F), 8);
 785                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>18)&0x3F), 8);
 786                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 787                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 788                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 789         }
 790
 791         return ok;
 792 }
 793
 794 FLAC__bool FLAC__bitwriter_write_utf8_uint64(FLAC__BitWriter *bw, FLAC__uint64 val)
 795 {
 796         FLAC__bool ok = 1;
 797
 798         FLAC__ASSERT(0 != bw);
 799         FLAC__ASSERT(0 != bw->buffer);
 800
 801         FLAC__ASSERT(!(val & FLAC__U64L(0xFFFFFFF000000000))); /* this version only handles 36 bits */
 802
 803         if(val < 0x80) {
 804                 return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, 8);
 805         }
 806         else if(val < 0x800) {
 807                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xC0 | (FLAC__uint32)(val>>6), 8);
 808                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 809         }
 810         else if(val < 0x10000) {
 811                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xE0 | (FLAC__uint32)(val>>12), 8);
 812                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 813                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 814         }
 815         else if(val < 0x200000) {
 816                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF0 | (FLAC__uint32)(val>>18), 8);
 817                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 818                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 819                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 820         }
 821         else if(val < 0x4000000) {
 822                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF8 | (FLAC__uint32)(val>>24), 8);
 823                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 824                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 825                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 826                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 827         }
 828         else if(val < 0x80000000) {
 829                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFC | (FLAC__uint32)(val>>30), 8);
 830                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 831                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 832                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 833                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 834                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 835         }
 836         else {
 837                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFE, 8);
 838                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>30)&0x3F), 8);
 839                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 840                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 841                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 842                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 843                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 844         }
 845
 846         return ok;
 847 }
 848
 849 FLAC__bool FLAC__bitwriter_zero_pad_to_byte_boundary(FLAC__BitWriter *bw)
 850 {
 851         /* 0-pad to byte boundary */
 852         if(bw->bits & 7u)
 853                 return FLAC__bitwriter_write_zeroes(bw, 8 - (bw->bits & 7u));
 854         else
 855                 return true;
 856 }