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

#define MAX 65535				// 字典項的最大數量, 默認采用兩個字節編碼, 且預留最大值作為空值.
								// 這是因為0表示了'\0'而不能表示空. 此值不能隨意修改! default: 65535

#define TIRED 256				// 疲勞忍受值, 當Hash沖突造成的順延量超過此值時, 清空Hash表. default: 256


/* --------------------- Structure Declarations ----------------------- */

struct _DICT {							// 字典結構
	unsigned short pre[MAX];	// 字典項的前綴, 即前面字符的編碼
	char ch[MAX];				// 字典項的后綴, 即最后的字符
};

typedef _DICT DICT;


/* ------------------- Global Function Declarations --------------------- */

void dicInit();													// 初始化或重置字典

int enCode();													// 編碼
int deCode();													// 解碼
void test();													// 調試用, 對用戶無意義

/* ------------------- Global Variable Declarations --------------------- */

DICT _dic; DICT* dic=&_dic;						// 字典
FILE* pf, * nf;									// pf 原文件, nf 壓縮后的文件


/* -------------------------- Source Begins ----------------------------- */

int main()
{
	char cmd; char s[99], t[99];
	printf("===== LZW Text Compression =====\n\n1.Compression\n2.Decompression\n0.Exit\n: ");
	scanf("%c", &cmd); fflush(stdin);
	switch (cmd) {
		case '1':
			printf("\nOrigin File: ");
			scanf("%s", s); fflush(stdin);
			pf=fopen(s, "rb");
			if (!pf) {
				printf("\nCannot find file %s. Please check the filename correct.\n", s);
				system("PAUSE"); return -1;
			}
			printf("Target File: ");
			scanf("%s", t); fflush(stdin);
			nf=fopen(t, "wb");
			printf("\nCompressing...\n"); enCode();
			fclose(pf); fclose(nf);
			break;
		case '2':
			printf("\nOrigin File: ");
			scanf("%s", t); fflush(stdin);
			nf=fopen(t, "rb");
			if (!nf) {
				printf("\nCannot find file %s. Please check the filename correct.\n", t);
				system("PAUSE"); return -1;
			}
			printf("Target File: ");
			scanf("%s", s); fflush(stdin);
			pf=fopen(s, "wb"); 
			printf("\nDecompressing...\n"); deCode();
			fclose(pf); fclose(nf);
			break;
		default:
			break;
	}
	return 0;
}

// 重置字典, 將127以后的項全部清空
void dicInit()
{
	int i;
	for (i=0; i<256; i++) {										// 建立基底, 即0-255的ASCII碼表
		dic->pre[i]=MAX; dic->ch[i]=(char)i;					// 基底的pre是無用的
	}
	for (i=256; i<MAX; i++) dic->pre[i]=MAX;					// 只需清空pre一項即可
}

// 編碼
// 若成功編碼, 返回0, 否則返回-1
int enCode()
{
	char buf[MAX];												// buf 讀取緩沖區
	unsigned short size=0;										// size 緩沖區有效長度
	int forecode, thecode, tmpcode=0;							// forecode 前一編碼, thecode 當前編碼, tmpcode 臨時編碼
	unsigned short tir;											// tir 疲勞度, 即順延的程度
	unsigned short n;											// n 狀態判斷, 1為正常, 0為文件尾, 2為字典已滿

	if (fread(&buf[0], sizeof(char), 1, pf)==0) {				// 空文件, 報錯
		printf("\n原文件為空, 壓縮失敗!\n"); return -1;
	}

	dicInit();													// 初始化字典
	rewind(pf);													// 文件復位, 準備開始
	fread(&buf[0], sizeof(char), 1, pf); size=1;				// 預先讀一個字符
	forecode=tmpcode=(int)buf[0];								// 前一編碼就是ASCII碼

	while (1) {

		/* ---------------- 搜索編碼 ---------------- */

		while (n=fread(&buf[size], sizeof(char), 1, pf)) {		// fread()返回成功讀取的數量, 為0時即文件尾, 跳出循環
			if (size>=MAX-1) {n=2; break;}						// 緩沖區滿, 強制跳出循環并清空字典
			tir=0;												// 疲勞度歸零
			thecode=(tmpcode+256+buf[size])%MAX; if (thecode<256) thecode=256;
			tmpcode=thecode;									// 暫存原始位置, 以備下一循環上面式子使用
			// 編碼的算法是: (長度-1)*256 + 最后一位ASCII + 前面字符串的編碼, 并對MAX取模, 采用順延解決Hash沖突
		
			while (dic->pre[thecode]!=forecode || dic->ch[thecode]!=buf[size]) {
				if (dic->pre[thecode]==MAX) break;				// 編碼不存在, 跳出循環并準備新建
				if (++tir>TIRED) { n=2; break;}					// 疲勞度超過忍受值時, 設置狀態值為2, 跳出循環并準備寫入文件后清空字典
				thecode=(thecode+1)%MAX; if (thecode<256) thecode=256;
			}
			if (dic->pre[thecode]==MAX || n==2) break;			// 編碼為空或字典已滿時, 跳出搜索循環, 準備新建
			forecode=thecode; size++;							// 找到編碼, 儲存前一編碼, 繼續循環
		}

		/* ---------------- 寫入文件 ---------------- */

		tir=(unsigned short)forecode;							// 找一個地方把forecode轉成unsigned short
		fwrite(&tir, sizeof(unsigned short), 1, nf);
		if (n==0) break;										// 文件結束, 跳出所有循環

		/* --------------- 新建字典項 --------------- */

		if (n==2) dicInit();									// 字典滿時清空字典
		else { dic->pre[thecode]=forecode; dic->ch[thecode]=buf[size];}
		buf[0]=buf[size]; size=1; forecode=tmpcode=(int)buf[0];	// 保留查找失敗的字符, 進入搜索循環

	}
	return 0;
}

// 解碼
// 若成功解碼, 返回0, 否則返回-1
int deCode()
{
	char buf1[MAX], buf2[MAX];									// buf1, buf2 寫入緩沖區, 緩沖區內的字符串都是逆序排列的, 方便操作
	unsigned short size1=0, size2=0;							// size1, size2 各緩沖區尾部位置
	unsigned short forecode, thecode=MAX;						// forecode 前一編碼, thecode 當前編碼
	int tmpcode;												// tmpcode 臨時編碼
	unsigned short tir;											// tir 疲勞度, 即順延的程度
	unsigned short n;											// n 狀態判斷, 1為正常, 0為文件尾, 2為字典已滿, 3為讀到未知編碼
	int i;														// 臨時變量

	if (fread(&thecode, sizeof(unsigned short), 1, nf)==0) {	// 空文件, 報錯
		printf("\n壓縮文件為空, 解壓失敗!\n"); return -1;
	}

	dicInit(); rewind(nf);										// 初始化字典并將文件復位, 準備開始

	while (1) {

		/* ---------------- 讀入編碼 ---------------- */

		forecode=thecode;										// 將上一編碼保存
		n=fread(&thecode, sizeof(unsigned short), 1, nf);

		/* ------------ 譯碼并寫入緩沖區 ------------ */
		
		if (dic->pre[thecode]==MAX && thecode>255) {			// 字典項不存在的情況
			// 這是因為在壓縮時剛生成的字典項馬上被使用, 而解壓生成的速度比壓縮時慢一步造成的
			// 這只有在一種情況下發生, 就是當前項加上當前項的首字的搭配, 由此可給出此解決方法
			dic->pre[thecode]=forecode; dic->ch[thecode]=buf1[size1-1]; n=3;
		}

		tmpcode=thecode;										// 迭代初值
		do {													// 迭代開始, 將字符依次讀出, 得到逆序字符串
			buf2[size2++]=dic->ch[tmpcode];						// 讀取時寫入緩沖區2
			tmpcode=dic->pre[tmpcode];
		} while (tmpcode<MAX);

		/* ---------- 寫入文件和新建字典項 ---------- */

		if (size1>0 && n) {										// 不是文件頭或文件尾時, 寫入文件并新建字典項

			for (i=size2-1; i>=0; i--) fwrite(&buf2[i], sizeof(char), 1, pf);
																// 將buf2中的字符串寫入文件
			
			if (size1>=MAX-2) n=2;								// buf1緩沖區滿, 強制清空字典
			if (n<2) {											// n==3時字典項已經新建過了, 故不再新建
				tmpcode=size1*256;
				for (i=size1-1; i>=0; i--) tmpcode+=(int)buf1[i];
				tmpcode=(tmpcode+(int)buf2[size2-1])%MAX;		// 這三句利用算法求得編碼的公式位置
				// 新的編碼為前一字符串buf1的所有字符加當前字符串buf2的第一個字符, 注意字符串的存儲是逆序的
			
				tir=0;											// 疲勞度歸零
				while (dic->pre[tmpcode]<MAX) {					// 字典項沖突, 順延解決沖突
					if (++tir>TIRED) { n=2; break;}				// 字典滿了
					tmpcode=(tmpcode+1)%MAX; if (tmpcode<256) tmpcode=256;
				}
				if (n!=2) {	dic->pre[tmpcode]=forecode; dic->ch[tmpcode]=buf2[size2-1];}
			}													// 本循環按照上面的規則新建字典項 
			if (n==2) {
				dicInit(); buf1[0]=buf2[0]; size1=1; size2=0;
			}													// 字典滿時, 清空字典并更新緩沖區
			else {
				for (i=0; i<size2; i++) buf1[i]=buf2[i];
				size1=size2; size2=0;							// 這兩句將緩沖區更新, 把當前字符串buf2復制到buf1, 并清空buf2
			}

		}
		else if (n) {
			fwrite(&buf2[0], sizeof(char), 1, pf);				// 文件頭只有一個字符, 寫入即可
			buf1[0]=buf2[0]; size1=1; size2=0;					// 更新緩沖區和size
		}
		else break;												// 文件結束, 退出循環

	}
	return 0;
}

void test()														// 調試用, 對用戶無意義
{
	FILE* tf1=fopen("result.bin", "rb");
	FILE* tf2=fopen("debug.txt", "w");
	unsigned short t;
	while (fread(&t, sizeof(unsigned short), 1, tf1)) fprintf(tf2, "%d ", t);
	fclose(tf1); fclose(tf2);
}