huffman.cpp

huffman编解码程序vc源码

#include "memory.h"
#include "io.h"
#include "fcntl.h"
#include "MyList.h"
#include "malloc.h"
#include "bitstream.h"
#include <sys/stat.h>
#include <sys/types.h>
#include "iostream.h"
#include "MyStack.h"

typedef struct _probability
{
	unsigned char m_code;
	int m_count;
} PROBABILITY;

typedef struct _htreenode
{
	PROBABILITY m_prob;
	struct _htreenode* parent;
	struct _htreenode* pLeft;
	struct _htreenode* pRight;
} HTNODE;

BITBUF* pB;

PROBABILITY m_probs[256]; //存储每个字节码出现的次数与编码值，该编码值用于排序时记录码值

HTNODE* pHfmR;			//霍夫曼树的根

void InitProbability(char* fname)
{
	int i;
	int fh;
	unsigned char m_buf[4096];
	int rc; //实际读到的字节数
	memset((void*)m_probs,0,256*sizeof(PROBABILITY));
	for(i=0;i<256;i++)
		m_probs[i].m_code=i;
	fh=_open(fname,_O_BINARY|_O_RDONLY);
	if(fh==-1)
	{
		return;
	}
	while(1)
	{
		rc=_read(fh,m_buf,4096);
		for(i=0;i<rc;i++)
			m_probs[*(m_buf+i)].m_count++;
		if(rc<4096)
			break;
	}
	_close(fh);
}

void SortProbability()
{
	PROBABILITY m_tmp;
	int i,j;
	for(i=0;i<256;i++)
	{
		for(j=i+1;j<256;j++)
		{
			if(m_probs[i].m_count>m_probs[j].m_count)
			{
				m_tmp=m_probs[i];
				m_probs[i]=m_probs[j];
				m_probs[j]=m_tmp;
			}
		}
	}
}
void SortAsCode()
{
	PROBABILITY m_tmp;
	int i,j;
	for(i=0;i<256;i++)
	{
		for(j=i+1;j<256;j++)
		{
			if(m_probs[i].m_code>m_probs[j].m_code)
			{
				m_tmp=m_probs[i];
				m_probs[i]=m_probs[j];
				m_probs[j]=m_tmp;
			}
		}
	}
}
int GEL(void* pD1,void* pD2)
{
	return ((HTNODE*)pD1)->m_prob.m_count-((HTNODE*)pD2)->m_prob.m_count;
}

void BuildSubTree(BERTLIST* pL)
{
	HTNODE *pT1,*pT2,*pT;
	if(::GetLength(pL)<=1)
		return;
	pT1=(HTNODE*)RemoveHead(pL);
	pT2=(HTNODE*)RemoveHead(pL);
	pT=(HTNODE*)malloc(sizeof(HTNODE));
	pT->m_prob.m_count=pT1->m_prob.m_count+pT2->m_prob.m_count;
	pT->parent=0;
	pT->pLeft=pT1;
	pT->pRight=pT2;
	pT1->parent=pT;
	pT2->parent=pT;
	::InsertToListAsc(pL,pT,GEL);
	BuildSubTree(pL);
}

void BuildHuffmanTree(char* fname)
{
	HTNODE* pT;
	int i;
	BERTLIST* m_list=::InitialList();
	InitProbability(fname);
	SortProbability();
	for(i=0;i<256;i++)
	{
		if(m_probs[i].m_count==0)
			continue;
		pT=(HTNODE*)malloc(sizeof(HTNODE));
		pT->m_prob=m_probs[i];
		pT->parent=0;
		pT->pLeft=0;
		pT->pRight=0;
		::AddDataToTail(m_list,(void*)pT);
	}
	BuildSubTree(m_list);
	pT=(HTNODE*)::RemoveHead(m_list);
	free(m_list);
	pHfmR=pT;
}

HTNODE* Visit(unsigned char c,HTNODE* pN)
{
	HTNODE* pT;
	if(pN==0)
		return 0;
	if(pN->pLeft==0 && pN->pRight==0 && pN->m_prob.m_code==c)
		return pN;
	pT=Visit(c,pN->pLeft);
	if(pT!=0)
		return pT;
	return Visit(c,pN->pRight);
}

HTNODE* FindLeaf(unsigned char c)
{
	return Visit(c,pHfmR);
}

void CodeByte(unsigned char c)
{
	STACK* pS=::InitialStack();
	HTNODE* pC=FindLeaf(c);
	if(pC==0)
	{
		cout<<"缺字符编码:"<<c<<endl;
		return;
	}
	HTNODE* pP=pC->parent;
	while(pP!=0)
	{
		if(pP->pLeft==pC)
		{
			PushByte(pS,0);

			//::SendOneBit(pB,0);
		}
		else if(pP->pRight==pC)
		{
			PushByte(pS,1);
			//::SendOneBit(pB,1);
		}
		pC=pP;
		pP=pC->parent;
	}
	while(!StackIsEmpty(pS))
		SendOneBit(pB,PopByte(pS));
	ReleaseStack(pS);
}
void WriteHead(char* dst)
{
	int fh;
	int i;
	fh=_open(dst,_O_CREAT|_O_BINARY|_O_RDWR|_O_TRUNC,_S_IREAD | _S_IWRITE);
	SortAsCode();
	for(i=0;i<256;i++)
		_write(fh,(void*)(&(m_probs[i].m_count)),sizeof(int));
	_close(fh);
}
void HuffmanCode(char* src,char* dst)
{
	struct _stat m_fs;
	int fh;
	int srcsize;
	unsigned char *pBuf;
	int i;
	fh=_open(src,_O_BINARY|_O_RDONLY);
	_fstat(fh,&m_fs);
	srcsize=m_fs.st_size;
	pB=::InitialBitBuf(srcsize,dst);
	pBuf=(unsigned char*)malloc(srcsize);
	_read(fh,pBuf,srcsize);
	_close(fh);
	for(i=0;i<srcsize;i++)
	{
		CodeByte(pBuf[i]);
		if(i%1024==0)
			cout<<".";
	}
	free(pBuf);
	WriteHead(dst);
	::WriteToFile(pB);
	free(pB);
}
unsigned char GetCode(HTNODE* pNode)
{
	if(pNode->pLeft==0 && pNode->pRight==0)
		return pNode->m_prob.m_code;
	if(GetBit(pB))
		return GetCode(pNode->pRight);
	else
		return GetCode(pNode->pLeft);
}
void UnCode(char* src,char* dst)
{
	struct stat m_stat;
	unsigned char *pBuf;
	int i;
	int fh=_open(src,_O_BINARY|_O_RDONLY);
	::fstat(fh,&m_stat);
	pB=::InitialBitBuf(m_stat.st_size-256*sizeof(unsigned int),src);
	_close(fh);
	::ReadFromFile(pB);
	pBuf=(unsigned char*)malloc(pHfmR->m_prob.m_count);
	for(i=0;i<pHfmR->m_prob.m_count;i++)
		*(pBuf+i)=GetCode(pHfmR);
	fh=_open(dst,_O_CREAT|_O_TRUNC|_O_BINARY|_O_WRONLY);
	_write(fh,pBuf,pHfmR->m_prob.m_count);
	_close(fh);
	free(pBuf);
}

void Compress(char* srcfname,char* dstfname)
{
	//建立霍夫曼树
	cout<<"\t\t压缩文件："<<srcfname<<"...\n";

	BuildHuffmanTree(srcfname);
	HuffmanCode(srcfname,dstfname);
}
void UnCompress(char* srcfname,char* dstfname)
{
	int fh;
	int i;
	HTNODE* pT;
	BERTLIST* m_list=::InitialList();
	fh=_open(srcfname,_O_BINARY|_O_RDONLY);
	for(i=0;i<256;i++)
	{
		m_probs[i].m_code=i;
		_read(fh,(void*)(&(m_probs[i].m_count)),sizeof(int));
	}
	_close(fh);
	SortProbability();
	for(i=0;i<256;i++)
	{
		if(m_probs[i].m_count==0)
			continue;
		pT=(HTNODE*)malloc(sizeof(HTNODE));
		pT->m_prob=m_probs[i];
		pT->parent=0;
		pT->pLeft=0;
		pT->pRight=0;
		::AddDataToTail(m_list,(void*)pT);
	}
	BuildSubTree(m_list);
	pT=(HTNODE*)::RemoveHead(m_list);
	free(m_list);
	pHfmR=pT;
	UnCode(srcfname,dstfname);
}