src/libFLAC/bitwriter.c

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