lz77.cpp

LZ77压缩算法的VC++实现。多媒体课程设计

#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,