huffman2.c

一个Huffman的例子

			GotC = CurNode->Char;
			if ( GotC == HUFF2_CODE_BRANCH )
				{
				CurCodeLen++;		

#ifdef DEBUG
				if ( CurCodeLen > 31 )
					{
					fprintf(stderr,"CodeLen > 31 !");
					return(0);
					}
#endif

				if ( CurNode->Down )
					{
					GotC = CurNode->Down->Char;
					if ( GotC == HUFF2_CODE_BRANCH )
						{
						StackArray[StackI++] = (ulong) CurNode->Down;
						StackArray[StackI++] = CurCodeLen;
	
#ifdef DEBUG
						if ( StackI >= (HI->NumSymbols * 2) )
							{
							errputs("Stack usage higher than expected!");
							exit(10);
							}
#endif
	
						}
					else
						{
						CodeLenTable[GotC] = CurCodeLen;
						NumCodesOfLen[CurCodeLen] ++;
						}
					}
	
				CurNode = CurNode->Up;
				}
			else
				{
				CodeLenTable[GotC] = CurCodeLen;
				NumCodesOfLen[CurCodeLen] ++;
				CurNode = NULL;
				}
			}
	
		}
		
	}
/* end codelen-retrieval registered variables */

return(1);
}

/*
 * at this point CodeLenTable & NumCodesOfLen are filled out
 *
 */
bool Huff2_BuildEncodeTable(struct Huff2Info *HI)
{
ulong LastCodePrefix;
ulong * CodePrefixByLen;
ulong * CharToCodeTable;
long * CodeLenTable;
long * NumCodesOfLen;
long NumSymbols;
long i;
long CurCodeLen;
ulong CurCode;

NumSymbols = HI->NumSymbols;

if ( HI->MaxCodeLen == 0 )
	return(0);
if ( HI->MaxCodeLen > 30 )
	return(0);

if ( HI->EnDe_codeTable )
	{
	CharToCodeTable = (ulong *) HI->EnDe_codeTable;
	MemClear((long *)CharToCodeTable,HI->EnDe_codeTableLen);
	}
else
	{
	if ( (CharToCodeTable = AllocMem(NumSymbols*sizeof(ulong),MEMF_ANY|MEMF_CLEAR)) == NULL )
		return(0);

	HI->EnDe_codeTable = (void *) CharToCodeTable;
	HI->EnDe_codeTableLen = NumSymbols*sizeof(ulong);
	}

CodePrefixByLen = HI->CodePrefixByLen;
CodeLenTable = HI->CodeLenTable;
NumCodesOfLen = HI->NumCodesOfLen;

LastCodePrefix = 0;
CodePrefixByLen[HI->MinCodeLen] = 0;
for(i=(HI->MinCodeLen);i<(HI->MaxCodeLen);)
	{
	LastCodePrefix = (LastCodePrefix + NumCodesOfLen[i]) << 1;
	i++;
	CodePrefixByLen[i] = LastCodePrefix;
	}

for(i=0;i<NumSymbols;i++)
	{
	CurCodeLen = CodeLenTable[i];
	if ( CurCodeLen > 0 )
		{
		CurCode = CodePrefixByLen[CurCodeLen]++;
		CharToCodeTable[i] = CurCode;
		}
	}

return(1);
}

/*
 * at this point CodeLenTable & NumCodesOfLen are filled out
 *
 */
bool Huff2_BuildDecodeTable(struct Huff2Info *HI)
{
ulong BaseCodeByLen[32]; /* I'm lazy! So sue me! */
ulong LastCodePrefix;
ulong * CodePrefixByLen;
uword * DecodeTable;
long * CodeLenTable;
long * NumCodesOfLen;
long NumSymbols;
long i,CurCodeLen;
ulong CurCode,PackedCode;
long NumCodesOfLowerLen;

NumSymbols = HI->NumSymbols;

if ( HI->MaxCodeLen == 0 )
	return(0);
if ( HI->MaxCodeLen > 30 )
	return(0);

if ( HI->EnDe_codeTable )
	{
	DecodeTable = (uword *) HI->EnDe_codeTable;
	MemClear((long *)DecodeTable,HI->EnDe_codeTableLen);
	}
else
	{
	HI->EnDe_codeTableLen = 2*NumSymbols*sizeof(uword);
	if ( (DecodeTable = AllocMem(HI->EnDe_codeTableLen,MEMF_ANY|MEMF_CLEAR)) == NULL )
		return(0);

	HI->EnDe_codeTable = (void *) DecodeTable;
	}

CodePrefixByLen = HI->CodePrefixByLen;
CodeLenTable = HI->CodeLenTable;
NumCodesOfLen = HI->NumCodesOfLen;

LastCodePrefix = 0;
NumCodesOfLowerLen = 0;
CodePrefixByLen[HI->MinCodeLen] = 0;
BaseCodeByLen[HI->MinCodeLen] = 0;
for(i=(HI->MinCodeLen);i<(HI->MaxCodeLen);)
	{
	LastCodePrefix = (LastCodePrefix + NumCodesOfLen[i]) << 1;
	NumCodesOfLowerLen += NumCodesOfLen[i];
	i++;
	CodePrefixByLen[i] = LastCodePrefix;
	BaseCodeByLen[i] = LastCodePrefix - NumCodesOfLowerLen;
	}

for(i=0;i<NumSymbols;i++)
	{
	CurCodeLen = CodeLenTable[i];
	if ( CurCodeLen > 0 )
		{
		CurCode = CodePrefixByLen[CurCodeLen]++;
		PackedCode = CurCode - BaseCodeByLen[CurCodeLen];
		DecodeTable[PackedCode] = CurCodeLen;
		DecodeTable[PackedCode+NumSymbols] = i;
		}
	}

for(i=(HI->MinCodeLen);i<=(HI->MaxCodeLen);i++)
	{
	CodePrefixByLen[i] = BaseCodeByLen[i];
	}

return(1);
}

/*
 * The FastDecodeTable is a raw 8 bit table (256 entries)
 *  it is indexed by the next 8 bits of the input bitstream
 *	and the value of the table is :
 *		number of bits used  (max of 8) = 3 bits -> 1byte
 *		number of chars made (max of 4) = 2 bits -> 1 byte
 *		values of chars made (max of 4) = 8 bytes
 * total size = 256*10 = 2560 bytes (not bad!)
 * 	( note that this could be as low as 256*5 = 1280 bytes )
 *
 * note that you must also keep the old decodetable around,
 *	in case the code is longer than 8 bits ( numberofcharsmade == 0 )
 * 
 * <> todo: make this routine take the number of bits of the table
 *	as a parameter
 *
 */

bool Huff2_BuildFastDecodeTable(struct Huff2Info *HI)
{
struct FastDecodeItem * FastDecodeTable;
uword * DecodeTable;
long NumSymbols;
long Huff2CodeLen;
ulong CurCode,StartCode,Huff2Code,CheckCode,ReadCodeMask,PackedCode;
long DecodeTableLen,FastDecodeTableLen;
long MinCodeLen,NumBitsUsed;
uword GotChar;
ulong * CodePrefixByLen;

CodePrefixByLen = HI->CodePrefixByLen;
NumSymbols = HI->NumSymbols;
MinCodeLen = HI->MinCodeLen;

if ( HI->MaxCodeLen == 0 )
	return(0);
if ( HI->MaxCodeLen > 30 )
	return(0);

DecodeTableLen = 2*NumSymbols*sizeof(uword);
FastDecodeTableLen = 256*sizeof(struct FastDecodeItem);

if ( HI->EnDe_codeTable )
	{
	DecodeTable = (uword *)HI->EnDe_codeTable;
	FastDecodeTable = (struct FastDecodeItem *) ( (char *)HI->EnDe_codeTable + DecodeTableLen );
	MemClear((long *)DecodeTable,DecodeTableLen);
	MemClear((long *)FastDecodeTable,FastDecodeTableLen);
	}
else
	{
	HI->EnDe_codeTableLen = DecodeTableLen + FastDecodeTableLen;
	if ( (HI->EnDe_codeTable = AllocMem(HI->EnDe_codeTableLen,MEMF_ANY|MEMF_CLEAR)) == NULL )
		return(0);

	DecodeTable = (uword *)HI->EnDe_codeTable;
	FastDecodeTable = (struct FastDecodeItem *) ( ((char *)HI->EnDe_codeTable) + DecodeTableLen ); 
	}

/* build the old style table */
if ( ! Huff2_BuildDecodeTable(HI) )
	return(0);

/* now DecodeTable is filled out */

/* step through all the codes & find what chars correspond to them
		when you find a char for a code, propagate it through all codes which
			have that as a prefix
	 keep going until NumBitsFree < Huff2CodeLen  for all entries */
for(StartCode=0;StartCode<255;StartCode++)
	{
	NumBitsUsed = FastDecodeTable[StartCode].NumBitsUsed;
	while ( (8-NumBitsUsed) >= MinCodeLen && FastDecodeTable[StartCode].NumCharsMade < FD_MAXCHARSMADE )
		{
		CurCode = StartCode ;

		/* find char that encodes to curcode */
		Huff2CodeLen = MinCodeLen;
		Huff2Code = ( CurCode >> (8 - NumBitsUsed - Huff2CodeLen) ) & ( (1<<Huff2CodeLen) - 1 ) ;
		ReadCodeMask = 1 << ( 7 - NumBitsUsed - Huff2CodeLen ) ;
		PackedCode = Huff2Code;
		while( DecodeTable[PackedCode] != Huff2CodeLen )
			{
			Huff2Code += Huff2Code;
			if ( CurCode & ReadCodeMask ) Huff2Code++;
			ReadCodeMask >>= 1;
			Huff2CodeLen++;

			if ( ReadCodeMask == 0 )
				goto DoneWithCurCode;

			PackedCode = Huff2Code - CodePrefixByLen[Huff2CodeLen];			
			}

		if ( Huff2CodeLen > (8 - NumBitsUsed) )
			goto DoneWithCurCode;

		GotChar = DecodeTable[PackedCode+NumSymbols];

		/* step through while Huff2Code is the next code
				all occurances of Huff2Code will be contiguous */
		do
			{
			if ( FastDecodeTable[CurCode].NumCharsMade < FD_MAXCHARSMADE )
				{
				FastDecodeTable[CurCode].CharsMade[FastDecodeTable[CurCode].NumCharsMade] = GotChar;
				FastDecodeTable[CurCode].NumCharsMade++;
				FastDecodeTable[CurCode].NumBitsUsed = NumBitsUsed + Huff2CodeLen;
				}
			CurCode ++;
			NumBitsUsed = FastDecodeTable[CurCode].NumBitsUsed;
			if ( Huff2CodeLen > (8-NumBitsUsed) ) break;
			CheckCode = ( CurCode >> (8 - NumBitsUsed - Huff2CodeLen) ) & ( (1<<Huff2CodeLen) - 1 ) ;
			} while ( CheckCode == Huff2Code );

		NumBitsUsed = FastDecodeTable[StartCode].NumBitsUsed;
		}

	DoneWithCurCode: /* see Knuth : "Structured use of Goto" :^> */ 

	continue;

	}

HI->NumCharsWaiting = 0;

return(1);
}

void Huff2_EncodeC(struct Huff2Info *HI,uword Symbol)
{
register ulong CurCode;
register long CurCodeLen;
register struct LBitIOInfo * BII;

CurCode 	 = ((ulong *)HI->EnDe_codeTable)[Symbol];
CurCodeLen = HI->CodeLenTable[Symbol];
BII 			 = HI->BII;

#ifdef DEBUG
if ( CurCodeLen == 0 )
	{
	errputs("Got EncodeC for CodeLen == 0 symbol!");
	exit(10);
	}
#endif

LBitIO_WriteBits(BII,CurCode,CurCodeLen);

}

bool Huff2_FastDecodeArray_Ubyte(struct Huff2Info *HI,ubyte * Array,long ArrayLen)
{
register ulong PeekedCode;
register struct FastDecodeItem * FastDecodeTable;
long NumCharsMade;
uword * CharsMade;
long NumSymbols;
uword * DecodeTable;
ulong * CodePrefixByLen;
ulong CurCode,PackedCode;
long CurCodeLen;
bool bit;
ubyte *CurArrayPtr,*ArrayPtrDone;
LocalLBitIO_Variables();

LocalLBitIO_GetState(HI->BII);
NumSymbols = HI->NumSymbols;
FastDecodeTable = (struct FastDecodeItem *) ( ((char *)HI->EnDe_codeTable) + 2*NumSymbols*sizeof(uword) );
DecodeTable = (uword *)HI->EnDe_codeTable;
CodePrefixByLen = HI->CodePrefixByLen;
CurArrayPtr = Array;
ArrayPtrDone = Array + ArrayLen - 4;

while ( CurArrayPtr < ArrayPtrDone )
	{
	LocalLBitIO_PeekBits(PeekedCode,8);
	
	NumCharsMade = FastDecodeTable[PeekedCode].NumCharsMade;
	if ( NumCharsMade > 0 )
		{
		CurCodeLen = FastDecodeTable[PeekedCode].NumBitsUsed;
		LocalLBitIO_SkipBits(CurCodeLen);
		switch ( NumCharsMade )
			{
			case 1:
				*CurArrayPtr++ = *(FastDecodeTable[PeekedCode].CharsMade);
				break;
			case 2:
				CharsMade = FastDecodeTable[PeekedCode].CharsMade;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade;
				break;
			case 3:
				CharsMade = FastDecodeTable[PeekedCode].CharsMade;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade;
				break;
			case 4:
				CharsMade = FastDecodeTable[PeekedCode].CharsMade;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade++;
				*CurArrayPtr++ = *CharsMade;
				break;
			}
		}
	else /* use old decode method, can read 9 bits automatically */
		{
		CurCodeLen = 8;
		CurCode = PeekedCode;
		LocalLBitIO_SkipBits(8);
		PackedCode = CurCode - CodePrefixByLen[CurCodeLen];
		
		/* could read another bit here, but who cares? */	

		while( DecodeTable[PackedCode] != CurCodeLen )
			{
			CurCode += CurCode;
			LocalLBitIO_ReadBit(bit);
			CurCode += bit;
			CurCodeLen++;
		
			PackedCode = CurCode - CodePrefixByLen[CurCodeLen];
			}
		
		*CurArrayPtr++ = DecodeTable[PackedCode+NumSymbols];
		}
	}

LocalLBitIO_PutState(HI->BII);

/* do normal decode for last 4 to make sure we don't go too far */

ArrayPtrDone += 4;
while ( CurArrayPtr < ArrayPtrDone )
	{
	*CurArrayPtr++ = Huff2_DecodeC(HI);
	}

return(1);
}

uword Huff2_FastDecodeC(struct Huff2Info *HI)
{

#if FD_MAXCHARSMADE_SUBONE > 0
if ( HI->NumCharsWaiting > 0 )
	{
	HI->NumCharsWaiting--;
	return(HI->CharsWaiting[HI->NumCharsWaiting]);
	}
#endif // FD_MAXCHARSMADE_SUBONE == 0

/* variables not init-ed if there are chars waiting */
 {
struct FastDecodeItem * FastDecodeTable;
ulong PeekedCode;
struct LBitIOInfo * BII;
long NumSymbols;

NumSymbols = HI->NumSymbols;

FastDecodeTable = (struct FastDecodeItem *) ( ((char *)HI->EnDe_codeTable) + 2*NumSymbols*sizeof(uword) );
BII = HI->BII;

LBitIO_PeekBits(BII,PeekedCode,8);

if ( FastDecodeTable[PeekedCode].NumCharsMade > 0 )
	{
	LBitIO_SkipBits(BII,FastDecodeTable[PeekedCode].NumBitsUsed);
#if FD_MAXCHARSMADE_SUBONE > 0
	HI->NumCharsWaiting = FastDecodeTable[PeekedCode].NumCharsMade - 1;
	switch ( HI->NumCharsWaiting ) /* !<>! */
		{
		case 0:
			break;
		case 1:
			HI->CharsWaiting[0] = FastDecodeTable[PeekedCode].CharsMade[1];
			break;
		case 2:
			HI->CharsWaiting[1] = FastDecodeTable[PeekedCode].CharsMade[1];
			HI->CharsWaiting[0] = FastDecodeTable[PeekedCode].CharsMade[2];
			break;
		case 3:
			HI->CharsWaiting[2] = FastDecodeTable[PeekedCode].CharsMade[1];
			HI->CharsWaiting[1] = FastDecodeTable[PeekedCode].CharsMade[2];
			HI->CharsWaiting[0] = FastDecodeTable[PeekedCode].CharsMade[3];
			break;
		}
#endif // FD_MAXCHARSMADE_SUBONE == 0
	return( FastDecodeTable[PeekedCode].CharsMade[0] );
	}
else /* use old decode method, can read 9 bits automatically */
	{
	uword * DecodeTable;
	ulong * CodePrefixByLen;
	ulong CurCode,PackedCode;
	long CurCodeLen;
	bool bit;
	
	DecodeTable = (uword *)HI->EnDe_codeTable;
	CodePrefixByLen = HI->CodePrefixByLen;
	
	CurCodeLen = 8;
	CurCode = PeekedCode;
	LBitIO_SkipBits(BII,8);
	PackedCode = CurCode - CodePrefixByLen[CurCodeLen];

	/* could read another bit here, but who cares? */	

	while( DecodeTable[PackedCode] != CurCodeLen )
		{
		CurCode += CurCode;
		LBitIO_ReadBit(BII,bit);
		CurCode += bit;
		CurCodeLen++;
	
		PackedCode = CurCode - CodePrefixByLen[CurCodeLen];
		}
	
#ifdef DEBUG
	if ( CurCodeLen > HI->MaxCodeLen )
		{
		errputs("Got code longer than MaxCodeLen!");
		exit(10);
		}
#endif
	
	return(DecodeTable[PackedCode+NumSymbols]);
	}

 }
/* end variable-space */

}

uword Huff2_DecodeC(struct Huff2Info *HI)
{
uword * DecodeTable;
long NumSymbols;
ulong * CodePrefixByLen;
ulong CurCode,PackedCode;
long CurCodeLen;
struct LBitIOInfo * BII;
bool bit;

NumSymbols = HI->NumSymbols;
DecodeTable = (uword *) HI->EnDe_codeTable;
CodePrefixByLen = HI->CodePrefixByLen;
BII = HI->BII;

CurCodeLen = HI->MinCodeLen;
LBitIO_ReadBits(BII,CurCode,CurCodeLen)
PackedCode = CurCode;

while( DecodeTable[PackedCode] != CurCodeLen )
	{
	CurCode += CurCode;
	LBitIO_ReadBit(BII,bit);
	CurCode += bit;
	CurCodeLen++;

	PackedCode = CurCode - CodePrefixByLen[CurCodeLen];
	}

#ifdef DEBUG
if ( CurCodeLen > HI->MaxCodeLen )
	{
	errputs("Got code longer than MaxCodeLen!");
	exit(10);
	}
#endif

return(DecodeTable[PackedCode+NumSymbols]);
}

/*
 * Scale Counts to [0,MaxVal] 
 *  (brackets indicate the range is "inclusive")
 *
 * a count which was > 0 will not be scaled to 0
 *
 */
void Huff2_ScaleCounts(struct Huff2Info *HI,long * CharCounts,long MaxVal)
{
long MaxCharCount;
long NumSymbols,i;
long OutCharCount;

NumSymbols = HI->NumSymbols;

//get maxcharcount
MaxCharCount = 0;
for(i=0;i<NumSymbols;i++)
	{
	if ( CharCounts[i] > MaxCharCount ) MaxCharCount = CharCounts[i];
	}

//scale counts
if ( MaxCharCount > MaxVal )
	{
	for(i=0;i<NumSymbols;i++)
		{
		OutCharCount = ( (long)CharCounts[i] * MaxVal ) / MaxCharCount;
		if ( OutCharCount > MaxVal ) OutCharCount = MaxVal;
		else if ( CharCounts[i] && ! OutCharCount ) OutCharCount = 1;
		CharCounts[i] = OutCharCount;
		}
	}

if ( HI->MaxCharCount != MaxVal && HI->SortType == HUFF2_SORT_RADIX &&
			HI->SortWork != NULL )
	{
	FreeMem(HI->SortWork,sizeofpointer*(HI->MaxCharCount+1));
	HI->SortWork = NULL;
	}

HI->MaxCharCount = min(MaxCharCount,MaxVal);

}

/*
 * Sets ->MaxCharCount in HI
 *
 */
void Huff2_GetMaxCharCount(struct Huff2Info *HI,long * CharCounts)