ve-27.tmp

自己写的huffman压缩 自己写的huffman压缩 自己写的huffman压缩

#include "StdAfx.h"
#include "WinZip.h"
#define BLOCKSIZE 1000
#define WRITEBLOCKSIZE 1000
#define WORDSIZE 256
CWinZip::CWinZip(void)
: m_Path(_T(""))
, m_dePath(_T(""))
{

	m_CountedMem=new int[WORDSIZE];
	for(UINT i=0;i<WORDSIZE;i++)
	{
		m_CountedMem[i]=0;
	}
}CWinZip::~CWinZip(void)
{

}
bool CWinZip::CountWeight(const UINT& size,unsigned char*pbuf)
{
	for(UINT i=0;i<size;i++)
	{
		m_CountedMem[(unsigned char)pbuf[i]]++;
	}
	return true;
}

Huffman* CWinZip::Min(Huffman *huff,int num,bool*reached,bool& Empty)
{
	Empty=true;
	int j=0;
	Huffman *temp=new Huffman;
	for(int i=0;i<num;i++)
	{
		if(!reached[i]&&*temp>huff[i])
		{
			j=i;
			*temp=huff[i];		
			Empty=false;
			if(*temp==1)
				break;
		}
	}
	reached[j]=true;
	return temp;
}
void  CWinZip::Insert (const Huffman &mem,Huffman *huff,int num,bool*reached)
{
	for(int i=0;i<num;i++)
	{
		if(reached[i])
		{
			huff[i]=mem;
			reached[i]=false;
			return;
		}
	} 
}
bool CWinZip::GetPath(const bool& in,CString& path,CString &n)//０为取得输出路径，１为取得输入路径
{
	HRESULT hResult;
	CFileDialog filedlg(true);
	hResult=(int)filedlg.DoModal();
	if(FAILED(hResult))
		return false;
	n=filedlg.GetFileExt();
	if(in)
	{
		m_Path=filedlg.GetPathName();
		path=m_Path;
	}
	else
	{
		m_dePath=filedlg.GetPathName();
		path=m_dePath;
	}
	return true;
}
bool CWinZip::Zip()
{
	m_ProgCtrl->SetRange(0,100);
	////////////////////////////////////////////////////////////
	//读文件
	CFile *fileFrom;                                              //源文件
	fileFrom=new CFile(m_Path,CFile::modeReadWrite);
	unsigned char *pbuf=new unsigned char[BLOCKSIZE];
	int nBytesRead;
	do{
		nBytesRead= fileFrom->Read(pbuf, BLOCKSIZE );				//读文件
		CountWeight(nBytesRead,pbuf);                               //统计出现频率
	}while(nBytesRead==BLOCKSIZE);   //到达文件尾
	m_ProgCtrl->OffsetPos(10);
	////////////////////////////////////////////////
	//统计频率不为零的元素 并创建huffman叶节点
	Huffman huff[WORDSIZE];                                     //存放huffman树的叶节点的数组
	int huffArraysize=0;                                        //数组大小
	for(UINT i=0;i<WORDSIZE;i++)                                //创建huffman树的叶节点 频率不为零的才创建
	{
		if(m_CountedMem[i])
		{
			Huffman *h=new Huffman(m_CountedMem[i],i,NULL,NULL);
			huff[huffArraysize]=*h; 
			huffArraysize++;
		}
	}
	m_ProgCtrl->OffsetPos(10);
	///////////////////////////////////////////////////////////////
	//创建huffman树
	/*MinHeap<Huffman> H(1);
	H.Initialize(*huff,huffArraysize,WORDSIZE);*/
	Huffman* x, *y,*z;                                             //存入权值最小的那两个节点
	bool Empty;                                                 //huffman树的叶节点是否已经全部插入huffman树
	bool *ReachedCode=new bool[huffArraysize];                  //是否已插入的标记数组
	for(int i=0;i<huffArraysize;i++)
		ReachedCode[i]=false;
	while(true)
	{
		x=Min(huff,huffArraysize,ReachedCode,Empty);
		y=Min(huff,huffArraysize,ReachedCode,Empty);
		z=new Huffman(x->count+y->count,-1,x,y);
		if(Empty)
			break;
		Insert(*z,huff,huffArraysize,ReachedCode);
	}
	m_ProgCtrl->OffsetPos(10);
	delete []ReachedCode;
	////////////////////////////////////////////////////////////////////
	//编码
	m_huffmanCodeWide=new int[huffArraysize];
	m_AllCodeArrary=new byte[huffArraysize*2];                       //huffman树统计后二进制编码存放的数组
	m_CountedCode=new unsigned char[huffArraysize];
	m_AllCode=new int[WORDSIZE];
	m_MemSign=new int[huffArraysize]; 
	int CodeNo=0,ArrayNo=0;
	for(int i=0;i<huffArraysize;i++)
	{
		m_huffmanCodeWide[i]=0;
		m_CountedCode[i]=0;
		m_MemSign[i]=0;
	}
	m_ProgCtrl->OffsetPos(10);
	for(int i=0;i<huffArraysize*4;i++)
		m_AllCodeArrary[i]=0;
	PreOrder(x,CodeNo,ArrayNo,huffArraysize);                               //通过huffman树统计出编码
	m_ProgCtrl->OffsetPos(10);
	/////////////////////////////////////////////////////////////////////////////
	//再读文件并写文件
	fileFrom->SeekToBegin();
	CFile *fileTo;                                               //目标文件
	fileTo=new CFile(m_dePath,CFile::modeCreate|CFile::typeBinary|CFile::modeWrite);//创建文件
	int lenth=ArrayNo+(m_huffmanCodeWide[huffArraysize-1]-1)/8;
	fileTo->Write(&huffArraysize,4);
	fileTo->Write(&ArrayNo,4);
	//fileTo->Write(&lenth,4);
	fileTo->Write(m_CountedCode,huffArraysize);
	fileTo->Write(m_huffmanCodeWide,huffArraysize*4);
	fileTo->Write(m_AllCodeArrary,ArrayNo+1);
	byte *b_pbuf=new byte[WRITEBLOCKSIZE];
	for(int i=0;i<WRITEBLOCKSIZE;i++)
	b_pbuf[i]=0;
	m_ProgCtrl->OffsetPos(20);
	nBytesRead=BLOCKSIZE;
	unsigned long int bufferPt;
	do{
		int temp;
		bufferPt=1;
		while((bufferPt<WRITEBLOCKSIZE*8-8)&&nBytesRead==BLOCKSIZE)
		{
			nBytesRead= fileFrom->Read(pbuf,BLOCKSIZE );//每次读blocksize大小
			temp=nBytesRead;
			Translate(pbuf,b_pbuf,temp,bufferPt);//放入byte型的数组b_pbuf，直到放满
		}
		fileFrom->Seek(-temp,CFile::current);
		fileTo->Write(b_pbuf,WRITEBLOCKSIZE);//将B_pbuf的所有元素写入磁盘
	}while(nBytesRead==BLOCKSIZE);
	m_ProgCtrl->OffsetPos(20);
	fileFrom->Close();
	fileTo->Close();
	delete []m_MemSign;
	//delete []m_AllCode;
	delete []m_CountedCode;
	delete []m_huffmanCodeWide;
//	delete []m_AllCodeArrary;
	delete []pbuf;
	delete fileFrom;
//	delete fileTo;
	m_ProgCtrl->OffsetPos(10);
	return true;
}

bool CWinZip::PreOrder(Huffman *root,int& CodeNo,int& ArrayNo,const int& huffArraysize)
{
	if(root->code==-1)
	{
		if (!(m_huffmanCodeWide[CodeNo]%8)&&(m_huffmanCodeWide[CodeNo]!=0))
			ArrayNo++;
		m_AllCodeArrary[ArrayNo]<<=1;
		m_huffmanCodeWide[CodeNo]++;
		if(PreOrder(root->left,CodeNo,ArrayNo,huffArraysize))
			return 1;

		//ArrayNo=k+(i-1)/8+1;
		if(!m_huffmanCodeWide[CodeNo])
		{
			int i=m_huffmanCodeWide[CodeNo-1],j=m_MemSign[CodeNo],k=m_MemSign[CodeNo-1];
			while(i>0)
			{
				ArrayNo++;
				m_AllCodeArrary[j++]=m_AllCodeArrary[k++];
				i-=8;
			}
			m_huffmanCodeWide[CodeNo]=m_huffmanCodeWide[CodeNo-1];
		}
		
		m_huffmanCodeWide[CodeNo]--;
		m_AllCodeArrary[ArrayNo]=m_AllCodeArrary[ArrayNo]>>1;
         if(!(m_huffmanCodeWide[CodeNo]%8)&&m_huffmanCodeWide[CodeNo])
			ArrayNo--;
		//m_AllCodeArrary[ArrayNo]=m_AllCodeArrary[ArrayNo]>>1;
		if (!(m_huffmanCodeWide[CodeNo]%8)&&(m_huffmanCodeWide[CodeNo]!=0))
			ArrayNo++;
		m_AllCodeArrary[ArrayNo]=m_AllCodeArrary[ArrayNo]<<1|1;
		m_huffmanCodeWide[CodeNo]++;
		if(PreOrder(root->right,CodeNo,ArrayNo,huffArraysize))
			return 1;
		
		if(!m_huffmanCodeWide[CodeNo]){
			
			int	i=m_huffmanCodeWide[CodeNo-1],j=m_MemSign[CodeNo],k=m_MemSign[CodeNo-1];
			//ArrayNo=k+(i-1)/8+1;
			while(i>0)
			{
				ArrayNo++;
				m_AllCodeArrary[j++]=m_AllCodeArrary[k++];
				i-=8;
			}

			m_huffmanCodeWide[CodeNo]=m_huffmanCodeWide[CodeNo-1];
			//m_AllCodeArrary[ArrayNo]=m_AllCodeArrary[ArrayNo-1];
		}
		m_huffmanCodeWide[CodeNo]--;
		m_AllCodeArrary[ArrayNo]=m_AllCodeArrary[ArrayNo]>>1;
		if(!(m_huffmanCodeWide[CodeNo]%8)&&m_huffmanCodeWide[CodeNo])
			ArrayNo--;
	}
	else if(CodeNo<huffArraysize)
	{
		m_CountedCode[CodeNo]=root->code;
		m_AllCode[root->code]=CodeNo;
		//ArrayNo++;
		CodeNo++;
		if(CodeNo<huffArraysize)
		{
			m_MemSign[CodeNo]=m_MemSign[CodeNo-1]+(m_huffmanCodeWide[CodeNo-1]-1)/8+1;
			return 0;
		}
		else
			return 1; 
	}
	return 0;
}
void CWinZip::Translate(unsigned char* from,byte*to,int& SourceSize,unsigned long int& ArraySize)
{	//int offset=m_huffmanCodeWide[m_AllCode[from[i]]];
	CStake sk;
	int offset,j=(ArraySize-1)/8;
	for(int i=0;i<SourceSize;i++)
	{
		//ArrayNo=ArraySize/8;
		int m=m_huffmanCodeWide[m_AllCode[from[i]]];
 	    int n=m_AllCode[from[i]];
		if(m>8)
				offset=7;
		else
				offset=m-1;
		for(;m>0;m--)
		{
			sk.Add((m_AllCodeArrary[n]&(1<<offset))>>offset);
			offset--;
			if(offset==-1)
				n++;
			if(sk.Full())
			{
			to[j]=sk.Copy();
			j++;
			}
		}
		ArraySize+=m_huffmanCodeWide[m_AllCode[from[i]]];
		if(ArraySize>8*WRITEBLOCKSIZE)
		{
			to[j-1]=to[j-1]<<(8-m_huffmanCodeWide[m_AllCode[from[i]]]%8);
			ArraySize-=m_huffmanCodeWide[m_AllCode[from[i]]];
			SourceSize=SourceSize-i;
			break;
		}
	}
}
bool CWinZip::BuildTree(int& CodeSize,int& AsciiSize,Huffman *&x)
{
	x=new Huffman;
	Huffman *y=x;
	int m=0,offset;
	int n,BitSign;
	for(int i=0;i<AsciiSize;i++)
	{
		x=y;
		BitSign=0;
		if(m_huffmanCodeWide[i]-BitSign<=7)
		offset=m_huffmanCodeWide[i]-BitSign-1;
		else
		offset=7;
		
		while(true)
		{
			n=(m_AllCodeArrary[m]&(1<<offset))>>offset;
			if(n==0)
			{
				if(!x->left)
					x->left=new Huffman;
				x=x->left;
			}
			if(n==1)
			{
				if(!x->right)
					x->right=new Huffman;
				x=x->right;
			}
			if(BitSign<m_huffmanCodeWide[i])
			{
				BitSign++;
				offset--;
			}
			if(BitSign>=m_huffmanCodeWide[i])
			{
				x->code=m_CountedCode[i];
				x->count=1;
				m++;
				break;
			}
			if(offset==-1)
			{
				m++;
				if(m_huffmanCodeWide[i]-BitSign<=8)
				offset=m_huffmanCodeWide[i]-BitSign-1;
				else
				offset=7;
			}
		}
	}
	x=y;
	return 1;
}
bool CWinZip::reversion(byte* Code,unsigned char*& Ascii,int& num,Huffman* x)
{
	Huffman* huffTmp=x;
   Ascii=new unsigned char[BLOCKSIZE];
   int cusor,i=num,offset=7,j=0;
   while(j<BLOCKSIZE&&i<WRITEBLOCKSIZE)
   {
	   huffTmp=x;
	   while(true)
	   {
		   cusor=(Code[i]&(1<<offset))>>offset;
		   offset--;
		   if(cusor==0)
			   huffTmp=huffTmp->left;
		   if(cusor==1)
			   huffTmp=huffTmp->right;
		   if(huffTmp->count==1)
		   {
			   Ascii[j]=huffTmp->code;
			   j++;
			   break;
		   }
		   if(offset==-1)
		   {
			   offset=7;
			   i++;
		       if(i>WRITEBLOCKSIZE)
				   break;
		   }
	   }
   }
   num=i+1;
    return 1;
}
bool CWinZip::ReZip()
{
	//读文件
	CFile *fileFrom;                                              //源文件
	fileFrom=new CFile(m_Path,CFile::typeBinary|CFile::modeRead);
	int huffArraysize,lenth,ArrayNo;
	fileFrom->Read(&huffArraysize,4);
	fileFrom->Read(&ArrayNo,4);
	//fileFrom->Read(&lenth,4);
	m_huffmanCodeWide=new int[huffArraysize];
	m_AllCodeArrary=new byte[ArrayNo+1];                               //huffman树统计后二进制编码存放的数组
	m_CountedCode=new unsigned char[huffArraysize];
	m_AllCode=new int[WORDSIZE]; 
	m_MemSign=new int[huffArraysize];
	fileFrom->Read(m_CountedCode,huffArraysize);
	fileFrom->Read(m_huffmanCodeWide,huffArraysize*4);
	fileFrom->Read(m_AllCodeArrary,ArrayNo+1);
	m_MemSign[0]=0;
	for(int i=1;i<huffArraysize;i++)
		m_MemSign[i]=m_MemSign[i-1]+(m_huffmanCodeWide[i-1]-1)/8+1;
	Huffman *x;
  	BuildTree(lenth,huffArraysize,x);
	 byte* pbuf=new byte[WRITEBLOCKSIZE];				
	 byte* wbuf=new byte[BLOCKSIZE];
	 unsigned char* Ascii;
	 UINT nBytesRead;
	CFile *fileTo=new CFile(m_dePath,CFile::modeCreate|CFile::modeWrite);
	do{
		nBytesRead=fileFrom->Read(pbuf,WRITEBLOCKSIZE);
		int num=0;
		while(num<BLOCKSIZE)
		{
		  reversion(pbuf,Ascii,num,x);
	      fileTo->Write(Ascii,num);
		}
	}while(nBytesRead==WRITEBLOCKSIZE);
	fileTo->Close();
	fileFrom->Close();
	return 1;
}