com.c

LZW的简单算法。主要能够进行简单的示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

#define NOT_USED -1
#define HASH_SIZE 4099

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 set_files(char *filename);

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

FILE *in, *out;
const int MAX_CODES = 4096;
const int BYTE_SIZE = 8;
const int EXCESS = 4;
const int ALPHA = 256;
const int MASK1 = 255;
const int MASK2 = 15;
int leftOver;
BOOL bitsLeftOver = FALSE;

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(pcode);
                if(codeUsed<MAX_CODES)
                    put( (pcode<<BYTE_SIZE)+c,codeUsed++);
            	pcode = c;
            }
            else pcode = e;
         	c=fgetc(in);
        }
        output(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(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 set_files(char *filename){
    char *s;
    if( (in = fopen(filename, "rb")) == NULL){
        printf("Cannot open input file - %s\n", filename);
        exit(1);;
	}
    s = strncat(filename, ".zzz", 4);
    if ((out = fopen(s, "wb"))== NULL){
        printf("Cannot open output file - %s\n", s);
        fclose(in);
        exit(1);
    }
}

int main(int argc, char* argv[]){
    if(argc<2){
        printf("Usage:compress <filename>\n");
        return(1);
    }
    set_files(argv[1]);
    compress();
    return 0;
}