//////////////////////////////
// LZ77.h
//////////////////////////////

// 使用在自己的堆中分配索引節點，不滑動窗口
// 每次最多壓縮 65536 字節數據
// 的優化版本

#ifndef _WIX_LZ77_COMPRESS_HEADER_001_
#define _WIX_LZ77_COMPRESS_HEADER_001_
#define _CRT_SECURE_NO_WARNINGS
// 滑動窗口的字節大小
#define _MAX_WINDOW_SIZE	65536
#define MAX_BUF 1024
class CCompress
{
public:
	CCompress() {};
	virtual ~CCompress() {};

public:
	virtual int Compress(BYTE* src, int srclen, BYTE* dest) = 0;
	virtual BOOL Decompress(BYTE* src, int srclen, BYTE* dest) = 0;

protected:
	// tools 

	/////////////////////////////////////////////////////////
	// CopyBitsInAByte : 在一個字節范圍內復制位流
	// 參數含義同 CopyBits 的參數
	// 說明：
	//		此函數由 CopyBits 調用，不做錯誤檢查，即
	//		假定要復制的位都在一個字節范圍內
	void CopyBitsInAByte(BYTE* memDest, int nDestPos, 
				  BYTE* memSrc, int nSrcPos, int nBits);

	////////////////////////////////////////////////////////
	// CopyBits : 復制內存中的位流
	//		memDest - 目標數據區
	//		nDestPos - 目標數據區第一個字節中的起始位
	//		memSrc - 源數據區
	//		nSrcPos - 源數據區第一個字節的中起始位
	//		nBits - 要復制的位數
	//	說明：
	//		起始位的表示約定為從字節的高位至低位（由左至右）
	//		依次為 0，1，... , 7
	//		要復制的兩塊數據區不能有重合
	void CopyBits(BYTE* memDest, int nDestPos, 
				  BYTE* memSrc, int nSrcPos, int nBits);

	//////////////////////////////////////////////////////////////
	// 將DWORD值從高位字節到低位字節排列
	void InvertDWord(DWORD* pDW);

	/////////////////////////////////////////////////////////////
	// 設置byte的第iBit位為aBit
	//		iBit順序為高位起從0記數（左起）
	void SetBit(BYTE* byte, int iBit, BYTE aBit);

	////////////////////////////////////////////////////////////
	// 得到字節byte第pos位的值
	//		pos順序為高位起從0記數（左起）
	BYTE GetBit(BYTE byte, int pos);

	////////////////////////////////////////////////////////////
	// 將位指針*piByte(字節偏移), *piBit(字節內位偏移)后移num位
	void MovePos(int* piByte, int* piBit, int num);

	/////////////////////////////////////////////////////////
	// 取log2(n)的upper_bound
	int UpperLog2(int n);

	/////////////////////////////////////////////////////////
	// 取log2(n)的lower_bound
	int LowerLog2(int n);
};

class CCompressLZ77 : public CCompress
{
public:
	CCompressLZ77();
	virtual ~CCompressLZ77();
public:
	/////////////////////////////////////////////
	// 壓縮一段字節流
	// src - 源數據區
	// srclen - 源數據區字節長度, srclen <= 65536
	// dest - 壓縮數據區，調用前分配srclen字節內存
	// 返回值 > 0 壓縮數據長度
	// 返回值 = 0 數據無法壓縮
	// 返回值 < 0 壓縮中異常錯誤
	int Compress(BYTE* src, int srclen, BYTE* dest);

	/////////////////////////////////////////////
	// 解壓縮一段字節流
	// src - 接收原始數據的內存區, srclen <= 65536
	// srclen - 源數據區字節長度
	// dest - 壓縮數據區
	// 返回值 - 成功與否
	BOOL Decompress(BYTE* src, int srclen, BYTE* dest);

	//壓縮文件
	bool CompressFile(char* unZipFile, char* zipFile); 
	//解壓文件
	bool DecompressFile(char* zipFile, char* unZipFile); 
	//壓縮目錄 includeSub：是否包含子目錄
	BOOL CompressDir(char* srcDir, char* zipFile, bool includeSub = true);
	//解壓目錄 
	BOOL DeCompressDir(char* zipFile, char* destDir);
protected:

	BYTE* pWnd;
	// 窗口大小最大為 64k ，并且不做滑動
	// 每次最多只壓縮 64k 數據，這樣可以方便從文件中間開始解壓
	// 當前窗口的長度
	int nWndSize;

	// 對滑動窗口中每一個2字節串排序
	// 排序是為了進行快速術語匹配
	// 排序的方法是用一個64k大小的指針數組
	// 數組下標依次對應每一個2字節串：(00 00) (00 01) ... (01 00) (01 01) ...
	// 每一個指針指向一個鏈表，鏈表中的節點為該2字節串的每一個出現位置
	struct STIDXNODE
	{
		WORD off;		// 在src中的偏移
		WORD off2;		// 用于對應的2字節串為重復字節的節點
						// 指從 off 到 off2 都對應了該2字節串
		WORD next;		// 在SortHeap中的指針
	};
	
	WORD SortTable[65536];  // 256 * 256 指向SortHeap中下標的指針

	// 因為窗口不滑動，沒有刪除節點的操作，所以
	// 節點可以在SortHeap 中連續分配
	struct STIDXNODE* SortHeap;
	int HeapPos;	// 當前分配位置

	// 當前輸出位置(字節偏移及位偏移)
	int CurByte, CurBit;

protected:
	////////////////////////////////////////
	// 輸出壓縮碼
	// code - 要輸出的數
	// bits - 要輸出的位數(對isGamma=TRUE時無效)
	// isGamma - 是否輸出為γ編碼
	void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma);

	///////////////////////////////////////////////////////////
	// 在滑動窗口中查找術語
	// nSeekStart - 從何處開始匹配
	// offset, len - 用于接收結果，表示在滑動窗口內的偏移和長度
	// 返回值- 是否查到長度為3或3以上的匹配字節串
	BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len);

	///////////////////////////////////////////////////////////
	// 得到已經匹配了3個字節的窗口位置offset
	// 共能匹配多少個字節
	inline int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset);

	//////////////////////////////////////////
	// 將窗口向右滑動n個字節
	inline void _ScrollWindow(int n);

	// 向索引中添加一個2字節串
	inline void _InsertIndexItem(int off);

	// 初始化索引表，釋放上次壓縮用的空間
	void _InitSortTable();
private:
	void GetCompressFileName(char *dst, char *src);
};



#endif // _WIX_LZW_COMPRESS_HEADER_001_