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