lzwhuff.c

LZW和Huffman相结合

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h> 
#include <io.h>  
#include <sys\stat.h>

#define BOOL int
#define MAX_CODES 4096
#define TRUE 1 
#define FALSE 0


#define NOT_USED -1
#define HASH_SIZE 4099
#define VERBOSE 1
#define MAXSTRING 1000
#define HUFF_IN_SIZE 4096
#define N 4096 

typedef struct{
    int prefix;
    int suffix;
}Element;

typedef struct{
    int address;
    int probabilty;
}Huffman_in;

typedef struct { 
	double probobility; /*某结点出现的概率*/
	int lnode; 
	int rnode; 
} node;			/* node为此结构的别名*/

node tree[N]; 		/* tree[]可通过.操作符使用node结构中的元素*/
int p = 0, total = 0; 	/* p记录叶子编号（例如tree[p]表示第p个叶子）；total为树的总叶子结点数*/
char stk[N], q = 0; 	/* stk[i]为第i结点的编码（即code，例如000001）；q为某结点编码后的长度（即Length）*/
int used[N],node_len[N];/* used[]为已使用的元素（结点）;node_len[i]为第i子树的长度（从根部开始）*/

const int BYTE_SIZE = 8;
const int EXCESS = 4;
const int ALPHA= 256;
const int MASK = 15;

int s[MAX_CODES];
int size;
int int_flag;
Element h[MAX_CODES];
Huffman_in huff[HUFF_IN_SIZE],temp;

int leftOver;
BOOL bitsLeftOver = FALSE;

/*******************************************************the method for LZW*******************************8*/
int get(int key);
int hash_code(int key);
void compress(void);
void init_hashtable(void);
void output(int pcode);
void print_binary(int i);
void put(int key, int element);

void decompress(void);
int get_code(void);
void output_encode(int pcode,int *addr);
void output_decode(int pcode);
void set_files_encode(char *filename);
void set_files_decode(char *filename);
void set_file1(char *f, char *file);
void set_file2(char *f, char *infile, char *outfile);
int string_tran(char *c);
/***************************************end of the LZW*********************************************/

/*************************************method for huffman*******************************************/
void print_code();
void print_avg_len(int len);
int find_min();
void create_tree(int num);
void traverse_tree(int i) ;
/****************************************end of the huffman********************************************/

struct HASH_TABLE{
	int key;
   int element;
}table[HASH_SIZE];

FILE *in, *out;   //file point of the source and destination
char *inname;     //the name of source and destination
char *outname;
char *huffoutname; 
char *flag;
char *cc;
const int MASK1 = 255;
const int MASK2 = 15;
int leftOver;

/*****************************************function for the huffman****************************************/
void print_code() 
{ 
	int i = 0; 
	for (i = 0; i < q; i++) 
	   {
		printf("%c", stk[i]); 
	//	huffoutname="f:\huffout.txt";
	//	fputc(stk[i], huffoutname);
		
	   }
} 

void print_avg_len(int len) 
{ 
	int i; 
	double avg_len=0; 	/*avg_len为经huffman编码后树的平均长度*/
	for(i=0;i<len;i++) 
		avg_len+=tree[i].probobility * (double)node_len[i]; 
        avg_len=avg_len/8.0+1.0;
	printf("The average length is %f\n",avg_len); 
}

int find_min() 		/*从剩下的子树或前两最小概率结点组成的新结点中找出概率最小的一个*/
{ 
	int i_min = 0, i; 
	while (used[i_min] && i_min < p) 
		i_min++; 
	for (i = 0; i < p; i++) 
		if (!used[i] 
		    && tree[i].probobility <= tree[i_min].probobility) 
			i_min = i; 
	return i_min; 
} 
 
 void create_tree(int num) 
{ 
	int  n1, n2; 
	int i ;
	node newnode; 
	for(i=0;i<num-1;i++)
	 {
		n1 = find_min(); 
		used[n1] = 1; 		/*标记为已使用*/
		n2 = find_min(); 
		used[n2] = 1; 
		newnode.probobility = 	/*创造一个新结点*/
		    tree[n1].probobility + tree[n2].probobility; 
		newnode.lnode = n1; 
		newnode.rnode = n2; 
		tree[p++] = newnode; 	/*把新结点加入未用队列中*/
	}
 
} 
 
 void traverse_tree(int i) 		/*遍历树*/
{ 
	if (tree[i].lnode == -1 && tree[i].rnode == -1) { 		/*如果是叶子结点则输出*/
		printf("%-f\t\t|", tree[i].probobility); 
		print_code(); 
		printf("\t\t|%-d\n",q); 
		node_len[i]=q; 
		return; 
	} 
	stk[q++] = '0'; 						/*如果不是叶子结点则递归*/
	traverse_tree(tree[i].rnode); 	/*如果是右子树则输出0，并递归直到叶子结点*/
	q--; 
	stk[q++] = '1'; 
	traverse_tree(tree[i].lnode); 	/*如果是左子树则输出1，并递归直到叶子结点*/
	q--;
} 


/**********************************************end of the huffman**********************************/
int get(int key){
    int b = hash_code(key);

    if(table[b].key == NOT_USED || table[b].key != key)
        return NOT_USED;
    return table[b].element;
}

int hash_code(int key){
    int i = key%HASH_SIZE;
    int j = i;
    do{
        if( table[j].key == NOT_USED || table[j].key == key)
            return j;

        j = (j+1)%HASH_SIZE;
        }while(j!=i);
    return j;
}

void compress(){
    int i, codeUsed, c, pcode, k, e;
    int addr;
    init_hashtable();
    for(i=0; i<ALPHA; i++)
        put(i,i);
	
    addr=0;
    codeUsed = ALPHA;
    c = fgetc(in);
    if(c!=EOF){
        pcode = c;
        c = fgetc(in);
      	while(c!=EOF){
         	k = (pcode<<BYTE_SIZE)+c;
            e = get(k);
            if(e==NOT_USED){    //not in dictionary
            	output_encode(pcode,&addr);
		        if(codeUsed<MAX_CODES)
                    put( (pcode<<BYTE_SIZE)+c,codeUsed++);
            	pcode = c;
            }
            else pcode = e;
         	c=fgetc(in);
        }
        output_encode(pcode,&addr);
        if(bitsLeftOver)
            fputc(leftOver<<EXCESS, out);
    }
    fclose(in);
	fclose(out);
}

void init_hashtable(void){
    int i;
    for(i=0; i<HASH_SIZE; i++)
        table[i].key = NOT_USED;
}

void output_encode(int pcode,int *addr){
	int c,d;
	int j;
    if(bitsLeftOver){
       c = (leftOver << EXCESS)+(pcode>>BYTE_SIZE);
	for (j=0;j<HUFF_IN_SIZE;j++)
        	{
        	  if (huff[j].address==c)
			{
			huff[j].probabilty=huff[j].probabilty+1;
			break;
			}
		      else
			{
		          huff[*addr].address=c;	
	                 huff[*addr].probabilty=1;	
			  break;
			}
		}	
		d = pcode & MASK1;
        for (j=0;j<HUFF_IN_SIZE;j++)
        	{
        	  
		if (huff[j].address==d)
			{
			huff[j].probabilty=huff[j].probabilty+1;
			break;
			}
		else
			{
			huff[*addr+1].address=d;	
	              huff[*addr+1].probabilty=1;
				  break;
        	}
		}
		
     
        printf("%i - ", c);print_binary(c);
        printf("%i - ", d);print_binary(d);
        fputc(c, out);
        fputc(d, out);
		
        *addr=*addr+2;
        	
        bitsLeftOver = FALSE;
    }
    else{
        leftOver = pcode & MASK2;
        c = pcode>>EXCESS;
        printf("%i - ", c);print_binary(c);
        fputc(c, out);
        for (j=0;j<HUFF_IN_SIZE;j++)
        	{
        	  if (huff[j].address==c)
			{
			huff[j].probabilty=huff[j].probabilty+1;
			break;
			}
		else
			{
			huff[*addr].address=c;	
	              huff[*addr].probabilty=1;	
				  break;
			}
		}
		*addr=*addr+1;
        bitsLeftOver = TRUE;
	}
}

//for debug used
void print_binary(int i){
    int j;
    for(j=7; j>=0; j--)
        printf("%i", (i>>j)&1);
    printf("\n");
}

void put(int key, int element){
    int b = hash_code(key);
    if(table[b].key == NOT_USED){
        table[b].key = key;
        table[b].element = element;
        return;
	}
    else{
        if(table[b].key == key){    //duplicate
            //this should not happen
            printf("Internal error occur during hashing:duplicate");
			exit(1);
		}
        else{ //table is full
            //this should not happen
            printf("Internal error occur during hashing:table full");
            exit(1);
		}
	}
}


void decompress(){
    int codeUsed = ALPHA;
    int pcode = get_code(), ccode;
    if(pcode>=0){
        s[0] = pcode;
        fputc(s[0], out);
        size = 0;

        do{
            ccode = get_code();
            if(ccode<0)break;
                if(ccode<codeUsed){
                    output_decode(ccode);
                    if(codeUsed<MAX_CODES){
                        h[codeUsed].prefix = pcode;
                        h[codeUsed].suffix = s[size];
                        codeUsed++;
                    }
                }
                else{
                    h[codeUsed].prefix = pcode;
                    h[codeUsed].suffix = s[size];
                    codeUsed++;
                    output_decode(ccode);
                }
                pcode = ccode;
        }while(TRUE);   /*DO*/
    }/*IF*/
    fclose(in);
    fclose(out);
}

int get_code(){
    int c = fgetc(in), d, code;
    if(c == -1)return -1;

    if(bitsLeftOver)
        code = (leftOver<<BYTE_SIZE)+c;
    else{
        d = fgetc(in);
        code = (c<<EXCESS)+(d>>EXCESS);
        leftOver = d&MASK;
    }
    bitsLeftOver = !bitsLeftOver;
    return code;
}

void output_decode(int code){
    int i;
    size = -1;
    while(code>=ALPHA){
        s[++size]=h[code].suffix;
        code = h[code].prefix;
    }
    s[++size]=code;
    for(i=size; i>=0; i--)
        fputc(s[i], out);
}

void set_files_encode(char *filename){
    char *s;
    if( (in = fopen(filename, "rb")) == NULL){
        printf("Cannot open input file - %s\n", filename);
        exit(1);;
	}
    s = strncat(filename, ".lzw", 4);
    if ((out = fopen(s, "wb"))== NULL){
        printf("Cannot open output file - %s\n", s);
        fclose(in);
        exit(1);
    }
}


void set_files_decode(char *filename){
    char *s;
    if( (in = fopen(filename, "rb")) == NULL){
        printf("Cannot open input file - %s\n", filename);
        exit(1);
	}
    if(strstr(filename, ".lzw")==NULL){
        printf("The filename must end with \"lzw\" extension");
        exit(1);
    }
    s = filename;
    s = s+(strlen(filename)-4)*sizeof(char);
    *s = NULL;  //seperate from ".lzw"
    if ((out = fopen(filename, "wb"))== NULL){
        printf("Cannot open output file - %s\n", filename);
        fclose(in);
        exit(1);
    }
}

void set_files1(char *f, char *infile){
    char *t;
    flag=f;
	inname = infile;
    outname = inname;	
}

void set_files2(char *f, char *infile, char *outfile){
    char *t;
    flag=f;
	inname = infile;
	outname= outfile;
}

long get_file_size( char * filename ) { 

		struct stat f_stat; 

        if( stat( filename, &f_stat ) == -1 ){ 
            return -1; 
        } 

        return (long)f_stat.st_size; 
    }

int string_tran(char *c) {
    char *t;
	int i,ii; 
	i=strcmp(c,"-encode");
	ii=strcmp(c,"-decode");
	if(i==ii) i=2;
	if(ii==0) i=1;
    return(i);
}

void printusage (void) {
  printf("Usage:lzw -flag source \n");
  printf("flag should be encode or decode\n");
  printf("When the flag is decode, the source file should be the format of \"*.lzw\"  \n");
  printf("Example: \"lzw -encode test.c\" ,then the output file would be test.c.lzw \n");
}


/************    Main Function *****************************************************************/
int main( int argc , char *argv[] ){
  time_t tm;
  int temp_flag;
  int j,k,l,tag;
  char *tempfile;
  long filesize;
  ///for huffman
  int i= 0,tmp_total_huff=0;
  int j_huff=0,temp_huff=0;
  double check_huff = 0; 
  node x; 
  memset(tree, 0, sizeof(tree)); 		/*把tree[]所指的前sizeof(tree)个字节设置为0（即将初始tree[]指向0）*/
  memset(used, 0, sizeof(used)); 
  memset(node_len,0,sizeof(node_len)); 
  //end of huffman
  if(argc!=3){
        printusage();
        return(1);
  }
  for(i=0;i<HUFF_IN_SIZE;i++)
  {
    huff[i].address=-1;
	huff[i].probabilty=-1;
  }
  // Read the number of alphabet elements from command line
  temp_flag=9; 
  temp_flag=string_tran(argv[1]);
  set_files1(argv[1],argv[2]);
  
 // Now read the source file
  if ( temp_flag==0) { //encode
     printf ("Decoding %s ......\n", argv[2]);
     set_files_encode(inname);
     tm = time(NULL);
     printf(ctime(&tm));
     compress();
     tm = time(NULL);
     printf(ctime(&tm));
	 filesize=get_file_size(inname);
	 printf("%l",filesize);
	 /*************************************************************************/
	 for(j=0;j<HUFF_IN_SIZE;j++)
	 {
		 for(k=j+1;k<HUFF_IN_SIZE;k++) 
		 {
           if ((huff[j].address==huff[k].address)&&(huff[j].address>0)&&(huff[k].address>0))
		   {
              huff[j].probabilty=huff[j].probabilty+huff[k].probabilty;
			  huff[k].address=-1;
			  huff[k].probabilty=-1;
		   }
		 }
 	 }
	 //sort
	 l=0;
	 do
	 {
		 tag=0;
		 for(j=HUFF_IN_SIZE;j>0;j--)
		 
			 if(huff[j].probabilty>huff[j-1].probabilty)
			 {
				 temp=huff[j];
				 huff[j]=huff[j-1];
				 huff[j-1]=temp;
				 tag=1;
			 }
			 l++;		 
	 }while(tag==1&&l<HUFF_IN_SIZE);
	 //sort
	 /*************************************for the huffman **************************************/
 	

      for(j_huff=0;j_huff<HUFF_IN_SIZE;j_huff++)
	{ 
		x.probobility=huff[j_huff].probabilty;//note that when break that the probobility of j is -1 and we can not put it in the tree
		if (x.probobility < 0 )  break; 
		//check += x.probobility; 
		x.lnode = -1; 			/*x的左子树为空*/
		x.rnode = -1; 			/*x的右子树为空*/
		tree[p++] = x; 
	}
	create_tree(j_huff); 
	printf("Proboblility\t\t|Code\t\t|Length\n"); 
      // print_avg_len(??); 
	traverse_tree(p - 1); 
//	print_avg_len();
/*************************************end of  the huffman **************************************/
 for (j=0;j<HUFF_IN_SIZE;j++)
	 {if (huff[j].address>0)
       printf("%d  %d\n",huff[j].address,huff[j].probabilty);
	 }
// print_avg_len(); 	

/*************************** ************************************************* */
	 return(0);
  } 
  else if (temp_flag==1) { // decode 
     printf ("Decoding %s ......\n", argv[2]);
	 set_files_decode(outname);
     tm = time(NULL);
     printf(ctime(&tm));
     decompress();
     tm = time(NULL);
     printf(ctime(&tm)); 
	 filesize=get_file_size(inname);
	 printf("%l",filesize);
	 return(0);
  }
  printusage();
  return(1);
}