lz77.h

lz77算法原代码

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

// 使用在自己的堆中分配索引节点，不滑动窗口
// 每次最多压缩 MAXSIZEBYTE字节数据
// 的优化版本

#ifndef _WIX_LZ77_COMPRESS_HEADER_001_
#define _WIX_LZ77_COMPRESS_HEADER_001_

// 滑动窗口的字节大小
const UINT  MAXSIZEBYTE = 1024;

#define min(a,b) (((a) < (b)) ? (a) : (b))


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

	void CopyBitsInAByte(BYTE* memDest, UINT nDestPos,
				  BYTE* memSrc, UINT nSrcPos, UINT nBits);

	void CopyBits(BYTE* memDest, UINT nDestPos,
				  BYTE* memSrc, UINT nSrcPos, UINT nBits);

	//////////////////////////////////////////////////////////////
	// 将DWORD值从高位字节到低位字节排列
	void InvertDWord(DWORD* pDW);

	/////////////////////////////////////////////////////////////
	// 设置byte的第iBit位为aBit
	//		iBit顺序为高位起从0记数（左起）
	void SetBit(BYTE* byte, UINT iBit, BYTE aBit);

	////////////////////////////////////////////////////////////
	// 得到字节byte第pos位的值
	//		pos顺序为高位起从0记数（左起）
	BYTE GetBit(BYTE byte, UINT pos);

	////////////////////////////////////////////////////////////
	// 将位指针*piByte(字节偏移), *piBit(字节内位偏移)后移num位
	void MovePos(UINT* piByte, UINT* piBit, UINT num);

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

	/////////////////////////////////////////////////////////
	// 取log2(n)的lower_bound
	UINT LowerLog2(UINT n);

};

class CCompressLZ77 : public CCompress
{
public:
	CCompressLZ77(){};
	virtual ~CCompressLZ77(){};
public:
	UINT Compress(BYTE* src, UINT srclen, BYTE* dest);

	BOOL Decompress(BYTE* src, UINT srclen, BYTE* dest);

protected:

	UINT nWndSize;
	BYTE *pWnd;
	BYTE table[MAXSIZEBYTE];
	UINT CurByte, CurBit;

protected:
	void _OutCode(BYTE* dest, DWORD code, UINT bits, BOOL isGamma);

	BOOL _SeekPhase(BYTE* src, UINT srclen, UINT nSeekStart, UINT &offset, UINT &len);

	inline void _ScrollWindow(UINT len);

	inline void _InsertIndexItem(UINT off);

	void _InitSortTable(UINT scrlen);
};



#endif