huff.c

mp3解码源代码

	{ 0,14,22,25,30,34,37,40,45,49,51,52,53,55,56,56,
	57,57,57,57,58,58,59,59,60,60,60,60,60,60,60,60,
	61,61,61,61,61,61,61,61,62,62,62,62,62,62,62,62,
	63,63,63,63,63,63,63,63,63,63,63,63,63,63,63,63,},

	{ 0,9,14,18,23,28,30,33,37,39,41,44,46,47,48,49,
	50,52,53,53,54,54,55,55,56,56,56,56,57,57,57,57,
	58,58,59,59,60,60,60,60,61,61,61,61,61,61,61,61,
	62,62,62,62,62,62,62,62,63,63,63,63,63,63,63,63,},

	{ 0,133,167,191,203,217,224,231,238,241,244,246,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 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,58,92,115,132,147,160,169,178,185,193,197,205,209,214,218,
	223,226,228,230,233,235,237,238,240,241,242,244,245,246,247,247,
	248,248,249,249,250,250,251,251,252,252,252,252,252,252,252,252,
	253,253,253,253,254,254,254,254,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,19,52,99,162,191,211,223,231,238,243,245,248,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,254,254,254,254,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},

	{ 0,4,8,11,13,16,18,20,22,24,26,29,58,58,58,58,
	59,82,98,114,131,149,160,169,177,185,193,202,209,213,217,221,
	226,231,234,236,238,241,243,244,245,247,248,248,249,249,250,251,
	252,252,252,252,253,253,253,253,254,254,254,254,255,255,255,255,},
};

static const UINT32 *tables[32] = {
	0,   h1,  h2,  h3,  0,   h5,  h6,  h7,
	h8,  h9,  h10, h11, h12, h13, 0,   h15,
	h16, h16, h16, h16, h16, h16, h16, h16,
	h24, h24, h24, h24, h24, h24, h24, h24
};

static const INT16 t_linbits[32] = {
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,6,8,10,13,4,5,6,7,8,9,11,13
};

/****************************************************************************/

int HUFF_decode_pair(HUFFMAN *h, INT16 table, INT16 count, INT16 *x)
{
	static const UINT32 mask[20] = {
		0x00000000, 0x80000000, 0xC0000000, 0xE0000000,
		0xF0000000, 0xF8000000, 0xFC000000, 0xFE000000,
		0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000,
		0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000,
		0xFFFF0000, 0xFFFF8000, 0xFFFFC000, 0xFFFFE000
	};

	const UINT32 *ht = tables[table];
	register const UINT32 *h_tab;
	UINT32 chunk;
	INT32 chunk_cache = 0;
	INT16 cache_size = 0;
	INT16 linbits = t_linbits[table];
	INT16 len, lag, dir_flag;
	int pos;
	INT16 tmp;
	const UINT8 *cue;

	if (!ht) {
		while (count--) {
			x[0] = x[1] = 0;
			x += 2;
		}
		return(0);
	}

	cue = h_cue[table];

	while (count--) {

		if (cache_size < (NC_O+2)) {
			// NC_O+1+1 (1+1 for signs of pair)
			chunk_cache |= HUFF_read_bits(h, 32-cache_size);
			cache_size = 32;
		}
		tmp = (UINT32)chunk_cache >> (32-NC_O);
		h_tab = ht + cue[tmp];
		len = (*h_tab >> 8) & 0x1F;

		if (((*h_tab ^ chunk_cache) & mask[len]) || (len > NC_O)) {
			if( cache_size < 21 ) {
				// 19+1+1 (1+1 for signs of pair)
				chunk_cache |= HUFF_read_bits(h, 32-cache_size);
				cache_size = 32;
			}

			lag = cue[tmp + 1] - cue[tmp];
			chunk = chunk_cache | 0x1FFF;
			dir_flag = 0;
			while (lag > 1) { // Dichotomic search
				if (!dir_flag)
					h_tab += lag>>1;
				else
					h_tab -= lag>>1;
				if (*h_tab > chunk) {
					if (!dir_flag)
						lag >>= 1;
					else
						lag -= lag>>1;
					dir_flag = -1;
				} else {
					if (!dir_flag)
					 	lag -= lag>>1;
					else
						lag >>= 1;
					dir_flag = 0;
				}
			}
			len = (*h_tab >> 8) & 0x1F;
			if ((*h_tab ^ chunk_cache) & mask[len]) {
				if (!dir_flag)
					h_tab++;
				else
					h_tab--;
				len = (*h_tab >> 8) & 0x1F;
			}
		}

		chunk_cache <<= len;
		cache_size -= len;

		x[0] = (*h_tab >> 4) & 0x0F;
		x[1] = *h_tab & 0x0F;

		if (!linbits) {
			if (x[0]) {
				if (chunk_cache < 0)
					 x[0] = -x[0];
				chunk_cache <<= 1;
				cache_size--;
			}
			if (x[1]) {
				if (chunk_cache < 0)
					x[1] = -x[1];
				chunk_cache <<= 1;
				cache_size--;
			}
		} else {
			if (x[0] == 15) {
				chunk_cache |= HUFF_read_bits(h, 32-cache_size);
				cache_size = 32 - linbits;
				x[0] += (UINT32)chunk_cache >> (cache_size);
				chunk_cache <<= linbits;
			}
			if (x[0]) {
				if (chunk_cache < 0)
					x[0] = -x[0];
				chunk_cache <<= 1;
				cache_size--;
			}
			if(x[1] == 15) {
				chunk_cache |= HUFF_read_bits(h, 32-cache_size);
				cache_size = 32 - linbits;
				x[1] += (UINT32)chunk_cache >> (cache_size);
				chunk_cache <<= linbits;
			}
			if (x[1]) {
				if (chunk_cache < 0)
					x[1] = -x[1];
				chunk_cache <<= 1;
				cache_size--;
			}
		}
		x += 2;
	}

	pos = HUFF_pos(h);
	pos -= cache_size;
	HUFF_seek(h, pos);
	return(0);
}

/****************************************************************************/

int HUFF_decode_quad(HUFFMAN *h, INT16 table, INT16 max_bits,
                      INT16 val_count, INT16 val_top, INT16 *isp)
{
	static const UINT8 huff_quad_tab1[64] = {
		0x6B, 0x6F, 0x6D, 0x6E, 0x67, 0x65,
		0x59, 0x59, 0x56, 0x56, 0x53, 0x53, 0x5A, 0x5A, 0x5C, 0x5C,
		0x42, 0x42, 0x42, 0x42, 0x41, 0x41, 0x41, 0x41,
		0x44, 0x44, 0x44, 0x44, 0x48, 0x48, 0x48, 0x48,
		0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
		0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
		0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10,
		0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10, 0x10
	};
	UINT8 q;
	UINT32 bit_cache = 0;
	INT16 bit_cache_size = 0;
	INT16 len;
	INT16 *x;

	x = isp;
	while ((max_bits > 0) && (val_count < val_top)) {
		if (bit_cache_size < 10) {
			bit_cache |= HUFF_read_bits(h, 32-bit_cache_size);
			bit_cache_size = 32;
		}
		max_bits -= bit_cache_size;
		if (table) {
			q = bit_cache >> (32-4);
			bit_cache <<= 4;
			bit_cache_size -= 4;
			q ^= 0xF;
		} else {
         		q = huff_quad_tab1[(INT16)(bit_cache >> (32-6))];
         		len = q >> 4;
         		q &= 0xF;
         		bit_cache <<= len;
         		bit_cache_size -= len;
		}
		if (q) {
			x[0] = (q>>3) & 1;
			x[1] = (q>>2) & 1;
			x[2] = (q>>1) & 1;
			x[3] = q & 1;

			q = 4;
			while (q--) {
				if (*x) {
					if (bit_cache & 0x80000000)
						*x = -*x;
					bit_cache <<= 1;
					bit_cache_size--;
				}
				x++;
			}
		} else {
			*x++ = 0;
			*x++ = 0;
			*x++ = 0;
			*x++ = 0;
		}
		val_count += 4,
		max_bits += bit_cache_size;
	}

	// Zero rest of band
	len = h->nul_begin - val_count;
	while((len--) > 0)
		*x++ = 0;
	h->nul_begin = val_count; // Update zero begin

	return(0);
}

/****************************************************************************/