/***
*Huffman.h - Huffman編碼用到的運行庫頭文件、宏定義、數據結構定義
*			 以及函數聲明
*
*Copyright (c) 2007，無有版權，歡迎復制
*All rights reserved.
*
*作者：
*	王頂
*	13582027613
*	wngding@gmail.com
*	
****/

#include <io.h>
#include <math.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <crtdbg.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <stdarg.h>

//
#define SNUM_MAX		256						// 信源符號個數最多為256個
#define NNUM_MAX		512						// 樹節點個數最多為512個
#define CMDARG_MAX		4						// 命令行參數個數最多為4個

#define LB10			3.321928095				// 以2為底10的對數
#define HEAD			NNUM_MAX - 1			// Huffman樹頭節點的位置
#define EOS				'\0'					// End of String
#define EOT				-1						// End of Tree

#define CMD_COMPRESS	(stricmp(argv[1], "/O:c") == 0)
#define CMD_DECOMPRESS	(stricmp(argv[1], "/O:e") == 0)

#define IS_SYMBOL		(frequence[i] != 0)
#define NOT_TOUCH_ROOT	(node->p != 0)
#define NOT_LEAF_NODE	(HfmTree[i].p == 0)
#define IS_LEAF_NODE	(node->l == 0) && (node->r == 0) && (node->p != 0)
#define IS_LEFT_CHILD	(HfmTree[node->p].l == pos)
#define MOVE_TO_ROOT	pos = node->p;	node = &HfmTree[pos]
#define MOVE_TO_LEAF	pos = (bit == 0x00) ? node->r : node->l;	node = &HfmTree[pos];
#define HEAD_NODE		&HfmTree[HfmTree[HEAD].w - 1]

#define HFM_FILE_TOKEN	"Hfm"
#define NOT_NEED_COMPRESS	(flenSrc - flenSrc * H / CHAR_BIT) < StoreCost()

//
typedef struct
{
	int l;		// left child
	int r;		// right child
	int p;		// parent
	int w;		// weight
}HufNode, HufTree;


/*
雜項函數 -	初始化全局變量；錯誤處理。
*/
void InitData(char* argv[]);
void Error(char* fmt, ...);

/*
信源分析函數 -	統計信源符號的頻次，計算信源剩余度。
*/
void StatFreq(void);
int  ScaleFreq(void);
void InfoSrcAnalyze(void);
double Entropy(void);

/*
Huffman編碼函數 - 根據信源符號的概率構造Huffman樹，生成碼字。
*/
void InitHfmTree(void);
void GenHfmTree(void);
void GenHfmCode(void);
int  Select(int* s1, int* s2);

/*
寫壓縮文件函數 - 利用編碼得到的碼字壓縮原始文件。
*/
void HufCompress(viod);
void WriteHfmFileHead(FILE* fpDst);
void WriteHfmFile(void);
void SaveFrqSerial(FILE *fpDst);
void SaveFrqRunLen(FILE *fpDst, int secNum);
void WrapSrcFile(void);
int  SuitRunLen(void);
int  StoreCost(void);

/*
解壓縮文件函數 - 將壓縮文件還原成原始文件。
*/
void HufDecompress(void);
int  IsHFMFile(FILE* fpSrc);
int  ReadFrq(FILE* fpSrc, int flag);
void DecodeFile(FILE* fpSrc, FILE* fpDst);

/*
用戶接口函數 - 打印提示命令行參數；輸出程序執行的結果。
*/
void PrintCmdPmt(void);
void Report(char* argv[]);

/*
調試函數 - 打印輸出程序執行的中間結果，用來觀察、判斷程序執行是否正確。
*/
void PrintFreq(void);
void PrintHfmTree(void);
void PrintHfmCode(void);
void PrintInfoSrcSum(void);
void PrintResult(long flenSrc, long flenDst);