main.cpp

使用霍夫曼huffman 編碼方式 對文件進行壓縮 程序很簡單 主要是幫助新人了解霍夫曼編碼的實現方法

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <conio.h>
#include "huffmantree.h"
//#include <strstream>  
#include <string.h>
using namespace std; 
static const int mask[8]={1,2,4,8,16,32,64,128};
static const char mask1=(mask1|1)&1;
const static int Open_Success=1,Open_Fail=0;

int  ReadFile(char * infile,char * & buff,unsigned int & sizeofbuff);
int  SaveFile(char * outfile,char * & buff,unsigned int & sizeofbuff);
void EncodeAnalyze(char * buff,unsigned int sizeofbuff,str_char * &charsTable,int & sizeofTable);
void DecodeAnalyze(char * buff,unsigned int sizeofbuff,str_char * &charsTable,int & sizeofTable);
bool Encoding(char * infile,char *outfile);
bool Decoding(char * infile,char *outfile);
bool CreateHuffman(str_char * &charsTable,int & sizeofTable,huffmantree *& Out_Hufftree);
void writebuf(char *buf, int offset,void*src,int stride);
void readbuf(char *buf, int offset,void*trg,int stride);
void wrongformat();
//int  FileClose();

//-----------------------------------------------------------------------

int main(int argc, char* argv[])
{
    system("cls");
    if(argc>=4)
    {
     if(strcmp(argv[1],"-e")==0)
         Encoding(argv[2],argv[3]);
     else if(strcmp(argv[1],"-d")==0)
             Decoding(argv[2],argv[3]);
          else
              wrongformat();
     }
     else
     wrongformat();
    //getche();
	return 0;
}
//-----------------------------------------------------------------------
bool Decoding(char * infile,char *outfile)
{
     char * buff=NULL,*outbuff=NULL;      //two buffs one for read file another for output file
     str_char * charsTable=NULL;          //Character Table is a set which contain each characters and their frequency
     int  sizeofTable=0,datastart=0;  
     unsigned int  sizeofbuff=0,sizeofoutbuff=0;
     huffmantree * Out_Hufftree=NULL;     //huffmantree is used to decoding
     if(ReadFile(infile,buff,sizeofbuff)==Open_Fail)
     {
         cout<<"Fail to open source-file"<<endl;
         return false;
     }
     cout<<"File read successfully"<<endl;
     cout<<"File size: "<<sizeofbuff<<endl;
     cout<<"File analyzing ..........................................."<<endl;
     DecodeAnalyze(buff,sizeofbuff,charsTable,sizeofTable);
     cout<<"Huffman codes generating.................................."<<endl;
     //cout<<"sizeofTable: "<<sizeofTable<<endl;
     
     if(!(CreateHuffman(charsTable,sizeofTable,Out_Hufftree)))
     {
       cout<<"Fail to generate huffman tree"<<endl;
       delete [] charsTable;
       delete [] buff;
       return false;
     }
     datastart=sizeof(int)+sizeofTable*sizeof(str_char);                   
     for(int i=0;i<sizeofTable;i++)
        sizeofoutbuff=sizeofoutbuff+charsTable[i].frequency;
     outbuff=new char[sizeofoutbuff];
     cout<<"Code size: "<<sizeofbuff-datastart<<endl;
     cout<<"Original Data size: "<<sizeofoutbuff<<endl;
     cout<<"Decoding ................................................."<<endl;
     
     int percent,last=sizeofoutbuff-1;
     char tempchr;int j=0;bool findout=false;
     for(unsigned int i=0;i<sizeofoutbuff;i++)
     {
         while(!findout)
         {
             if(j<8)
             {
                 if((buff[datastart]&1)==mask1)
                 {
                     if(Out_Hufftree->getchr(true,tempchr))
                       findout=true;
                 }
                 else
                 {
                     if(Out_Hufftree->getchr(false,tempchr))
                       findout=true;
                 }
                 buff[datastart]=buff[datastart]>>1;
                 j++;
             }
             else
             {
                 j=0;
                 datastart++;
             }
         }
         writebuf(outbuff,i,&tempchr,1);
         findout=false;
         //percent=((double)i/last)*100;
         //printf("\b\b\b\b\b\b\b\b\b\b\b\b\b\b");
         //printf("%3d%% finishied",percent);
     }
     cout<<"\nSaving to file............................................"<<endl;
     if(SaveFile(outfile,outbuff,sizeofoutbuff)==Open_Fail)
     {
         cout<<"Fail to save target-file"<<endl;
     }
     delete [] outbuff;
     delete Out_Hufftree;
     delete [] charsTable;
     delete [] buff;
     return true;
}
//-----------------------------------------------------------------------
bool Encoding(char * infile,char *outfile)
{
     char * buff=NULL,*outbuff=NULL;
     str_char * charsTable=NULL;
     int  sizeofTable=0,sizeofheader=0;
     unsigned int  sizeofbuff=0,sizeofoutbuff=0;
     huffmantree * Out_Hufftree=NULL;
     //----------------read file and anazyze file----------------------------------------------------
     if(ReadFile(infile,buff,sizeofbuff)==Open_Fail)
     {
         cout<<"Fail to open source-file"<<endl;
         return false;
     }
     cout<<"File read successfully"<<endl;
     cout<<"File size: "<<sizeofbuff<<endl;
     cout<<"File analyzing ..........................................."<<endl;
     
     EncodeAnalyze(buff,sizeofbuff,charsTable,sizeofTable);

     cout<<"Huffman codes generating.................................."<<endl;
     //----------------------------------------------------------------------------------------------
     
     //----------------Huffmantree and codeTable generate--------------------------------------------
     if(!(CreateHuffman(charsTable,sizeofTable,Out_Hufftree)))
     {
       cout<<"Fail to generate huffman tree"<<endl;
       delete [] charsTable;
       delete [] buff;
       return false;
     }
     //----------------------------------------------------------------------------------------------
     
     //----------------------------analyze output buff size and save header to buff------------------
     sizeofheader=sizeof(sizeofTable)+sizeofTable*sizeof(str_char);
     sizeofoutbuff=(unsigned int)sizeofheader+Out_Hufftree->WEP;
     outbuff=new char[sizeofoutbuff];
     cout<<"Header size: "<<sizeofheader<<"  Data size: "<<Out_Hufftree->WEP
     <<"  Total size: "<<sizeofoutbuff<<endl;
     cout<<"Encoding data............................................."<<endl;
     int offset=0;
     writebuf(outbuff,offset,&sizeofTable,sizeof(sizeofTable));
     offset=sizeof(sizeofTable);
     writebuf(outbuff,offset,charsTable,sizeofTable*sizeof(struct str_char));
     offset=offset+sizeofTable*sizeof(struct str_char);
     //----------------------------------------------------------------------------------------------
     
     //-------------------------start encoding and save to buff--------------------------------------
     bool *code=NULL;int length=0;char tempchr=tempchr&0;int j=0;//----------------------
     int percent;
     int stride=sizeof(tempchr);int last=sizeofbuff-1;
     for(unsigned int i=0;i<sizeofbuff;i++)
     {
            Out_Hufftree->codes_get(buff[i],code,length);        //encode----------------
            for(int k=0;k<length;)
            {
                    if(j<8)
                    {
                        if(code[k])                              //if code[k]==true then current bit set to 1 otherwise do nothing
                           tempchr=tempchr|mask[j];
                        j++;
                        k++;
                    }
                    else
                    {
                        
                        writebuf(outbuff,offset,&tempchr,stride);
                        offset=offset+stride;
                        tempchr=tempchr&0;
                        j=0;
                    }
            }
            //percent=((double)i/last)*100;
            //printf("\b\b\b\b\b\b\b\b\b\b\b\b\b\b");
            //printf("%3d%% finishied",percent);
            if(i==last&&offset!=sizeofoutbuff)                                          //if reach the last char,save it anyway
              writebuf(outbuff,offset,&tempchr,stride);
            
     }
     //----------------------------------------------------------------------------------------------

     //---------------------------------output buff to file------------------------------------------
     cout<<"\nSaving to file............................................"<<endl;
     if(SaveFile(outfile,outbuff,sizeofoutbuff)==Open_Fail)
     {
         cout<<"Fail to save target-file"<<endl;
     }
     percent=(1.0-(double)sizeofoutbuff/sizeofbuff)*100;
     cout<<"Compression finished at the ratio of "<<percent<<"%"<<endl;
     //----------------------------------------------------------------------------------------------
     delete [] outbuff;
     delete Out_Hufftree;
     delete [] charsTable;
     delete [] buff;
     return true;
}
//-----------------------------------------------------------------------
int  SaveFile(char * outfile,char * & buff,unsigned int & sizeofbuff)
{
     ofstream file(outfile,ios::out|ios::binary);
     if(!file.is_open())                       //open fail then return
        return Open_Fail;

     file.write(buff,sizeofbuff);
     file.close();
     return Open_Success;
}
//-----------------------------------------------------------------------
int  ReadFile(char * infile,char * & buff,unsigned int & sizeofbuff)
{
     ifstream file(infile,ios::in|ios::binary);
     if(!file.is_open())                       //open fail then return
        return Open_Fail;
     file.seekg(0,std::ios::end);              //-------------
     sizeofbuff=file.tellg();                  //get file size
     file.seekg(0);                            //-------------
     buff=new char[sizeofbuff];                //buff made
     file.read(buff,sizeofbuff);
     file.close();
     return Open_Success;
}
//-----------------------------------------------------------------------
void DecodeAnalyze(char * buff,unsigned int sizeofbuff,str_char * &charsTable,int & sizeofTable)
{
     int offset=0;
     readbuf(buff,offset,&sizeofTable,sizeof(sizeofTable));
     offset=sizeof(sizeofTable);
     charsTable=new str_char[sizeofTable];
     int stride=sizeofTable*sizeof(struct str_char);
     readbuf(buff,offset,charsTable,stride);
}
//-----------------------------------------------------------------------
void EncodeAnalyze(char * buff,unsigned int sizeofbuff,str_char * &charsTable,int & sizeofTable)
{
     huffmantree chr_ord_tree,fre_ord_tree;
     for(unsigned int i=0;i<sizeofbuff;i++)           //--------------
     {                                                //--------------
         chr_ord_tree.Insertbychr(buff[i]);           //characters analyzing  and make a tree in char order
     }                                                //--------------
     
     chr_ord_tree.treetoarray(charsTable,sizeofTable);//transform a tree to table
     
     for(int i=0;i<sizeofTable;i++)                    //-------------------------
     {
         fre_ord_tree.Insertbyfre(charsTable[i]);     //sort tree by frequency
     }
     delete [] charsTable;                            //free memory for temparray
     
     fre_ord_tree.treetoarray(charsTable,sizeofTable); //make a new array from frequency ordered tree;
      
}
//-----------------------------------------------------------------------
bool CreateHuffman(str_char * &charsTable,int & sizeofTable,huffmantree *& Out_Hufftree)
{
     delete Out_Hufftree;
     Out_Hufftree=new huffmantree;
     if((Out_Hufftree->makeHufftree(charsTable,sizeofTable)))//making huffman tree
     {
        if(Out_Hufftree->codes_makeCodestree())
          return true;
     }
     delete  Out_Hufftree;
     Out_Hufftree=NULL;  
     return false;
}
//-----------------------------------------------------------------------
void writebuf(char *buf, int offset,void*src,int stride)
{
     buf=buf+offset;
     memcpy(buf,src,stride);
}
void readbuf(char *buf, int offset,void*trg,int stride)
{
     buf=buf+offset;
     memcpy(trg,buf,stride);
}
//-----------------------------------------------------------------------
void wrongformat()
{
     cout<<"Format error. Please give the correct format of arguments."<<endl;
     cout<<"Driver:\\Dir\\huffman <argument '-e' or '-d'> <inputfile.name> <ouputfile.name>"<<endl<<"Example:"<<endl;
     cout<<"Encoding: c:\\huffman -e c:\\test.txt  c:\\test.huff"<<endl;
     cout<<"Decoding: c:\\huffman -d c:\\test.huff c:\\test.txt"<<endl;
}