unredfun.cpp

利用shannon定理对文件进行压缩与解压缩

#include <fstream.h>
#include <string.h>
#include <math.h>
#include "unredfun.h"

/*-------------------------------------------------------
目的：读取文件头中有关解码的信息,并将其保存到类变量中
输入：无
输出：bool 读表头成功返回true，否则返回false
-------------------------------------------------------*/
bool FUReduce::ReadFHead()
{
	if(m_fileName != NULL)
	{
		ifstream in(m_fileName, ios::binary | ios::nocreate);
		unsigned char tempCh = 0x00;
		in.read(&tempCh, 1);							// 读表头第一个字节（编码规则个数）
		m_codeNum = tempCh + 1;
		if(m_codeNum == 0)
		{
			return false;
		}
		m_pCode = new CRule [m_codeNum];				// 为编码规则分配空间
		m_pCodeLength = new unsigned char [m_codeNum];	// 存放各码字个长度
		int i = 0;		// 指示第i+1组编码规则
		int j = 0;		// 指示码字中第j个码元
		int time = 0;
		char* str = NULL;
		bool flag = true;
		while(i<m_codeNum)
		{
			in.read(&m_pCode[i].fByte,1);
			in.read(&m_pCodeLength[i], 1);
			m_pCode[i].code = new char[m_pCodeLength[i]+1];
			for(int t=0; t<m_pCodeLength[i]; t++)
			{
				m_pCode[i].code[t] = '\0';
			}
			j = 0;
			time = 0;
			unsigned char bitCode = 0x00;		// 存放码字
			in.read(&bitCode, 1);
			flag = true;
			while(flag)
			{	
				str = Trans(bitCode);
				if((m_pCodeLength[i]-time*8)<=8)
				{
					for(; j<m_pCodeLength[i]; j++)
					{
						m_pCode[i].code[j] = str[j-time*8];
					}
					m_pCode[i].code[j] = '\0';
					flag = false;
				}
				else
				{
					if(0!=strlen(m_pCode[i].code))
					{
						strcat(m_pCode[i].code, str);
					}
					else
					{
						strcpy(m_pCode[i].code, str);
					}
					j+=8;
					time++;
					in.read(&bitCode, 1);
				}
			}
			i++;
		}
		m_here = in.tellg();		// 记录编码规则的结尾处
		return true;
	}
	else
	{
		return false;
	}
}

/*-------------------------------------------------------
目的：构造函数，初始化对象
输入：char* FileName 待解压文件名
输出：无
-------------------------------------------------------*/
FUReduce::FUReduce(char* FileName)
{
	strcpy(m_fileName, FileName);
	m_pCodeLength = NULL;
	m_pCode = NULL;
	m_codeNum = 0;
	m_pT = NULL;
}

/*-------------------------------------------------------
目的：构造函数，初始化对象
输入：char* FileName 待解压文件名
输出：无
-------------------------------------------------------*/
FUReduce::~FUReduce()
{
	m_fileName[0] = '\0';
	m_pCodeLength = NULL;
	m_pCode = NULL;
	m_codeNum = 0;
	m_pT = NULL;
}

/*-------------------------------------------------------
目的：构造译码树
输入：无
输出：构造树成功返回true；否则返回false；
-------------------------------------------------------*/
bool FUReduce::CreatDecodeTree()
{
	if(m_fileName==NULL)
	{
		return false;
	}
	else
	{
		m_pT = new DecodeTree;				// 头结点
		m_pT->data = '\0';
		m_pT->lchild = NULL;
		m_pT->rchild = NULL;
		DecodeTree* prePoint = m_pT;		// 指向前一个结点
		DecodeTree* curPoint = m_pT;		// 指向当前结点

		int i = 0, j = 0;
		for(i=0; i<m_codeNum; i++)
		{
			j = 0;							// 指示码字长度
			while(j<m_pCodeLength[i])
			{
				if(m_pCode[i].code[j] == '1')
				{					
					if(curPoint->lchild == NULL)
					{
						curPoint = new DecodeTree;
						curPoint->data = '1';
						curPoint->lchild = NULL;
						curPoint->rchild = NULL;
						prePoint->lchild = curPoint;
						prePoint = curPoint;
					}
					else
					{
						curPoint = curPoint->lchild;
						prePoint = curPoint;
					}
				}
				else
				{
					if(curPoint->rchild == NULL)
					{
						curPoint = new DecodeTree;
						curPoint->data = '0';
						curPoint->lchild = NULL;
						curPoint->rchild = NULL;
						prePoint->rchild = curPoint;
						prePoint = curPoint;
					}
					else
					{
						curPoint = curPoint->rchild;
						prePoint = curPoint;
					}
				}
				j++;
			}
			curPoint->lchild = curPoint->rchild = new DecodeTree;
			curPoint->lchild->data = m_pCode[i].fByte;		// 将码字对应的数据做为译码树的叶子结点
			curPoint->lchild->lchild = NULL;
			curPoint->lchild->rchild = NULL;
			curPoint = prePoint = m_pT;

		}
		return true;
	}
}

/*-------------------------------------------------------
目的：将文件解压缩，恢复成源文件
输入：char* destFile 解压后文件的存贮路径
输出：解压缩成功返回true；否则返回false；
-------------------------------------------------------*/
bool FUReduce::UnReduceSaving(char* destFile)
{
	if(destFile == NULL)
	{
		return false;
	}
	else
	{
		ofstream out(destFile, ios::binary);
		ifstream in(m_fileName, ios::binary);
		in.seekg(m_here);		// 跳过待解压文件的编码规则
		DecodeTree* prePoint = m_pT;
		DecodeTree* curPoint = m_pT;
		unsigned char biBuffer = '\0';
		int i = 0;		// 标识数据块第i位
		in.read(&biBuffer, 1);
		while(!in.eof())
		{
			while(curPoint->lchild!=curPoint->rchild)
			{
				if(i<8)
				{
					if(GetBit(biBuffer, i+1) == 1)
					{
						prePoint = curPoint;
						curPoint = curPoint->lchild;
						i++;
					}
					else
					{
						prePoint = curPoint;
						curPoint = curPoint->rchild;
						i++;
					}
				}
				else 		// 码字长度大于8
				{
					in.read(&biBuffer, 1);
					if(!in.eof())
					{
						i = 0;
					}
					else
					{
						return true;
					}
				}
			}
			out<<curPoint->lchild->data;
			curPoint = prePoint = m_pT;
		}
		return true;
	}
}

/*-------------------------------------------------------
目的：从一个数据块中取第n位的值
输入：unsigned char ch 数据块的值
	  int n	要取的位
输出：unsigned char 返回的第n位的值
-------------------------------------------------------*/
unsigned char FUReduce::GetBit(unsigned char ch, int n)
{
	return (ch & (1<<(8-n)))>>(8-n);
}

/*-------------------------------------------------------
目的：把一个数据块按位转换成字符串
输入：unsigned char block 一字节数据块
输出：char* 指向字符串的指针
-------------------------------------------------------*/
char* FUReduce::Trans(unsigned char block)
{
	char* ch = new char[9];
	unsigned char mask = 0x01;
	unsigned char t = 0x00;
	for(int i=0; i<8; i++)
	{
		mask <<= 8-i-1;
		t = (block & mask)>>(8-i-1);
		if(t==1)
		{
			ch[i] = '1';
		}
		else
		{
			ch[i] = '0';
		}
		mask = 0x01;
		t = 0x00;
	}
	ch[i] = '\0';
	return ch;
}

/*-------------------------------------------------------
目的：打印测试结果
输入：无
输出：无
-------------------------------------------------------*/
void FUReduce::TestRusult()
{
	cout<<"生成的译码树："<<endl;
	cout<<"xi"<<'\t'<<'l'<<'\t'<<'r'<<'\t'<<'w'<<endl;
	cout<<"----------------------------------------"<<endl;
	PutTree(m_pT);
	cout<<"----------------------------------------"<<endl;

}

/*-------------------------------------------------------
目的：打印译码树
输入：DecodeTree* T 译码树头结点
输出：无
-------------------------------------------------------*/
void FUReduce::PutTree(DecodeTree* T)
{
	static int i = 0;
	i++;
	if(T&&(T->lchild!=NULL||T->rchild!=NULL))
	{
		cout<<'x'<<i<<'\t'<< hex <<T->lchild<<'\t'<<T->rchild<<'\t'<<T->data<<endl;
		PutTree(T->lchild);
		PutTree(T->rchild);
	}
}