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