lz.cpp

使用LZ77算法压缩文件的C代码

			iBitSrc += nBitsToFill - nBitsCanFill;
		}
		else 
		{
			iBitSrc += nBitsCanFill;
			if (iBitSrc >= 8)
			{
				iByteSrc++; iBitSrc = 0;
			}
		}

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



// 初始化索引表，释放上次压缩用的空间
void _InitSortTable()
{
	memset(SortTable, 0, sizeof(WORD) * 65536);
	nWndSize = 0;
	HeapPos = 1;
}

// 向索引中添加一个2字节串
void _InsertIndexItem(int off)
{
	WORD q;
	BYTE ch1, ch2;
	ch1 = pWnd[off]; ch2 = pWnd[off + 1];	
	
	if (ch1 != ch2)
	{
		// 新建节点
		q = HeapPos;
		HeapPos++;
		SortHeap[q].off = off;
		SortHeap[q].next = SortTable[ch1 * 256 + ch2];
		SortTable[ch1 * 256 + ch2] = q;
	}
	else
	{
		// 对重复2字节串
		// 因为没有虚拟偏移也没有删除操作，只要比较第一个节点
		// 是否和 off 相连接即可
		q = SortTable[ch1 * 256 + ch2];
		if (q != 0 && off == SortHeap[q].off2 + 1)
		{		
			// 节点合并
			SortHeap[q].off2 = off;
		}		
		else
		{
			// 新建节点
			q = HeapPos;
			HeapPos++;
			SortHeap[q].off = off;
			SortHeap[q].off2 = off;
			SortHeap[q].next = SortTable[ch1 * 256 + ch2];
			SortTable[ch1 * 256 + ch2] = q;
		}
	}
}

//////////////////////////////////////////
// 将窗口向右滑动n个字节
void _ScrollWindow(int n)
{	
	for (int i = 0; i < n; i++)
	{		
		nWndSize++;		
		if (nWndSize > 1)			
			_InsertIndexItem(nWndSize - 2);
	}
}

///////////////////////////////////////////////////////////
// 得到已经匹配了2个字节的窗口位置offset
// 共能匹配多少个字节
int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset)
{
	int i = 2; // 已经匹配了2个字节
	int maxsame = min(srclen - nSeekStart, nWndSize - offset);
	while (i < maxsame
			&& src[nSeekStart + i] == pWnd[offset + i])
		i++;
	if(!(nSeekStart + i <= srclen && offset + i <= nWndSize))
		return i;
	return	0;
}

///////////////////////////////////////////////////////////
// 在滑动窗口中查找术语
// nSeekStart - 从何处开始匹配
// offset, len - 用于接收结果，表示在滑动窗口内的偏移和长度
// 返回值- 是否查到长度为2或2以上的匹配字节串
BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len)
{	
	int j, m, n;

	if (nSeekStart < srclen - 1)
	{
		BYTE ch1, ch2;
		ch1 = src[nSeekStart]; ch2 = src[nSeekStart + 1];
		WORD p;
		p = SortTable[ch1 * 256 + ch2];
		if (p != 0)
		{
			m = 2; n = SortHeap[p].off;
			while (p != 0)
			{
				j = _GetSameLen(src, srclen, 
					nSeekStart, SortHeap[p].off);
				if ( j > m )
				{ 
					m = j; 
					n = SortHeap[p].off;
				}			
				p = SortHeap[p].next;
			}	
			(*offset) = n; 
			(*len) = m;
			return TRUE;		
		}	
	}
	return FALSE;
}

////////////////////////////////////////
// 输出压缩码
// code - 要输出的数
// bits - 要输出的位数(对isGamma=TRUE时无效)
// isGamma - 是否输出为γ编码
void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma)
{	
	if ( isGamma )
	{
		BYTE* pb;
		DWORD out;
		// 计算输出位数
		int GammaCode = (int)code - 1;
		int q = LowerLog2(GammaCode);
		if (q > 0)
		{
			out = 0xffff;
			pb = (BYTE*)&out;
			// 输出q个1
			CopyBits(dest + CurByte, CurBit, 
				pb, 0, q);
			MovePos(&CurByte, &CurBit, q);
		}
		// 输出一个0
		out = 0;
		pb = (BYTE*)&out;		
		CopyBits(dest + CurByte, CurBit, pb + 3, 7, 1);
		MovePos(&CurByte, &CurBit, 1);
		if (q > 0)
		{
			// 输出余数, q位
			int sh = 1;
			sh <<= q;
			out = GammaCode - sh;
			pb = (BYTE*)&out;
			InvertDWord(&out);
			CopyBits(dest + CurByte, CurBit, 
				pb + (32 - q) / 8, (32 - q) % 8, q);
			MovePos(&CurByte, &CurBit, q);
		}
	}
	else 
	{
		DWORD dw = (DWORD)code;
		BYTE* pb = (BYTE*)&dw;
		InvertDWord(&dw);
		CopyBits(dest + CurByte, CurBit, 
				pb + (32 - bits) / 8, (32 - bits) % 8, bits);
		MovePos(&CurByte, &CurBit, bits);
	}
}




/////////////////////////////////////////////
// 压缩一段字节流
// src - 源数据区
// srclen - 源数据区字节长度
// dest - 压缩数据区，调用前分配srclen+5字节内存
// 返回值 > 0 压缩数据长度
// 返回值 = 0 数据无法压缩
// 返回值 < 0 压缩中异常错误
int compress(BYTE* src, int srclen, BYTE* dest)
{
	

	
	int i;

	int off, len;
	CurByte = 0; 
	CurBit = 0;	
	if (srclen > 65536) 
		return -1;

	pWnd = src;
	_InitSortTable();
	for (i = 0; i < srclen; i++)
	{		
		if (CurByte >= srclen)
			return 0;
		if (_SeekPhase(src, srclen, i, &off, &len))
		{			
			// 输出匹配术语 flag(1bit) + len(γ编码) + offset(最大16bit)
			_OutCode(dest, 1, 1, FALSE);
			_OutCode(dest, len, 0, TRUE);

			// 在窗口不满64k大小时，不需要16位存储偏移
			_OutCode(dest, off, UpperLog2(nWndSize), FALSE);
						
			_ScrollWindow(len);
			i += len - 1;
		}
		else
		{
			// 输出单个非匹配字符 0(1bit) + char(8bit)
			_OutCode(dest, 0, 1, FALSE);
			_OutCode(dest, (DWORD)(src[i]), 8, FALSE);
			_ScrollWindow(1);
		}
	}
	int destlen = CurByte + ((CurBit) ? 1 : 0);
	if (destlen >= srclen)
		return 0;
	return destlen;
}

/////////////////////////////////////////////
// 解压缩一段字节流
// src - 接收原始数据的内存区
// srclen - 源数据区字节长度
// dest - 压缩数据区
// 返回值 - 成功与否
BOOL decompress(BYTE* src, int srclen, BYTE* dest)
{
	int i;
	CurByte = 0; CurBit = 0;
	pWnd = src;		// 初始化窗口
	nWndSize = 0;

	if (srclen > 65536) 
		return FALSE;
	
	for (i = 0; i < srclen; i++)
	{		
		BYTE b = GetBit(dest[CurByte], CurBit);
		MovePos(&CurByte, &CurBit, 1);
		if (b == 0) // 单个字符
		{
			CopyBits(src + i, 0, dest + CurByte, CurBit, 8);
			MovePos(&CurByte, &CurBit, 8);
			nWndSize++;
		}
		else		// 窗口内的术语
		{
			int q = -1;
			while (b != 0)
			{
				q++;
				b = GetBit(dest[CurByte], CurBit);
				MovePos(&CurByte, &CurBit, 1);				
			}
			int len, off;
			DWORD dw = 0;
			BYTE* pb;
			if (q > 0)
			{				
				pb = (BYTE*)&dw;
				CopyBits(pb + (32 - q) / 8, (32 - q) % 8, dest + CurByte, CurBit, q);
				MovePos(&CurByte, &CurBit, q);
				InvertDWord(&dw);
				len = 1;
				len <<= q;
				len += dw;
				len += 1;
			}
			else
				len = 2;

			// 在窗口不满64k大小时，不需要16位存储偏移
			dw = 0;
			pb = (BYTE*)&dw;
			int bits = UpperLog2(nWndSize);
			CopyBits(pb + (32 - bits) / 8, (32 - bits) % 8, dest + CurByte, CurBit, bits);
			MovePos(&CurByte, &CurBit, bits);
			InvertDWord(&dw);
			off = (int)dw;
			// 输出术语
			for (int j = 0; j < len; j++)
			{
				if((i + j <  srclen)&&(off + j <  _MAX_WINDOW_SIZE))
					src[i + j] = pWnd[off + j];
			}
			nWndSize += len;
			i += len - 1;
		}
		// 滑动窗口
		if (nWndSize > _MAX_WINDOW_SIZE)
		{
			pWnd += nWndSize - _MAX_WINDOW_SIZE;
			nWndSize = _MAX_WINDOW_SIZE;			
		}
	}

	return TRUE;
}