huffman.c

用huffman编码定理对文件进行压缩与解压缩

输入：
		FILE* fpDst		压缩文件的文件指针
输出：
		无
------------------------------------------------------------*/
void WriteHfmFileHead(FILE* fpDst)
{
	int secNum = 0;
	unsigned char flag = 0;

	_ASSERT(fpDst != NULL);

	// 写Huffman文件标识符
	fwrite(&HFM_FILE_TOKEN, sizeof(char), strlen(HFM_FILE_TOKEN), fpDst);

	if((secNum = SuitRunLen()) != 0)
	{
		flag = 0x40;			// 第7位置0，代表对信源文件进行压缩
								// 第6位置1，代表采用行程方式存储频次
		fputc(flag, fpDst);
		SaveFrqRunLen(fpDst, secNum);
	}
	else
	{
		flag = 0x00;			// 第7位置0，代表对信源文件进行压缩
								// 第6位置0，代表采用顺序方式存储频次
		fputc(flag, fpDst);
		SaveFrqSerial(fpDst);
	}
}

/*------------------------------------------------------------
目的：	打印压缩结果。包括信源文件长度，目标文件长度和压缩率。
输入：
		long  flenSrc		信源文件长度
		long  flenDst		目标文件长度
输出：
		无
------------------------------------------------------------*/
void PrintResult(long flenSrc, long flenDst)
{
	printf("\n\n压缩结果：\n");
	printf("---------------------------------------------\n");
	printf("原始文件：\t%s\t%1d 字节\n", srcFile, flenSrc);
	printf("目标文件：\t%s\t%1d 字节\n", dstFile, flenDst);
	printf("---------------------------------------------\n");
	printf("压缩率：\t%.2f %%\n", (double)flenDst * 100.0 / (double)flenSrc);
}

/*------------------------------------------------------------
目的：	Huffman解压缩。
输入：
		无
输出：
		无
------------------------------------------------------------*/
void HufDecompress(void)
{
	int ch = 0;
	unsigned char mask  = 0x80;				// 取最高位的掩码
	unsigned char HFour = 0xf0;				// 取高4位的掩码
	FILE *fpSrc = NULL, *fpDst = NULL;

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

	if(IsHFMFile(fpSrc) != 1)
	{
		fclose(fpSrc);
		Error("%s 压缩文件格式不正确！\n", srcFile);
	}

	ch = getc(fpSrc);						// 读取FLAG字段
	
	// 对FLAG 字段进行合法性校验，参考设计文档
	if(((ch & HFour) != 0x80)
		&& ((ch & HFour) != 0x40) 
		&& ((ch & HFour) != 0x00))
	{
		fclose(fpSrc);
		Error("%s 压缩文件格式不正确！！\n", srcFile);
	}

	if((fpDst=fopen(dstFile, "wb")) == NULL)
	{
		fclose(fpSrc);
		Error("%s 文件创建失败！\n", dstFile);
	}

	if((ch & mask) == mask)					// 信源文件没有被压缩
	{
		while((ch=fgetc(fpSrc)) != EOF)		fputc(ch, fpDst);
		fclose(fpSrc);
		fclose(fpDst);
		return;
	}

	if(ReadFrq(fpSrc, ch) == 0)				// 频次读取错误的处理
	{
		fclose(fpSrc);
		fclose(fpDst);
		remove(dstFile);
		exit(-1);
	}

	InfoSrcAnalyze();
	InitHfmTree();
	GenHfmTree();
	GenHfmCode();
	DecodeFile(fpSrc, fpDst);

	fclose(fpSrc);
	fclose(fpDst);
}

/*------------------------------------------------------------
目的：	判断是否为合法的Huffman压缩文件。
输入：
		FILE* fpSrc	压缩文件指针
输出：
		int			是否合法
		1			合法
		0			非法
------------------------------------------------------------*/
int IsHFMFile(FILE* fpSrc)
{
	char ch[sizeof(HFM_FILE_TOKEN)] = "";

	_ASSERT(fpSrc != NULL);
	fread(&ch, sizeof(char), strlen(HFM_FILE_TOKEN), fpSrc);

	return((strcmp(&HFM_FILE_TOKEN, ch) == 0) ? 1 : 0);
}

/*------------------------------------------------------------
目的：	从压缩文件读取频次表信息。
输入：
		FILE* fpSrc		压缩文件指针
		int   flag		压缩文件的FLAG字段，用来判断频次表
						存储的方式
输出：
		int				读取是否成功
		1				成功
		0				失败
------------------------------------------------------------*/
int ReadFrq(FILE* fpSrc, int flag)
{
	int i, j, secNum, len;
	long *p = NULL;							// 频次数组操作指针
	const char mask = 0x40;					// 取FLAG字段的第六位
	int total = 0;

	_ASSERT(fpSrc != NULL);
	if((flag & mask) == mask)				// 行程模式读取频次表
	{
		secNum = fgetc(fpSrc);
		for(i=0; i<secNum; i++)
		{
			p = &frequence[fgetc(fpSrc)];
			len = fgetc(fpSrc);
			for(j=0; j<len; j++)	*(p++) = fgetc(fpSrc);
		}
	}
	else									// 顺序模式读取频次表
	{
		for(i=0; i<SNUM_MAX; i++)		frequence[i] = fgetc(fpSrc);
	}
	
	// 检验频次读取是否正确。频次不能为负，所有频次不能为0。
	for(i=0; i<SNUM_MAX; i++)
	{
		if(frequence[i] < 0)
		{
			printf("ERROR: %s 原文件格式不正确或者已损坏！\n", srcFile);
			return(0);
		}
		total += frequence[i];
	}

	if(total == 0)
	{
		printf("ERROR: %s 原文件格式不正确或者已损坏！\n", srcFile);
		return(0);
	}

#ifdef _DEBUG
	PrintFreq();
#endif
	return(1);
}

/*------------------------------------------------------------
目的：	将压缩文件中的Huffman编码还原成信源文件符号。
输入：
		FILE* fpSrc		原始文件指针
		FILE* fpDst		目标文件指针
输出：
		无
------------------------------------------------------------*/
void DecodeFile(FILE* fpSrc, FILE* fpDst)
{
	unsigned char bit = 0x00;
	const unsigned char mask  = 0x80;		// 取最高位的掩码
	const unsigned char LFour = 0x0f;		// 取低四位的掩码
	HufNode *node = HEAD_NODE;
	int i, ch, pos = HfmTree[HEAD].w - 1;
	long fpos = 0, flen = 0, len = 0;

	_ASSERT(fpSrc != NULL);
	_ASSERT(fpDst != NULL);
	
	fpos = ftell(fpSrc);
	fseek(fpSrc, strlen(HFM_FILE_TOKEN), SEEK_SET);
	len = fgetc(fpSrc) & LFour;
	
	fseek(fpSrc, 0, SEEK_END);
	flen = ftell(fpSrc);

	fseek(fpSrc, fpos, SEEK_SET);

	while(ftell(fpSrc) < (flen-1))
	{
		ch = fgetc(fpSrc);
		for(i=0; i<CHAR_BIT; i++)
		{
			bit = ch & (mask >> i);

			MOVE_TO_LEAF;

			if(IS_LEAF_NODE)
			{
				fputc(pos, fpDst);
				node = HEAD_NODE;
			}
		}
	}
	
	// 翻译最后一个字节，最后一个字节可能没有填满
	ch  = fgetc(fpSrc);
	len = (len == 0) ? CHAR_BIT : len;
	for(i=0; i<len; i++)
	{
		bit = ch & (mask >> i);

		MOVE_TO_LEAF;

		if(IS_LEAF_NODE)
		{
			fputc(pos, fpDst);
			node = HEAD_NODE;
		}
	}
}

/*------------------------------------------------------------
目的：	打印报告。包括：信源分析、编码信息以及压缩效果。
输入：
		char* argv[]	命令行参数
输出：
		无
------------------------------------------------------------*/
void Report(char* argv[])
{
	int i, num = 0;
	struct	_stat buf;
	long	sfLen = 0, dfLen = 0;
	double	H = 0, avgLen = 0;

	printf("\n\t\t-- REPORT --\n\n");

	if(CMD_COMPRESS)
	{
		for(i=0; i<SNUM_MAX; i++)
		{
			if(IS_SYMBOL)
			{
				num++;
				avgLen += p[i] * strlen(HfmCode[i]);
			}
		}

		printf("信源：\n");
		printf("---------------------------------------------\n");
		printf("符号个数：\t%d\n", num);
		printf("熵：\t\t%.3f bit\n", H = Entropy());
		printf("剩余度：\t%.3f\n\n", 1 - (H / (LB10 * log10(num)))); 
		
		printf("编码：\n");
		printf("---------------------------------------------\n");
		avgLen = (avgLen <= 0) ? CHAR_BIT : avgLen;
		printf("平均码长：\t%.3f bit\n", avgLen);
		printf("编码效率：\t%.2f %%\n", 100.0 * H / avgLen);
		printf("理论压缩率：\t%.2f %%\n\n", 100.0 * avgLen / CHAR_BIT);
		
		printf("压缩：\n");
		printf("---------------------------------------------\n");	
	}

	_stat(srcFile, &buf);
	sfLen = buf.st_size;
	printf("原始文件：\t%s\t%ld 字节\n", srcFile, sfLen);

	_stat(dstFile, &buf);
	dfLen = buf.st_size;
	printf("目标文件：\t%s\t%ld 字节\n", dstFile, dfLen);
	
	if(CMD_COMPRESS)
	{
		printf("节省空间：\t%ld 字节\n", sfLen - dfLen);
		printf("压缩率：\t%.2f %%\n", ((double)dfLen) * 100.0 / ((double)sfLen));
	}
}


/*------------------------------------------------------------
目的：	将信源文件打包。因为对信源文件的压缩不足以抵消存储
		频次表的开销，因此不压缩信源文件，仅仅将其封装。即
		仅仅加上Huffman文件头标识符，其他部分与信源文件的每
		个字节都完全相同。
输入：
		无
输出：
		无
------------------------------------------------------------*/
void WrapSrcFile(void)
{
	int ch = 0;
	FILE *fpSrc = NULL, *fpDst = NULL;
	const unsigned char flag = 0x80;		// 最高位为1，代表信源文件
											// 没有被压缩
	if((fpSrc=fopen(srcFile, "rb")) == NULL)
		Error("%s 文件找不到！\n", srcFile);

	if((fpDst=fopen(dstFile, "wb")) == NULL)
	{
		fclose(fpSrc);
		Error("%s 文件创建失败！\n", dstFile);
	}

	// 写Huffman文件标识符
	fwrite(&HFM_FILE_TOKEN, sizeof(char), strlen(HFM_FILE_TOKEN), fpDst);
	fputc(flag, fpDst);

	// 写Huffman文件主体，与信源文件的每个字节完全相同 
	while((ch=fgetc(fpSrc)) != EOF)		fputc(ch, fpDst);
	
	fclose(fpSrc);
	fclose(fpDst);
}

/*------------------------------------------------------------
目的：	按连续方式存储频次表信息。
输入：
		FILE* fpDst		压缩文件的文件指针
输出：
		无
------------------------------------------------------------*/
void SaveFrqSerial(FILE *fpDst)
{
	int i;

	_ASSERT(fpDst != NULL);
	for(i=0; i<SNUM_MAX; i++)		fputc(frequence[i], fpDst);
}

/*------------------------------------------------------------
目的：	判断频次表是否适合用行程方式压缩。
输入：
		无
输出：
		int			是否适合
		<>0			适合，行程段的数量
		==0			不适合
------------------------------------------------------------*/
int SuitRunLen(void)
{
	int			i;
	int			secNum			 = 0;		// 行程段的数量
	int			totalLen		 = 0;		// 行程段中频次的总数量
	const char	SPAN[]			 = "000";	// 行程段与段之间的间隙
	char		strFrq[SNUM_MAX+1] = "";		// 频次字符串
	char		*p1 = NULL, *p2  = NULL;	// 操作频次字符串的指针

	// 初始化频次字符串
	for(i=0; i<SNUM_MAX; i++)	strFrq[i] = (frequence[i]==0) ? '0':'1';

#ifdef _DEBUG
	printf("频次表的行程分析：\nstart\tlen\tfreq\n");
	printf("---------------------------------------------");
#endif

	p1 = strstr(strFrq, "1");
	while((p2 = strstr(p1, SPAN)) != NULL)
	{
		secNum++;
		totalLen += p2 - p1;

#ifdef _DEBUG
		printf("\n%0.2X\t%d    ", p1-strFrq, p2-p1);
		while(p1<p2)	printf("%5d", frequence[(p1++)-strFrq]);
#endif
		
		if((p1 = strstr(p2, "1")) == NULL) break;
	}
	
	if(p1 != NULL)
	{
		if(*p1 == '1')
		{
			secNum++;
			while(*(p1++) != EOS) totalLen++;
		}
	}

#ifdef _DEBUG
	printf("\n---------------------------------------------\n");
	printf("行程段数：\t%d\n频次总数：\t%d", secNum, totalLen);
#endif

	return(((totalLen + secNum * 2)< SNUM_MAX) ? secNum : 0);
}

/*------------------------------------------------------------
目的：	按行程方式存储频次表。
输入：
		FILE* fpDst		压缩文件的文件指针
		int   secNum	行程段的数量
输出：
		无
------------------------------------------------------------*/
void SaveFrqRunLen(FILE *fpDst, int secNum)
{
	int			i;
	const char	SPAN[]			 = "000";	// 行程段与段之间的间隙
	char		strFrq[SNUM_MAX+1] = "";		// 频次字符串
	char		*p1 = NULL, *p2  = NULL;	// 操作频次字符串的指针

	// 初始化频次字符串
	for(i=0; i<SNUM_MAX; i++)	strFrq[i] = (frequence[i]==0) ? '0':'1';

	p1 = strstr(strFrq, "1");
	fputc(secNum, fpDst);					// 保存行程段的数量
	while((p2 = strstr(p1, SPAN)) != NULL)
	{
		fputc(p1-strFrq, fpDst);			// 保存行程段的起始位置
		fputc(p2-p1, fpDst);				// 保存行程段的长度
		
		// 保存行程段中的频次值
		while(p1<p2)	fputc(frequence[(p1++)-strFrq], fpDst);

		if((p1 = strstr(p2, "1")) == NULL)	break;
	}

	if(p1 != NULL)
	{
		if(*p1 == '1')
		{
			fputc(p1-strFrq, fpDst);		// 保存行程段的起始位置
			p2 = &strFrq[SNUM_MAX];
			fputc(p2-p1, fpDst);			// 保存行程段的长度

			while(*p1 != EOS)
			{
				fputc(frequence[(p1++)-strFrq], fpDst);
			}
		}
	}
}

/*------------------------------------------------------------
目的：	初始化全局数据，包括：频次数组、概率数组、Huffman树
		的节点数组以及码字数组。
输入：
		char* argv[]	命令行参数，用于获取信源文件和目标
						文件的文件名
输出：
		无
------------------------------------------------------------*/
void InitData(char* argv[])
{
	int i;

	for(i=0; i<SNUM_MAX; i++)
	{
		frequence[i] = 0l;
		p[i]		 = 0;

		HfmTree[i].l = 0;
		HfmTree[i].r = 0;
		HfmTree[i].p = 0;
		HfmTree[i].w = 0;

		strset(HfmCode[i], EOS);
	}

	strcpy(srcFile, argv[2]);
	strcpy(dstFile, argv[3]);
}

/*------------------------------------------------------------
目的：	严重错误处理。在屏幕上显示错误信息，并退出执行。
输入：
		char* fmt	格式化字符串
		...			可变参数列表
输出：
		无
------------------------------------------------------------*/
void Error(char* fmt, ...)
{
	va_list argptr;

	va_start(argptr, fmt);
	printf("ERROR: ");
	vprintf(fmt, argptr);
	va_end(argptr);
	exit(-1);
}

/*------------------------------------------------------------
目的：	计算压缩文件头部存储频次表等信息的开销。
输入：
		无
输出：
		int		以字节为单位的开销大小
------------------------------------------------------------*/
int StoreCost(void)
{
	int			i;
	int			secNum			 = 0;		// 行程段的数量
	int			totalLen		 = 0;		// 存储总开销
	const char	SPAN[]			 = "000";	// 行程段与段之间的间隙
	char		strFrq[SNUM_MAX+1] = "";		// 频次字符串
	char		*p1 = NULL, *p2  = NULL;	// 操作频次字符串的指针

	// 初始化频次字符串
	for(i=0; i<SNUM_MAX; i++)	strFrq[i] = (frequence[i]==0) ? '0':'1';

	p1 = strstr(strFrq, "1");
	while((p2 = strstr(p1, SPAN)) != NULL)
	{
		secNum++;
		totalLen += p2 - p1;	
		if((p1 = strstr(p2, "1")) == NULL) break;
	}
	
	if(p1 != NULL)
	{
		if(*p1 == '1')
		{
			secNum++;
			while(*(p1++) != EOS) totalLen++;
		}
	}

	totalLen += secNum * 2;
	totalLen = (totalLen < SNUM_MAX) ? (totalLen + 1) : SNUM_MAX;
	totalLen += sizeof(HFM_FILE_TOKEN);

#ifdef _DEBUG
	printf("文件头部存储开销：%d 字节\n\n", totalLen);
#endif

	return(totalLen);
}