bitbuffer.c 71.9 KB
Newer Older
1
/* libFLAC - Free Lossless Audio Codec library
Josh Coalson's avatar
Josh Coalson committed
2
 * Copyright (C) 2000,2001,2002,2003,2004,2005  Josh Coalson
Josh Coalson's avatar
Josh Coalson committed
3
 *
4
5
6
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
Josh Coalson's avatar
Josh Coalson committed
7
 *
8
9
 * - Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
Josh Coalson's avatar
Josh Coalson committed
10
 *
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 * - Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * - Neither the name of the Xiph.org Foundation nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Josh Coalson's avatar
Josh Coalson committed
30
31
32
33
34
 */

#include <stdlib.h> /* for malloc() */
#include <string.h> /* for memcpy(), memset() */
#include "private/bitbuffer.h"
35
#include "private/bitmath.h"
36
#include "private/crc.h"
37
#include "FLAC/assert.h"
Josh Coalson's avatar
Josh Coalson committed
38

39
40
41
42
43
44
45
46
/*
 * Along the way you will see two versions of some functions, selected
 * by a FLAC__NO_MANUAL_INLINING macro.  One is the simplified, more
 * readable, and slow version, and the other is the same function
 * where crucial parts have been manually inlined and are much faster.
 *
 */

47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
 * This should be at least twice as large as the largest number of blurbs
 * required to represent any 'number' (in any encoding) you are going to
 * read.  With FLAC this is on the order of maybe a few hundred bits.
 * If the buffer is smaller than that, the decoder won't be able to read
 * in a whole number that is in a variable length encoding (e.g. Rice).
 *
 * The number we are actually using here is based on what would be the
 * approximate maximum size of a verbatim frame at the default block size,
 * for CD audio (4096 sample * 4 bytes per sample), plus some wiggle room.
 * 32kbytes sounds reasonable.  For kicks we subtract out 64 bytes for any
 * alignment or malloc overhead.
 *
 * Increase this number to decrease the number of read callbacks, at the
 * expense of using more memory.  Or decrease for the reverse effect,
 * keeping in mind the limit from the first paragraph.
 */
static const unsigned FLAC__BITBUFFER_DEFAULT_CAPACITY = ((65536 - 64) * 8) / FLAC__BITS_PER_BLURB; /* blurbs */

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
static const unsigned char byte_to_unary_table[] = {
	8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
	3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

85
86
87
88
89
90
91
#if FLAC__BITS_PER_BLURB == 8
#define FLAC__BITS_PER_BLURB_LOG2 3
#define FLAC__BYTES_PER_BLURB 1
#define FLAC__BLURB_ALL_ONES ((FLAC__byte)0xff)
#define FLAC__BLURB_TOP_BIT_ONE ((FLAC__byte)0x80)
#define BLURB_BIT_TO_MASK(b) (((FLAC__blurb)'\x80') >> (b))
#define CRC16_UPDATE_BLURB(bb, blurb, crc) FLAC__CRC16_UPDATE((blurb), (crc));
92
#define FLAC__ALIGNED_BLURB_UNARY(blurb) (byte_to_unary_table[blurb])
93
94
95
96
97
98
99
#elif FLAC__BITS_PER_BLURB == 32
#define FLAC__BITS_PER_BLURB_LOG2 5
#define FLAC__BYTES_PER_BLURB 4
#define FLAC__BLURB_ALL_ONES ((FLAC__uint32)0xffffffff)
#define FLAC__BLURB_TOP_BIT_ONE ((FLAC__uint32)0x80000000)
#define BLURB_BIT_TO_MASK(b) (((FLAC__blurb)0x80000000) >> (b))
#define CRC16_UPDATE_BLURB(bb, blurb, crc) crc16_update_blurb((bb), (blurb));
100
#define FLAC__ALIGNED_BLURB_UNARY(blurb) ((blurb) <= 0xff ? byte_to_unary_table[blurb] + 24 : ((blurb) <= 0xffff ? byte_to_unary_table[(blurb) >> 8] + 16 : ((blurb) <= 0xffffff ? byte_to_unary_table[(blurb) >> 16] + 8 : byte_to_unary_table[(blurb) >> 24])))
101
102
103
#else
/* ERROR, only sizes of 8 and 32 are supported */
#endif
Josh Coalson's avatar
Josh Coalson committed
104

105
#define FLAC__BLURBS_TO_BITS(blurbs) ((blurbs) << FLAC__BITS_PER_BLURB_LOG2)
Josh Coalson's avatar
Josh Coalson committed
106

Josh Coalson's avatar
Josh Coalson committed
107
108
109
110
111
112
113
114
115
#ifdef min
#undef min
#endif
#define min(x,y) ((x)<(y)?(x):(y))
#ifdef max
#undef max
#endif
#define max(x,y) ((x)>(y)?(x):(y))

116
117
118
119
120
121
122
/* adjust for compilers that can't understand using LLU suffix for uint64_t literals */
#ifdef _MSC_VER
#define FLAC__U64L(x) x
#else
#define FLAC__U64L(x) x##LLU
#endif

123
124
#ifndef FLaC__INLINE
#define FLaC__INLINE
125
126
#endif

127
128
129
130
131
132
133
134
135
136
137
138
139
140
struct FLAC__BitBuffer {
	FLAC__blurb *buffer;
	unsigned capacity; /* in blurbs */
	unsigned blurbs, bits;
	unsigned total_bits; /* must always == FLAC__BITS_PER_BLURB*blurbs+bits */
	unsigned consumed_blurbs, consumed_bits;
	unsigned total_consumed_bits; /* must always == FLAC__BITS_PER_BLURB*consumed_blurbs+consumed_bits */
	FLAC__uint16 read_crc16;
#if FLAC__BITS_PER_BLURB == 32
	unsigned crc16_align;
#endif
	FLAC__blurb save_head, save_tail;
};

141
#if FLAC__BITS_PER_BLURB == 32
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
static void crc16_update_blurb(FLAC__BitBuffer *bb, FLAC__blurb blurb)
{
	if(bb->crc16_align == 0) {
		FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
		FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
		FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
		FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
	}
	else if(bb->crc16_align == 8) {
		FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
		FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
		FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
	}
	else if(bb->crc16_align == 16) {
		FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
		FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
	}
	else if(bb->crc16_align == 24) {
		FLAC__CRC16_UPDATE(blurb & 0xff, bb->read_crc16);
	}
	bb->crc16_align = 0;
}
164
#endif
165
166
167
168
169
170
171
172

/*
 * WATCHOUT: The current implentation is not friendly to shrinking, i.e. it
 * does not shift left what is consumed, it just chops off the end, whether
 * there is unconsumed data there or not.  This is OK because currently we
 * never shrink the buffer, but if this ever changes, we'll have to do some
 * fixups here.
 */
Josh Coalson's avatar
Josh Coalson committed
173
static FLAC__bool bitbuffer_resize_(FLAC__BitBuffer *bb, unsigned new_capacity)
Josh Coalson's avatar
Josh Coalson committed
174
{
175
	FLAC__blurb *new_buffer;
Josh Coalson's avatar
Josh Coalson committed
176

Josh Coalson's avatar
Josh Coalson committed
177
178
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
Josh Coalson's avatar
Josh Coalson committed
179
180
181
182

	if(bb->capacity == new_capacity)
		return true;

183
	new_buffer = (FLAC__blurb*)calloc(new_capacity, sizeof(FLAC__blurb));
Josh Coalson's avatar
Josh Coalson committed
184
185
	if(new_buffer == 0)
		return false;
186
187
188
	memcpy(new_buffer, bb->buffer, sizeof(FLAC__blurb)*min(bb->blurbs+(bb->bits?1:0), new_capacity));
	if(new_capacity < bb->blurbs+(bb->bits?1:0)) {
		bb->blurbs = new_capacity;
Josh Coalson's avatar
Josh Coalson committed
189
		bb->bits = 0;
190
		bb->total_bits = FLAC__BLURBS_TO_BITS(new_capacity);
Josh Coalson's avatar
Josh Coalson committed
191
	}
192
193
	if(new_capacity < bb->consumed_blurbs+(bb->consumed_bits?1:0)) {
		bb->consumed_blurbs = new_capacity;
Josh Coalson's avatar
Josh Coalson committed
194
		bb->consumed_bits = 0;
195
		bb->total_consumed_bits = FLAC__BLURBS_TO_BITS(new_capacity);
Josh Coalson's avatar
Josh Coalson committed
196
	}
Josh Coalson's avatar
Josh Coalson committed
197
	free(bb->buffer); /* we've already asserted above that (0 != bb->buffer) */
Josh Coalson's avatar
Josh Coalson committed
198
199
200
201
202
	bb->buffer = new_buffer;
	bb->capacity = new_capacity;
	return true;
}

203
static FLAC__bool bitbuffer_grow_(FLAC__BitBuffer *bb, unsigned min_blurbs_to_add)
Josh Coalson's avatar
Josh Coalson committed
204
205
206
{
	unsigned new_capacity;

207
	FLAC__ASSERT(min_blurbs_to_add > 0);
Josh Coalson's avatar
Josh Coalson committed
208

209
	new_capacity = max(bb->capacity * 2, bb->capacity + min_blurbs_to_add);
Josh Coalson's avatar
Josh Coalson committed
210
211
212
	return bitbuffer_resize_(bb, new_capacity);
}

Josh Coalson's avatar
Josh Coalson committed
213
static FLAC__bool bitbuffer_ensure_size_(FLAC__BitBuffer *bb, unsigned bits_to_add)
Josh Coalson's avatar
Josh Coalson committed
214
{
Josh Coalson's avatar
Josh Coalson committed
215
216
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
217

218
219
	if(FLAC__BLURBS_TO_BITS(bb->capacity) < bb->total_bits + bits_to_add)
		return bitbuffer_grow_(bb, (bits_to_add >> FLAC__BITS_PER_BLURB_LOG2) + 2);
Josh Coalson's avatar
Josh Coalson committed
220
221
222
223
	else
		return true;
}

Josh Coalson's avatar
Josh Coalson committed
224
static FLAC__bool bitbuffer_read_from_client_(FLAC__BitBuffer *bb, FLAC__bool (*read_callback)(FLAC__byte buffer[], unsigned *bytes, void *client_data), void *client_data)
Josh Coalson's avatar
Josh Coalson committed
225
226
{
	unsigned bytes;
227
	FLAC__byte *target;
Josh Coalson's avatar
Josh Coalson committed
228
229

	/* first shift the unconsumed buffer data toward the front as much as possible */
230
	if(bb->total_consumed_bits >= FLAC__BITS_PER_BLURB) {
231
232
233
234
235
236
237
238
239
240
241
242
243
#if FLAC__BITS_PER_BLURB == 8
		/*
		 * memset and memcpy are usually implemented in assembly language
		 * by the system libc, and they can be much faster
		 */
		const unsigned r_end = bb->blurbs + (bb->bits? 1:0);
		const unsigned r = bb->consumed_blurbs, l = r_end - r;
		memmove(&bb->buffer[0], &bb->buffer[r], l);
		memset(&bb->buffer[l], 0, r);
#elif FLAC__BITS_PER_BLURB == 32
		/* still needs optimization */
		const unsigned r_end = bb->blurbs + (bb->bits? 1:0);
		unsigned l = 0, r = bb->consumed_blurbs;
Josh Coalson's avatar
Josh Coalson committed
244
245
246
247
		for( ; r < r_end; l++, r++)
			bb->buffer[l] = bb->buffer[r];
		for( ; l < r_end; l++)
			bb->buffer[l] = 0;
248
249
250
251
#else
		FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif /* FLAC__BITS_PER_BLURB == 32 or 8 */

252
253
254
		bb->blurbs -= bb->consumed_blurbs;
		bb->total_bits -= FLAC__BLURBS_TO_BITS(bb->consumed_blurbs);
		bb->consumed_blurbs = 0;
Josh Coalson's avatar
Josh Coalson committed
255
256
		bb->total_consumed_bits = bb->consumed_bits;
	}
257

Josh Coalson's avatar
Josh Coalson committed
258
259
260
261
262
	/* grow if we need to */
	if(bb->capacity <= 1) {
		if(!bitbuffer_resize_(bb, 16))
			return false;
	}
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277

	/* set the target for reading, taking into account blurb alignment */
#if FLAC__BITS_PER_BLURB == 8
	/* blurb == byte, so no gyrations necessary: */
	target = bb->buffer + bb->blurbs;
	bytes = bb->capacity - bb->blurbs;
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	FLAC__ASSERT((bb->bits & 7) == 0);
	target = (FLAC__byte*)(bb->buffer + bb->blurbs) + (bb->bits >> 3);
	bytes = ((bb->capacity - bb->blurbs) << 2) - (bb->bits >> 3); /* i.e. (bb->capacity - bb->blurbs) * FLAC__BYTES_PER_BLURB - (bb->bits / 8) */
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif

Josh Coalson's avatar
Josh Coalson committed
278
	/* finally, read in some data */
279
	if(!read_callback(target, &bytes, client_data))
Josh Coalson's avatar
Josh Coalson committed
280
		return false;
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297

	/* now we have to handle partial blurb cases: */
#if FLAC__BITS_PER_BLURB == 8
	/* blurb == byte, so no gyrations necessary: */
	bb->blurbs += bytes;
	bb->total_bits += FLAC__BLURBS_TO_BITS(bytes);
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	{
		const unsigned aligned_bytes = (bb->bits >> 3) + bytes;
		bb->blurbs += (aligned_bytes >> 2); /* i.e. aligned_bytes / FLAC__BYTES_PER_BLURB */
		bb->bits = (aligned_bytes & 3u) << 3; /* i.e. (aligned_bytes % FLAC__BYTES_PER_BLURB) * 8 */
		bb->total_bits += (bytes << 3);
	}
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
Josh Coalson's avatar
Josh Coalson committed
298
299
300
	return true;
}

301
302
303
304
305
306
307
308
/***********************************************************************
 *
 * Class constructor/destructor
 *
 ***********************************************************************/

FLAC__BitBuffer *FLAC__bitbuffer_new()
{
309
	FLAC__BitBuffer *bb = (FLAC__BitBuffer*)calloc(1, sizeof(FLAC__BitBuffer));
310

311
	/* calloc() implies:
Josh Coalson's avatar
Josh Coalson committed
312
		memset(bb, 0, sizeof(FLAC__BitBuffer));
313
314
315
316
		bb->buffer = 0;
		bb->capacity = 0;
		bb->blurbs = bb->bits = bb->total_bits = 0;
		bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
317
	*/
318
	return bb;
319
320
321
}

void FLAC__bitbuffer_delete(FLAC__BitBuffer *bb)
Josh Coalson's avatar
Josh Coalson committed
322
{
Josh Coalson's avatar
Josh Coalson committed
323
	FLAC__ASSERT(0 != bb);
324

325
326
	FLAC__bitbuffer_free(bb);
	free(bb);
Josh Coalson's avatar
Josh Coalson committed
327
328
}

329
330
331
332
333
334
335
/***********************************************************************
 *
 * Public class methods
 *
 ***********************************************************************/

FLAC__bool FLAC__bitbuffer_init(FLAC__BitBuffer *bb)
Josh Coalson's avatar
Josh Coalson committed
336
{
Josh Coalson's avatar
Josh Coalson committed
337
	FLAC__ASSERT(0 != bb);
338

339
340
341
342
343
344
	bb->buffer = 0;
	bb->capacity = 0;
	bb->blurbs = bb->bits = bb->total_bits = 0;
	bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;

	return FLAC__bitbuffer_clear(bb);
Josh Coalson's avatar
Josh Coalson committed
345
346
}

347
FLAC__bool FLAC__bitbuffer_init_from(FLAC__BitBuffer *bb, const FLAC__byte buffer[], unsigned bytes)
348
{
Josh Coalson's avatar
Josh Coalson committed
349
	FLAC__ASSERT(0 != bb);
350
	FLAC__ASSERT(bytes > 0);
351

352
353
354
355
356
357
	if(!FLAC__bitbuffer_init(bb))
		return false;

	if(!bitbuffer_ensure_size_(bb, bytes << 3))
		return false;

Josh Coalson's avatar
Josh Coalson committed
358
	FLAC__ASSERT(0 != buffer);
359
360
361
362
363
364
	/* @@@ WATCHOUT: code currently only works for 8-bits-per-blurb inclusive-or big-endian: */
	memcpy((FLAC__byte*)bb->buffer, buffer, sizeof(FLAC__byte)*bytes);
	bb->blurbs = bytes / FLAC__BYTES_PER_BLURB;
	bb->bits = (bytes % FLAC__BYTES_PER_BLURB) << 3;
	bb->total_bits = bytes << 3;
	return true;
365
366
}

Josh Coalson's avatar
Josh Coalson committed
367
FLAC__bool FLAC__bitbuffer_concatenate_aligned(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
Josh Coalson's avatar
Josh Coalson committed
368
369
{
	unsigned bits_to_add = src->total_bits - src->total_consumed_bits;
370

Josh Coalson's avatar
Josh Coalson committed
371
372
	FLAC__ASSERT(0 != dest);
	FLAC__ASSERT(0 != src);
Josh Coalson's avatar
Josh Coalson committed
373
374
375
376
377
378
379
380

	if(bits_to_add == 0)
		return true;
	if(dest->bits != src->consumed_bits)
		return false;
	if(!bitbuffer_ensure_size_(dest, bits_to_add))
		return false;
	if(dest->bits == 0) {
381
		memcpy(dest->buffer+dest->blurbs, src->buffer+src->consumed_blurbs, sizeof(FLAC__blurb)*(src->blurbs-src->consumed_blurbs + ((src->bits)? 1:0)));
Josh Coalson's avatar
Josh Coalson committed
382
	}
383
384
385
386
	else if(dest->bits + bits_to_add > FLAC__BITS_PER_BLURB) {
		dest->buffer[dest->blurbs] <<= (FLAC__BITS_PER_BLURB - dest->bits);
		dest->buffer[dest->blurbs] |= (src->buffer[src->consumed_blurbs] & ((1u << (FLAC__BITS_PER_BLURB-dest->bits)) - 1));
		memcpy(dest->buffer+dest->blurbs+1, src->buffer+src->consumed_blurbs+1, sizeof(FLAC__blurb)*(src->blurbs-src->consumed_blurbs-1 + ((src->bits)? 1:0)));
Josh Coalson's avatar
Josh Coalson committed
387
388
	}
	else {
389
390
		dest->buffer[dest->blurbs] <<= bits_to_add;
		dest->buffer[dest->blurbs] |= (src->buffer[src->consumed_blurbs] & ((1u << bits_to_add) - 1));
Josh Coalson's avatar
Josh Coalson committed
391
392
393
	}
	dest->bits = src->bits;
	dest->total_bits += bits_to_add;
394
	dest->blurbs = dest->total_bits / FLAC__BITS_PER_BLURB;
Josh Coalson's avatar
Josh Coalson committed
395
396
397
398
399
400

	return true;
}

void FLAC__bitbuffer_free(FLAC__BitBuffer *bb)
{
Josh Coalson's avatar
Josh Coalson committed
401
	FLAC__ASSERT(0 != bb);
402

Josh Coalson's avatar
Josh Coalson committed
403
	if(0 != bb->buffer)
Josh Coalson's avatar
Josh Coalson committed
404
405
406
		free(bb->buffer);
	bb->buffer = 0;
	bb->capacity = 0;
407
408
	bb->blurbs = bb->bits = bb->total_bits = 0;
	bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
Josh Coalson's avatar
Josh Coalson committed
409
410
}

Josh Coalson's avatar
Josh Coalson committed
411
FLAC__bool FLAC__bitbuffer_clear(FLAC__BitBuffer *bb)
Josh Coalson's avatar
Josh Coalson committed
412
413
414
{
	if(bb->buffer == 0) {
		bb->capacity = FLAC__BITBUFFER_DEFAULT_CAPACITY;
415
		bb->buffer = (FLAC__blurb*)calloc(bb->capacity, sizeof(FLAC__blurb));
Josh Coalson's avatar
Josh Coalson committed
416
417
418
419
		if(bb->buffer == 0)
			return false;
	}
	else {
420
		memset(bb->buffer, 0, bb->blurbs + (bb->bits?1:0));
Josh Coalson's avatar
Josh Coalson committed
421
	}
422
423
	bb->blurbs = bb->bits = bb->total_bits = 0;
	bb->consumed_blurbs = bb->consumed_bits = bb->total_consumed_bits = 0;
Josh Coalson's avatar
Josh Coalson committed
424
425
426
	return true;
}

Josh Coalson's avatar
Josh Coalson committed
427
FLAC__bool FLAC__bitbuffer_clone(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
Josh Coalson's avatar
Josh Coalson committed
428
{
Josh Coalson's avatar
Josh Coalson committed
429
430
431
432
	FLAC__ASSERT(0 != dest);
	FLAC__ASSERT(0 != dest->buffer);
	FLAC__ASSERT(0 != src);
	FLAC__ASSERT(0 != src->buffer);
433

Josh Coalson's avatar
Josh Coalson committed
434
435
436
	if(dest->capacity < src->capacity)
		if(!bitbuffer_resize_(dest, src->capacity))
			return false;
437
438
	memcpy(dest->buffer, src->buffer, sizeof(FLAC__blurb)*min(src->capacity, src->blurbs+1));
	dest->blurbs = src->blurbs;
Josh Coalson's avatar
Josh Coalson committed
439
440
	dest->bits = src->bits;
	dest->total_bits = src->total_bits;
441
	dest->consumed_blurbs = src->consumed_blurbs;
Josh Coalson's avatar
Josh Coalson committed
442
443
	dest->consumed_bits = src->consumed_bits;
	dest->total_consumed_bits = src->total_consumed_bits;
444
	dest->read_crc16 = src->read_crc16;
Josh Coalson's avatar
Josh Coalson committed
445
446
447
	return true;
}

448
449
void FLAC__bitbuffer_reset_read_crc16(FLAC__BitBuffer *bb, FLAC__uint16 seed)
{
Josh Coalson's avatar
Josh Coalson committed
450
451
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
452
453
454
455
456
457
458
459
460
461
462
463
464
465
	FLAC__ASSERT((bb->consumed_bits & 7) == 0);

	bb->read_crc16 = seed;
#if FLAC__BITS_PER_BLURB == 8
	/* no need to do anything */
#elif FLAC__BITS_PER_BLURB == 32
	bb->crc16_align = bb->consumed_bits;
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
}

FLAC__uint16 FLAC__bitbuffer_get_read_crc16(FLAC__BitBuffer *bb)
{
Josh Coalson's avatar
Josh Coalson committed
466
467
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
	FLAC__ASSERT((bb->bits & 7) == 0);
	FLAC__ASSERT((bb->consumed_bits & 7) == 0);

#if FLAC__BITS_PER_BLURB == 8
	/* no need to do anything */
#elif FLAC__BITS_PER_BLURB == 32
	/*@@@ BUG: even though this probably can't happen with FLAC, need to fix the case where we are called here for the very first blurb and crc16_align is > 0 */
	if(bb->bits == 0 || bb->consumed_blurbs < bb->blurbs) {
		if(bb->consumed_bits == 8) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
		}
		else if(bb->consumed_bits == 16) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
		}
		else if(bb->consumed_bits == 24) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> 24, bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> 16) & 0xff, bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> 8) & 0xff, bb->read_crc16);
		}
	}
	else {
		if(bb->consumed_bits == 8) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
		}
		else if(bb->consumed_bits == 16) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> (bb->bits-16)) & 0xff, bb->read_crc16);
		}
		else if(bb->consumed_bits == 24) {
			const FLAC__blurb blurb = bb->buffer[bb->consumed_blurbs];
			FLAC__CRC16_UPDATE(blurb >> (bb->bits-8), bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> (bb->bits-16)) & 0xff, bb->read_crc16);
			FLAC__CRC16_UPDATE((blurb >> (bb->bits-24)) & 0xff, bb->read_crc16);
		}
	}
	bb->crc16_align = bb->consumed_bits;
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
	return bb->read_crc16;
}

FLAC__uint16 FLAC__bitbuffer_get_write_crc16(const FLAC__BitBuffer *bb)
{
	FLAC__ASSERT((bb->bits & 7) == 0); /* assert that we're byte-aligned */

#if FLAC__BITS_PER_BLURB == 8
	return FLAC__crc16(bb->buffer, bb->blurbs);
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	return FLAC__crc16((FLAC__byte*)(bb->buffer), (bb->blurbs * FLAC__BYTES_PER_BLURB) + (bb->bits >> 3));
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
}

FLAC__byte FLAC__bitbuffer_get_write_crc8(const FLAC__BitBuffer *bb)
{
532
	FLAC__ASSERT(0 != bb);
533
	FLAC__ASSERT((bb->bits & 7) == 0); /* assert that we're byte-aligned */
534
	FLAC__ASSERT(bb->buffer[0] == 0xff); /* MAGIC NUMBER for the first byte of the sync code */
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
#if FLAC__BITS_PER_BLURB == 8
	return FLAC__crc8(bb->buffer, bb->blurbs);
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	return FLAC__crc8((FLAC__byte*)(bb->buffer), (bb->blurbs * FLAC__BYTES_PER_BLURB) + (bb->bits >> 3));
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
}

FLAC__bool FLAC__bitbuffer_is_byte_aligned(const FLAC__BitBuffer *bb)
{
	return ((bb->bits & 7) == 0);
}

FLAC__bool FLAC__bitbuffer_is_consumed_byte_aligned(const FLAC__BitBuffer *bb)
{
	return ((bb->consumed_bits & 7) == 0);
}

unsigned FLAC__bitbuffer_bits_left_for_byte_alignment(const FLAC__BitBuffer *bb)
{
	return 8 - (bb->consumed_bits & 7);
}

unsigned FLAC__bitbuffer_get_input_bytes_unconsumed(const FLAC__BitBuffer *bb)
{
	FLAC__ASSERT((bb->consumed_bits & 7) == 0 && (bb->bits & 7) == 0);
	return (bb->total_bits - bb->total_consumed_bits) >> 3;
}

void FLAC__bitbuffer_get_buffer(FLAC__BitBuffer *bb, const FLAC__byte **buffer, unsigned *bytes)
{
	FLAC__ASSERT((bb->consumed_bits & 7) == 0 && (bb->bits & 7) == 0);
#if FLAC__BITS_PER_BLURB == 8
	*buffer = bb->buffer + bb->consumed_blurbs;
	*bytes = bb->blurbs - bb->consumed_blurbs;
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	*buffer = (FLAC__byte*)(bb->buffer + bb->consumed_blurbs) + (bb->consumed_bits >> 3);
	*bytes = (bb->total_bits - bb->total_consumed_bits) >> 3;
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
}

void FLAC__bitbuffer_release_buffer(FLAC__BitBuffer *bb)
{
#if FLAC__BITS_PER_BLURB == 8
	(void)bb;
#elif FLAC__BITS_PER_BLURB == 32
	/* @@@ WATCHOUT: code currently only works for big-endian: */
	(void)bb;
#else
	FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif
}

Josh Coalson's avatar
Josh Coalson committed
593
FLAC__bool FLAC__bitbuffer_write_zeroes(FLAC__BitBuffer *bb, unsigned bits)
Josh Coalson's avatar
Josh Coalson committed
594
{
595
	unsigned n;
Josh Coalson's avatar
Josh Coalson committed
596

Josh Coalson's avatar
Josh Coalson committed
597
598
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
Josh Coalson's avatar
Josh Coalson committed
599
600
601
602
603
604
605

	if(bits == 0)
		return true;
	if(!bitbuffer_ensure_size_(bb, bits))
		return false;
	bb->total_bits += bits;
	while(bits > 0) {
606
607
		n = min(FLAC__BITS_PER_BLURB - bb->bits, bits);
		bb->buffer[bb->blurbs] <<= n;
Josh Coalson's avatar
Josh Coalson committed
608
609
		bits -= n;
		bb->bits += n;
610
611
		if(bb->bits == FLAC__BITS_PER_BLURB) {
			bb->blurbs++;
Josh Coalson's avatar
Josh Coalson committed
612
613
614
615
616
617
			bb->bits = 0;
		}
	}
	return true;
}

618
FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_raw_uint32(FLAC__BitBuffer *bb, FLAC__uint32 val, unsigned bits)
Josh Coalson's avatar
Josh Coalson committed
619
620
621
{
	unsigned n, k;

Josh Coalson's avatar
Josh Coalson committed
622
623
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
Josh Coalson's avatar
Josh Coalson committed
624

625
	FLAC__ASSERT(bits <= 32);
Josh Coalson's avatar
Josh Coalson committed
626
627
	if(bits == 0)
		return true;
628
	/* inline the size check so we don't incure a function call unnecessarily */
629
	if(FLAC__BLURBS_TO_BITS(bb->capacity) < bb->total_bits + bits) {
630
631
632
		if(!bitbuffer_ensure_size_(bb, bits))
			return false;
	}
633
634

	/* zero-out unused bits; WATCHOUT: other code relies on this, so this needs to stay */
635
636
	if(bits < 32) /* @@@ gcc seems to require this because the following line causes incorrect results when bits==32; investigate */
		val &= (~(0xffffffff << bits)); /* zero-out unused bits */
637

Josh Coalson's avatar
Josh Coalson committed
638
639
	bb->total_bits += bits;
	while(bits > 0) {
640
641
642
643
		n = FLAC__BITS_PER_BLURB - bb->bits;
		if(n == FLAC__BITS_PER_BLURB) { /* i.e. bb->bits == 0 */
			if(bits < FLAC__BITS_PER_BLURB) {
				bb->buffer[bb->blurbs] = (FLAC__blurb)val;
Josh Coalson's avatar
Josh Coalson committed
644
645
646
				bb->bits = bits;
				break;
			}
647
648
			else if(bits == FLAC__BITS_PER_BLURB) {
				bb->buffer[bb->blurbs++] = (FLAC__blurb)val;
Josh Coalson's avatar
Josh Coalson committed
649
650
651
				break;
			}
			else {
652
653
654
				k = bits - FLAC__BITS_PER_BLURB;
				bb->buffer[bb->blurbs++] = (FLAC__blurb)(val >> k);
				/* we know k < 32 so no need to protect against the gcc bug mentioned above */
Josh Coalson's avatar
Josh Coalson committed
655
				val &= (~(0xffffffff << k));
656
				bits -= FLAC__BITS_PER_BLURB;
Josh Coalson's avatar
Josh Coalson committed
657
658
659
			}
		}
		else if(bits <= n) {
660
661
			bb->buffer[bb->blurbs] <<= bits;
			bb->buffer[bb->blurbs] |= val;
Josh Coalson's avatar
Josh Coalson committed
662
			if(bits == n) {
663
				bb->blurbs++;
Josh Coalson's avatar
Josh Coalson committed
664
665
666
667
668
669
670
671
				bb->bits = 0;
			}
			else
				bb->bits += bits;
			break;
		}
		else {
			k = bits - n;
672
673
674
			bb->buffer[bb->blurbs] <<= n;
			bb->buffer[bb->blurbs] |= (val >> k);
			/* we know n > 0 so k < 32 so no need to protect against the gcc bug mentioned above */
Josh Coalson's avatar
Josh Coalson committed
675
676
			val &= (~(0xffffffff << k));
			bits -= n;
677
			bb->blurbs++;
Josh Coalson's avatar
Josh Coalson committed
678
679
680
681
682
683
684
			bb->bits = 0;
		}
	}

	return true;
}

Josh Coalson's avatar
Josh Coalson committed
685
FLAC__bool FLAC__bitbuffer_write_raw_int32(FLAC__BitBuffer *bb, FLAC__int32 val, unsigned bits)
Josh Coalson's avatar
Josh Coalson committed
686
{
Josh Coalson's avatar
Josh Coalson committed
687
	return FLAC__bitbuffer_write_raw_uint32(bb, (FLAC__uint32)val, bits);
Josh Coalson's avatar
Josh Coalson committed
688
689
}

Josh Coalson's avatar
Josh Coalson committed
690
FLAC__bool FLAC__bitbuffer_write_raw_uint64(FLAC__BitBuffer *bb, FLAC__uint64 val, unsigned bits)
Josh Coalson's avatar
Josh Coalson committed
691
{
Josh Coalson's avatar
Josh Coalson committed
692
	static const FLAC__uint64 mask[] = {
Josh Coalson's avatar
Josh Coalson committed
693
		0,
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
		FLAC__U64L(0x0000000000000001), FLAC__U64L(0x0000000000000003), FLAC__U64L(0x0000000000000007), FLAC__U64L(0x000000000000000F),
		FLAC__U64L(0x000000000000001F), FLAC__U64L(0x000000000000003F), FLAC__U64L(0x000000000000007F), FLAC__U64L(0x00000000000000FF),
		FLAC__U64L(0x00000000000001FF), FLAC__U64L(0x00000000000003FF), FLAC__U64L(0x00000000000007FF), FLAC__U64L(0x0000000000000FFF),
		FLAC__U64L(0x0000000000001FFF), FLAC__U64L(0x0000000000003FFF), FLAC__U64L(0x0000000000007FFF), FLAC__U64L(0x000000000000FFFF),
		FLAC__U64L(0x000000000001FFFF), FLAC__U64L(0x000000000003FFFF), FLAC__U64L(0x000000000007FFFF), FLAC__U64L(0x00000000000FFFFF),
		FLAC__U64L(0x00000000001FFFFF), FLAC__U64L(0x00000000003FFFFF), FLAC__U64L(0x00000000007FFFFF), FLAC__U64L(0x0000000000FFFFFF),
		FLAC__U64L(0x0000000001FFFFFF), FLAC__U64L(0x0000000003FFFFFF), FLAC__U64L(0x0000000007FFFFFF), FLAC__U64L(0x000000000FFFFFFF),
		FLAC__U64L(0x000000001FFFFFFF), FLAC__U64L(0x000000003FFFFFFF), FLAC__U64L(0x000000007FFFFFFF), FLAC__U64L(0x00000000FFFFFFFF),
		FLAC__U64L(0x00000001FFFFFFFF), FLAC__U64L(0x00000003FFFFFFFF), FLAC__U64L(0x00000007FFFFFFFF), FLAC__U64L(0x0000000FFFFFFFFF),
		FLAC__U64L(0x0000001FFFFFFFFF), FLAC__U64L(0x0000003FFFFFFFFF), FLAC__U64L(0x0000007FFFFFFFFF), FLAC__U64L(0x000000FFFFFFFFFF),
		FLAC__U64L(0x000001FFFFFFFFFF), FLAC__U64L(0x000003FFFFFFFFFF), FLAC__U64L(0x000007FFFFFFFFFF), FLAC__U64L(0x00000FFFFFFFFFFF),
		FLAC__U64L(0x00001FFFFFFFFFFF), FLAC__U64L(0x00003FFFFFFFFFFF), FLAC__U64L(0x00007FFFFFFFFFFF), FLAC__U64L(0x0000FFFFFFFFFFFF),
		FLAC__U64L(0x0001FFFFFFFFFFFF), FLAC__U64L(0x0003FFFFFFFFFFFF), FLAC__U64L(0x0007FFFFFFFFFFFF), FLAC__U64L(0x000FFFFFFFFFFFFF),
		FLAC__U64L(0x001FFFFFFFFFFFFF), FLAC__U64L(0x003FFFFFFFFFFFFF), FLAC__U64L(0x007FFFFFFFFFFFFF), FLAC__U64L(0x00FFFFFFFFFFFFFF),
		FLAC__U64L(0x01FFFFFFFFFFFFFF), FLAC__U64L(0x03FFFFFFFFFFFFFF), FLAC__U64L(0x07FFFFFFFFFFFFFF), FLAC__U64L(0x0FFFFFFFFFFFFFFF),
		FLAC__U64L(0x1FFFFFFFFFFFFFFF), FLAC__U64L(0x3FFFFFFFFFFFFFFF), FLAC__U64L(0x7FFFFFFFFFFFFFFF), FLAC__U64L(0xFFFFFFFFFFFFFFFF)
Josh Coalson's avatar
Josh Coalson committed
710
711
712
	};
	unsigned n, k;

Josh Coalson's avatar
Josh Coalson committed
713
714
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
Josh Coalson's avatar
Josh Coalson committed
715

716
	FLAC__ASSERT(bits <= 64);
Josh Coalson's avatar
Josh Coalson committed
717
718
719
720
721
722
723
724
	if(bits == 0)
		return true;
	if(!bitbuffer_ensure_size_(bb, bits))
		return false;
	val &= mask[bits];
	bb->total_bits += bits;
	while(bits > 0) {
		if(bb->bits == 0) {
725
726
			if(bits < FLAC__BITS_PER_BLURB) {
				bb->buffer[bb->blurbs] = (FLAC__blurb)val;
Josh Coalson's avatar
Josh Coalson committed
727
728
729
				bb->bits = bits;
				break;
			}
730
731
			else if(bits == FLAC__BITS_PER_BLURB) {
				bb->buffer[bb->blurbs++] = (FLAC__blurb)val;
Josh Coalson's avatar
Josh Coalson committed
732
733
734
				break;
			}
			else {
735
736
737
				k = bits - FLAC__BITS_PER_BLURB;
				bb->buffer[bb->blurbs++] = (FLAC__blurb)(val >> k);
				/* we know k < 64 so no need to protect against the gcc bug mentioned above */
738
				val &= (~(FLAC__U64L(0xffffffffffffffff) << k));
739
				bits -= FLAC__BITS_PER_BLURB;
Josh Coalson's avatar
Josh Coalson committed
740
741
742
			}
		}
		else {
743
			n = min(FLAC__BITS_PER_BLURB - bb->bits, bits);
Josh Coalson's avatar
Josh Coalson committed
744
			k = bits - n;
745
746
747
			bb->buffer[bb->blurbs] <<= n;
			bb->buffer[bb->blurbs] |= (val >> k);
			/* we know n > 0 so k < 64 so no need to protect against the gcc bug mentioned above */
748
			val &= (~(FLAC__U64L(0xffffffffffffffff) << k));
Josh Coalson's avatar
Josh Coalson committed
749
750
			bits -= n;
			bb->bits += n;
751
752
			if(bb->bits == FLAC__BITS_PER_BLURB) {
				bb->blurbs++;
Josh Coalson's avatar
Josh Coalson committed
753
754
755
756
757
758
759
760
				bb->bits = 0;
			}
		}
	}

	return true;
}

Josh Coalson's avatar
Josh Coalson committed
761
#if 0 /* UNUSED */
Josh Coalson's avatar
Josh Coalson committed
762
FLAC__bool FLAC__bitbuffer_write_raw_int64(FLAC__BitBuffer *bb, FLAC__int64 val, unsigned bits)
Josh Coalson's avatar
Josh Coalson committed
763
{
Josh Coalson's avatar
Josh Coalson committed
764
	return FLAC__bitbuffer_write_raw_uint64(bb, (FLAC__uint64)val, bits);
Josh Coalson's avatar
Josh Coalson committed
765
}
Josh Coalson's avatar
Josh Coalson committed
766
#endif
Josh Coalson's avatar
Josh Coalson committed
767

768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_raw_uint32_little_endian(FLAC__BitBuffer *bb, FLAC__uint32 val)
{
	/* this doesn't need to be that fast as currently it is only used for vorbis comments */

	/* NOTE: we rely on the fact that FLAC__bitbuffer_write_raw_uint32() masks out the unused bits */
	if(!FLAC__bitbuffer_write_raw_uint32(bb, val, 8))
		return false;
	if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>8, 8))
		return false;
	if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>16, 8))
		return false;
	if(!FLAC__bitbuffer_write_raw_uint32(bb, val>>24, 8))
		return false;

	return true;
}

FLaC__INLINE FLAC__bool FLAC__bitbuffer_write_byte_block(FLAC__BitBuffer *bb, const FLAC__byte vals[], unsigned nvals)
{
	unsigned i;

	/* this could be faster but currently we don't need it to be */
	for(i = 0; i < nvals; i++) {
		if(!FLAC__bitbuffer_write_raw_uint32(bb, (FLAC__uint32)(vals[i]), 8))
			return false;
	}

	return true;
}

Josh Coalson's avatar
Josh Coalson committed
798
FLAC__bool FLAC__bitbuffer_write_unary_unsigned(FLAC__BitBuffer *bb, unsigned val)
799
800
801
802
803
804
805
806
807
808
809
810
{
	if(val < 32)
		return FLAC__bitbuffer_write_raw_uint32(bb, 1, ++val);
	else if(val < 64)
		return FLAC__bitbuffer_write_raw_uint64(bb, 1, ++val);
	else {
		if(!FLAC__bitbuffer_write_zeroes(bb, val))
			return false;
		return FLAC__bitbuffer_write_raw_uint32(bb, 1, 1);
	}
}

811
812
813
814
unsigned FLAC__bitbuffer_rice_bits(int val, unsigned parameter)
{
	unsigned msbs, uval;

Josh Coalson's avatar
Josh Coalson committed
815
	/* fold signed to unsigned */
816
817
818
	if(val < 0)
		/* equivalent to
		 *     (unsigned)(((--val) << 1) - 1);
Josh Coalson's avatar
Josh Coalson committed
819
		 * but without the overflow problem at MININT
820
821
822
823
824
825
826
827
828
829
		 */
		uval = (unsigned)(((-(++val)) << 1) + 1);
	else
		uval = (unsigned)(val << 1);

	msbs = uval >> parameter;

	return 1 + parameter + msbs;
}

830
#if 0 /* UNUSED */
831
832
833
834
835
unsigned FLAC__bitbuffer_golomb_bits_signed(int val, unsigned parameter)
{
	unsigned bits, msbs, uval;
	unsigned k;

836
	FLAC__ASSERT(parameter > 0);
837

Josh Coalson's avatar
Josh Coalson committed
838
	/* fold signed to unsigned */
839
840
841
	if(val < 0)
		/* equivalent to
		 *     (unsigned)(((--val) << 1) - 1);
Josh Coalson's avatar
Josh Coalson committed
842
		 * but without the overflow problem at MININT
843
844
845
846
847
		 */
		uval = (unsigned)(((-(++val)) << 1) + 1);
	else
		uval = (unsigned)(val << 1);

848
	k = FLAC__bitmath_ilog2(parameter);
849
	if(parameter == 1u<<k) {
850
		FLAC__ASSERT(k <= 30);
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869

		msbs = uval >> k;
		bits = 1 + k + msbs;
	}
	else {
		unsigned q, r, d;

		d = (1 << (k+1)) - parameter;
		q = uval / parameter;
		r = uval - (q * parameter);

		bits = 1 + q + k;
		if(r >= d)
			bits++;
	}
	return bits;
}

unsigned FLAC__bitbuffer_golomb_bits_unsigned(unsigned uval, unsigned parameter)
Josh Coalson's avatar
Josh Coalson committed
870
871
{
	unsigned bits, msbs;
872
873
	unsigned k;

874
	FLAC__ASSERT(parameter > 0);
875

876
	k = FLAC__bitmath_ilog2(parameter);
877
	if(parameter == 1u<<k) {
878
		FLAC__ASSERT(k <= 30);
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895

		msbs = uval >> k;
		bits = 1 + k + msbs;
	}
	else {
		unsigned q, r, d;

		d = (1 << (k+1)) - parameter;
		q = uval / parameter;
		r = uval - (q * parameter);

		bits = 1 + q + k;
		if(r >= d)
			bits++;
	}
	return bits;
}
896
#endif /* UNUSED */
897

898
#ifdef FLAC__SYMMETRIC_RICE
Josh Coalson's avatar
Josh Coalson committed
899
FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
900
901
{
	unsigned total_bits, interesting_bits, msbs;
Josh Coalson's avatar
Josh Coalson committed
902
	FLAC__uint32 pattern;
903

Josh Coalson's avatar
Josh Coalson committed
904
905
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
906
	FLAC__ASSERT(parameter <= 31);
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936

	/* init pattern with the unary end bit and the sign bit */
	if(val < 0) {
		pattern = 3;
		val = -val;
	}
	else
		pattern = 2;

	msbs = val >> parameter;
	interesting_bits = 2 + parameter;
	total_bits = interesting_bits + msbs;
	pattern <<= parameter;
	pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */

	if(total_bits <= 32) {
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
			return false;
	}
	else {
		/* write the unary MSBs */
		if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
			return false;
		/* write the unary end bit, the sign bit, and binary LSBs */
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
			return false;
	}
	return true;
}

937
#if 0 /* UNUSED */
Josh Coalson's avatar
Josh Coalson committed
938
FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, FLAC__bool *overflow)
939
940
{
	unsigned total_bits, interesting_bits, msbs;
Josh Coalson's avatar
Josh Coalson committed
941
	FLAC__uint32 pattern;
942

Josh Coalson's avatar
Josh Coalson committed
943
944
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
945
	FLAC__ASSERT(parameter <= 31);
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980

	*overflow = false;

	/* init pattern with the unary end bit and the sign bit */
	if(val < 0) {
		pattern = 3;
		val = -val;
	}
	else
		pattern = 2;

	msbs = val >> parameter;
	interesting_bits = 2 + parameter;
	total_bits = interesting_bits + msbs;
	pattern <<= parameter;
	pattern |= (val & ((1<<parameter)-1)); /* the binary LSBs */

	if(total_bits <= 32) {
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
			return false;
	}
	else if(total_bits > max_bits) {
		*overflow = true;
		return true;
	}
	else {
		/* write the unary MSBs */
		if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
			return false;
		/* write the unary end bit, the sign bit, and binary LSBs */
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
			return false;
	}
	return true;
}
981
#endif /* UNUSED */
982

Josh Coalson's avatar
Josh Coalson committed
983
FLAC__bool FLAC__bitbuffer_write_symmetric_rice_signed_escape(FLAC__BitBuffer *bb, int val, unsigned parameter)
Josh Coalson's avatar
Josh Coalson committed
984
985
{
	unsigned total_bits, val_bits;
Josh Coalson's avatar
Josh Coalson committed
986
	FLAC__uint32 pattern;
Josh Coalson's avatar
Josh Coalson committed
987

Josh Coalson's avatar
Josh Coalson committed
988
989
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
990
	FLAC__ASSERT(parameter <= 31);
Josh Coalson's avatar
Josh Coalson committed
991

992
	val_bits = FLAC__bitmath_silog2(val);
Josh Coalson's avatar
Josh Coalson committed
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
	total_bits = 2 + parameter + 5 + val_bits;

	if(total_bits <= 32) {
		pattern = 3;
		pattern <<= (parameter + 5);
		pattern |= val_bits;
		pattern <<= val_bits;
		pattern |= (val & ((1 << val_bits) - 1));
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
			return false;
	}
	else {
		/* write the '-0' escape code first */
		if(!FLAC__bitbuffer_write_raw_uint32(bb, 3u << parameter, 2+parameter))
			return false;
		/* write the length */
		if(!FLAC__bitbuffer_write_raw_uint32(bb, val_bits, 5))
			return false;
		/* write the value */
		if(!FLAC__bitbuffer_write_raw_int32(bb, val, val_bits))
			return false;
	}
	return true;
}
1017
#endif /* ifdef FLAC__SYMMETRIC_RICE */
Josh Coalson's avatar
Josh Coalson committed
1018

Josh Coalson's avatar
Josh Coalson committed
1019
FLAC__bool FLAC__bitbuffer_write_rice_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
1020
{
1021
	unsigned total_bits, interesting_bits, msbs, uval;
Josh Coalson's avatar
Josh Coalson committed
1022
	FLAC__uint32 pattern;
Josh Coalson's avatar
Josh Coalson committed
1023

Josh Coalson's avatar
Josh Coalson committed
1024
1025
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
1026
	FLAC__ASSERT(parameter <= 30);
1027

Josh Coalson's avatar
Josh Coalson committed
1028
	/* fold signed to unsigned */
1029
1030
1031
	if(val < 0)
		/* equivalent to
		 *     (unsigned)(((--val) << 1) - 1);
Josh Coalson's avatar
Josh Coalson committed
1032
		 * but without the overflow problem at MININT
1033
1034
		 */
		uval = (unsigned)(((-(++val)) << 1) + 1);
Josh Coalson's avatar
Josh Coalson committed
1035
	else
1036
		uval = (unsigned)(val << 1);
Josh Coalson's avatar
Josh Coalson committed
1037

1038
	msbs = uval >> parameter;
1039
1040
	interesting_bits = 1 + parameter;
	total_bits = interesting_bits + msbs;
1041
1042
	pattern = 1 << parameter; /* the unary end bit */
	pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
Josh Coalson's avatar
Josh Coalson committed
1043

1044
1045
	if(total_bits <= 32) {
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
Josh Coalson's avatar
Josh Coalson committed
1046
1047
1048
1049
1050
1051
			return false;
	}
	else {
		/* write the unary MSBs */
		if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
			return false;
1052
		/* write the unary end bit and binary LSBs */
1053
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
Josh Coalson's avatar
Josh Coalson committed
1054
1055
1056
1057
1058
			return false;
	}
	return true;
}

1059
#if 0 /* UNUSED */
Josh Coalson's avatar
Josh Coalson committed
1060
FLAC__bool FLAC__bitbuffer_write_rice_signed_guarded(FLAC__BitBuffer *bb, int val, unsigned parameter, unsigned max_bits, FLAC__bool *overflow)
Josh Coalson's avatar
Josh Coalson committed
1061
{
1062
	unsigned total_bits, interesting_bits, msbs, uval;
Josh Coalson's avatar
Josh Coalson committed
1063
	FLAC__uint32 pattern;
Josh Coalson's avatar
Josh Coalson committed
1064

Josh Coalson's avatar
Josh Coalson committed
1065
1066
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
1067
	FLAC__ASSERT(parameter <= 30);
Josh Coalson's avatar
Josh Coalson committed
1068
1069
1070

	*overflow = false;

Josh Coalson's avatar
Josh Coalson committed
1071
	/* fold signed to unsigned */
1072
1073
1074
	if(val < 0)
		/* equivalent to
		 *     (unsigned)(((--val) << 1) - 1);
Josh Coalson's avatar
Josh Coalson committed
1075
		 * but without the overflow problem at MININT
1076
1077
		 */
		uval = (unsigned)(((-(++val)) << 1) + 1);
Josh Coalson's avatar
Josh Coalson committed
1078
	else
1079
		uval = (unsigned)(val << 1);
Josh Coalson's avatar
Josh Coalson committed
1080

1081
	msbs = uval >> parameter;
1082
1083
	interesting_bits = 1 + parameter;
	total_bits = interesting_bits + msbs;
1084
1085
	pattern = 1 << parameter; /* the unary end bit */
	pattern |= (uval & ((1<<parameter)-1)); /* the binary LSBs */
Josh Coalson's avatar
Josh Coalson committed
1086

1087
1088
	if(total_bits <= 32) {
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
Josh Coalson's avatar
Josh Coalson committed
1089
1090
			return false;
	}
1091
	else if(total_bits > max_bits) {
Josh Coalson's avatar
Josh Coalson committed
1092
1093
1094
1095
		*overflow = true;
		return true;
	}
	else {
1096
1097
		/* write the unary MSBs */
		if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
Josh Coalson's avatar
Josh Coalson committed
1098
			return false;
1099
		/* write the unary end bit and binary LSBs */
1100
		if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, interesting_bits))
Josh Coalson's avatar
Josh Coalson committed
1101
			return false;
1102
1103
1104
	}
	return true;
}
1105
#endif /* UNUSED */
1106

1107
#if 0 /* UNUSED */
Josh Coalson's avatar
Josh Coalson committed
1108
FLAC__bool FLAC__bitbuffer_write_golomb_signed(FLAC__BitBuffer *bb, int val, unsigned parameter)
1109
{
1110
	unsigned total_bits, msbs, uval;
1111
1112
	unsigned k;

Josh Coalson's avatar
Josh Coalson committed
1113
1114
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
1115
	FLAC__ASSERT(parameter > 0);
1116

Josh Coalson's avatar
Josh Coalson committed
1117
	/* fold signed to unsigned */
1118
1119
1120
	if(val < 0)
		/* equivalent to
		 *     (unsigned)(((--val) << 1) - 1);
Josh Coalson's avatar
Josh Coalson committed
1121
		 * but without the overflow problem at MININT
1122
1123
1124
1125
1126
		 */
		uval = (unsigned)(((-(++val)) << 1) + 1);
	else
		uval = (unsigned)(val << 1);

1127
	k = FLAC__bitmath_ilog2(parameter);
1128
1129
1130
	if(parameter == 1u<<k) {
		unsigned pattern;

1131
		FLAC__ASSERT(k <= 30);
1132
1133

		msbs = uval >> k;
1134
		total_bits = 1 + k + msbs;
1135
1136
1137
		pattern = 1 << k; /* the unary end bit */
		pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */

1138
1139
		if(total_bits <= 32) {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
				return false;
		}
		else {
			/* write the unary MSBs */
			if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
				return false;
			/* write the unary end bit and binary LSBs */
			if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
				return false;
		}
	}
	else {
		unsigned q, r, d;

		d = (1 << (k+1)) - parameter;
		q = uval / parameter;
		r = uval - (q * parameter);
Josh Coalson's avatar
Josh Coalson committed
1157
		/* write the unary MSBs */
1158
		if(!FLAC__bitbuffer_write_zeroes(bb, q))
Josh Coalson's avatar
Josh Coalson committed
1159
			return false;
1160
		/* write the unary end bit */
Josh Coalson's avatar
Josh Coalson committed
1161
1162
		if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
			return false;
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
		/* write the binary LSBs */
		if(r >= d) {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
				return false;
		}
		else {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
				return false;
		}
	}
	return true;
}

Josh Coalson's avatar
Josh Coalson committed
1176
FLAC__bool FLAC__bitbuffer_write_golomb_unsigned(FLAC__BitBuffer *bb, unsigned uval, unsigned parameter)
1177
{
1178
	unsigned total_bits, msbs;
1179
1180
	unsigned k;

Josh Coalson's avatar
Josh Coalson committed
1181
1182
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
1183
	FLAC__ASSERT(parameter > 0);
1184

1185
	k = FLAC__bitmath_ilog2(parameter);
1186
1187
1188
	if(parameter == 1u<<k) {
		unsigned pattern;

1189
		FLAC__ASSERT(k <= 30);
1190
1191

		msbs = uval >> k;
1192
		total_bits = 1 + k + msbs;
1193
1194
1195
		pattern = 1 << k; /* the unary end bit */
		pattern |= (uval & ((1u<<k)-1)); /* the binary LSBs */

1196
1197
		if(total_bits <= 32) {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, total_bits))
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
				return false;
		}
		else {
			/* write the unary MSBs */
			if(!FLAC__bitbuffer_write_zeroes(bb, msbs))
				return false;
			/* write the unary end bit and binary LSBs */
			if(!FLAC__bitbuffer_write_raw_uint32(bb, pattern, k+1))
				return false;
		}
	}
	else {
		unsigned q, r, d;

		d = (1 << (k+1)) - parameter;
		q = uval / parameter;
		r = uval - (q * parameter);
		/* write the unary MSBs */
		if(!FLAC__bitbuffer_write_zeroes(bb, q))
			return false;
		/* write the unary end bit */
		if(!FLAC__bitbuffer_write_raw_uint32(bb, 1, 1))
			return false;
		/* write the binary LSBs */
		if(r >= d) {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, r+d, k+1))
				return false;
		}
		else {
			if(!FLAC__bitbuffer_write_raw_uint32(bb, r, k))
				return false;
		}
Josh Coalson's avatar
Josh Coalson committed
1230
1231
1232
	}
	return true;
}
1233
#endif /* UNUSED */
Josh Coalson's avatar
Josh Coalson committed
1234

Josh Coalson's avatar
Josh Coalson committed
1235
FLAC__bool FLAC__bitbuffer_write_utf8_uint32(FLAC__BitBuffer *bb, FLAC__uint32 val)
Josh Coalson's avatar
Josh Coalson committed
1236
{
Josh Coalson's avatar
Josh Coalson committed
1237
	FLAC__bool ok = 1;
Josh Coalson's avatar
Josh Coalson committed
1238

Josh Coalson's avatar
Josh Coalson committed
1239
1240
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);
Josh Coalson's avatar
Josh Coalson committed
1241

1242
	FLAC__ASSERT(!(val & 0x80000000)); /* this version only handles 31 bits */
Josh Coalson's avatar
Josh Coalson committed
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280

	if(val < 0x80) {
		return FLAC__bitbuffer_write_raw_uint32(bb, val, 8);
	}
	else if(val < 0x800) {
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xC0 | (val>>6), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
	}
	else if(val < 0x10000) {
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xE0 | (val>>12), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
	}
	else if(val < 0x200000) {
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF0 | (val>>18), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
	}
	else if(val < 0x4000000) {
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xF8 | (val>>24), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
	}
	else {
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0xFC | (val>>30), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>24)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>18)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>12)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | ((val>>6)&0x3F), 8);
		ok &= FLAC__bitbuffer_write_raw_uint32(bb, 0x80 | (val&0x3F), 8);
	}

	return ok;
}

Josh Coalson's avatar
Josh Coalson committed
1281
FLAC__bool FLAC__bitbuffer_write_utf8_uint64(FLAC__BitBuffer *bb, FLAC__uint64 val)