huff.cpp

自己编写的对文件做哈夫曼无损压缩编码/解码的程序；

#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#include "HUFF.h"

#define MEM_LIMITLEN		1024000
#define END_OF_TABLE		256
#define MAX_TABLELEN		0x200

int Build_HuffTree(Huff_Item table[])
{	
	int min1,min2;	

	table[MAX_TABLELEN-1].count=0xffffffff;
	for(int cur=END_OF_TABLE;;cur++)
	{
		min1=MAX_TABLELEN-1;
		min2=MAX_TABLELEN-1;	
		for(int i=0; i<cur; i++)
		{
			if( table[i].count!=0 )
			{
				if( table[i].count<table[min1].count )
				{
					min2=min1;
					min1=i;
				}
				else if( table[i].count<table[min2].count )
					min2=i;				
			}			
		}

		if( min2==MAX_TABLELEN-1 )break;	
		
		table[cur].child_0 = min1;
		table[cur].child_1 = min2;
		table[cur].parent  = -1;
		table[cur].count   = table[min1].count+table[min2].count;

		table[min1].count = 0;
		table[min2].count = 0;
		table[min1].parent= cur;
		table[min2].parent= cur;		
	}
	return (cur-1);
}

void Covert_HuffTree_toCode(Huff_Item huffTable[], Huff_Code codeTable[])
{	
	int cur, parent, bitCount;
	unsigned long code,mask;
	for( int i=0; i<END_OF_TABLE; i++)
	{
		bitCount = 0;
		code = 0;
		mask = 1;
		cur = i;
		parent = huffTable[i].parent;
		while( parent!=-1 )
		{			
			if( cur==huffTable[parent].child_1 )code|=mask;
			bitCount++;
			mask<<=1;

			cur = parent;
			parent=huffTable[parent].parent;			
		}

		codeTable[i].bitCount = bitCount;
		codeTable[i].code = code;	
		//printf("%d -> \t%d:\t%d\n",i,bitCount,code);
	}

	return;
}

bool Compress_Data(BYTE* pSrc, int nSrcLen, BYTE** ppDes, int* pDesLen,Huff_Code table[])
{
	BYTE* pDes = new BYTE[nSrcLen];
	if( pDes==NULL )return false;

	unsigned long code=0;
	int bitCount=0;
	BYTE *p1=pSrc,*p2=pDes;
	for(int i=0; i<nSrcLen; i++,p1++)
	{
		code<<=table[*p1].bitCount;
		code |=table[*p1].code;

		bitCount+=table[*p1].bitCount;		
		if( bitCount>8 )
		{
			while( bitCount>8 )
			{
				bitCount = bitCount-8;
				*p2++=(BYTE)((code>>bitCount)&0xff);
			}
			code&=(0xff>>(8-bitCount));
		}		
	}

	if( bitCount!=0 )*p2++=(BYTE)(code<<(8-bitCount));

	bool ret=false;
	int len=p2-pDes;
	*ppDes = new BYTE[len];
	if( *ppDes!=NULL )
	{
		memcpy(*ppDes,pDes,len);
		*pDesLen = len;
		ret = true;
	}

	delete[] pDes;
	return ret;
}

bool Decompress_Data(BYTE* pSrc, int nSrcLen, BYTE* pDes, int nDesLen,Huff_Item table[], int root)
{
	unsigned long code=0, mask=0x80;
	int cur=0,parent=0, bitCount=0;
	BYTE *p1=pSrc,*p2=pDes, *pMax=pSrc+nSrcLen;
	while(nDesLen>0)
	{	
		cur = root;
		while(1)
		{
			if(bitCount<=0 )
			{
				code|=*p1++;			
				bitCount+=8;
			}
			parent = cur;
			if( code&mask )cur = table[parent].child_1;
			else cur = table[parent].child_0;
			if( cur==-1 )break;
			code<<=1;
			bitCount--;
		}
		
		*p2++ = parent;	
		nDesLen--;
	}

	if( p1-pSrc!=nSrcLen )return false;
	return true;
}

bool HUFF_Compress(BYTE* pSrc, int nSrcLen, BYTE** ppDes, int* pDesLen)
{
	if( nSrcLen<=3 )return false;
	//计算频度
	unsigned long count[END_OF_TABLE]={0};
	BYTE* pMax=pSrc+nSrcLen;
	BYTE* ptmp=pSrc;
	while(ptmp<pMax)count[*ptmp++]++;

	//初始化霍夫曼树
	Huff_Item huffTable[MAX_TABLELEN];
	memset(huffTable,0,sizeof(huffTable));
	for( int i=0; i<END_OF_TABLE; i++)
	{	
		huffTable[i].child_0 = -1;
		huffTable[i].child_1 = -1;
		huffTable[i].parent  = -1;
		huffTable[i].count   = count[i];
	}
	//创建霍夫曼树
	int root = Build_HuffTree(huffTable);

	//转换霍夫曼树为编码表
	Huff_Code codeTable[END_OF_TABLE];
	Covert_HuffTree_toCode(huffTable, codeTable);

	//编码数据
	BYTE *pDes=NULL;
	int desLen=0;
	if( !Compress_Data(pSrc,nSrcLen, &pDes, &desLen, codeTable) )return false;

	//存储数据
	int len = sizeof(nSrcLen)+sizeof(root)+sizeof(huffTable[0])*(root+1)+desLen;
	*ppDes = new BYTE[len];
	if( *ppDes==NULL )
	{
		delete[] pDes;
		return false;
	}	

	int off=0;
	memcpy(*ppDes+off,&nSrcLen,sizeof(nSrcLen));  off += sizeof(nSrcLen);
	memcpy(*ppDes+off,&root,sizeof(root)); off += sizeof(root);
	memcpy(*ppDes+off,huffTable,sizeof(huffTable[0])*(root+1)); off += sizeof(huffTable[0])*(root+1);
	memcpy(*ppDes+off,pDes,desLen);
	*pDesLen = len;

	delete[] pDes;
	return true;
}

bool HUFF_Decompress(BYTE* pSrc, int nSrcLen, BYTE** ppDes, int* pDesLen)
{	
	if( nSrcLen<=3 )return false;

	//准备压缩参数
	int nDesLen=0;
	int root=0;
	Huff_Item huffTable[MAX_TABLELEN];	
	int off=0;

	//得到字节数	
	memcpy(&nDesLen,pSrc+off,sizeof(nDesLen));  off += sizeof(nDesLen);
	//得到根节点号	
	memcpy(&root,pSrc+off,sizeof(root)); off += sizeof(root);
	if( nSrcLen<sizeof(nDesLen)+sizeof(root)+sizeof(huffTable[0])*(root+1) )return false;
	//得到霍夫曼表
	memcpy(huffTable,pSrc+off,sizeof(huffTable[0])*(root+1)); off += sizeof(huffTable[0])*(root+1);	

	*ppDes = new BYTE[nDesLen];
	if( *ppDes==NULL )return false;
	*pDesLen = nDesLen;
	//解压数据
	Decompress_Data(pSrc+off,nSrcLen-off,*ppDes,*pDesLen,huffTable,root);
	return true;
}