bitbuffer.c

tcpmp.src.0.72RC1 优秀的多媒体播放器TCPMP的源代码

/* libFLAC - Free Lossless Audio Codec library
 * Copyright (C) 2000,2001,2002,2003,2004,2005  Josh Coalson
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * - 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.
 */

#include <stdlib.h> /* for malloc() */
#include <string.h> /* for memcpy(), memset() */
#include "private/bitbuffer.h"
#include "private/bitmath.h"
#include "private/crc.h"
#include "FLAC/assert.h"

/*
 * 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.
 *
 */

/*
 * Some optimization strategies are slower with older versions of MSVC
 */
#if defined _MSC_VER && _MSC_VER <= 1200
#define FLAC__OLD_MSVC_FLAVOR
#endif

/*
 * 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 */

#ifndef FLAC__OLD_MSVC_FLAVOR
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
};
#endif

#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));
#ifndef FLAC__OLD_MSVC_FLAVOR
#define FLAC__ALIGNED_BLURB_UNARY(blurb) (byte_to_unary_table[blurb])
#endif
#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));
#ifndef FLAC__OLD_MSVC_FLAVOR
#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])))
#endif
#else
/* ERROR, only sizes of 8 and 32 are supported */
#endif

#define FLAC__BLURBS_TO_BITS(blurbs) ((blurbs) << FLAC__BITS_PER_BLURB_LOG2)

#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))

/* 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

#ifndef FLaC__INLINE
#define FLaC__INLINE
#endif

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;
};

#if FLAC__BITS_PER_BLURB == 32
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;
}
#endif

/*
 * 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.
 */
static FLAC__bool bitbuffer_resize_(FLAC__BitBuffer *bb, unsigned new_capacity)
{
	FLAC__blurb *new_buffer;

	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);

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

	new_buffer = (FLAC__blurb*)calloc(new_capacity, sizeof(FLAC__blurb));
	if(new_buffer == 0)
		return false;
	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;
		bb->bits = 0;
		bb->total_bits = FLAC__BLURBS_TO_BITS(new_capacity);
	}
	if(new_capacity < bb->consumed_blurbs+(bb->consumed_bits?1:0)) {
		bb->consumed_blurbs = new_capacity;
		bb->consumed_bits = 0;
		bb->total_consumed_bits = FLAC__BLURBS_TO_BITS(new_capacity);
	}
	free(bb->buffer); /* we've already asserted above that (0 != bb->buffer) */
	bb->buffer = new_buffer;
	bb->capacity = new_capacity;
	return true;
}

static FLAC__bool bitbuffer_grow_(FLAC__BitBuffer *bb, unsigned min_blurbs_to_add)
{
	unsigned new_capacity;

	FLAC__ASSERT(min_blurbs_to_add > 0);

	new_capacity = max(bb->capacity * 2, bb->capacity + min_blurbs_to_add);
	return bitbuffer_resize_(bb, new_capacity);
}

static FLAC__bool bitbuffer_ensure_size_(FLAC__BitBuffer *bb, unsigned bits_to_add)
{
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(0 != bb->buffer);

	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);
	else
		return true;
}

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)
{
	unsigned bytes;
	FLAC__byte *target;

	/* first shift the unconsumed buffer data toward the front as much as possible */
	if(bb->total_consumed_bits >= FLAC__BITS_PER_BLURB) {
#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;
		for( ; r < r_end; l++, r++)
			bb->buffer[l] = bb->buffer[r];
		for( ; l < r_end; l++)
			bb->buffer[l] = 0;
#else
		FLAC__ASSERT(false); /* ERROR, only sizes of 8 and 32 are supported */
#endif /* FLAC__BITS_PER_BLURB == 32 or 8 */

		bb->blurbs -= bb->consumed_blurbs;
		bb->total_bits -= FLAC__BLURBS_TO_BITS(bb->consumed_blurbs);
		bb->consumed_blurbs = 0;
		bb->total_consumed_bits = bb->consumed_bits;
	}

	/* grow if we need to */
	if(bb->capacity <= 1) {
		if(!bitbuffer_resize_(bb, 16))
			return false;
	}

	/* 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

	/* finally, read in some data */
	if(!read_callback(target, &bytes, client_data))
		return false;

	/* 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
	return true;
}

/***********************************************************************
 *
 * Class constructor/destructor
 *
 ***********************************************************************/

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

	/* calloc() implies:
		memset(bb, 0, sizeof(FLAC__BitBuffer));
		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 bb;
}

void FLAC__bitbuffer_delete(FLAC__BitBuffer *bb)
{
	FLAC__ASSERT(0 != bb);

	FLAC__bitbuffer_free(bb);
	free(bb);
}

/***********************************************************************
 *
 * Public class methods
 *
 ***********************************************************************/

FLAC__bool FLAC__bitbuffer_init(FLAC__BitBuffer *bb)
{
	FLAC__ASSERT(0 != bb);

	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);
}

FLAC__bool FLAC__bitbuffer_init_from(FLAC__BitBuffer *bb, const FLAC__byte buffer[], unsigned bytes)
{
	FLAC__ASSERT(0 != bb);
	FLAC__ASSERT(bytes > 0);

	if(!FLAC__bitbuffer_init(bb))
		return false;

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

	FLAC__ASSERT(0 != buffer);
	/* @@@ 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;
}

FLAC__bool FLAC__bitbuffer_concatenate_aligned(FLAC__BitBuffer *dest, const FLAC__BitBuffer *src)
{
	unsigned bits_to_add = src->total_bits - src->total_consumed_bits;

	FLAC__ASSERT(0 != dest);
	FLAC__ASSERT(0 != src);

	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) {
		memcpy(dest->buffer+dest->blurbs, src->buffer+src->consumed_blurbs, sizeof(FLAC__blurb)*(src->blurbs-src->consumed_blurbs + ((src->bits)? 1:0)));
	}
	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)));
	}
	else {
		dest->buffer[dest->blurbs] <<= bits_to_add;
		dest->buffer[dest->blurbs] |= (src->buffer[src->consumed_blurbs] & ((1u << bits_to_add) - 1));
	}
	dest->bits = src->bits;
	dest->total_bits += bits_to_add;
	dest->blurbs = dest->total_bits / FLAC__BITS_PER_BLURB;

	return true;
}

void FLAC__bitbuffer_free(FLAC__BitBuffer *bb)
{
	FLAC__ASSERT(0 != bb);

	if(0 != bb->buffer)
		free(bb->buffer);
	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;
}

FLAC__bool FLAC__bitbuffer_clear(FLAC__BitBuffer *bb)
{
	if(bb->buffer == 0) {
		bb->capacity = FLAC__BITBUFFER_DEFAULT_CAPACITY;
		bb->buffer = (FLAC__blurb*)calloc(bb->capacity, sizeof(FLAC__blurb));
		if(bb->buffer == 0)
			return false;
	}