FLAC/src/bitwriter.c

   1 /* libFLAC - Free Lossless Audio Codec library
   2  * Copyright (C) 2000-2009  Josh Coalson
   3  * Copyright (C) 2011-2022  Xiph.Org Foundation
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *
  12  * - Redistributions in binary form must reproduce the above copyright
  13  * notice, this list of conditions and the following disclaimer in the
  14  * documentation and/or other materials provided with the distribution.
  15  *
  16  * - Neither the name of the Xiph.org Foundation nor the names of its
  17  * contributors may be used to endorse or promote products derived from
  18  * this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
  24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #ifdef HAVE_CONFIG_H
  34 #  include <config.h>
  35 #endif
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include "private/bitwriter.h"
  40 #include "private/crc.h"
  41 #include "private/format.h"
  42 #include "private/macros.h"
  43 #include "private/stream_encoder.h"
  44 #include "FLAC/assert.h"
  45 #include "share/alloc.h"
  46 #include "share/compat.h"
  47 #include "share/endswap.h"
  48
  49 /* Things should be fastest when this matches the machine word size */
  50 /* WATCHOUT: if you change this you must also change the following #defines down to SWAP_BE_WORD_TO_HOST below to match */
  51 /* WATCHOUT: there are a few places where the code will not work unless bwword is >= 32 bits wide */
  52
  53 #if (ENABLE_64_BIT_WORDS == 0)
  54
  55 typedef FLAC__uint32 bwword;
  56 #define FLAC__BYTES_PER_WORD 4          /* sizeof bwword */
  57 #define FLAC__BITS_PER_WORD 32
  58 /* SWAP_BE_WORD_TO_HOST swaps bytes in a bwword (which is always big-endian) if necessary to match host byte order */
  59 #if WORDS_BIGENDIAN
  60 #define SWAP_BE_WORD_TO_HOST(x) (x)
  61 #else
  62 #define SWAP_BE_WORD_TO_HOST(x) ENDSWAP_32(x)
  63 #endif
  64
  65 #else
  66
  67 typedef FLAC__uint64 bwword;
  68 #define FLAC__BYTES_PER_WORD 8          /* sizeof bwword */
  69 #define FLAC__BITS_PER_WORD 64
  70 /* SWAP_BE_WORD_TO_HOST swaps bytes in a bwword (which is always big-endian) if necessary to match host byte order */
  71 #if WORDS_BIGENDIAN
  72 #define SWAP_BE_WORD_TO_HOST(x) (x)
  73 #else
  74 #define SWAP_BE_WORD_TO_HOST(x) ENDSWAP_64(x)
  75 #endif
  76
  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 uint32_t FLAC__BITWRITER_DEFAULT_CAPACITY = 32768u / sizeof(bwword); /* size in words */
  86 /* When growing, increment 4K at a time */
  87 static const uint32_t 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 struct FLAC__BitWriter {
  93         bwword *buffer;
  94         bwword accum; /* accumulator; bits are right-justified; when full, accum is appended to buffer */
  95         uint32_t capacity; /* capacity of buffer in words */
  96         uint32_t words; /* # of complete words in buffer */
  97         uint32_t bits; /* # of used bits in accum */
  98 };
  99
 100 /* * WATCHOUT: The current implementation only grows the buffer. */
 101 #ifndef __SUNPRO_C
 102 static
 103 #endif
 104 FLAC__bool bitwriter_grow_(FLAC__BitWriter *bw, uint32_t bits_to_add)
 105 {
 106         uint32_t new_capacity;
 107         bwword *new_buffer;
 108
 109         FLAC__ASSERT(0 != bw);
 110         FLAC__ASSERT(0 != bw->buffer);
 111
 112         /* calculate total words needed to store 'bits_to_add' additional bits */
 113         new_capacity = bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD);
 114
 115         /* it's possible (due to pessimism in the growth estimation that
 116          * leads to this call) that we don't actually need to grow
 117          */
 118         if(bw->capacity >= new_capacity)
 119                 return true;
 120
 121         if(new_capacity * sizeof(bwword) > (1u << FLAC__STREAM_METADATA_LENGTH_LEN))
 122                 /* Requested new capacity is larger than the largest possible metadata block,
 123                  * which is also larger than the largest sane framesize. That means something
 124                  * went very wrong somewhere and previous checks failed.
 125                  * To prevent chrashing, give up */
 126                 return false;
 127
 128         /* round up capacity increase to the nearest FLAC__BITWRITER_DEFAULT_INCREMENT */
 129         if((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT)
 130                 new_capacity += FLAC__BITWRITER_DEFAULT_INCREMENT - ((new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 131         /* make sure we got everything right */
 132         FLAC__ASSERT(0 == (new_capacity - bw->capacity) % FLAC__BITWRITER_DEFAULT_INCREMENT);
 133         FLAC__ASSERT(new_capacity > bw->capacity);
 134         FLAC__ASSERT(new_capacity >= bw->words + ((bw->bits + bits_to_add + FLAC__BITS_PER_WORD - 1) / FLAC__BITS_PER_WORD));
 135
 136         new_buffer = safe_realloc_nofree_mul_2op_(bw->buffer, sizeof(bwword), /*times*/new_capacity);
 137         if(new_buffer == 0)
 138                 return false;
 139         bw->buffer = new_buffer;
 140         bw->capacity = new_capacity;
 141         return true;
 142 }
 143
 144
 145 /***********************************************************************
 146  *
 147  * Class constructor/destructor
 148  *
 149  ***********************************************************************/
 150
 151 FLAC__BitWriter *FLAC__bitwriter_new(void)
 152 {
 153         FLAC__BitWriter *bw = calloc(1, sizeof(FLAC__BitWriter));
 154         /* note that calloc() sets all members to 0 for us */
 155         return bw;
 156 }
 157
 158 void FLAC__bitwriter_delete(FLAC__BitWriter *bw)
 159 {
 160         FLAC__ASSERT(0 != bw);
 161
 162         FLAC__bitwriter_free(bw);
 163         free(bw);
 164 }
 165
 166 /***********************************************************************
 167  *
 168  * Public class methods
 169  *
 170  ***********************************************************************/
 171
 172 FLAC__bool FLAC__bitwriter_init(FLAC__BitWriter *bw)
 173 {
 174         FLAC__ASSERT(0 != bw);
 175
 176         bw->words = bw->bits = 0;
 177         bw->capacity = FLAC__BITWRITER_DEFAULT_CAPACITY;
 178         bw->buffer = malloc(sizeof(bwword) * bw->capacity);
 179         if(bw->buffer == 0)
 180                 return false;
 181
 182         return true;
 183 }
 184
 185 void FLAC__bitwriter_free(FLAC__BitWriter *bw)
 186 {
 187         FLAC__ASSERT(0 != bw);
 188
 189         if(0 != bw->buffer)
 190                 free(bw->buffer);
 191         bw->buffer = 0;
 192         bw->capacity = 0;
 193         bw->words = bw->bits = 0;
 194 }
 195
 196 void FLAC__bitwriter_clear(FLAC__BitWriter *bw)
 197 {
 198         bw->words = bw->bits = 0;
 199 }
 200
 201 void FLAC__bitwriter_dump(const FLAC__BitWriter *bw, FILE *out)
 202 {
 203         uint32_t i, j;
 204         if(bw == 0) {
 205                 fprintf(out, "bitwriter is NULL\n");
 206         }
 207         else {
 208                 fprintf(out, "bitwriter: capacity=%u words=%u bits=%u total_bits=%u\n", bw->capacity, bw->words, bw->bits, FLAC__TOTAL_BITS(bw));
 209
 210                 for(i = 0; i < bw->words; i++) {
 211                         fprintf(out, "%08X: ", i);
 212                         for(j = 0; j < FLAC__BITS_PER_WORD; j++)
 213                                 fprintf(out, "%01d", bw->buffer[i] & ((bwword)1 << (FLAC__BITS_PER_WORD-j-1)) ? 1:0);
 214                         fprintf(out, "\n");
 215                 }
 216                 if(bw->bits > 0) {
 217                         fprintf(out, "%08X: ", i);
 218                         for(j = 0; j < bw->bits; j++)
 219                                 fprintf(out, "%01d", bw->accum & ((bwword)1 << (bw->bits-j-1)) ? 1:0);
 220                         fprintf(out, "\n");
 221                 }
 222         }
 223 }
 224
 225 FLAC__bool FLAC__bitwriter_get_write_crc16(FLAC__BitWriter *bw, FLAC__uint16 *crc)
 226 {
 227         const FLAC__byte *buffer;
 228         size_t bytes;
 229
 230         FLAC__ASSERT((bw->bits & 7) == 0); /* assert that we're byte-aligned */
 231
 232         if(!FLAC__bitwriter_get_buffer(bw, &buffer, &bytes))
 233                 return false;
 234
 235         *crc = (FLAC__uint16)FLAC__crc16(buffer, bytes);
 236         FLAC__bitwriter_release_buffer(bw);
 237         return true;
 238 }
 239
 240 FLAC__bool FLAC__bitwriter_get_write_crc8(FLAC__BitWriter *bw, FLAC__byte *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__crc8(buffer, bytes);
 251         FLAC__bitwriter_release_buffer(bw);
 252         return true;
 253 }
 254
 255 FLAC__bool FLAC__bitwriter_is_byte_aligned(const FLAC__BitWriter *bw)
 256 {
 257         return ((bw->bits & 7) == 0);
 258 }
 259
 260 uint32_t FLAC__bitwriter_get_input_bits_unconsumed(const FLAC__BitWriter *bw)
 261 {
 262         return FLAC__TOTAL_BITS(bw);
 263 }
 264
 265 FLAC__bool FLAC__bitwriter_get_buffer(FLAC__BitWriter *bw, const FLAC__byte **buffer, size_t *bytes)
 266 {
 267         FLAC__ASSERT((bw->bits & 7) == 0);
 268         /* double protection */
 269         if(bw->bits & 7)
 270                 return false;
 271         /* if we have bits in the accumulator we have to flush those to the buffer first */
 272         if(bw->bits) {
 273                 FLAC__ASSERT(bw->words <= bw->capacity);
 274                 if(bw->words == bw->capacity && !bitwriter_grow_(bw, FLAC__BITS_PER_WORD))
 275                         return false;
 276                 /* append bits as complete word to buffer, but don't change bw->accum or bw->bits */
 277                 bw->buffer[bw->words] = SWAP_BE_WORD_TO_HOST(bw->accum << (FLAC__BITS_PER_WORD-bw->bits));
 278         }
 279         /* now we can just return what we have */
 280         *buffer = (FLAC__byte*)bw->buffer;
 281         *bytes = (FLAC__BYTES_PER_WORD * bw->words) + (bw->bits >> 3);
 282         return true;
 283 }
 284
 285 void FLAC__bitwriter_release_buffer(FLAC__BitWriter *bw)
 286 {
 287         /* nothing to do.  in the future, strict checking of a 'writer-is-in-
 288          * get-mode' flag could be added everywhere and then cleared here
 289          */
 290         (void)bw;
 291 }
 292
 293 inline FLAC__bool FLAC__bitwriter_write_zeroes(FLAC__BitWriter *bw, uint32_t bits)
 294 {
 295         uint32_t n;
 296
 297         FLAC__ASSERT(0 != bw);
 298         FLAC__ASSERT(0 != bw->buffer);
 299
 300         if(bits == 0)
 301                 return true;
 302         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 303         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 304                 return false;
 305         /* first part gets to word alignment */
 306         if(bw->bits) {
 307                 n = flac_min(FLAC__BITS_PER_WORD - bw->bits, bits);
 308                 bw->accum <<= n;
 309                 bits -= n;
 310                 bw->bits += n;
 311                 if(bw->bits == FLAC__BITS_PER_WORD) {
 312                         bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 313                         bw->bits = 0;
 314                 }
 315                 else
 316                         return true;
 317         }
 318         /* do whole words */
 319         while(bits >= FLAC__BITS_PER_WORD) {
 320                 bw->buffer[bw->words++] = 0;
 321                 bits -= FLAC__BITS_PER_WORD;
 322         }
 323         /* do any leftovers */
 324         if(bits > 0) {
 325                 bw->accum = 0;
 326                 bw->bits = bits;
 327         }
 328         return true;
 329 }
 330
 331 static inline FLAC__bool FLAC__bitwriter_write_raw_uint32_nocheck(FLAC__BitWriter *bw, FLAC__uint32 val, uint32_t bits)
 332 {
 333         register uint32_t left;
 334
 335         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 336         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 337
 338         if(bw == 0 || bw->buffer == 0)
 339                 return false;
 340
 341         if (bits > 32)
 342                 return false;
 343
 344         if(bits == 0)
 345                 return true;
 346
 347         FLAC__ASSERT((bits == 32) || (val>>bits == 0));
 348
 349         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+bits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 350         if(bw->capacity <= bw->words + bits && !bitwriter_grow_(bw, bits))
 351                 return false;
 352
 353         left = FLAC__BITS_PER_WORD - bw->bits;
 354         if(bits < left) {
 355                 bw->accum <<= bits;
 356                 bw->accum |= val;
 357                 bw->bits += bits;
 358         }
 359         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 */
 360                 bw->accum <<= left;
 361                 bw->accum |= val >> (bw->bits = bits - left);
 362                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 363                 bw->accum = val; /* unused top bits can contain garbage */
 364         }
 365         else { /* at this point bits == FLAC__BITS_PER_WORD == 32  and  bw->bits == 0 */
 366                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST((bwword)val);
 367         }
 368
 369         return true;
 370 }
 371
 372 inline FLAC__bool FLAC__bitwriter_write_raw_uint32(FLAC__BitWriter *bw, FLAC__uint32 val, uint32_t bits)
 373 {
 374         /* check that unused bits are unset */
 375         if((bits < 32) && (val>>bits != 0))
 376                 return false;
 377
 378         return FLAC__bitwriter_write_raw_uint32_nocheck(bw, val, bits);
 379 }
 380
 381 inline FLAC__bool FLAC__bitwriter_write_raw_int32(FLAC__BitWriter *bw, FLAC__int32 val, uint32_t bits)
 382 {
 383         /* zero-out unused bits */
 384         if(bits < 32)
 385                 val &= (~(0xffffffff << bits));
 386
 387         return FLAC__bitwriter_write_raw_uint32_nocheck(bw, (FLAC__uint32)val, bits);
 388 }
 389
 390 inline FLAC__bool FLAC__bitwriter_write_raw_uint64(FLAC__BitWriter *bw, FLAC__uint64 val, uint32_t bits)
 391 {
 392         /* this could be a little faster but it's not used for much */
 393         if(bits > 32) {
 394                 return
 395                         FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)(val>>32), bits-32) &&
 396                         FLAC__bitwriter_write_raw_uint32_nocheck(bw, (FLAC__uint32)val, 32);
 397         }
 398         else
 399                 return FLAC__bitwriter_write_raw_uint32(bw, (FLAC__uint32)val, bits);
 400 }
 401
 402 inline FLAC__bool FLAC__bitwriter_write_raw_int64(FLAC__BitWriter *bw, FLAC__int64 val, uint32_t bits)
 403 {
 404         FLAC__uint64 uval = val;
 405         /* zero-out unused bits */
 406         if(bits < 64)
 407                 uval &= (~(UINT64_MAX << bits));
 408         return FLAC__bitwriter_write_raw_uint64(bw, uval, bits);
 409 }
 410
 411 inline FLAC__bool FLAC__bitwriter_write_raw_uint32_little_endian(FLAC__BitWriter *bw, FLAC__uint32 val)
 412 {
 413         /* this doesn't need to be that fast as currently it is only used for vorbis comments */
 414
 415         if(!FLAC__bitwriter_write_raw_uint32_nocheck(bw, val & 0xff, 8))
 416                 return false;
 417         if(!FLAC__bitwriter_write_raw_uint32_nocheck(bw, (val>>8) & 0xff, 8))
 418                 return false;
 419         if(!FLAC__bitwriter_write_raw_uint32_nocheck(bw, (val>>16) & 0xff, 8))
 420                 return false;
 421         if(!FLAC__bitwriter_write_raw_uint32_nocheck(bw, val>>24, 8))
 422                 return false;
 423
 424         return true;
 425 }
 426
 427 inline FLAC__bool FLAC__bitwriter_write_byte_block(FLAC__BitWriter *bw, const FLAC__byte vals[], uint32_t nvals)
 428 {
 429         uint32_t i;
 430
 431         /* grow capacity upfront to prevent constant reallocation during writes */
 432         if(bw->capacity <= bw->words + nvals / (FLAC__BITS_PER_WORD / 8) + 1 && !bitwriter_grow_(bw, nvals * 8))
 433                 return false;
 434
 435         /* this could be faster but currently we don't need it to be since it's only used for writing metadata */
 436         for(i = 0; i < nvals; i++) {
 437                 if(!FLAC__bitwriter_write_raw_uint32_nocheck(bw, (FLAC__uint32)(vals[i]), 8))
 438                         return false;
 439         }
 440
 441         return true;
 442 }
 443
 444 FLAC__bool FLAC__bitwriter_write_unary_unsigned(FLAC__BitWriter *bw, uint32_t val)
 445 {
 446         if(val < 32)
 447                 return FLAC__bitwriter_write_raw_uint32_nocheck(bw, 1, ++val);
 448         else
 449                 return
 450                         FLAC__bitwriter_write_zeroes(bw, val) &&
 451                         FLAC__bitwriter_write_raw_uint32_nocheck(bw, 1, 1);
 452 }
 453
 454 uint32_t FLAC__bitwriter_rice_bits(FLAC__int32 val, uint32_t parameter)
 455 {
 456         FLAC__uint32 uval;
 457
 458         FLAC__ASSERT(parameter < 32);
 459
 460         /* fold signed to uint32_t; actual formula is: negative(v)? -2v-1 : 2v */
 461         uval = val;
 462         uval <<= 1;
 463         uval ^= (val>>31);
 464
 465         return 1 + parameter + (uval >> parameter);
 466 }
 467
 468 #if 0 /* UNUSED */
 469 uint32_t FLAC__bitwriter_golomb_bits_signed(int val, uint32_t parameter)
 470 {
 471         uint32_t bits, msbs, uval;
 472         uint32_t k;
 473
 474         FLAC__ASSERT(parameter > 0);
 475
 476         /* fold signed to uint32_t */
 477         if(val < 0)
 478                 uval = (uint32_t)(((-(++val)) << 1) + 1);
 479         else
 480                 uval = (uint32_t)(val << 1);
 481
 482         k = FLAC__bitmath_ilog2(parameter);
 483         if(parameter == 1u<<k) {
 484                 FLAC__ASSERT(k <= 30);
 485
 486                 msbs = uval >> k;
 487                 bits = 1 + k + msbs;
 488         }
 489         else {
 490                 uint32_t q, r, d;
 491
 492                 d = (1 << (k+1)) - parameter;
 493                 q = uval / parameter;
 494                 r = uval - (q * parameter);
 495
 496                 bits = 1 + q + k;
 497                 if(r >= d)
 498                         bits++;
 499         }
 500         return bits;
 501 }
 502
 503 uint32_t FLAC__bitwriter_golomb_bits_unsigned(uint32_t uval, uint32_t parameter)
 504 {
 505         uint32_t bits, msbs;
 506         uint32_t k;
 507
 508         FLAC__ASSERT(parameter > 0);
 509
 510         k = FLAC__bitmath_ilog2(parameter);
 511         if(parameter == 1u<<k) {
 512                 FLAC__ASSERT(k <= 30);
 513
 514                 msbs = uval >> k;
 515                 bits = 1 + k + msbs;
 516         }
 517         else {
 518                 uint32_t q, r, d;
 519
 520                 d = (1 << (k+1)) - parameter;
 521                 q = uval / parameter;
 522                 r = uval - (q * parameter);
 523
 524                 bits = 1 + q + k;
 525                 if(r >= d)
 526                         bits++;
 527         }
 528         return bits;
 529 }
 530 #endif /* UNUSED */
 531
 532 FLAC__bool FLAC__bitwriter_write_rice_signed(FLAC__BitWriter *bw, FLAC__int32 val, uint32_t parameter)
 533 {
 534         uint32_t total_bits, interesting_bits, msbs;
 535         FLAC__uint32 uval, pattern;
 536
 537         FLAC__ASSERT(0 != bw);
 538         FLAC__ASSERT(0 != bw->buffer);
 539         FLAC__ASSERT(parameter < 32);
 540
 541         /* fold signed to uint32_t; actual formula is: negative(v)? -2v-1 : 2v */
 542         uval = val;
 543         uval <<= 1;
 544         uval ^= (val>>31);
 545
 546         msbs = uval >> parameter;
 547         interesting_bits = 1 + parameter;
 548         total_bits = interesting_bits + msbs;
 549         pattern = 1 << parameter; /* the unary end bit */
 550         pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
 551
 552         if(total_bits <= 32)
 553                 return FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits);
 554         else
 555                 return
 556                         FLAC__bitwriter_write_zeroes(bw, msbs) && /* write the unary MSBs */
 557                         FLAC__bitwriter_write_raw_uint32(bw, pattern, interesting_bits); /* write the unary end bit and binary LSBs */
 558 }
 559
 560 FLAC__bool FLAC__bitwriter_write_rice_signed_block(FLAC__BitWriter *bw, const FLAC__int32 *vals, uint32_t nvals, uint32_t parameter)
 561 {
 562         const FLAC__uint32 mask1 = (FLAC__uint32)0xffffffff << parameter; /* we val|=mask1 to set the stop bit above it... */
 563         const FLAC__uint32 mask2 = (FLAC__uint32)0xffffffff >> (31-parameter); /* ...then mask off the bits above the stop bit with val&=mask2 */
 564         FLAC__uint32 uval;
 565         uint32_t left;
 566         const uint32_t lsbits = 1 + parameter;
 567         uint32_t msbits, total_bits;
 568
 569         FLAC__ASSERT(0 != bw);
 570         FLAC__ASSERT(0 != bw->buffer);
 571         FLAC__ASSERT(parameter < 31);
 572         /* WATCHOUT: code does not work with <32bit words; we can make things much faster with this assertion */
 573         FLAC__ASSERT(FLAC__BITS_PER_WORD >= 32);
 574
 575         while(nvals) {
 576                 /* fold signed to uint32_t; actual formula is: negative(v)? -2v-1 : 2v */
 577                 uval = *vals;
 578                 uval <<= 1;
 579                 uval ^= (*vals>>31);
 580
 581                 msbits = uval >> parameter;
 582                 total_bits = lsbits + msbits;
 583
 584                 if(bw->bits && bw->bits + total_bits < 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 += total_bits;
 587                         uval |= mask1; /* set stop bit */
 588                         uval &= mask2; /* mask off unused top bits */
 589                         bw->accum <<= total_bits;
 590                         bw->accum |= uval;
 591                 }
 592                 else {
 593                         /* slightly pessimistic size check but faster than "<= bw->words + (bw->bits+msbits+lsbits+FLAC__BITS_PER_WORD-1)/FLAC__BITS_PER_WORD" */
 594                         /* OPT: pessimism may cause flurry of false calls to grow_ which eat up all savings before it */
 595                         if(bw->capacity <= bw->words + bw->bits + msbits + 1 /* lsbits always fit in 1 bwword */ && !bitwriter_grow_(bw, total_bits))
 596                                 return false;
 597
 598                         if(msbits) {
 599                                 /* first part gets to word alignment */
 600                                 if(bw->bits) {
 601                                         left = FLAC__BITS_PER_WORD - bw->bits;
 602                                         if(msbits < left) {
 603                                                 bw->accum <<= msbits;
 604                                                 bw->bits += msbits;
 605                                                 goto break1;
 606                                         }
 607                                         else {
 608                                                 bw->accum <<= left;
 609                                                 msbits -= left;
 610                                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 611                                                 bw->bits = 0;
 612                                         }
 613                                 }
 614                                 /* do whole words */
 615                                 while(msbits >= FLAC__BITS_PER_WORD) {
 616                                         bw->buffer[bw->words++] = 0;
 617                                         msbits -= FLAC__BITS_PER_WORD;
 618                                 }
 619                                 /* do any leftovers */
 620                                 if(msbits > 0) {
 621                                         bw->accum = 0;
 622                                         bw->bits = msbits;
 623                                 }
 624                         }
 625 break1:
 626                         uval |= mask1; /* set stop bit */
 627                         uval &= mask2; /* mask off unused top bits */
 628
 629                         left = FLAC__BITS_PER_WORD - bw->bits;
 630                         if(lsbits < left) {
 631                                 bw->accum <<= lsbits;
 632                                 bw->accum |= uval;
 633                                 bw->bits += lsbits;
 634                         }
 635                         else {
 636                                 /* if bw->bits == 0, left==FLAC__BITS_PER_WORD which will always
 637                                  * be > lsbits (because of previous assertions) so it would have
 638                                  * triggered the (lsbits<left) case above.
 639                                  */
 640                                 FLAC__ASSERT(bw->bits);
 641                                 FLAC__ASSERT(left < FLAC__BITS_PER_WORD);
 642                                 bw->accum <<= left;
 643                                 bw->accum |= uval >> (bw->bits = lsbits - left);
 644                                 bw->buffer[bw->words++] = SWAP_BE_WORD_TO_HOST(bw->accum);
 645                                 bw->accum = uval; /* unused top bits can contain garbage */
 646                         }
 647                 }
 648                 vals++;
 649                 nvals--;
 650         }
 651         return true;
 652 }
 653
 654 #if 0 /* UNUSED */
 655 FLAC__bool FLAC__bitwriter_write_golomb_signed(FLAC__BitWriter *bw, int val, uint32_t parameter)
 656 {
 657         uint32_t total_bits, msbs, uval;
 658         uint32_t k;
 659
 660         FLAC__ASSERT(0 != bw);
 661         FLAC__ASSERT(0 != bw->buffer);
 662         FLAC__ASSERT(parameter > 0);
 663
 664         /* fold signed to uint32_t */
 665         if(val < 0)
 666                 uval = (uint32_t)(((-(++val)) << 1) + 1);
 667         else
 668                 uval = (uint32_t)(val << 1);
 669
 670         k = FLAC__bitmath_ilog2(parameter);
 671         if(parameter == 1u<<k) {
 672                 uint32_t pattern;
 673
 674                 FLAC__ASSERT(k <= 30);
 675
 676                 msbs = uval >> k;
 677                 total_bits = 1 + k + msbs;
 678                 pattern = 1 << k; /* the unary end bit */
 679                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 680
 681                 if(total_bits <= 32) {
 682                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 683                                 return false;
 684                 }
 685                 else {
 686                         /* write the unary MSBs */
 687                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 688                                 return false;
 689                         /* write the unary end bit and binary LSBs */
 690                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 691                                 return false;
 692                 }
 693         }
 694         else {
 695                 uint32_t q, r, d;
 696
 697                 d = (1 << (k+1)) - parameter;
 698                 q = uval / parameter;
 699                 r = uval - (q * parameter);
 700                 /* write the unary MSBs */
 701                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 702                         return false;
 703                 /* write the unary end bit */
 704                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 705                         return false;
 706                 /* write the binary LSBs */
 707                 if(r >= d) {
 708                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 709                                 return false;
 710                 }
 711                 else {
 712                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 713                                 return false;
 714                 }
 715         }
 716         return true;
 717 }
 718
 719 FLAC__bool FLAC__bitwriter_write_golomb_unsigned(FLAC__BitWriter *bw, uint32_t uval, uint32_t parameter)
 720 {
 721         uint32_t total_bits, msbs;
 722         uint32_t k;
 723
 724         FLAC__ASSERT(0 != bw);
 725         FLAC__ASSERT(0 != bw->buffer);
 726         FLAC__ASSERT(parameter > 0);
 727
 728         k = FLAC__bitmath_ilog2(parameter);
 729         if(parameter == 1u<<k) {
 730                 uint32_t pattern;
 731
 732                 FLAC__ASSERT(k <= 30);
 733
 734                 msbs = uval >> k;
 735                 total_bits = 1 + k + msbs;
 736                 pattern = 1 << k; /* the unary end bit */
 737                 pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */
 738
 739                 if(total_bits <= 32) {
 740                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, total_bits))
 741                                 return false;
 742                 }
 743                 else {
 744                         /* write the unary MSBs */
 745                         if(!FLAC__bitwriter_write_zeroes(bw, msbs))
 746                                 return false;
 747                         /* write the unary end bit and binary LSBs */
 748                         if(!FLAC__bitwriter_write_raw_uint32(bw, pattern, k+1))
 749                                 return false;
 750                 }
 751         }
 752         else {
 753                 uint32_t q, r, d;
 754
 755                 d = (1 << (k+1)) - parameter;
 756                 q = uval / parameter;
 757                 r = uval - (q * parameter);
 758                 /* write the unary MSBs */
 759                 if(!FLAC__bitwriter_write_zeroes(bw, q))
 760                         return false;
 761                 /* write the unary end bit */
 762                 if(!FLAC__bitwriter_write_raw_uint32(bw, 1, 1))
 763                         return false;
 764                 /* write the binary LSBs */
 765                 if(r >= d) {
 766                         if(!FLAC__bitwriter_write_raw_uint32(bw, r+d, k+1))
 767                                 return false;
 768                 }
 769                 else {
 770                         if(!FLAC__bitwriter_write_raw_uint32(bw, r, k))
 771                                 return false;
 772                 }
 773         }
 774         return true;
 775 }
 776 #endif /* UNUSED */
 777
 778 FLAC__bool FLAC__bitwriter_write_utf8_uint32(FLAC__BitWriter *bw, FLAC__uint32 val)
 779 {
 780         FLAC__bool ok = 1;
 781
 782         FLAC__ASSERT(0 != bw);
 783         FLAC__ASSERT(0 != bw->buffer);
 784
 785         if((val & 0x80000000) != 0) /* this version only handles 31 bits */
 786                 return false;
 787
 788         if(val < 0x80) {
 789                 return FLAC__bitwriter_write_raw_uint32_nocheck(bw, val, 8);
 790         }
 791         else if(val < 0x800) {
 792                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xC0 | (val>>6), 8);
 793                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (val&0x3F), 8);
 794         }
 795         else if(val < 0x10000) {
 796                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xE0 | (val>>12), 8);
 797                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>6)&0x3F), 8);
 798                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (val&0x3F), 8);
 799         }
 800         else if(val < 0x200000) {
 801                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xF0 | (val>>18), 8);
 802                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>12)&0x3F), 8);
 803                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>6)&0x3F), 8);
 804                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (val&0x3F), 8);
 805         }
 806         else if(val < 0x4000000) {
 807                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xF8 | (val>>24), 8);
 808                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>18)&0x3F), 8);
 809                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>12)&0x3F), 8);
 810                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>6)&0x3F), 8);
 811                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (val&0x3F), 8);
 812         }
 813         else {
 814                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xFC | (val>>30), 8);
 815                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>24)&0x3F), 8);
 816                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>18)&0x3F), 8);
 817                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>12)&0x3F), 8);
 818                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | ((val>>6)&0x3F), 8);
 819                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (val&0x3F), 8);
 820         }
 821
 822         return ok;
 823 }
 824
 825 FLAC__bool FLAC__bitwriter_write_utf8_uint64(FLAC__BitWriter *bw, FLAC__uint64 val)
 826 {
 827         FLAC__bool ok = 1;
 828
 829         FLAC__ASSERT(0 != bw);
 830         FLAC__ASSERT(0 != bw->buffer);
 831
 832         if((val & FLAC__U64L(0xFFFFFFF000000000)) != 0) /* this version only handles 36 bits */
 833                 return false;
 834
 835         if(val < 0x80) {
 836                 return FLAC__bitwriter_write_raw_uint32_nocheck(bw, (FLAC__uint32)val, 8);
 837         }
 838         else if(val < 0x800) {
 839                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xC0 | (FLAC__uint32)(val>>6), 8);
 840                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 841         }
 842         else if(val < 0x10000) {
 843                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xE0 | (FLAC__uint32)(val>>12), 8);
 844                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 845                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 846         }
 847         else if(val < 0x200000) {
 848                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xF0 | (FLAC__uint32)(val>>18), 8);
 849                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 850                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 851                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 852         }
 853         else if(val < 0x4000000) {
 854                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xF8 | (FLAC__uint32)(val>>24), 8);
 855                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 856                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 857                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 858                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 859         }
 860         else if(val < 0x80000000) {
 861                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xFC | (FLAC__uint32)(val>>30), 8);
 862                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 863                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 864                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 865                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 866                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 867         }
 868         else {
 869                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0xFE, 8);
 870                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>30)&0x3F), 8);
 871                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>24)&0x3F), 8);
 872                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>18)&0x3F), 8);
 873                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>12)&0x3F), 8);
 874                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)((val>>6)&0x3F), 8);
 875                 ok &= FLAC__bitwriter_write_raw_uint32_nocheck(bw, 0x80 | (FLAC__uint32)(val&0x3F), 8);
 876         }
 877
 878         return ok;
 879 }
 880
 881 FLAC__bool FLAC__bitwriter_zero_pad_to_byte_boundary(FLAC__BitWriter *bw)
 882 {
 883         /* 0-pad to byte boundary */
 884         if(bw->bits & 7u)
 885                 return FLAC__bitwriter_write_zeroes(bw, 8 - (bw->bits & 7u));
 886         else
 887                 return true;
 888 }
 889
 890 /* These functions are declared inline in this file but are also callable as
 891  * externs from elsewhere.
 892  * According to the C99 spec, section 6.7.4, simply providing a function
 893  * prototype in a header file without 'inline' and making the function inline
 894  * in this file should be sufficient.
 895  * Unfortunately, the Microsoft VS compiler doesn't pick them up externally. To
 896  * fix that we add extern declarations here.
 897  */
 898 extern FLAC__bool FLAC__bitwriter_write_zeroes(FLAC__BitWriter *bw, uint32_t bits);
 899 extern FLAC__bool FLAC__bitwriter_write_raw_uint32(FLAC__BitWriter *bw, FLAC__uint32 val, uint32_t bits);
 900 extern FLAC__bool FLAC__bitwriter_write_raw_int32(FLAC__BitWriter *bw, FLAC__int32 val, uint32_t bits);
 901 extern FLAC__bool FLAC__bitwriter_write_raw_uint64(FLAC__BitWriter *bw, FLAC__uint64 val, uint32_t bits);
 902 extern FLAC__bool FLAC__bitwriter_write_raw_int64(FLAC__BitWriter *bw, FLAC__int64 val, uint32_t bits);
 903 extern FLAC__bool FLAC__bitwriter_write_raw_uint32_little_endian(FLAC__BitWriter *bw, FLAC__uint32 val);
 904 extern FLAC__bool FLAC__bitwriter_write_byte_block(FLAC__BitWriter *bw, const FLAC__byte vals[], uint32_t nvals);