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