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