数据压缩dlg.cpp

自己做的作业（自适应霍夫曼解压缩） 完成功能解压缩文件！方法：自适应霍夫曼编码（8bit编码）（有GUI界面）

	m_Time.SetWindowText(gmsg);
	sprintf(gmsg,"");
	m_Ratio.SetWindowText(gmsg);
	
	//设置存储空间
    BYTE *output,*outputmemp;
	outputmemp = (BYTE *)GlobalAlloc(GMEM_MOVEABLE,length);
    output = (BYTE *)GlobalLock(outputmemp);
	//创建Huffman树，并初始化
	TREE Tree;
	InitializeTree(&Tree);
	
	outlength = 0;//输出压缩比特长度
	for(unsigned long i=0;i<length;i++)
	{//逐个字符进行压缩
		jc = i;
		EncodeSymbol(&Tree,buf[i],output);//对字符进行编码，新字符加入树
		UpdateWeight(&Tree,buf[i]);//更新码重，并调整树
	}

	CString savename = CurrentFileName + ".lcg";
    CurrentFileName = FileName + ".lcg";
	FileHeader *fileheader = new FileHeader;
	fileheader->namelength = FileName.GetLength()+1;
	
	fileheader->oldlength = length;
	fileheader->newlength = outlength;
	//写文件头信息（被压缩文件名，压缩前长度，压缩后长度（比特））
	CFile savefile;
	savefile.Open(savename,CFile::modeCreate | CFile::modeReadWrite  | CFile::shareDenyNone);
	savefile.WriteHuge(fileheader,sizeof(FileHeader));
	savefile.Close();
	savefile.Open(savename,CFile::modeReadWrite  | CFile::shareDenyNone);
	savefile.Seek(sizeof(FileHeader),CFile::begin);
	savefile.WriteHuge(FileName,fileheader->namelength);
	savefile.Close();
	//写文件压缩数据
	savefile.Open(savename,CFile::modeReadWrite  | CFile::shareDenyNone);
	savefile.Seek(sizeof(FileHeader) + fileheader->namelength,CFile::begin);
	savefile.WriteHuge(output,(outlength+7)/8);
	savefile.Close();
	//释放内存
	delete(fileheader);
	GlobalUnlock(filebuf);
	GlobalFree(filememp);
	GlobalUnlock(output);
	GlobalFree(outputmemp);
	//压缩后文件长度
	sprintf(gmsg,"%d",outlength/8/1024);
	m_FileLength2.SetWindowText(gmsg);
    //计算压缩比
	sprintf(gmsg,"%2.2f",(double)(outlength)/(length*8)*100);
	m_Ratio.SetWindowText(gmsg);
	//设置工作状态
	m_ProgBar.SetPos(100);
	workflag = false;
}
void CMyDlg::Decode()
{//解压
	char gmsg[300];
	BYTE tmp[300];
	workflag = true;
	timenum = 0;
	SetTimer(1,100,NULL);
	outlength = 0;
	CurrentFileName = FileList[0];
	//读入文件
	CFile openfile;
	openfile.Open(CurrentFileName,CFile::modeRead | CFile::shareDenyNone);
	length = openfile.GetLength();
	BYTE *filebuf,*filememp;
	filememp = (BYTE *)GlobalAlloc(GMEM_MOVEABLE,length);
    filebuf = (BYTE *)GlobalLock(filememp);
	length = openfile.ReadHuge(filebuf,length);
	openfile.Close();

    FileHeader *fileheader = (FileHeader *)filebuf;
    memcpy(tmp,&filebuf[sizeof(FileHeader)],fileheader->namelength);
	
	BYTE *buf = &filebuf[sizeof(FileHeader) + fileheader->namelength];
	
	sprintf(gmsg,"解压前长度：");
	m_L1.SetWindowText(gmsg);
	sprintf(gmsg,"解压后长度：");
	m_L2.SetWindowText(gmsg);
	sprintf(gmsg,"解压比：");
	m_R1.SetWindowText(gmsg);
	sprintf(gmsg,"解压时间：");
	m_T1.SetWindowText(gmsg);
	sprintf(gmsg,"%d",length/1024);
	m_FileLength.SetWindowText(gmsg);
	sprintf(gmsg,"%d",fileheader->oldlength/1024);
	m_FileLength2.SetWindowText(gmsg);
    sprintf(gmsg,"%02d时%02d分%02d秒",timenum/36000,timenum/600,timenum/10);
	m_Time.SetWindowText(gmsg);
	sprintf(gmsg,"");
	m_Ratio.SetWindowText(gmsg);
	
    BYTE *output,*outputmemp;
	outputmemp = (BYTE *)GlobalAlloc(GMEM_MOVEABLE,length*5);
    output = (BYTE *)GlobalLock(outputmemp);
	TREE Tree;
	InitializeTree(&Tree);
	outlength = 0;
	BYTE ch = 0;
	unsigned long j = 0;
	for(;outlength<fileheader->newlength;)
	{
		jc = outlength/8;
		output[j++] = ch = DecodeSymbol(&Tree,buf);
		UpdateWeight(&Tree,ch);
	}
	CString str,savename ;
	str.Format("%s",tmp);
	savename = "LCG_" + str;
	CurrentFileName = savename;
	CFile savefile;
	savefile.Open(savename,CFile::modeCreate | CFile::modeReadWrite  | CFile::shareDenyNone);
	savefile.WriteHuge(output,j);
	savefile.Close();
	GlobalUnlock(filebuf);
	GlobalFree(filememp);
	GlobalUnlock(output);
	GlobalFree(outputmemp);
	
	sprintf(gmsg,"%2.2f",(double)(outlength)/(j*8)*100);
	m_Ratio.SetWindowText(gmsg);
	m_ProgBar.SetPos(100);
	workflag = false;
	
}
void CMyDlg::InitializeTree(TREE *tree)
{
	//初始化Huffman树，设置根节点 = NYT
	tree->nodes[ROOT_NODE].child = NYT;
	tree->nodes[ROOT_NODE].child_is_leaf = true;
	tree->nodes[ROOT_NODE].weight = 0;
	tree->nodes[ROOT_NODE].parent = -1;

	tree->leaf[NYT] = ROOT_NODE;
	for(int i = 0;i < NYT; i++)
	{//每个字符所在节点位置，初值 -1，当发现此字符节点位置 = -1时，说明是新字符
		tree->leaf[i] = -1;
	}
}
void CMyDlg::EncodeSymbol(TREE *tree, BYTE ch, BYTE *output)
{//对字符进行编码，新字符加入树
	long int current_node;
	current_node = tree->leaf[ch];
	BYTE tabletmp[8] = {0x00,0x80,0xc0,0xe0,0xf0,0xf8,0xfc,0xfe};//两个临时码表，用于计算
	BYTE tabletmp2[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
	int x,y,n;
	char chartmp[256],tmp;//临时记录字符编码，然后**倒序**输出
	x = outlength/8;      //获得输出位置
	y = outlength%8;      //获得非整字节剩余比特数
	if(current_node == -1)
	{//字符是第一次出现,把位置指到NYT所在节点位置
		current_node = tree->leaf[NYT];
	}
	n = 0;//记录字符编码长度
	while(current_node !=ROOT_NODE)
	{//从叶节点向父节点查询，直到根节点结束
		chartmp[n++] = (current_node%2);
	//如果节点是偶数，说明在左边，用0编码
	//如果节点是奇数，说明在右边，用1编码
		current_node = tree->nodes[current_node].parent;
	}
	if(y == 0)         //如果是整字节
		tmp = 0;
	else
		tmp = output[x];//否则，提取最后一字节信息部分
	for(n--;n>=0;n--)
	{//倒序输出编码
		if(chartmp[n])//在相应的位置上加 1
			tmp += tabletmp2[y++];
		else
			y++;
		if(y == 8)
		{//当tmp装满，输出到output
			output[x++] = tmp;
			tmp = 0;
			y = 0;
		}
	}
	output[x] = tmp;//输出剩余比特
	outlength = x * 8 + y;//记录编码长度
	if(tree->leaf[ch] == -1)
	{//字符是第一次出现,输出源码,8比特
		x = outlength/8;
		y = outlength%8;
		if(y == 0)
		{//整字节，直接装入
			output[x] = ch;
		}
		else
		{//非整字节，需移位
			output[x] = (output[x]&tabletmp[y]) + (ch>>y);
			output[x + 1] = (ch<<(8-y));
		}
		outlength += 8;//记录编码长度
		add_new_node(tree,ch);//把新字符装到Huffman树中
	}
}
int CMyDlg::DecodeSymbol(TREE *tree, BYTE *intput)
{//对压缩编码解码
	long int current_node;
	int ch;
	int x,y;
	BYTE tabletmp2[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
	WORD tmp;
	current_node = ROOT_NODE ;
	while(!tree->nodes[current_node].child_is_leaf)
	{//从根节点向子节点查询，直到叶节点结束
		current_node = tree->nodes[current_node].child - 1;
		x = outlength/8;
		y = outlength%8;
		if((intput[x] & tabletmp2[y]) == 0)//根据编码判断向左走，还是向右走
			current_node += 1;//如果是1向右走，0向左走
		outlength++;//压缩编码计数
	}
	ch = tree->nodes[current_node].child;//获得叶节点字符
	if(ch == NYT)
	{//如果字符是NYT，输出后面8比特源码
		x = outlength/8;
		y = outlength%8;
		if(y == 0)
			ch = intput[x];
		else
		{
		    tmp = (intput[x]<<8) +intput[x+1];
			ch  = (tmp>>(8-y))&0xff;
		}
		outlength += 8;//压缩编码计数
		add_new_node(tree,ch);//把新字符装到Huffman树中
	}
	return(ch);//返回解码字符
}
void CMyDlg::UpdateWeight(TREE *tree, WORD ch)
{//更新码重，并调整树
	long int current_node;
	long int new_node;
	current_node = tree->leaf[ch];
	while(current_node != -1)
	{//从当前节点向上比较,
		for(new_node = current_node; new_node > ROOT_NODE ;new_node--)
		{//从当前节点到根节点
			if(tree->nodes[new_node -1 ].weight > tree->nodes[current_node].weight)
				break;//如果有比它权重大的,跳出
		}
		if(tree->nodes[current_node].parent != new_node && current_node != new_node)
		{//如果比它大的节点的前一个节点不是他的父亲,也不是他自己,交换节点
			swap_nodes(tree,current_node,new_node);//交换节点
			current_node = new_node;
		}
		tree->nodes[current_node].weight++;//当前节点权重加1
		current_node = tree->nodes[current_node].parent;//继续向父亲查询
	}
}
void CMyDlg::swap_nodes(TREE *tree, long int current_node, long int new_node)
{//交换节点
	CMyDlg::tree::node temp;
	if(tree->nodes[current_node].child_is_leaf)//是叶节点,更新孩子(字符)的位置
		tree->leaf[tree->nodes[current_node].child] = new_node;
	else
	{//不是叶节点,更新两个孩子的父节点位置
		tree->nodes[tree->nodes[current_node].child].parent = new_node;
		tree->nodes[tree->nodes[current_node].child - 1].parent = new_node;
	}
	if(tree->nodes[new_node].child_is_leaf)
		tree->leaf[tree->nodes[new_node].child] = current_node;
	else
	{
		tree->nodes[tree->nodes[new_node].child].parent = current_node;
		tree->nodes[tree->nodes[new_node].child - 1].parent = current_node;
	}
	temp = tree->nodes[current_node];
	tree->nodes[current_node] = tree->nodes[new_node];
	tree->nodes[current_node].parent = temp.parent;
	temp.parent = tree->nodes[new_node].parent;
	tree->nodes[new_node] = temp;
}
void CMyDlg::add_new_node(TREE *tree, WORD ch)
{//添加新字符到Huffman树
	long int old_node;//原节点 
    long int new_node;//新字符节点
	long int NYT_node;//
	old_node = tree->leaf[NYT];
	new_node = tree->leaf[NYT] + 1;
	NYT_node = tree->leaf[NYT] + 2;
	
	tree->nodes[old_node].child = new_node + 1;
	tree->nodes[old_node].child_is_leaf = false;

	tree->nodes[new_node].child = ch;
	tree->nodes[new_node].parent = old_node;
	tree->nodes[new_node].child_is_leaf = true;
	tree->nodes[new_node].weight = 0;
	
	tree->nodes[NYT_node].child = NYT;
	tree->nodes[NYT_node].child_is_leaf = true;
	tree->nodes[NYT_node].weight = 0;
	tree->nodes[NYT_node].parent = old_node;
	
	tree->leaf[ch] = new_node;
	tree->leaf[NYT] = NYT_node;
}

void CMyDlg::OnBtnhelp() 
{
   CHelp dlg;
   dlg.DoModal();
}