lzw1.c

LZW压缩解压的完整程序

#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

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

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];
int leftOver;
BOOL bitsLeftOver = FALSE;

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);
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);



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 *flag;
char *cc;
const int MASK1 = 255;
const int MASK2 = 15;
int leftOver;

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;
    init_hashtable();
    for(i=0; i<ALPHA; i++)
        put(i,i);

    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);
                if(codeUsed<MAX_CODES)
                    put( (pcode<<BYTE_SIZE)+c,codeUsed++);
            	pcode = c;
            }
            else pcode = e;
         	c=fgetc(in);
        }
        output_encode(pcode);
        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 c,d;
    if(bitsLeftOver){
        d = pcode & MASK1;
        c = (leftOver << EXCESS)+(pcode>>BYTE_SIZE);
        //printf("%i - ", c);print_binary(c);
        //printf("%i - ", d);print_binary(d);
        fputc(c, out);
        fputc(d, out);
        bitsLeftOver = FALSE;
    }
    else{
        leftOver = pcode & MASK2;
        c = pcode>>EXCESS;
        //printf("%i - ", c);print_binary(c);
        fputc(c, out);
        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;
  char *tempfile;
  long filesize;
  if(argc!=3){
        printusage();
        return(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);
	 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);
}