#include ".\chuffman.h"
CHuffman::CHuffman(void){}
CHuffman::~CHuffman(void){}
void CHuffman::Select(HuffmanTree HT,int num,int &s1,int &s2)
{
unsigned int weight=~0;
unsigned int weight1=~0;
int i;
for(i=1;i<=num;i++){
if(HT[i].parent)
continue;
if(HT[i].weight<=weight){
weight1=weight,weight=HT[i].weight;
s2=s1,s1=i;
}
else if(HT[i].weight<weight1)
weight1=HT[i].weight,s2=i;
}
}
void CHuffman::HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,unsigned int*weight,int n){
if(n<=1)
return;
int i,m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p;
for(p=HT+1,i=1;i<=n;++i,++p,++weight)
p->weight=*weight,p->parent=0,p->lchild = 0,p->rchild= 0;
for(;i<=m;++i,++p)
p->weight=0,p->parent=0,p->lchild = 0,p->rchild= 0;
for(i=n+1;i<m+1;++i){
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
unsigned char* cd=(unsigned char*)malloc(n*sizeof(unsigned char));
cd[n-1]='\0';
for(i=1;i<=n;++i){
int start=n-1;
unsigned int c,f;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(unsigned char*)malloc((n-start)*sizeof(unsigned char));
memcpy(HC[i],&cd[start],n-start);
}
free(cd);
}
void CHuffman::setBit(BYTE_8&b,int j,unsigned char c){
static unsigned char bvec[9]={255,254,253,251,247,239,223,191,127};
unsigned char*p=(unsigned char*)&b;
if(c==1)
*p|=~bvec[j];
else
*p&=bvec[j];
}
void CHuffman::FindIndex(const char &ch,int &i,const unsigned char*charSet,int setNum){
int a=0,b=setNum;
i=(a+b)/2;
unsigned char tmp=(ch+256)%256;
while(charSet[i]!=tmp){
if(charSet[i]<tmp)a=i;
else b=i;
i=(a+b)/2;
}
}
void CHuffman::setByte0(BYTE_8&b){memset(&b,0,1);}
void CHuffman::Coding(const unsigned char*origbuff,unsigned char*&destbuff,int origNum,int destNum,
const HuffmanCode &HC, const unsigned char*charSet,int setNum){
int i,l;
destNum++;
destbuff=new unsigned char[destNum];
memset(destbuff,0,destNum*sizeof(char));
int num=0;
BYTE_8 b;
setByte0(b);
int index=0;
size_t j=1,k=1;
for(l=0;l<origNum;l++){
FindIndex(origbuff[l],i,charSet,setNum);
i=i+1,j=0;
while(HC[i][j]){
while(HC[i][j]&&k<=8){
setBit(b,k,HC[i][j]-'0');
k++,j++;
}
if(k>8){
destbuff[num++]=b.data;
setByte0(b),k=1;
}
}
}
if(k<=8)destbuff[num++]=b.data;
}
int CHuffman::Child(const HuffmanTree &HT,int p,int&j,const BYTE_8 &b){
unsigned i=b[j];
j++;
if(i)return HT[p].rchild;
else return HT[p].lchild;
}
void CHuffman::UnCoding(const unsigned char*origbuff,const HuffmanTree &HT,unsigned char*&destbuff,int root,int len, const unsigned char*charSet){
destbuff=new unsigned char[HT[root].weight+1];
memset(destbuff,0,HT[root].weight+1);
int i,num=0,j=1;
int p=root;
BYTE_8 b;
setByte0(b);
for(i=0;i<=len;i++){
b=*((BYTE_8*)&origbuff[i]);
j=1;
while(j<=8){
while(j<=8&&HT[p].lchild&&HT[p].rchild)p=Child(HT,p,j,b);
if(HT[p].lchild==0){
destbuff[num++]=charSet[p-1];
p=root;
}
}
}
}
void CHuffman::compress(const char*sourcefile,const char*destfile){
unsigned int w[256]={0};
unsigned int pv[256]={0};
unsigned char charSet[256]={0};
ifstream inFile(sourcefile,ios::in|ios::binary);
inFile.seekg(0,ios::end);
long len=inFile.tellg();
unsigned char *buff=new unsigned char[len];
inFile.seekg(0,0);
inFile.read((char*)buff,len);
inFile.close();
for(int i=0;i<len;i++)
w[buff[i]]++;
int n=0;
for(i=0;i<256;i++){
if(w[i]){
charSet[n++]=i,pv[n-1]=w[i];
}
}
memset(w,0,256*sizeof(int));
memcpy(w,pv,n*sizeof(unsigned int));
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT,HC,w,n);
int destNum=0;
for(i=0;i<n;i++)
destNum+=w[i]*strlen((char*)HC[i+1]);
destNum/=8;
unsigned char* buff2;
char tag[12]="ZhouYuncai";i=0;while(i<11)tag[i++]-=20;
Coding(buff,buff2,len,destNum,HC,charSet,n);
ofstream outFile(destfile,ios::out|ios::binary);
outFile.write(tag,11);
outFile.write((char*)charSet,256*sizeof(unsigned char));
outFile.write((char*)&n,sizeof(int));
outFile.write((char*)&destNum,sizeof(int));
outFile.write((char*)HT,2*n*sizeof(HTNode));
outFile.write((char*)buff2,destNum);
outFile.close();
}
void CHuffman::uncompress(const char*sourcefile,const char*destfile){
unsigned char charSet[256]={0};
ifstream inFile(sourcefile,ios::in|ios::binary);
int n,destNum;
char tag[12]={0};
inFile.read(tag,11);int i=0;while(i<11)tag[i++]+=20;
if(strcmp(tag,"ZhouYuncai")){
cout<<"文件格式不对！"<<endl;
return;
}
inFile.read((char*)charSet,256*sizeof(unsigned char));
inFile.read((char*)&n,sizeof(int));
inFile.read((char*)&destNum,sizeof(int));
HuffmanTree HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
memset(HT,0,2*n*sizeof(HTNode));
inFile.read((char*)HT,2*n*sizeof(HTNode));
unsigned char*buff=new unsigned char[destNum];
inFile.read((char*)buff,destNum);
inFile.close();
ofstream of1(destfile,ios::out|ios::binary);
unsigned char*buff2;
UnCoding(buff,HT,buff2,2*n-1,destNum,charSet);
of1.write((char*)buff2,HT[2*n-1].weight);
of1.close();
}
评论0