src/libFLAC/bitwriter.c

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