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