/***
*Huffman.cpp - 利用Huffman編碼對信源文件壓縮和解壓縮。
*
*Copyright (c) 2007，無有版權(quán)，歡迎復(fù)制
*All rights reserved.
*
*作者：
*	王頂
*	13582027613
*	wngding@gmail.com
*
*目的:
*	做為《信息科學(xué)基礎(chǔ)》課程的實(shí)驗(yàn)，通過程序的設(shè)計和編寫。
*	1、幫助理解和掌握信源分析的方法，能夠計算信源熵和冗余度；
*	2、幫助理解和掌握Huffman編碼的原理，能夠計算平均碼長和編碼效率；
*	3、幫助理解和掌握編碼壓縮的原理、方法和過程；解壓縮的原理、方法和過程；
*	4、通過對編碼壓縮前后文件的比較，分析壓縮比和信源剩余度的關(guān)系；
*	5、理解和掌握二叉樹的生成和遍歷算法；
*	6、理解和掌握文件的創(chuàng)建和讀/寫操作；
*	7、理解和掌握二進(jìn)制的位運(yùn)算；
*	8、掌握C語言程序編寫的常規(guī)技術(shù)：基本語法、代碼風(fēng)格、編程規(guī)范、
*	   數(shù)據(jù)合法性校驗(yàn)、軟件測試，等。
*
*設(shè)計參數(shù)：
*	1、信源文件的最大尺寸2147483647字節(jié)，即2G；
*	2、信源文件中符號的頻次最大值為2147483647；
*	3、計算結(jié)果顯示精度為小數(shù)點(diǎn)后3位，計算精度采用double變量類型；
*	4、字符命令行界面，命令格式：Huffman /O:opt SrcFile DstFile；
*	5、只能對一個文件進(jìn)行壓縮，不能對多文檔或整個目錄進(jìn)行壓縮；
*	6、不能還原原始文件的訪問狀態(tài)信息，如：創(chuàng)建時間、修改時間和最后
*	   間以及只讀或歸檔屬性；
*	7、全局?jǐn)?shù)據(jù)結(jié)構(gòu)的詳細(xì)描述，請參考-設(shè)計資料.xls;
*	8、壓縮文件的存儲格式，請參考-設(shè)計資料.xls;
*
****/

#include "Huffman.h"

//
double		p[SNUM_MAX];							// 信源符號的概率分布
HufTree		HfmTree[NNUM_MAX];						// 用于編碼的Huffman樹
long		frequence[SNUM_MAX];					// 信源符號出現(xiàn)的頻次
char		HfmCode[SNUM_MAX][SNUM_MAX];			// 信源符號對應(yīng)的碼字
char		srcFile[FILENAME_MAX];					// 原始文件名
char		dstFile[FILENAME_MAX];					// 目標(biāo)文件名

//
void main(int argc, char* argv[])
{
	if((argc != CMDARG_MAX) || (!CMD_COMPRESS && !CMD_DECOMPRESS))
	{
		PrintCmdPmt();
		exit(0);
	}

	InitData(argv);
	if(CMD_COMPRESS)		HufCompress();
	if(CMD_DECOMPRESS)		HufDecompress();

	Report(argv);
}


/*------------------------------------------------------------
目的：	打印命令行提示信息
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void PrintCmdPmt(void)
{
	printf("使用Huffman編碼算法壓縮和解壓縮文件。\n\n");
	printf("Huffman /O:opt SrcFile DstFile\n\n");
	printf("  /O\t\t指定操作選項(xiàng)開關(guān)\n");
	printf("  opt\t\tc  壓縮\n");
	printf("     \t\te  解壓縮\n");
	printf("  SrcFile\t指定待壓縮（或解壓縮）的原文件名。\n");
	printf("  DstFile\t指定將要生成的目標(biāo)文件名。\n");
}

/*------------------------------------------------------------
目的：	對信源文件進(jìn)行頻次統(tǒng)計，根據(jù)概率空間進(jìn)行Huffman編碼，
		生成與信源符號對應(yīng)的變長碼字。利用Huffman變長碼字對信
		源文件重新編碼，生成目標(biāo)文件。實(shí)現(xiàn)對信源文件的壓縮。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void HufCompress(void)
{
	double H = 0;
	struct _stat buf;
	long   flenSrc = 0;

	if(_access(srcFile, 0) == -1)
		Error("%s 文件找不到！\n", srcFile);

	_stat(srcFile, &buf);
	flenSrc = buf.st_size;
	if(flenSrc < 0)
		Error("%s 文件太大，程序無法處理！\n", srcFile);

	StatFreq();
	InfoSrcAnalyze();
	H = Entropy();
	
	if(NOT_NEED_COMPRESS)
	{
		WrapSrcFile();
		return;
	}

	if(ScaleFreq() == 1)	InfoSrcAnalyze();

	InitHfmTree();
	GenHfmTree();
	GenHfmCode();
	WriteHfmFile();
}

/*------------------------------------------------------------
目的：	統(tǒng)計信源文件中每個符號出現(xiàn)的頻次。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void StatFreq(void)
{
	int ch = 0;
	FILE* fpSrc = NULL;

	if((fpSrc=fopen(srcFile, "rb")) == NULL)
		Error("%s 文件找不到！\n", srcFile);
	
	while((ch=fgetc(fpSrc)) != EOF)		frequence[ch]++;
	fclose(fpSrc);

#ifdef _DEBUG
	PrintFreq();
#endif
}

/*------------------------------------------------------------
目的：	將信源文件中每個符號出現(xiàn)的頻次，等比例縮小，使縮小
		后的頻次取值在0～255之間。頻次為零的保持不變，頻次
		不為零的等比例縮小不會為零。
輸入：
		無
輸出：
		int		是否進(jìn)行了等比縮小
		0		沒有縮小
		1		實(shí)現(xiàn)縮小
------------------------------------------------------------*/
int ScaleFreq(void)
{
	int i, f = 0;
	long max=0, scale = 0;

	for(i=0; i<SNUM_MAX; i++)
	{
		if(frequence[i] > max)	max = frequence[i];
	}
	
	if(max < SNUM_MAX) return(0);

	scale = (max / SNUM_MAX) + 1;
	
	for(i=0; i<SNUM_MAX; i++)
	{
		if(IS_SYMBOL)
		{
			f = frequence[i] / scale;
			frequence[i] = (f == 0) ? 1 : f;
		}
	}

#ifdef _DEBUG
	printf("等比例縮小之后");
	PrintFreq();
#endif

	return(1);
}

/*------------------------------------------------------------
目的：	打印信源文件每個符號出現(xiàn)的頻次。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void PrintFreq(void)
{
	int i, num = 0;
	long total = 0;

	printf("信源符號的頻次：\n");
	printf("xi    value\tfreq\n");
	printf("-------------------------\n");
	for(i=0; i<SNUM_MAX; i++)
	{
		if(IS_SYMBOL)
		{
			total += frequence[i];
			printf("x%d =\t%02X\t%d\n", ++num, i, frequence[i]);
		}
	}
	printf("-------------------------\n");
	printf("頻次合計:\t%d\n\n", total);
}

/*------------------------------------------------------------
目的：	信源文件分析——計算信源文件每個符號的概率。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void InfoSrcAnalyze(void)
{
	int  i;
	long total = 0;

	for(i=0; i<SNUM_MAX; i++)		total += frequence[i];
	
	for(i=0; i<SNUM_MAX; i++)
	{
		p[i] = (double)frequence[i] / (double)total;
	}

#ifdef _DEBUG
	PrintInfoSrcSum();
#endif
}

/*------------------------------------------------------------
目的：	打印信源文件分析結(jié)果，信源文件每個符號的概率、信源
		熵以及信源的剩余度。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void PrintInfoSrcSum(void)
{
	double H = 0;
	int i, num = 0;

	printf("信源符號的概率分布：\n");
	printf("xi    value\tp\n");
	printf("-------------------------\n");
	for(i=0; i<SNUM_MAX; i++)
	{
		if(IS_SYMBOL)	printf("x%d =\t%02X\t%f\n", ++num, i, p[i]);
	}
	printf("-------------------------\n");
	printf("熵:\t\t%.3f bit\n", H = Entropy());
	printf("剩余度:\t\t%.3f\n\n", 1 - (H / (LB10 * log10(num)))); 
}

/*------------------------------------------------------------
目的：	根據(jù)信源符號的概率分布計算信源熵。
輸入：
		無
輸出：
		double		信源熵
------------------------------------------------------------*/
double Entropy(void)
{
	int		i;
	double	H = 0;

	for(i=0; i<SNUM_MAX; i++)
	{
		if(IS_SYMBOL)	H += -p[i] * log10(p[i]) * LB10;
	}

	return(H);
}

/*------------------------------------------------------------
目的：	初始化Huffman樹。為Huffman樹的葉子節(jié)點(diǎn)賦權(quán)重，并設(shè)置
		啞節(jié)點(diǎn)的初始信息，啞節(jié)點(diǎn)的權(quán)重信息表示用來存儲信源縮
		減的中間節(jié)點(diǎn)的當(dāng)前可用位置（即，數(shù)組的下標(biāo)值）。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void InitHfmTree(void)
{
	int i;

	for(i=0; i<SNUM_MAX; i++)		HfmTree[i].w = frequence[i];
	
	HfmTree[HEAD].p = EOT;
	HfmTree[HEAD].w = SNUM_MAX;

#ifdef _DEBUG
	printf("初始化的");
	PrintHfmTree();
#endif
}

/*------------------------------------------------------------
目的：	打印Huffman樹各個活動節(jié)點(diǎn)的信息。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void PrintHfmTree(void)
{
	int i, num = 0;

	printf("Huffman樹：\n");
	printf("xi\tpos\tweight\tl\tr\tp\n");
	printf("---------------------------------------------\n");
	for(i=0; i<NNUM_MAX; i++)
	{
		if(HfmTree[i].w != 0)
		{
			printf("x%d\t%d\t%d\t%d\t%d\t%d\n", ++num, i, 
				HfmTree[i].w, HfmTree[i].l, HfmTree[i].r, HfmTree[i].p);
		}
	}
	printf("---------------------------------------------\n\n");
}

/*------------------------------------------------------------
目的：	利用信源符號縮減的原理，將Huffman樹各個活動葉子節(jié)點(diǎn)
		與縮減的中間節(jié)點(diǎn)連接成一棵二叉樹。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void GenHfmTree(void)
{
	int s1 = 0, s2 = 0, s3 = 0;

#ifdef _DEBUG
	printf("信源縮減過程：\n");
#endif

	while(Select(&s1, &s2) != 0)
	{
		_ASSERT(HfmTree[HEAD].w < NNUM_MAX);
		s3 = HfmTree[HEAD].w++;
				
		HfmTree[s3].l = s1;
		HfmTree[s3].r = s2;
		HfmTree[s3].w = HfmTree[s1].w + HfmTree[s2].w;

		HfmTree[s1].p = s3;
		HfmTree[s2].p = s3;

		// 可以在這里調(diào)試打印每一步信源縮減后的Huffman樹信息
	}

#ifdef _DEBUG
	printf("\n生成的");
	PrintHfmTree();
#endif
}

/*------------------------------------------------------------
目的：	從Huffman樹中選擇權(quán)重最小的兩個節(jié)點(diǎn)。條件是這兩個節(jié)
		點(diǎn)是活動節(jié)點(diǎn)，并且是孤立節(jié)點(diǎn)，可以是葉子節(jié)點(diǎn)也可以是
		中間節(jié)點(diǎn)，最后權(quán)重需要滿足下面的不等式：
			weight(s1) <= weight(s2) <= weight(other node)。
輸入：
		int* s1		第一個節(jié)點(diǎn)的下標(biāo)
		int* s2		第二個節(jié)點(diǎn)的下標(biāo)
輸出：
		int			選擇是否成功
			1		成功
			0		失敗，只剩下一個滿足條件的活動節(jié)點(diǎn)了
------------------------------------------------------------*/
int Select(int* s1, int* s2)
{
	int i;
	const int num = HfmTree[HEAD].w;
	int MinWeight = INT_MAX;

	*s1 = *s2 = HEAD;
	for(i=0; i<num; i++)
	{
		if((HfmTree[i].w < MinWeight)		/* HfmTree[i]的權(quán)重最小 */
			&& (HfmTree[i].w != 0)			/* HfmTree[i]是活動節(jié)點(diǎn) */
			&& (HfmTree[i].p == 0))			/* HfmTree[i]是孤立節(jié)點(diǎn) */
		{
			MinWeight = HfmTree[i].w;
			*s1 = i;
		}
	}

	MinWeight = INT_MAX;
	for(i=0; i<num; i++)
	{
		if((HfmTree[i].w < MinWeight)		/* HfmTree[i]的權(quán)重最小 */
			&& (HfmTree[i].w != 0)			/* HfmTree[i]是活動節(jié)點(diǎn) */
			&& (HfmTree[i].p == 0)			/* HfmTree[i]是孤立節(jié)點(diǎn) */
			&& (i != *s1))					/* *s2 <> *s1			*/
		{
			MinWeight = HfmTree[i].w;
			*s2 = i;
		}
	}

#ifdef _DEBUG
	printf("s1 = %3d,   s2 = %3d,   s3 = %3d\n", *s1, *s2, num);
#endif

	return(((*s2 == HEAD) && (*s1 == num-1)) ? 0 : 1);
}

/*------------------------------------------------------------
目的：	利用Huffman樹為每個信源符號生成相應(yīng)的碼字。每個信源
		符號都是Huffman樹的活動葉子節(jié)點(diǎn)，從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)
		行進(jìn)路徑就是分配碼元符號，產(chǎn)生編碼的過程。中間節(jié)點(diǎn)的
		左分支分配碼元符號'1'，右分支分配碼元符號'0'。碼字的
		實(shí)際順序與此過程正好相反，因此需要有一個反轉(zhuǎn)的操作。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void GenHfmCode(void)
{
	int  i, pos;
	char code[SNUM_MAX] = "";
	char* pCode = code;
	char* pHfmCode = NULL;
	HufNode* node = NULL;

	for(i=0; i<SNUM_MAX; i++)
	{
		if(NOT_LEAF_NODE)	continue;

		node = &HfmTree[i];
		pos  = i;
		
		// 生成碼字
		while(NOT_TOUCH_ROOT)
		{
			*(pCode++) = IS_LEFT_CHILD ? '1' : '0';
			MOVE_TO_ROOT;
		}
		
		// 反轉(zhuǎn)碼字
		pHfmCode = HfmCode[i];
		while(pCode > code)
		{
			*(pHfmCode++) = *(--pCode);
		}
	}

#ifdef _DEBUG
	PrintHfmCode();
#endif
}

/*------------------------------------------------------------
目的：	打印Huffman編碼生成的碼字。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void PrintHfmCode(void)
{
	int i, num = 0;
	double avgLen = 0;

	printf("碼字：\n");
	printf("xi\tpos\tfreq\tlen\tCode\n");
	printf("---------------------------------------------\n");
	for(i=0; i<SNUM_MAX; i++)
	{
		if(IS_SYMBOL)
		{
			num++;
			avgLen += p[i] * strlen(HfmCode[i]);
			printf("x%d\t%d\t%d\t%d\t%s\n", num, i,
				frequence[i], strlen(HfmCode[i]), HfmCode[i]);
		}
	}
	printf("---------------------------------------------\n");
	printf("平均碼長：\t%.3f\n", avgLen);
	printf("編碼效率：\t%.2f %%\n", 100.0 * Entropy() / avgLen);
	printf("理論壓縮率：\t%.2f %%\n\n", 100.0 * avgLen / CHAR_BIT);
}

/*------------------------------------------------------------
目的：	利用信源符號對應(yīng)的碼字，對信源文件重新編碼，實(shí)現(xiàn)
		壓縮。
輸入：
		無
輸出：
		無
------------------------------------------------------------*/
void WriteHfmFile(void)
{
	int ch = 0;
	unsigned int  i, len = 0U;
	unsigned char buf = 0x00;
	const unsigned char mask = 0x80;
	FILE *fpSrc = NULL, *fpDst = NULL;

	if((fpSrc=fopen(srcFile, "rb")) == NULL)
		Error("%s 文件找不到！\n", srcFile);

	if((fpDst=fopen(dstFile, "w+b")) == NULL)
	{
		fclose(fpSrc);
		Error("%s 文件創(chuàng)建失敗！\n", dstFile);
	}

	WriteHfmFileHead(fpDst);

	while((ch=fgetc(fpSrc)) != EOF)			// 寫壓縮文件編碼主體
	{
		for(i=0; HfmCode[ch][i] != EOS; i++)
		{
			if(HfmCode[ch][i] == '1')	buf |= mask >> len;

			if(len == (CHAR_BIT - 1))
			{
				fputc(buf, fpDst);
				len = -1;
				buf = 0x00;
			}

			len++;
		}
	}
	
	_ASSERT(len != -1);

	if(len != 0)	// buf沒有填充完畢，寫壓縮文件的最后一個字節(jié)
	{
		fputc(buf, fpDst);
		fseek(fpDst, strlen(HFM_FILE_TOKEN), SEEK_SET);
		buf = fgetc(fpDst) + len;
		fseek(fpDst, strlen(HFM_FILE_TOKEN), SEEK_SET);
		fputc(buf, fpDst);
		fseek(fpDst, 0, SEEK_END);
	}

#ifdef _DEBUG
	PrintResult(ftell(fpSrc), ftell(fpDst));
#endif

	fclose(fpSrc);
	fclose(fpDst);
}

/*------------------------------------------------------------
目的：	寫Huffman壓縮文件的頭信息，包括三部分：文件標(biāo)識符、
		FLAG和頻次表。頻次表的存儲有兩種方式，行程長度存儲
		和連續(xù)存儲。