#include <windows.h>
#include <stdio.h>
#include <memory.h>
#include <crtdbg.h>

#define _MAX_WINDOW_SIZE	65536

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:

	void CopyBitsInAByte(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);
	// 在一個字節范圍內復制位流
	void CopyBits(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);
	//復制內存中的位流
	void InvertDWord(DWORD* pDW);	// 將DWORD值從高位字節到低位字節排列
	void SetBit(BYTE* byte, int iBit, BYTE aBit); // 設置byte的第iBit位為aBit
	BYTE GetBit(BYTE byte, int pos); 	// 得到字節byte第pos位的值
	void MovePos(int* piByte, int* piBit, int num);	
	// 將位指針*piByte(字節偏移), *piBit(字節內位偏移)后移num
	int UpperLog2(int n);	// 取log2(n)的upper_bound
	int LowerLog2(int n);	// 取log2(n)的upper_bound
};

class CCompressLZ77 : public CCompress
{
public:
	CCompressLZ77();
	virtual ~CCompressLZ77();
public:

	int Compress(BYTE* src, int srclen, BYTE* dest);	// 壓縮一段字節流	
	BOOL Decompress(BYTE* src, int srclen, BYTE* dest);// 解壓縮一段字節流

protected:

	BYTE* pWnd;
	int nWndSize;   // 當前窗口的長度
	struct STIDXNODE
	{
		WORD off;		// 在src中的偏移
		WORD off2;		// 用于對應的2字節串為重復字節的節點
						// 指從 off 到 off2 都對應了該2字節串
		WORD next;		// 在SortHeap中的指針
	};	
	WORD SortTable[65536];  // 256 * 256 指向SortHeap中下標的指針
	struct STIDXNODE* SortHeap;
	int HeapPos;  // 當前分配位置
	int CurByte, CurBit;

protected:

	void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma);	// 輸出壓縮碼
	BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len);
	// 在滑動窗口中查找術語
	inline int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset);
	// 得到已經匹配了3個字節的窗口位置offset
	inline void _ScrollWindow(int n);
	inline void _InsertIndexItem(int off);// 向索引中添加一個2字節串
	void _InitSortTable();// 初始化索引表，釋放上次壓縮用的空間

};

/**************************************************************************/

void main(int argc, char* argv[])
{	
	if (argc != 4)
	{
		printf("%d  ",argc);
		puts("Usage: ");
		printf("    Compress : %s c sourcefile destfile\n", argv[0]);
		printf("  Decompress : %s d sourcefile destfile\n", argv[0]);
		return;
	}

	BYTE soubuf[65536];
	BYTE destbuf[65536 + 16];

	FILE* in;
	FILE* out;
	in = fopen(argv[2], "rb");
	if (in == NULL)
	{
		puts("Can't open source file");
		return;
	}
	out = fopen(argv[3], "wb");
	if (out == NULL)
	{
		puts("Can't open dest file");
		fclose(in);
		return;
	}
	fseek(in, 0, SEEK_END);
	long soulen = ftell(in);
	fseek(in, 0, SEEK_SET);

	CCompressLZ77 cc;
	WORD flag1, flag2;
	
	if (argv[1][0] == 'c') // compress
	{
		int last = soulen, act;
		while ( last > 0 )
		{
			act = min(65536, last);
			fread(soubuf, act, 1, in);
			last -= act;
			if (act == 65536)			// out 65536 bytes				
				flag1 = 0;		
			else					// out last blocks
				flag1 = act;
			fwrite(&flag1, sizeof(WORD), 1, out);

			int destlen = cc.Compress((BYTE*)soubuf, act, (BYTE*)destbuf);
			if (destlen == 0)		// can't compress the block
			{
				flag2 = flag1;
				fwrite(&flag2, sizeof(WORD), 1, out);
				fwrite(soubuf, act, 1, out);
			}
			else
			{
				flag2 = (WORD)destlen;
				fwrite(&flag2, sizeof(WORD), 1, out);				
				fwrite(destbuf, destlen, 1, out);				
			}
		}
	}
	else if (argv[1][0] == 'd') // decompress
	{
		int last = soulen, act;
		while (last > 0)
		{
			fread(&flag1, sizeof(WORD), 1, in);
			fread(&flag2, sizeof(WORD), 1, in);
			last -= 2 * sizeof(WORD);
			if (flag1 == 0)
				act = 65536;
			else
				act = flag1;
			last-= flag2 ? (flag2) : act;

			if (flag2 == flag1)
			{
				fread(soubuf, act, 1, in);				
			}
			else
			{
				fread(destbuf, flag2, 1, in);
				if (!cc.Decompress((BYTE*)soubuf, act, (BYTE*)destbuf))
				{
					puts("Decompress error");
					fclose(in);
					fclose(out);
					return;
				}
			}
			fwrite((BYTE*)soubuf, act, 1, out);				
		}
	}
	else
	{
		puts("Usage: ");
		printf("    Compress : %s c sourcefile destfile\n", argv[0]);
		printf("  Decompress : %s d sourcefile destfile\n", argv[0]);		
	}

	fclose(in);
	fclose(out);
}

/********************************************************************/

// 取log2(n)的upper_bound
int CCompress::UpperLog2(int n)
{
	int i = 0;
	if (n > 0)
	{
		int m = 1;
		while(1)
		{
			if (m >= n)
				return i;
			m <<= 1;
			i++;
		}
	}
	else 
		return -1;
}


// 取log2(n)的lower_bound
int CCompress::LowerLog2(int n)
{
	int i = 0;
	if (n > 0)
	{
		int m = 1;
		while(1)
		{
			if (m == n)
				return i;
			if (m > n)
				return i - 1;
			m <<= 1;
			i++;
		}
	}
	else 
		return -1;
}

// 將位指針*piByte(字節偏移), *piBit(字節內位偏移)后移num位
void CCompress::MovePos(int* piByte, int* piBit, int num)
{
	num += (*piBit);
	(*piByte) += num / 8;
	(*piBit) = num % 8;
}

// 得到字節byte第pos位的值
//		pos順序為高位起從0記數（左起）
BYTE CCompress::GetBit(BYTE byte, int pos)
{
	int j = 1;
	j <<= 7 - pos;
	if (byte & j)
		return 1;
	else 
		return 0;
}

// 設置byte的第iBit位為aBit
//		iBit順序為高位起從0記數（左起）
void CCompress::SetBit(BYTE* byte, int iBit, BYTE aBit)
{
	if (aBit)
		(*byte) |= (1 << (7 - iBit));
	else
		(*byte) &= ~(1 << (7 - iBit));
}

// 將DWORD值從高位字節到低位字節排列
void CCompress::InvertDWord(DWORD* pDW)
{
	union UDWORD{ DWORD dw; BYTE b[4]; };
	UDWORD* pUDW = (UDWORD*)pDW;
	BYTE b;
	b = pUDW->b[0];	pUDW->b[0] = pUDW->b[3]; pUDW->b[3] = b;
	b = pUDW->b[1];	pUDW->b[1] = pUDW->b[2]; pUDW->b[2] = b;
}

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

	int nBitsToFill, nBitsCanFill;

	while (nBits > 0)
	{
		// 計算要在目標區當前字節填充的位數
		nBitsToFill = min(nBits, iByteDest ? 8 : 8 - nDestPos);
		// 目標區當前字節要填充的起始位
		iBitDest = iByteDest ? 0 : nDestPos;
		// 計算可以一次從源數據區中復制的位數
		nBitsCanFill = min(nBitsToFill, 8 - iBitSrc);
		// 字節內復制
		CopyBitsInAByte(memDest + iByteDest, iBitDest, 
			memSrc + iByteSrc, iBitSrc, nBitsCanFill);		
		// 如果還沒有復制完 nBitsToFill 個
		if (nBitsToFill > nBitsCanFill)
		{
			iByteSrc++; iBitSrc = 0; iBitDest += nBitsCanFill;
			CopyBitsInAByte(memDest + iByteDest, iBitDest, 
					memSrc + iByteSrc, iBitSrc, 
					nBitsToFill - nBitsCanFill);
			iBitSrc += nBitsToFill - nBitsCanFill;
		}
		else 
		{
			iBitSrc += nBitsCanFill;
			if (iBitSrc >= 8)
			{
				iByteSrc++; iBitSrc = 0;
			}
		}

		nBits -= nBitsToFill;	// 已經填充了nBitsToFill位
		iByteDest++;
	}	
}

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