lz77.cpp

lz77算法原代码

#include <windows.h>
#include <conio.h>
#include <stdio.h>
#include <assert.h>
#include <memory.h>
#include <iostream.h>

#include "lz77.h"


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

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

////////////////////////////////////////////////////////////
// 将位指针*piBYTE(字节偏移), *piBit(字节内位偏移)后移num位
void CCompress::MovePos(UINT* piBYTE, UINT* piBit, UINT num)
{
	num += (*piBit);
	(*piBYTE) += num / 8;
	(*piBit) = num % 8;
}
// MovePos
////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////
// 得到字节BYTE第pos位的值
//		pos顺序为高位起从0记数（左起）
BYTE CCompress::GetBit(BYTE BYTE, UINT pos)
{
	UINT j = 1;
	j <<= 7 - pos;
	if (BYTE & j)
		return 1;
	else 
		return 0;
}
// GetBit
/////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////
// 设置BYTE的第iBit位为aBit
//		iBit顺序为高位起从0记数（左起）
void CCompress::SetBit(BYTE* B, UINT iBit, BYTE aBit)
{
	if (aBit)
		(*B) |= (1 << (7 - iBit));
	else
		(*B) &= ~(1 << (7 - iBit));
}
// SetBit
//////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////
// 将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;
}


void CCompress::CopyBitsInAByte(BYTE* memDest, UINT nDestPos,
			BYTE* memSrc, UINT nSrcPos, UINT nBits)
{
	BYTE b1, b2;
	b1 = *memSrc;
	b1 <<= nSrcPos; b1 >>= 8 - nBits;	// 将不用复制的位清0
	b1 <<= 8 - nBits - nDestPos;		// 将源和目的字节对齐
	*memDest |= b1;		// 复制值为1的位
	b2 = 0xff; b2 <<= 8 - nDestPos;		// 将不用复制的位置1
	b1 |= b2;
	b2 = 0xff; b2 >>= nDestPos + nBits;
	b1 |= b2;
	*memDest &= b1;		// 复制值为0的位
}



void CCompress::CopyBits(BYTE* memDest, UINT nDestPos, 
			  BYTE* memSrc, UINT nSrcPos, UINT nBits)
{
	UINT iByteDest = 0, iBitDest;
	UINT iByteSrc = 0, iBitSrc = nSrcPos;

	UINT 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++;
	}
}

/////////////////////////////////////////////////////////


//------------------------------------------------------------------



// 初始化索引表，释放上次压缩用的空间
void CCompressLZ77::_InitSortTable(UINT srclen)
{
	
	memset(table,0,sizeof(table[0])*srclen+1);
	nWndSize = 0;

}


//////////////////////////////////////////
// 将窗口向右滑动n个字节
void CCompressLZ77::_ScrollWindow(UINT len)
{
	for(UINT i=0;i<len;i++)
	{
		table[nWndSize]=pWnd[nWndSize];
		nWndSize++;
	}
}


///////////////////////////////////////////////////////////
// 在滑动窗口中查找术语
// nSeekStart - 从何处开始匹配
// offset, len - 用于接收结果，表示在滑动窗口内的偏移和长度
// 返回值- 是否查到长度为2或2以上的匹配字节串
BOOL CCompressLZ77::_SeekPhase(BYTE* src, UINT srclen, UINT nSeekStart, UINT &offset, UINT &len)
{	
	if (nSeekStart < srclen - 1)
	{
		UINT maxLen=0;
		UINT maxOffset=0;
		if(nWndSize<2)
		{
			return 0;
		}
		for(UINT i=0;i<nWndSize;)
		{
			len=0;
			// 先在窗口中查找第一个与src[nSeekStart]相同的字符
			for(UINT j = nSeekStart; src[j] != table[i] && i< nWndSize; i++);
			// 如果到了窗口的最后一个字符，匹配工作已完成。
			if(i == nWndSize)		break; 
			offset = i;
			// 开始计算匹配字符串的长度
			for(j = nSeekStart; j< srclen && i<nWndSize && src[j] == table[i]; j++, i++)
				len++ ;
			
			i+= len-1;
			if(maxLen< len) { maxLen = len; maxOffset = offset;}

		}
		if( maxLen <2 )
			return 0;
		else
		{
			len = maxLen;
			offset = maxOffset;
			return 1;
		}

	}
	return FALSE;
}

////////////////////////////////////////
// 输出压缩码
// code - 要输出的数
// bits - 要输出的位数(对isGamma=TRUE时无效)
// isGamma - 是否输出为γ编码
void CCompressLZ77::_OutCode(BYTE* dest, DWORD code, UINT bits, BOOL isGamma)
{
	if ( isGamma )
	{
		BYTE* pb;
		DWORD out;
		// 计算输出位数
		UINT GammaCode = (UINT)code - 1;
		UINT 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位
			UINT 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 压缩中异常错误
UINT CCompressLZ77::Compress(BYTE* src, UINT srclen, BYTE* dest)
{
	UINT i;
	CurByte = 0; CurBit = 0;
	UINT off, len;
	pWnd=src;

	if (srclen > MAXSIZEBYTE)
		return 0;
	memset(dest,0,sizeof(dest));

	_InitSortTable(srclen);
	for (i = 0; i < srclen; i++)
	{
		if (CurByte >= srclen)
			return 0;
		if (_SeekPhase(src, srclen, i, off, len))
		{
			_OutCode(dest, 1, 1, FALSE);
			_OutCode(dest, len, 0, TRUE);

			_OutCode(dest, off, UpperLog2(nWndSize), FALSE);

		     _ScrollWindow(len);
			i += len - 1;
		}
		else
		{
			_OutCode(dest, 0, 1, FALSE);
			_OutCode(dest, (DWORD)(src[i]), 8, FALSE);
		    _ScrollWindow(1);
		}
	}
	UINT destlen = CurByte + ((CurBit) ? 1 : 0);
	if (destlen >= srclen)
		return 0;
	return destlen;
}



/////////////////////////////////////////////
// 解压缩一段字节流
// src - 接收原始数据的内存区
// srclen - 源数据区字节长度
// dest - 压缩数据区
// 返回值 - 成功与否
BOOL CCompressLZ77::Decompress(BYTE* src, UINT srclen, BYTE* dest)
{


	if (srclen > MAXSIZEBYTE)
		return FALSE;
	CurByte = 0; CurBit = 0;
	nWndSize = 0;
	pWnd=src;
	
	for (UINT i = 0; i < srclen; i++)
	{		
		BYTE b = GetBit(dest[CurByte], CurBit);


		MovePos(&CurByte, &CurBit, 1);

		// 标志位b为0时，后面是单个字符
		if (b == 0) 
		{
			CopyBits(src + i, 0, dest + CurByte, CurBit, 8);
			MovePos(&CurByte, &CurBit, 8);
			nWndSize++;
		}
		// 标志位b为1时，开始求q=?即，多少个1?	 q=2:11
		else		
		{
			UINT q = -1;
			while (b != 0)
			{
				q++;
				b = GetBit(dest[CurByte], CurBit);
				MovePos(&CurByte, &CurBit, 1);
			}
			UINT 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);  // dw:len-1
				len = 1;
				len <<= q;
				len += dw;
				len += 1;
			}
			else	// 0个1时
				len = 2;
			dw = 0;
			pb = (BYTE*)&dw;
			UINT bits = UpperLog2(nWndSize);
			CopyBits(pb + (32 - bits) / 8, (32 - bits) % 8, dest + CurByte, CurBit, bits);
			MovePos(&CurByte, &CurBit, bits);
			InvertDWord(&dw);
			off = (UINT)dw;

			for (UINT j = 0; j < len; j++)
			{
				assert(i + j <  srclen);
				assert(off + j < nWndSize);

				src[i + j] = pWnd[off + j];
			}
			nWndSize += len;
			i += len - 1;
		}
	}
	return TRUE;
}

 

// abc			abdabce
//	|			|
// pWnd[off+j]  src[i+j]