/*
 C implementation of LZW compression on stdio
 Features: Code word size is 4 bytes.
*/
#include <stdio.h>
#include <search.h>

#define HASH_SIZE 256*256*64

ENTRY *hashFind (char *key) {
 ENTRY h;
	h.key = key;
	return hsearch(h, FIND);
}

ENTRY *hashAdd (char *key, int data) {
 ENTRY h;
	h.key = (char*)strdup(key);
	h.data = (char*)data;
	return hsearch(h, ENTER);
}

void LZWhashInit (void) {
 char str[2]={0};
 int i;
	hcreate(HASH_SIZE);
	for (i=0; i<256; i++) {
		*str = (char)i;
		if (hashAdd(str, i) == NULL ) { 
			fprintf (stderr, "ERROR: hashInit(): couldn't add root string to table\n");
			exit (-1);
		}
	}
}

void removeLastCharacter (char *str) {
	str[strlen(str)-1] = 0;
}

int lzwCompress (int inDescriptor, int outDescriptor) {
 ENTRY *hp;
 int tableCount=256,  /* AFTER INITIALIZING, TABLE CONTAINS 256 ENTRIES */
     maxStringLength=0;
 char str[65500]={0}, /* LETS HOPE LZW STRINGS DON'T GET THIS BIG */
      ch[2]={0};

	LZWhashInit();

	read (inDescriptor, str, 1);

	while (read(inDescriptor, ch, 1)) {
		strncat (str, ch, 1); /* APPEND ch TO str */
		if (maxStringLength < strlen(str)) maxStringLength = strlen(str);
		if (hashFind(str) == NULL) {
			if (hashAdd(str, tableCount++) == NULL) {; /* ADD str + ch to hash table */
				fprintf (stderr, "ERROR: lzwCompress(): couldn't add string [%s] to table\n", str);
				return -1;
			}
			removeLastCharacter (str);
			hp = hashFind(str); /* ADD str + ch to hash table */
			if (hp == NULL) {
				fprintf (stderr, "\nERROR: lzwCompress(): couldn't find string [%s] in hash \n", str);
				return -1;
			}
			write (outDescriptor, &(hp->data), 4);
			strncpy(str, ch, 2); /* str = ch */
		}
	}

	if ((hp=hashFind(str)) == NULL) {
		fprintf (stderr, "\nERROR: lzwCompress(): final output: couldn't find string [%s] in hash \n", str);
		return -1 ;
	}
	write (outDescriptor, &(hp->data), 4);

	fprintf (stderr, "Table Entry Count:%d  Maximum String Length:%d\n", tableCount, maxStringLength);

	return 0;
}

int main (void) {
	return lzwCompress(0, 1);
}