huffman2.c

一个Huffman的例子

{
long MaxCharCount;
long NumSymbols,i;

NumSymbols = HI->NumSymbols;

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

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

HI->MaxCharCount = MaxCharCount;
}

/*
 * sets MinCodeLen & MaxCodeLen which must be set
 *	for BuildEncodeTable
 *
 */
void Huff2_SetMinMaxCodeLen(struct Huff2Info *HI)
{
long MinCodeLen,MaxCodeLen;

MinCodeLen = 1;
while ( HI->NumCodesOfLen[MinCodeLen] == 0 ) MinCodeLen++;
MaxCodeLen = 31;
while ( HI->NumCodesOfLen[MaxCodeLen] == 0 ) MaxCodeLen--;

HI->MaxCodeLen = MaxCodeLen;
HI->MinCodeLen = MinCodeLen;
}

/*
 * Writes codelens out to the BII
 *
 * also sets MinCodeLen & MaxCodeLen which must be set
 *	for BuildEncodeTable
 *
 */
void Huff2_PackCodeLens(struct Huff2Info *HI)
{
long MinCodeLen,MaxCodeLen;
long i,j,GotNumSymbols;
ubyte RunData[32];
long RunLen;
long CurCodeLen;
struct LBitIOInfo * BII;

BII = HI->BII;

#ifdef PACKCODES_TOPSYM
GotNumSymbols = HI->NumSymbols;
while ( HI->CodeLenTable[GotNumSymbols-1] == 0 ) GotNumSymbols--;
if ( (HI->NumSymbols - GotNumSymbols) < 32 )
	{
	LBitIO_WriteBit(BII,0);
	GotNumSymbols = HI->NumSymbols;
	}
else
	{
	LBitIO_WriteBit(BII,1);
	CurCodeLen = intlog2(HI->NumSymbols);
	LBitIO_WriteBits(BII,GotNumSymbols,CurCodeLen);
	}
#else
GotNumSymbols = HI->NumSymbols;
#endif // PACKCODES_TOPSYM

MinCodeLen = 1;
while ( HI->NumCodesOfLen[MinCodeLen] == 0 ) MinCodeLen++;
MaxCodeLen = 31;
while ( HI->NumCodesOfLen[MaxCodeLen] == 0 ) MaxCodeLen--;

HI->MaxCodeLen = MaxCodeLen;
HI->MinCodeLen = MinCodeLen;

if ( MaxCodeLen >= 0xF )
	{
	LBitIO_WriteBits(BII,0xF,4);
	LBitIO_WriteBits(BII,MaxCodeLen-0xF,4);
	}
else
	{
	LBitIO_WriteBits(BII,MaxCodeLen,4);
	}

for(i=0;i<GotNumSymbols;)
	{
	RunLen = 0;
	while ( HI->CodeLenTable[i] == 0 && RunLen < 32 && i<GotNumSymbols )
		{
		RunLen++;
		i++;
		}
	if ( RunLen > 0 )
		{
		LBitIO_WriteBit(BII,0);
		LBitIO_WriteBits(BII,(RunLen-1),5);
		}

	RunLen = 0;
	while ( ( HI->CodeLenTable[i] != 0 || HI->CodeLenTable[i+1] != 0 ) && RunLen < 32 && i<GotNumSymbols )
		{
		RunData[RunLen] = HI->CodeLenTable[i];
		RunLen++; i++;
		}

	if ( RunLen > 0 )
		{
		LBitIO_WriteBit(BII,1);
		LBitIO_WriteBits(BII,(RunLen-1),5);

		for(j=0;j<RunLen;j++)
			{
			CurCodeLen = MaxCodeLen - RunData[j];
			while ( CurCodeLen >= 0x7 )
				{
				LBitIO_WriteBits(BII,0x7,3);
				CurCodeLen -= 0x7;
				}
			LBitIO_WriteBits(BII,CurCodeLen,3);
			}
		}
	}

}

/*
 * reads packed codelens to CodeLenTable
 *
 * also sets NumCodesOfLen
 *
 */
void Huff2_UnPackCodeLens(struct Huff2Info *HI)
{
long i,j,GotNumSymbols;
long MinCodeLen,MaxCodeLen,CurCodeLen;
long RunLen,CurCode;
struct LBitIOInfo * BII;
bool bit;

MemClearMacroFast(HI->CodeLenTable,HI->NumSymbols);
MemClearMacroFast(HI->NumCodesOfLen,32);
HI->MinCodeLen = HI->MaxCodeLen = 0;

BII = HI->BII;

#ifdef PACKCODES_TOPSYM
LBitIO_ReadBit(BII,bit);
if ( bit )
	{
	CurCodeLen = intlog2(HI->NumSymbols);
	LBitIO_ReadBits(BII,GotNumSymbols,CurCodeLen);
	}
else
	{
	GotNumSymbols = HI->NumSymbols;
	}
#else
GotNumSymbols = HI->NumSymbols;
#endif // PACKCODES_TOPSYM

LBitIO_ReadBits(BII,CurCode,4);
if ( CurCode == 0xF )
	{
	LBitIO_ReadBits(BII,CurCode,4);
	MaxCodeLen = CurCode + 0xF;
	}
else
	{
	MaxCodeLen = CurCode;
	}
HI->MaxCodeLen = MaxCodeLen;

MinCodeLen = MaxCodeLen;

for(i=0;i<GotNumSymbols; )
	{
	LBitIO_ReadBit(BII,bit);
	LBitIO_ReadBits(BII,RunLen,5);
	RunLen++;
	if ( bit == 0 )
		{
		for(j=0;j<RunLen;j++)
			{
			HI->CodeLenTable[i++] = 0;
			}
		}
	else
		{
		for(j=0;j<RunLen;j++)
			{
			CurCodeLen = 0;
			LBitIO_ReadBits(BII,CurCode,3);
			while( CurCode == 0x7 )
				{
				CurCodeLen += 0x7;
				LBitIO_ReadBits(BII,CurCode,3);
				}
			CurCodeLen += CurCode;

			CurCodeLen = MaxCodeLen - CurCodeLen;

			HI->CodeLenTable[i++] = CurCodeLen;
			if ( CurCodeLen > 0 )	HI->NumCodesOfLen[CurCodeLen] ++;

			if ( CurCodeLen < MinCodeLen && CurCodeLen > 0 ) MinCodeLen = CurCodeLen;
			}
		}
	}

HI->MinCodeLen = MinCodeLen;
}

/*
 * Writes codelens out to the BII
 *
 *	compresses differences for an earlier huff build
 *	 you must allocate lastcodelens, & set to 0 initially
 *
 * also sets MinCodeLen & MaxCodeLen which must be set
 *	for BuildEncodeTable
 *
 */
void Huff2_PackCodeLens_Delta(struct Huff2Info *HI,long * LastCodeLens)
{
long MinCodeLen,MaxCodeLen;
long i,j,GotNumSymbols;
ubyte RunData[512],RunDataLast[512];
long RunLen;
long CurCodeLen;
struct LBitIOInfo * BII;

BII = HI->BII;

#ifdef PACKCODES_TOPSYM
GotNumSymbols = HI->NumSymbols;
while ( HI->CodeLenTable[GotNumSymbols-1] == 0 ) GotNumSymbols--;
if ( (HI->NumSymbols - GotNumSymbols) < 32 )
	{
	LBitIO_WriteBit(BII,0);
	GotNumSymbols = HI->NumSymbols;
	}
else
	{
	LBitIO_WriteBit(BII,1);
	CurCodeLen = intlog2(HI->NumSymbols);
	LBitIO_WriteBits(BII,GotNumSymbols,CurCodeLen);
	}
#else
GotNumSymbols = HI->NumSymbols;
#endif // PACKCODES_TOPSYM

MinCodeLen = 1;
while ( HI->NumCodesOfLen[MinCodeLen] == 0 ) MinCodeLen++;
MaxCodeLen = 31;
while ( HI->NumCodesOfLen[MaxCodeLen] == 0 ) MaxCodeLen--;

HI->MaxCodeLen = MaxCodeLen;
HI->MinCodeLen = MinCodeLen;

if ( MaxCodeLen >= 0xF )
	{
	LBitIO_WriteBits(BII,0xF,4);
	LBitIO_WriteBits(BII,MaxCodeLen-0xF,4);
	}
else
	{
	LBitIO_WriteBits(BII,MaxCodeLen,4);
	}

for(i=0;i<GotNumSymbols;)
	{
	RunLen = 0;
	while ( ( HI->CodeLenTable[i] - LastCodeLens[i] ) == 0 && i<GotNumSymbols )
		{
		RunLen++;
		i++;
		}
	if ( RunLen >= 0x03 )
		{
		LBitIO_WriteBits(BII,0x03,2);
		RunLen -= 0x3;
		if ( RunLen >= 0x07 )
			{
			long Thresh,Bits;

			LBitIO_WriteBits(BII,0x07,3);
			RunLen -= 0x7;

			Thresh = 0xF; Bits = 4;
			while ( RunLen >= Thresh )
				{
				LBitIO_WriteBits(BII,Thresh,Bits);
				RunLen -= Thresh;
				Thresh += Thresh + 1; Bits++;
				}
			LBitIO_WriteBits(BII,RunLen,Bits);
			}
		else
			{
			LBitIO_WriteBits(BII,RunLen,3);
			}	
		}
	else
		{
		LBitIO_WriteBits(BII,RunLen,2);
		}
	if ( i == GotNumSymbols ) break;

	RunLen = 0;
	while ( ( ( HI->CodeLenTable[i] - LastCodeLens[i] ) != 0 ) && i<GotNumSymbols )
		{
		RunData[RunLen] = HI->CodeLenTable[i];
		RunDataLast[RunLen] = LastCodeLens[i];
		RunLen++; i++;
		if ( RunLen == 512 ) return; /* BAD ! */
		}
	if ( RunLen >= 0x03 )
		{
		j = RunLen;
		LBitIO_WriteBits(BII,0x03,2);
		RunLen -= 0x3;
		if ( RunLen >= 0x07 )
			{
			long Thresh,Bits;

			LBitIO_WriteBits(BII,0x07,3);
			RunLen -= 0x7;

			Thresh = 0xF; Bits = 4;
			while ( RunLen >= Thresh )
				{
				LBitIO_WriteBits(BII,Thresh,Bits);
				RunLen -= Thresh;
				Thresh += Thresh + 1; Bits++;
				}
			LBitIO_WriteBits(BII,RunLen,Bits);
			}
		else
			{
			LBitIO_WriteBits(BII,RunLen,3);
			}	
		RunLen = j;
		}
	else
		{
		LBitIO_WriteBits(BII,RunLen,2);
		}

	if ( RunLen > 0 )
		{
		for(j=0;j<RunLen;j++)
			{
			if ( RunDataLast[j] == 0 )
				{
				CurCodeLen = MaxCodeLen - RunData[j];
				while ( CurCodeLen >= 0x7 )
					{
					LBitIO_WriteBits(BII,0x7,3);
					CurCodeLen -= 0x7;
					}
				LBitIO_WriteBits(BII,CurCodeLen,3);				
				}
			else
				{
				CurCodeLen = RunData[j] - RunDataLast[j];
				if ( CurCodeLen < 0 )
					{
					LBitIO_WriteBit(BII,0);
					CurCodeLen = - (CurCodeLen + 1);
					}
				else
					{
					LBitIO_WriteBit(BII,1);
					CurCodeLen--;
					}
				while ( CurCodeLen > 0 )
					{
					LBitIO_WriteBit(BII,0);
					CurCodeLen --;
					}
				LBitIO_WriteBit(BII,1);
				}
			}
		}
	}

for(i=0;i<HI->NumSymbols;i++)
	{
	LastCodeLens[i] = HI->CodeLenTable[i];
	}

}

/*
 * reads packed codelens to CodeLenTable
 *
 * also sets NumCodesOfLen
 *
 * <> doesn't decode new style of runlen yet
 *
 */
void Huff2_UnPackCodeLens_Delta(struct Huff2Info *HI,long * LastCodeLens)
{
long i,j,GotNumSymbols;
long MinCodeLen,MaxCodeLen,CurCodeLen;
long RunLen,CurCode;
struct LBitIOInfo * BII;
bool bit;
long sign;

BII = HI->BII;

MemClear((long *)HI->NumCodesOfLen,32*sizeof(long));

#ifdef PACKCODES_TOPSYM
LBitIO_ReadBit(BII,bit);
if ( bit )
	{
	CurCodeLen = intlog2(HI->NumSymbols);
	LBitIO_ReadBits(BII,GotNumSymbols,CurCodeLen);
	}
else
	{
	GotNumSymbols = HI->NumSymbols;
	}
#else
GotNumSymbols = HI->NumSymbols;
#endif // PACKCODES_TOPSYM

LBitIO_ReadBits(BII,CurCode,4);
if ( CurCode == 0xF )
	{
	LBitIO_ReadBits(BII,CurCode,4);
	MaxCodeLen = CurCode + 0xF;
	}
else
	{
	MaxCodeLen = CurCode;
	}
HI->MaxCodeLen = MaxCodeLen;

MinCodeLen = MaxCodeLen;

for(i=0;i<GotNumSymbols; )
	{
	LBitIO_ReadBit(BII,bit);
	LBitIO_ReadBits(BII,RunLen,5);
	RunLen++;
	if ( bit == 0 )
		{
		for(j=0;j<RunLen;j++)
			{
			HI->CodeLenTable[i] = LastCodeLens[i]; i++;
			}
		}
	else
		{
		for(j=0;j<RunLen;j++)
			{
			if ( LastCodeLens[i] > 0 )
				{
				LBitIO_ReadBit(BII,bit);
				if ( bit ) sign = -1;
				else sign = 1;
				LBitIO_ReadBit(BII,bit);
				CurCodeLen = 1;
				while( bit == 0 )
					{
					CurCodeLen++;
					LBitIO_ReadBit(BII,bit);
					}

				CurCodeLen = CurCodeLen * sign + LastCodeLens[i];
				}
			else
				{
				CurCodeLen = 0;
				LBitIO_ReadBits(BII,CurCode,3);
				while( CurCode == 0x7 )
					{
					CurCodeLen += 0x7;
					LBitIO_ReadBits(BII,CurCode,3);
					}
				CurCodeLen += CurCode;
	
				CurCodeLen = MaxCodeLen - CurCodeLen;
				}

			HI->CodeLenTable[i++] = CurCodeLen;
			if ( CurCodeLen > 0 )	HI->NumCodesOfLen[CurCodeLen] ++;

			if ( CurCodeLen < MinCodeLen && CurCodeLen > 0 ) MinCodeLen = CurCodeLen;
			}
		}
	}

for(i=0;i<HI->NumSymbols;i++)
	{
	LastCodeLens[i] = HI->CodeLenTable[i];
	}

HI->MinCodeLen = MinCodeLen;
}


/*
 * QuickSort on the NodeWork array
 *  set Huff2QuickSortArray
 *
 */
void Huff2QuickSort(long Left,long Right)
{
if ( (Right - Left) > 1 )
	{
	long i;
		{
		long j;
		long pivot;
		struct Huff2CodeNode *swapper;
		register struct Huff2CodeNode ** Array;

		Array = Huff2QuickSortArray;

		pivot = Array[Right]->Count;
		i = Left-1;
		j = Right;
		for(;;)
			{
			/* could remove i < Right && j > Left checking by putting
				dummy array slots in [-1] and [GotNumSymbols] w/ Counts 0 and LONG_MAX */
			do ++i; while(Array[i]->Count < pivot && i < Right);
			do --j; while(Array[j]->Count > pivot && j > Left);
			if (i >= j) break;
			swapper  = Array[i];
			Array[i] = Array[j];
			Array[j] = swapper;
			}
		swapper  = Array[i];
		Array[i] = Array[Right];
		Array[Right] = swapper;
		}
	Huff2QuickSort(Left,i-1);
	Huff2QuickSort(i+1,Right);
	}
else
	{
	if ( Right > Left )
		{
		if ( Huff2QuickSortArray[Right]->Count < Huff2QuickSortArray[Left]->Count )
			{
			struct Huff2CodeNode *swapper;

			swapper  = Huff2QuickSortArray[Left];
			Huff2QuickSortArray[Left] = Huff2QuickSortArray[Right];
			Huff2QuickSortArray[Right] = swapper;
			}
		}
	}
}

/*
 * Radix sort on the NodeWork
 *	counts must be bounded by [0,MaxCharCount]
 * this is much faster than QuickSort for large NumSymbols
 *
 * I think NumSymbols as small as 256 is still faster here
 *	    Radix = O(256 + 2*NumSymbols)
 *	QuickSort = O(NumSymbols*log2(NumSymbols))
 * bigOs are equal for NumSymbols == 64
 *
 * NOTEZ: uses the ->Up in the codenode structure
 *  			resets ->Up to NULL when its done
 *
 */
bool  Huff2RadixSort(struct Huff2CodeNode ** BucketArray,
	long MaxCharCount,struct Huff2CodeNode ** Array,long ArraySize)
{
register struct Huff2CodeNode * CurNode;
register long i,j;

MemClear((long *)BucketArray,sizeofpointer*(MaxCharCount+1));

/* go backwards so that alphabetic order is preserved */
for(i=(ArraySize-1);i>=0;i--)
	{
	Array[i]->Up = BucketArray[Array[i]->Count];
	BucketArray[Array[i]->Count] = Array[i];
	}

j=0;
for(i=0;i<=MaxCharCount;i++)
	{
	CurNode = BucketArray[i];
	while(CurNode) /* $ 15% */
		{
		Array[j] = CurNode;
		CurNode = CurNode->Up;
		Array[j]->Up = NULL;
		j++;
		}
	}

if ( j != ArraySize )
	{
	return(0);
	}

return(1);
}