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 #ifndef FLaC__INLINE
  79 #define FLaC__INLINE
  80 #endif
  81
  82 struct FLAC__BitWriter {
  83         uint32_t *buffer;
  84         uint32_t accum; /* accumulator; bits are right-justified; when full, accum is appended to buffer */
  85         unsigned capacity; /* capacity of buffer in words */
  86         unsigned words; /* # of complete words in buffer */
  87         unsigned bits; /* # of used bits in accum */
  88 };
  89
  90 /* * WATCHOUT: The current implementation only grows the buffer. */
  91 static FLAC__bool bitwriter_grow_(FLAC__BitWriter *bw, unsigned bits_to_add)
  92 {
  93         unsigned new_capacity;
  94         uint32_t *new_buffer;
  95
  96         FLAC__ASSERT(0 != bw);
  97         FLAC__ASSERT(0 != bw->buffer);
  98
  99         /* calculate total words needed to store 'bits_to_add' additional bits */
 100         new_capacity = bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD);
 101
 102         /* it's possible (due to pessimism in the growth estimation that
 103          * leads to this call) that we don't actually need to grow
 104          */
 105         if(bw->capacity >= new_capacity)
 106                 return true;
 107
 108         /* round up capacity increase to the nearest FLAC__BITWRITER_DEFAULT_INCREMENT */
 109         if((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT)
 110                 new_capacity += FLAC__BITWRITER_DEFAULT_INCREMENT - ((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 111         /* make sure we got everything right */
 112         FLAC__ASSERT(0 == (new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 113         FLAC__ASSERT(new_capacity > bw->capacity);
 114         FLAC__ASSERT(new_capacity >= bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD));
 115
 116         new_buffer = safe_realloc_mul_2op_(bw->buffer, sizeof(uint32_t), /*times*/new_capacity);
 117         if(new_buffer == 0)
 118                 return false;
 119         bw->buffer = new_buffer;
 120         bw->capacity = new_capacity;
 121         return true;
 122 }
 123
 124
 125 /***********************************************************************
 126  *
 127  * Class constructor/destructor
 128  *
 129  ***********************************************************************/
 130
 131 FLAC__BitWriter *FLAC__bitwriter_new(void)
 132 {
 133         FLAC__BitWriter *bw = calloc(1, sizeof(FLAC__BitWriter));
 134         /* note that calloc() sets all members to 0 for us */
 135         return bw;
 136 }
 137
 138 void FLAC__bitwriter_delete(FLAC__BitWriter *bw)
 139 {
 140         FLAC__ASSERT(0 != bw);
 141
 142         FLAC__bitwriter_free(bw);
 143         free(bw);
 144 }
 145
 146 /***********************************************************************
 147  *
 148  * Public class methods
 149  *
 150  ***********************************************************************/
 151
 152 FLAC__bool FLAC__bitwriter_init(FLAC__BitWriter *bw)
 153 {
 154         FLAC__ASSERT(0 != bw);
 155
 156         bw->words = bw->bits = 0;
 157         bw->capacity = FLAC__BITWRITER_DEFAULT_CAPACITY;
 158         bw->buffer = malloc(sizeof(uint32_t) * bw->capacity);
 159         if(bw->buffer == 0)
 160                 return false;
 161
 162         return true;
 163 }
 164
 165 void FLAC__bitwriter_free(FLAC__BitWriter *bw)
 166 {
 167         FLAC__ASSERT(0 != bw);
 168
 169         if(0 != bw->buffer)
 170                 free(bw->buffer);
 171         bw->buffer = 0;
 172         bw->capacity = 0;
 173         bw->words = bw->bits = 0;
 174 }
 175
 176 void FLAC__bitwriter_clear(FLAC__BitWriter *bw)
 177 {
 178         bw->words = bw->bits = 0;
 179 }
 180
 181 void FLAC__bitwriter_dump(const FLAC__BitWriter *bw, FILE *out)
 182 {
 183         unsigned i, j;
 184         if(bw == 0) {
 185                 fprintf(out, "bitwriter is NULL\n");
 186         }
 187         else {
 188                 fprintf(out, "bitwriter: capacity=%u words=%u bits=%u total_bits=%u\n", bw->capacity, bw->words, bw->bits, FLAC__TOTAL_BITS(bw));
 189
 190                 for(i = 0; i < bw->words; i++) {
 191                         fprintf(out, "%08X: ", i);
 192                         for(j = 0; j < FLAC__BITS_PER_WORD; j++)
 193                                 fprintf(out, "%01u", bw->buffer[i] & (1 << (FLAC__BITS_PER_WORD-j-1)) ? 1:0);
 194                         fprintf(out, "\n");
 195                 }
 196                 if(bw->bits > 0) {
 197                         fprintf(out, "%08X: ", i);
 198                         for(j = 0; j < bw->bits; j++)
 199                                 fprintf(out, "%01u", bw->accum & (1 << (bw->bits-j-1)) ? 1:0);
 200                         fprintf(out, "\n");
 201                 }
 202         }
 203 }
 204
 205 FLAC__bool FLAC__bitwriter_get_write_crc16(FLAC__BitWriter *bw, FLAC__uint16 *crc)
 206 {
 207         const FLAC__byte *buffer;
 208         size_t bytes;
 209
 210         FLAC__ASSERT((bw->bits & 7) == 0); /* assert that we're byte-aligned */
 211
 212         if(!FLAC__bitwriter_get_buffer(bw, &buffer, &bytes))
 213                 return false;
 214
 215         *crc = (FLAC__uint16)FLAC__crc16(buffer, bytes);
 216         FLAC__bitwriter_release_buffer(bw);
 217         return true;
 218 }
 219
 220 FLAC__bool FLAC__bitwriter_get_write_crc8(FLAC__BitWriter *bw, FLAC__byte *crc)
 221 {
 222         const FLAC__byte *buffer;
 223         size_t bytes;
 224
 225         FLAC__ASSERT((bw->bits & 7) == 0); /* assert that we're byte-aligned */
 226
 227         if(!FLAC__bitwriter_get_buffer(bw, &buffer, &bytes))
 228                 return false;
 229
 230         *crc = FLAC__crc8(buffer, bytes);
 231         FLAC__bitwriter_release_buffer(bw);
 232         return true;
 233 }
 234
 235 FLAC__bool FLAC__bitwriter_is_byte_aligned(const FLAC__BitWriter *bw)
 236 {
 237         return ((bw->bits & 7) == 0);
 238 }
 239
 240 unsigned FLAC__bitwriter_get_input_bits_unconsumed(const FLAC__BitWriter *bw)
 241 {
 242         return FLAC__TOTAL_BITS(bw);
 243 }
 244
 245 FLAC__bool FLAC__bitwriter_get_buffer(FLAC__BitWriter *bw, const FLAC__byte **buffer, size_t *bytes)
 246 {
 247         FLAC__ASSERT((bw->bits & 7) == 0);
 248         /* double protection */
 249         if(bw->bits & 7)
 250                 return false;
 251         /* if we have bits in the accumulator we have to flush those to the buffer first */
 252         if(bw->bits) {
 253                 FLAC__ASSERT(bw->words <= bw->capacity);
 254                 if(bw->words == bw->capacity && !bitwriter_grow_(bw, FLAC__BITS_PER_WORD))
 255                         return false;
 256                 /* append bits as complete word to buffer, but don't change bw->accum or bw->bits */
 257                 bw->buffer[bw->words] = SWAP_BE_WORD_TO_HOST(bw->accum << (FLAC__BITS_PER_WORD-bw->bits));
 258         }
 259         /* now we can just return what we have */
 260         *buffer = (FLAC__byte*)bw->buffer;
 261         *bytes = (FLAC__BYTES_PER_WORD * bw->words) + (bw->bits >> 3);
 262         return true;
 263 }
 264
 265 void FLAC__bitwriter_release_buffer(FLAC__BitWriter *bw)
 266 {
 267         /* nothing to do.  in the future, strict checking of a 'writer-is-in-
 268          * get-mode' flag could be added everywhere and then cleared here
 269          */
 270         (void)bw;
 271 }
 272
 273 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_zeroes(FLAC__BitWriter *bw, unsigned bits)
 274 {
 275         unsigned n;
 276
 277         FLAC__ASSERT(0 != bw);
 278         FLAC__ASSERT(0 != bw->buffer);
 279
 280         if(bits == 0)
 281                 return true;
 282         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 283         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 284                 return false;
 285         /* first part gets to word alignment */
 286         if(bw->bits) {
 287                 n = flac_min(FLAC__BITS_PER_WORD - bw->bits, bits);
 288                 bw->accum <<= n;
 289                 bits -= n;
 290                 bw->bits += n;
 291                 if(bw->bits == FLAC__BITS_PER_WORD) {
 292                         bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 293                         bw->bits = 0;
 294                 }
 295                 else
 296                         return true;
 297         }
 298         /* do whole words */
 299         while(bits >= FLAC__BITS_PER_WORD) {
 300                 bw->buffer[bw->words++] = 0;
 301                 bits -= FLAC__BITS_PER_WORD;
 302         }
 303         /* do any leftovers */
 304         if(bits > 0) {
 305                 bw->accum = 0;
 306                 bw->bits = bits;
 307         }
 308         return true;
 309 }
 310
 311 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_raw_uint32(FLAC__BitWriter *bw, FLAC__uint32 val, unsigned bits)
 312 {
 313         register unsigned left;
 314
 315         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 316         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 317
 318         FLAC__ASSERT(0 != bw);
 319         FLAC__ASSERT(0 != bw->buffer);
 320
 321         FLAC__ASSERT(bits <= 32);
 322         if(bits == 0)
 323                 return true;
 324
 325         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 326         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 327                 return false;
 328
 329         left = FLAC__BITS_PER_WORD - bw->bits;
 330         if(bits < left) {
 331                 bw->accum <<= bits;
 332                 bw->accum |= val;
 333                 bw->bits += bits;
 334         }
 335         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 */
 336                 bw->accum <<= left;
 337                 bw->accum |= val >> (bw->bits = bits - left);
 338                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 339                 bw->accum = val;
 340         }
 341         else {
 342                 bw->accum = val;
 343                 bw->bits = 0;
 344                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(val);
 345         }
 346
 347         return true;
 348 }
 349
 350 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_raw_int32(FLAC__BitWriter *bw, FLAC__int32 val, unsigned bits)
 351 {
 352         /* zero-out unused bits */
 353         if(bits < 32)
 354                 val &= (~(0xffffffff << bits));
 355
 356         return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, bits);
 357 }
 358
 359 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_raw_uint64(FLAC__BitWriter *bw, FLAC__uint64 val, unsigned bits)
 360 {
 361         /* this could be a little faster but it's not used for much */
 362         if(bits > 32) {
 363                 return
 364                         FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)(val>>32), bits-32) &&
 365                         FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, 32);
 366         }
 367         else
 368                 return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, bits);
 369 }
 370
 371 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_raw_uint32_little_endian(FLAC__BitWriter *bw, FLAC__uint32 val)
 372 {
 373         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
 374
 375         if(!FLAC__bitwriter_write_raw_uint32(bw, val & 0xff, 8))
 376                 return false;
 377         if(!FLAC__bitwriter_write_raw_uint32(bw, (val>>8) & 0xff, 8))
 378                 return false;
 379         if(!FLAC__bitwriter_write_raw_uint32(bw, (val>>16) & 0xff, 8))
 380                 return false;
 381         if(!FLAC__bitwriter_write_raw_uint32(bw, val>>24, 8))
 382                 return false;
 383
 384         return true;
 385 }
 386
 387 FLaC__INLINE FLAC__bool FLAC__bitwriter_write_byte_block(FLAC__BitWriter *bw, const FLAC__byte vals[], unsigned nvals)
 388 {
 389         unsigned i;
 390
 391         /* this could be faster but currently we don't need it to be since it's only used for writing metadata */
 392         for(i = 0; i < nvals; i++) {
 393                 if(!FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)(vals[i]), 8))
 394                         return false;
 395         }
 396
 397         return true;
 398 }
 399
 400 FLAC__bool FLAC__bitwriter_write_unary_unsigned(FLAC__BitWriter *bw, unsigned val)
 401 {
 402         if(val < 32)
 403                 return FLAC__bitwriter_write_raw_uint32(bw, 1, ++val);
 404         else
 405                 return
 406                         FLAC__bitwriter_write_zeroes(bw, val) &&
 407                         FLAC__bitwriter_write_raw_uint32(bw, 1, 1);
 408 }
 409
 410 unsigned FLAC__bitwriter_rice_bits(FLAC__int32 val, unsigned parameter)
 411 {
 412         FLAC__uint32 uval;
 413
 414         FLAC__ASSERT(parameter < sizeof(unsigned)*8);
 415
 416         /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 417         uval = (val<<1) ^ (val>>31);
 418
 419         return 1 + parameter + (uval >> parameter);
 420 }
 421
 422 #if 0 /* UNUSED */
 423 unsigned FLAC__bitwriter_golomb_bits_signed(int val, unsigned parameter)
 424 {
 425         unsigned bits, msbs, uval;
 426         unsigned k;
 427
 428         FLAC__ASSERT(parameter > 0);
 429
 430         /* fold signed to unsigned */
 431         if(val < 0)
 432                 uval = (unsigned)(((-(++val)) << 1) + 1);
 433         else
 434                 uval = (unsigned)(val << 1);
 435
 436         k = FLAC__bitmath_ilog2(parameter);
 437         if(parameter == 1u<<k) {
 438                 FLAC__ASSERT(k <= 30);
 439
 440                 msbs = uval >> k;
 441                 bits = 1 + k + msbs;
 442         }
 443         else {
 444                 unsigned q, r, d;
 445
 446                 d = (1 << (k+1)) - parameter;
 447                 q = uval / parameter;
 448                 r = uval - (q * parameter);
 449
 450                 bits = 1 + q + k;
 451                 if(r >= d)
 452                         bits++;
 453         }
 454         return bits;
 455 }
 456
 457 unsigned FLAC__bitwriter_golomb_bits_unsigned(unsigned uval, unsigned parameter)
 458 {
 459         unsigned bits, msbs;
 460         unsigned k;
 461
 462         FLAC__ASSERT(parameter > 0);
 463
 464         k = FLAC__bitmath_ilog2(parameter);
 465         if(parameter == 1u<<k) {
 466                 FLAC__ASSERT(k <= 30);
 467
 468                 msbs = uval >> k;
 469                 bits = 1 + k + msbs;
 470         }
 471         else {
 472                 unsigned q, r, d;
 473
 474                 d = (1 << (k+1)) - parameter;
 475                 q = uval / parameter;
 476                 r = uval - (q * parameter);
 477
 478                 bits = 1 + q + k;
 479                 if(r >= d)
 480                         bits++;
 481         }
 482         return bits;
 483 }
 484 #endif /* UNUSED */
 485
 486 FLAC__bool FLAC__bitwriter_write_rice_signed(FLAC__BitWriter *bw, FLAC__int32 val, unsigned parameter)
 487 {
 488         unsigned total_bits, interesting_bits, msbs;
 489         FLAC__uint32 uval, pattern;
 490
 491         FLAC__ASSERT(0 != bw);
 492         FLAC__ASSERT(0 != bw->buffer);
 493         FLAC__ASSERT(parameter < 8*sizeof(uval));
 494
 495         /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 496         uval = (val<<1) ^ (val>>31);
 497
 498         msbs = uval >> parameter;
 499         interesting_bits = 1 + parameter;
 500         total_bits = interesting_bits + msbs;
 501         pattern = 1 << parameter; /* the unary end bit */
 502         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
 503
 504         if(total_bits <= 32)
 505                 return FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits);
 506         else
 507                 return
 508                         FLAC__bitwriter_write_zeroes(bw, msbs) && /* write the unary MSBs */
 509                         FLAC__bitwriter_write_raw_uint32(bw, pattern, interesting_bits); /* write the unary end bit and binary LSBs */
 510 }
 511
 512 FLAC__bool FLAC__bitwriter_write_rice_signed_block(FLAC__BitWriter *bw, const FLAC__int32 *vals, unsigned nvals, unsigned parameter)
 513 {
 514         const FLAC__uint32 mask1 = FLAC__WORD_ALL_ONES << parameter; /* we val|=mask1 to set the stop bit above it... */
 515         const FLAC__uint32 mask2 = FLAC__WORD_ALL_ONES >> (31-parameter); /* ...then mask off the bits above the stop bit with val&=mask2*/
 516         FLAC__uint32 uval;
 517         unsigned left;
 518         const unsigned lsbits = 1 + parameter;
 519         unsigned msbits;
 520
 521         FLAC__ASSERT(0 != bw);
 522         FLAC__ASSERT(0 != bw->buffer);
 523         FLAC__ASSERT(parameter < 8*sizeof(uint32_t)-1);
 524         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 525         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 526
 527         while(nvals) {
 528                 /* fold signed to unsigned; actual formula is: negative(v)? -2v-1 : 2v */
 529                 uval = (*vals<<1) ^ (*vals>>31);
 530
 531                 msbits = uval >> parameter;
 532
 533 #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) */
 534                 if(bw->bits && bw->bits + msbits + lsbits <= FLAC__BITS_PER_WORD) { /* i.e. if the whole thing fits in the current uint32_t */
 535                         /* ^^^ if bw->bits is 0 then we may have filled the buffer and have no free uint32_t to work in */
 536                         bw->bits = bw->bits + msbits + lsbits;
 537                         uval |= mask1; /* set stop bit */
 538                         uval &= mask2; /* mask off unused top bits */
 539                         /* NOT: bw->accum <<= msbits + lsbits because msbits+lsbits could be 32, then the shift would be a NOP */
 540                         bw->accum <<= msbits;
 541                         bw->accum <<= lsbits;
 542                         bw->accum |= uval;
 543                         if(bw->bits == FLAC__BITS_PER_WORD) {
 544                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 545                                 bw->bits = 0;
 546                                 /* burying the capacity check down here means we have to grow the buffer a little if there are more vals to do */
 547                                 if(bw->capacity <= bw->words && nvals > 1 && !bitwriter_grow_(bw, 1)) {
 548                                         FLAC__ASSERT(bw->capacity == bw->words);
 549                                         return false;
 550                                 }
 551                         }
 552                 }
 553                 else {
 554 #elif 1 /*@@@@@@ OPT: try this version with MSVC6 to see if better, not much difference for gcc-4 */
 555                 if(bw->bits && bw->bits + msbits + lsbits < FLAC__BITS_PER_WORD) { /* i.e. if the whole thing fits in the current uint32_t */
 556                         /* ^^^ if bw->bits is 0 then we may have filled the buffer and have no free uint32_t to work in */
 557                         bw->bits = bw->bits + msbits + lsbits;
 558                         uval |= mask1; /* set stop bit */
 559                         uval &= mask2; /* mask off unused top bits */
 560                         bw->accum <<= msbits + lsbits;
 561                         bw->accum |= uval;
 562                 }
 563                 else {
 564 #endif
 565                         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+msbits+lsbits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 566                         /* OPT: pessimism may cause flurry of false calls to grow_ which eat up all savings before it */
 567                         if(bw->capacity <= bw->words + bw->bits + msbits + 1/*lsbits always fit in 1 uint32_t*/ && !bitwriter_grow_(bw, msbits+lsbits))
 568                                 return false;
 569
 570                         if(msbits) {
 571                                 /* first part gets to word alignment */
 572                                 if(bw->bits) {
 573                                         left = FLAC__BITS_PER_WORD - bw->bits;
 574                                         if(msbits < left) {
 575                                                 bw->accum <<= msbits;
 576                                                 bw->bits += msbits;
 577                                                 goto break1;
 578                                         }
 579                                         else {
 580                                                 bw->accum <<= left;
 581                                                 msbits -= left;
 582                                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 583                                                 bw->bits = 0;
 584                                         }
 585                                 }
 586                                 /* do whole words */
 587                                 while(msbits >= FLAC__BITS_PER_WORD) {
 588                                         bw->buffer[bw->words++] = 0;
 589                                         msbits -= FLAC__BITS_PER_WORD;
 590                                 }
 591                                 /* do any leftovers */
 592                                 if(msbits > 0) {
 593                                         bw->accum = 0;
 594                                         bw->bits = msbits;
 595                                 }
 596                         }
 597 break1:
 598                         uval |= mask1; /* set stop bit */
 599                         uval &= mask2; /* mask off unused top bits */
 600
 601                         left = FLAC__BITS_PER_WORD - bw->bits;
 602                         if(lsbits < left) {
 603                                 bw->accum <<= lsbits;
 604                                 bw->accum |= uval;
 605                                 bw->bits += lsbits;
 606                         }
 607                         else {
 608                                 /* if bw->bits == 0, left==FLAC__BITS_PER_WORD which will always
 609                                  * be > lsbits (because of previous assertions) so it would have
 610                                  * triggered the (lsbits<left) case above.
 611                                  */
 612                                 FLAC__ASSERT(bw->bits);
 613                                 FLAC__ASSERT(left < FLAC__BITS_PER_WORD);
 614                                 bw->accum <<= left;
 615                                 bw->accum |= uval >> (bw->bits = lsbits - left);
 616                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 617                                 bw->accum = uval;
 618                         }
 619 #if 1
 620                 }
 621 #endif
 622                 vals++;
 623                 nvals--;
 624         }
 625         return true;
 626 }
 627
 628 #if 0 /* UNUSED */
 629 FLAC__bool FLAC__bitwriter_write_golomb_signed(FLAC__BitWriter *bw, int val, unsigned parameter)
 630 {
 631         unsigned total_bits, msbs, uval;
 632         unsigned k;
 633
 634         FLAC__ASSERT(0 != bw);
 635         FLAC__ASSERT(0 != bw->buffer);
 636         FLAC__ASSERT(parameter > 0);
 637
 638         /* fold signed to unsigned */
 639         if(val < 0)
 640                 uval = (unsigned)(((-(++val)) << 1) + 1);
 641         else
 642                 uval = (unsigned)(val << 1);
 643
 644         k = FLAC__bitmath_ilog2(parameter);
 645         if(parameter == 1u<<k) {
 646                 unsigned pattern;
 647
 648                 FLAC__ASSERT(k <= 30);
 649
 650                 msbs = uval >> k;
 651                 total_bits = 1 + k + msbs;
 652                 pattern = 1 << k; /* the unary end bit */
 653                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 654
 655                 if(total_bits <= 32) {
 656                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 657                                 return false;
 658                 }
 659                 else {
 660                         /* write the unary MSBs */
 661                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 662                                 return false;
 663                         /* write the unary end bit and binary LSBs */
 664                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 665                                 return false;
 666                 }
 667         }
 668         else {
 669                 unsigned q, r, d;
 670
 671                 d = (1 << (k+1)) - parameter;
 672                 q = uval / parameter;
 673                 r = uval - (q * parameter);
 674                 /* write the unary MSBs */
 675                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 676                         return false;
 677                 /* write the unary end bit */
 678                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 679                         return false;
 680                 /* write the binary LSBs */
 681                 if(r >= d) {
 682                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 683                                 return false;
 684                 }
 685                 else {
 686                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 687                                 return false;
 688                 }
 689         }
 690         return true;
 691 }
 692
 693 FLAC__bool FLAC__bitwriter_write_golomb_unsigned(FLAC__BitWriter *bw, unsigned uval, unsigned parameter)
 694 {
 695         unsigned total_bits, msbs;
 696         unsigned k;
 697
 698         FLAC__ASSERT(0 != bw);
 699         FLAC__ASSERT(0 != bw->buffer);
 700         FLAC__ASSERT(parameter > 0);
 701
 702         k = FLAC__bitmath_ilog2(parameter);
 703         if(parameter == 1u<<k) {
 704                 unsigned pattern;
 705
 706                 FLAC__ASSERT(k <= 30);
 707
 708                 msbs = uval >> k;
 709                 total_bits = 1 + k + msbs;
 710                 pattern = 1 << k; /* the unary end bit */
 711                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 712
 713                 if(total_bits <= 32) {
 714                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 715                                 return false;
 716                 }
 717                 else {
 718                         /* write the unary MSBs */
 719                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 720                                 return false;
 721                         /* write the unary end bit and binary LSBs */
 722                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 723                                 return false;
 724                 }
 725         }
 726         else {
 727                 unsigned q, r, d;
 728
 729                 d = (1 << (k+1)) - parameter;
 730                 q = uval / parameter;
 731                 r = uval - (q * parameter);
 732                 /* write the unary MSBs */
 733                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 734                         return false;
 735                 /* write the unary end bit */
 736                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 737                         return false;
 738                 /* write the binary LSBs */
 739                 if(r >= d) {
 740                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 741                                 return false;
 742                 }
 743                 else {
 744                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 745                                 return false;
 746                 }
 747         }
 748         return true;
 749 }
 750 #endif /* UNUSED */
 751
 752 FLAC__bool FLAC__bitwriter_write_utf8_uint32(FLAC__BitWriter *bw, FLAC__uint32 val)
 753 {
 754         FLAC__bool ok = 1;
 755
 756         FLAC__ASSERT(0 != bw);
 757         FLAC__ASSERT(0 != bw->buffer);
 758
 759         FLAC__ASSERT(!(val & 0x80000000)); /* this version only handles 31 bits */
 760
 761         if(val < 0x80) {
 762                 return FLAC__bitwriter_write_raw_uint32(bw, val, 8);
 763         }
 764         else if(val < 0x800) {
 765                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xC0 | (val>>6), 8);
 766                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 767         }
 768         else if(val < 0x10000) {
 769                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xE0 | (val>>12), 8);
 770                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 771                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 772         }
 773         else if(val < 0x200000) {
 774                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF0 | (val>>18), 8);
 775                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 776                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 777                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 778         }
 779         else if(val < 0x4000000) {
 780                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF8 | (val>>24), 8);
 781                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>18)&0x3F), 8);
 782                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 783                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 784                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 785         }
 786         else {
 787                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFC | (val>>30), 8);
 788                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>24)&0x3F), 8);
 789                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>18)&0x3F), 8);
 790                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>12)&0x3F), 8);
 791                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | ((val>>6)&0x3F), 8);
 792                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (val&0x3F), 8);
 793         }
 794
 795         return ok;
 796 }
 797
 798 FLAC__bool FLAC__bitwriter_write_utf8_uint64(FLAC__BitWriter *bw, FLAC__uint64 val)
 799 {
 800         FLAC__bool ok = 1;
 801
 802         FLAC__ASSERT(0 != bw);
 803         FLAC__ASSERT(0 != bw->buffer);
 804
 805         FLAC__ASSERT(!(val & FLAC__U64L(0xFFFFFFF000000000))); /* this version only handles 36 bits */
 806
 807         if(val < 0x80) {
 808                 return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, 8);
 809         }
 810         else if(val < 0x800) {
 811                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xC0 | (FLAC__uint32)(val>>6), 8);
 812                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 813         }
 814         else if(val < 0x10000) {
 815                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xE0 | (FLAC__uint32)(val>>12), 8);
 816                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 817                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 818         }
 819         else if(val < 0x200000) {
 820                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF0 | (FLAC__uint32)(val>>18), 8);
 821                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 822                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 823                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 824         }
 825         else if(val < 0x4000000) {
 826                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xF8 | (FLAC__uint32)(val>>24), 8);
 827                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 828                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 829                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 830                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 831         }
 832         else if(val < 0x80000000) {
 833                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFC | (FLAC__uint32)(val>>30), 8);
 834                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 835                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 836                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 837                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 838                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 839         }
 840         else {
 841                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0xFE, 8);
 842                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>30)&0x3F), 8);
 843                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 844                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 845                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 846                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 847                 ok &= FLAC__bitwriter_write_raw_uint32(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 848         }
 849
 850         return ok;
 851 }
 852
 853 FLAC__bool FLAC__bitwriter_zero_pad_to_byte_boundary(FLAC__BitWriter *bw)
 854 {
 855         /* 0-pad to byte boundary */
 856         if(bw->bits & 7u)
 857                 return FLAC__bitwriter_write_zeroes(bw, 8 - (bw->bits & 7u));
 858         else
 859                 return true;
 860 }