src/libFLAC/bitwriter.c

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