huffman.c

著名的 helix realplayer 基于手机 symbian 系统的 播放器全套源代码

/* ***** BEGIN LICENSE BLOCK ***** 
 * Version: RCSL 1.0/RPSL 1.0 
 *  
 * Portions Copyright (c) 1995-2002 RealNetworks, Inc. All Rights Reserved. 
 *      
 * The contents of this file, and the files included with this file, are 
 * subject to the current version of the RealNetworks Public Source License 
 * Version 1.0 (the "RPSL") available at 
 * http://www.helixcommunity.org/content/rpsl unless you have licensed 
 * the file under the RealNetworks Community Source License Version 1.0 
 * (the "RCSL") available at http://www.helixcommunity.org/content/rcsl, 
 * in which case the RCSL will apply. You may also obtain the license terms 
 * directly from RealNetworks.  You may not use this file except in 
 * compliance with the RPSL or, if you have a valid RCSL with RealNetworks 
 * applicable to this file, the RCSL.  Please see the applicable RPSL or 
 * RCSL for the rights, obligations and limitations governing use of the 
 * contents of the file.  
 *  
 * This file is part of the Helix DNA Technology. RealNetworks is the 
 * developer of the Original Code and owns the copyrights in the portions 
 * it created. 
 *  
 * This file, and the files included with this file, is distributed and made 
 * available on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 
 * EXPRESS OR IMPLIED, AND REALNETWORKS HEREBY DISCLAIMS ALL SUCH WARRANTIES, 
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS 
 * FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 
 * 
 * Technology Compatibility Kit Test Suite(s) Location: 
 *    http://www.helixcommunity.org/content/tck 
 * 
 * Contributor(s): 
 *  
 * ***** END LICENSE BLOCK ***** */ 

/**************************************************************************************
 * Fixed-point MP3 decoder
 * Jon Recker ([e-mail]), Ken Cooke ([e-mail])
 * July 2003
 *
 * huffman.c - Huffman decoding of transform coefficients
 **************************************************************************************/

#include "coder.h"

/* helper macros - see comments in hufftabs.c about the format of the huffman tables */
#define GetMaxbits(x)   ((int)( (((unsigned short)(x)) >>  0) & 0x000f))
#define GetHLen(x)      ((int)( (((unsigned short)(x)) >> 12) & 0x000f))
#define GetCWY(x)       ((int)( (((unsigned short)(x)) >>  8) & 0x000f))
#define GetCWX(x)       ((int)( (((unsigned short)(x)) >>  4) & 0x000f))
#define GetSignBits(x)  ((int)( (((unsigned short)(x)) >>  0) & 0x000f))

#define GetHLenQ(x)     ((int)( (((unsigned char)(x)) >> 4) & 0x0f))
#define GetCWVQ(x)      ((int)( (((unsigned char)(x)) >> 3) & 0x01))
#define GetCWWQ(x)      ((int)( (((unsigned char)(x)) >> 2) & 0x01))
#define GetCWXQ(x)      ((int)( (((unsigned char)(x)) >> 1) & 0x01))
#define GetCWYQ(x)      ((int)( (((unsigned char)(x)) >> 0) & 0x01))

/* apply sign of s to the positive number x (save in MSB, will do two's complement in dequant) */
#define ApplySign(x, s)	{ (x) |= ((s) & 0x80000000); }

/**************************************************************************************
 * Function:    DecodeHuffmanPairs
 *
 * Description: decode 2-way vector Huffman codes in the "bigValues" region of spectrum
 *
 * Inputs:      valid BitStreamInfo struct, pointing to start of pair-wise codes
 *              pointer to xy buffer to received decoded values
 *              number of codewords to decode
 *              index of Huffman table to use
 *              number of bits remaining in bitstream
 *
 * Outputs:     pairs of decoded coefficients in vwxy
 *              updated BitStreamInfo struct
 *
 * Return:      number of bits used, or -1 if out of bits
 *
 * Notes:       assumes that nVals is an even number
 *              si_huff.bit tests every Huffman codeword in every table (though not
 *                necessarily all linBits outputs for x,y > 15)
 **************************************************************************************/
static int DecodeHuffmanPairs(int *xy, int nVals, int tabIdx, int bitsLeft, unsigned char *buf, int bitOffset)
{
	int i, x, y;
	int cachedBits, padBits, len, startBits, linBits, maxBits, minBits;
	HuffTabType tabType;
	unsigned short cw, *tBase, *tCurr;
	unsigned int cache;

	if(nVals <= 0) 
		return 0;

	if (bitsLeft < 0)
		return -1;
	startBits = bitsLeft;

	tBase = (unsigned short *)(huffTable + huffTabOffset[tabIdx]);
	linBits = huffTabLookup[tabIdx].linBits;
	tabType = huffTabLookup[tabIdx].tabType;

	ASSERT(!(nVals & 0x01));
	ASSERT(tabIdx < HUFF_PAIRTABS);
	ASSERT(tabIdx >= 0);
	ASSERT(tabType != invalidTab);

	/* initially fill cache with any partial byte */
	cache = 0;
	cachedBits = (8 - bitOffset) & 0x07;
	if (cachedBits)
		cache = (unsigned int)(*buf++) << (32 - cachedBits);
	bitsLeft -= cachedBits;

	if (tabType == noBits) {
		/* table 0, no data, x = y = 0 */
		for (i = 0; i < nVals; i+=2) {
			xy[i+0] = 0;
			xy[i+1] = 0;
		}
		return 0;
	} else if (tabType == oneShot) {
		/* single lookup, no escapes */
		maxBits = GetMaxbits(tBase[0]);
		tBase++;
		padBits = 0;
		while (nVals > 0) {
			/* refill cache - assumes cachedBits <= 16 */
			if (bitsLeft >= 16) {
				/* load 2 new bytes into left-justified cache */
				cache |= (unsigned int)(*buf++) << (24 - cachedBits);
				cache |= (unsigned int)(*buf++) << (16 - cachedBits);
				cachedBits += 16;
				bitsLeft -= 16;
			} else {
				/* last time through, pad cache with zeros and drain cache */
				if (cachedBits + bitsLeft <= 0)	return -1;
				if (bitsLeft > 0)	cache |= (unsigned int)(*buf++) << (24 - cachedBits);
				if (bitsLeft > 8)	cache |= (unsigned int)(*buf++) << (16 - cachedBits);
				cachedBits += bitsLeft;
				bitsLeft = 0;

				cache &= (signed int)0x80000000 >> (cachedBits - 1);
				padBits = 11;
				cachedBits += padBits;	/* okay if this is > 32 (0's automatically shifted in from right) */
			}

			/* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */
			while (nVals > 0 && cachedBits >= 11 ) {
				cw = tBase[cache >> (32 - maxBits)];
				len = GetHLen(cw);
				cachedBits -= len;
				cache <<= len;

				x = GetCWX(cw);		if (x)	{ApplySign(x, cache); cache <<= 1; cachedBits--;}
				y = GetCWY(cw);		if (y)	{ApplySign(y, cache); cache <<= 1; cachedBits--;}

				/* ran out of bits - should never have consumed padBits */
				if (cachedBits < padBits)
					return -1;

				*xy++ = x;
				*xy++ = y;
				nVals -= 2;
			}
		}
		bitsLeft += (cachedBits - padBits);
		return (startBits - bitsLeft);
	} else if (tabType == loopLinbits || tabType == loopNoLinbits) {
		tCurr = tBase;
		padBits = 0;
		while (nVals > 0) {
			/* refill cache - assumes cachedBits <= 16 */
			if (bitsLeft >= 16) {
				/* load 2 new bytes into left-justified cache */
				cache |= (unsigned int)(*buf++) << (24 - cachedBits);
				cache |= (unsigned int)(*buf++) << (16 - cachedBits);
				cachedBits += 16;
				bitsLeft -= 16;
			} else {
				/* last time through, pad cache with zeros and drain cache */
				if (cachedBits + bitsLeft <= 0)	return -1;
				if (bitsLeft > 0)	cache |= (unsigned int)(*buf++) << (24 - cachedBits);
				if (bitsLeft > 8)	cache |= (unsigned int)(*buf++) << (16 - cachedBits);
				cachedBits += bitsLeft;
				bitsLeft = 0;

				cache &= (signed int)0x80000000 >> (cachedBits - 1);
				padBits = 11;
				cachedBits += padBits;	/* okay if this is > 32 (0's automatically shifted in from right) */
			}

			/* largest maxBits = 9, plus 2 for sign bits, so make sure cache has at least 11 bits */
			while (nVals > 0 && cachedBits >= 11 ) {
				maxBits = GetMaxbits(tCurr[0]);
				cw = tCurr[(cache >> (32 - maxBits)) + 1];
				len = GetHLen(cw);
				if (!len) {
					cachedBits -= maxBits;
					cache <<= maxBits;
					tCurr += cw;
					continue;
				}
				cachedBits -= len;
				cache <<= len;
			
				x = GetCWX(cw);
				y = GetCWY(cw);

				if (x == 15 && tabType == loopLinbits) {
					minBits = linBits + 1 + (y ? 1 : 0);
					if (cachedBits + bitsLeft < minBits)
						return -1;
					while (cachedBits < minBits) {
						cache |= (unsigned int)(*buf++) << (24 - cachedBits);
						cachedBits += 8;
						bitsLeft -= 8;
					}
					if (bitsLeft < 0) {
						cachedBits += bitsLeft;
						bitsLeft = 0;
						cache &= (signed int)0x80000000 >> (cachedBits - 1);
					}
					x += (int)(cache >> (32 - linBits));
					cachedBits -= linBits;
					cache <<= linBits;
				}
				if (x)	{ApplySign(x, cache); cache <<= 1; cachedBits--;}

				if (y == 15 && tabType == loopLinbits) {
					minBits = linBits + 1;
					if (cachedBits + bitsLeft < minBits)