compress.cpp

这是我自己写的wince程序

#include "stdafx.h"
#include "compress.h"

/////////////////////////////////////////////////////////////////////
//hashfun：计算hash值
//此前已经保证至少有三个元素
word hashfun(char *windows)
{       
	word a,b,c;
	a=windows[0];
	a*=256;            //左移八位
	a+=windows[1];
	b=windows[1];
	b*=256;            //左移八位
	b+=windows[2];
	c=a^b;
	return c;
}
/////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//scrollwindows :滚动窗口
//i 开始位址   windows 窗口   content 缓存数组
//最多读入17个
//返回窗口读入的个数
int scrollwindows(word i,char *windows, char *content,word last)
{      
	word k,c;
	c=i;
	for( k = 0;k < 17 ; k++)
	{
		if(c+k == last) return k;
		windows[k]=content[k+c];
	}
	return 17;
}
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//seek ：真正寻找匹配串
//返回匹配个数，并通过address传地址
char seek(char *windows,word *address,char *content,word i,word *hash,word *hashtable,word flag,word c_flag)
{
	word hashnum,k,index,j;
	char tem_match,match=0;
	j=(word) flag;
	hashnum=hashfun(windows);  
	if(hash[hashnum] == 65535)
	{
		hash[hashnum]=i;
		hashtable[i]=65535;            //防止死循环
		*address=65535;
		return 1;
	}
	else
	{      
		k=hash[hashnum];
		if(k == i) k=hashtable[i];   //前次已在hashtable中了，再找是自己和自己比，现在应跳过

		while(k != 65535)
		{   
			tem_match=0;
			index=0;
			while(windows[index] == content[k+index])
			{
				tem_match++;
				index++;
				if(index >= j)  break;    //最大匹配长度为窗口读入的个数
				if(k+index >= 65534)  break;   //防止超出content的范围
			}
			if(tem_match>match)             //k表示当前正在比较的字符串地址
			{
				*address=k;
				match=tem_match;
			}
			if(match == j) break;//已到最大匹配
			k=hashtable[k];
		}
		if(c_flag == 0)
		{
			hashtable[i]=hash[hashnum];
			hash[hashnum]=i;
		}
		return match;
	}
}

////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//seek_phrase：寻找匹配的字符串
//两次调用seek比较最佳的压缩方式
//返回匹配个数，并通过address传地址
char seek_phrase(char *windows,word flag ,word *c_flag,word *address,word i,char *content,word *hash,word *hashtable,word last,int type)
{
	char match1,match2,match;
	word address1,address2;
	int lev;                                     //随type 的不同而不同
	if(type == 1)  lev =2;
	else lev=3;
	match1=seek(windows,&address1,content,i,hash,hashtable,flag,*c_flag);
	if( flag <= 3)                                                                          //跳过贪婪匹配
	{match2=0;address2=address1;}
	else
		match2=seek(windows+1,&address2,content,i+1,hash,hashtable,flag-1,*c_flag);         //注意windows+1和i+1
	if(match1 < match2 || match1 <= lev)      
	{
		match=1;
		*c_flag=1;                                           //匹配一个，下个的hashtable已写入，否则会死循环
		*address=address2;
	}
	else
	{
		match=match1;
		*c_flag=0;                                          //下个的hashtable已写入，但可以跳过它
		*address=address1;
	}
	return match;
}

////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//out_code2：将压缩结果写入特定的缓存
void out_code2(char match,word *af_length,word *cp_length,word address,char *windows,char *neirong,char *len_date)
{                
	word ah,al;
	int c;
	char len;
	if(match == 0|| match== 2 || match == 3)  
	{
		MessageBox(NULL,_T("Compress Fatal Error!"),_T("Error!"),MB_OK);
		exit(0);
	}    //检验
	if(match == 1)
	{
		neirong[*af_length-1]=windows[0];
		if(windows[0] == -1) 
		{
			(*cp_length)++;                       //＋＋  比  * 优先！！！
			c=(*cp_length-1)/2;
			len_date[c]=(len_date[c]*16+0);     //写入len_date  左移4位
		}
	}
	else
	{     
		len=match-2;     
		c=(*cp_length-1)/2;
		len_date[c]=(len_date[c]*16+len);     //写入len_date  左移4位
		neirong[*af_length-1]=-1;
		if(address<0) 
		{
			MessageBox(NULL,_T("Compress Fatal Error!"),_T("Error!"),MB_OK);
			exit(0);
		}    //检验
		ah=address/256;
		al=address%256;
		neirong[*af_length]=(char)ah;    //写入outdate
		neirong[*af_length+1]=(char)al;   
		(*af_length)++;
		(*af_length)++;
	}
}

////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//file_out_code2:写入文件
//
void file_out_code2(FILE *out,word af_length,word cp_length,char *neirong,word last,char *len_date)
{
	int i,c=0;
	word len=0;
	fwrite(&last,2,1,out);
	fwrite(&af_length,2,1,out);
	fwrite(&cp_length,2,1,out);
	i=cp_length/2;
	if(cp_length%2 != 0) 
	{
		len_date[i]=len_date[i]*16;
		i++;
	}
	fwrite(len_date,i,1,out);
	fwrite(neirong,af_length,1,out);
}
////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
//compress: 压缩数据的函数
//in 源数据区；out 目标数据区；
//一次最大处理65536个字节；
//type : 1 为文本型，2为其他型。
int compress(FILE *in,FILE *out,int type)
{
	word af_length;                      //type1时 ：计算处理的次数，为对照表(table)提供长度。//type2时 ：为neirong提供长度
	word cp_length;                      //type1时 ：计算作缩略的次数，为len_date提供长度。 //type2时 ：计算－1和作缩略的次数，为len_date提供长度。
	char* content;                         //将待压数据读入缓存
	word* hash;                            //hash值的索引
	char windows[17];                      //预读区，限制了最大匹配长度为17
	word* hashtable;                       //hash 表
	char* len_date;                        //记录每次缩略的长度
	char *neirong;                      //经处理过的字符或地址。255  -1  代表缩略 ，后跟两字节地址， 其余皆为字符。    
	word i;                                 //计数，指明当前处理的位置
	word address;                          //能匹配的地址
	char match;                           //能匹配的长度
	int k=1;                                 //辅助计数
	fseek(in,0,SEEK_END);
	long length=ftell(in);                //计算文件长度
	fseek(in,0,SEEK_SET);
	a_file+=length;
	len_fi=length;
	fwrite(&length,4,1,out);
	word last;                             //本次处理的个数
	word flag;                             //窗口中读入的个数
	word c_flag;                           //是否加入hashtable过。 0 为否；1 为加入过
	word ii=0;                               //遇到文件的末尾使用，加0
	word a;                              //初始化使用	
	last=(word)((65535>length)?length:65535);
	al_se=no_se=0;
	len_se=0;
	len_db=0;
	pe_num=0;
	al_se=length/16384+1;

	content = (char*)malloc(65536*sizeof(char));           //各数据缓存的初始化
	memset(content,0,sizeof(content));
	hash = (word*)malloc(65536*sizeof(word));
	memset(hash,0,sizeof(hash));
	hashtable = (word*)malloc(65536*sizeof(word));
	memset(hashtable,0,sizeof(hashtable));
	len_date = (char*)malloc(65536*sizeof(char));
	memset(len_date,0,sizeof(len_date));

	while(k>0)
	{ 
		len_se=16387;
		c_flag=0;
		af_length=0;
		cp_length=0;
		length -= 65535;
		for(a=0;a<65535;a++)                   //初始化为0
			len_date[a]=0;
		len_date[a]=0;
		neirong=(char *)malloc(last);
		fread(content,1,last,in);
		for(a=0;a<65535;a++)                   //初始化为65535
		{
			hash[a]=65535;
			hashtable[a]=65535;
		}
		hash[65535]=65536;
		hashtable[65535]=65535;    //单独初始化,防止上个for死循环
		flag=scrollwindows(0,windows,content,last);       
		for(i=0;i<last;)
		{
			if(flag <= 2) match=1;
			else  
				match=seek_phrase(windows,flag, &c_flag, &address,i,content,hash,hashtable,last,type);     
			af_length++;
			if(match == 2 || match <= 0|| match > 17)
			{ 
				MessageBox(NULL,_T("Compress Error!"),_T("Error"),MB_OK); 
				return 1;
			}            //做一些检测
			if(match > 2)  cp_length++;  
			out_code2(match,&af_length,&cp_length,address,windows,neirong,len_date);           
			i+=match;
			if(i == 0) break;//防止i重回0，死循环
			flag=scrollwindows(i,windows,content,last);       //滚动窗口
		}
		len_cp+=cp_length;len_cp+=2; 
		len_af+=af_length;len_af+=2;
		file_out_code2(out,af_length,cp_length,neirong,last,len_date);
		free(neirong);
		k = (65535>length)?length:65535;