LZO代码及实现原理详解

LZO实现原理详解，通过举例使你更加容易理解.比较与lz77、lzw等算法的优缺点，最后对lzo优化。

#include 
#include 
#include 
typedef unsigned char byte;
int _stdcall compress（byte *src unsigned src_len byte *dst）;
int _stdcall decompress（byte *src  unsigned src_len	byte *dst）;

// 新字符（<18）: -3匹配长度-1匹配位置-1保留位:新字符数
// 新字符（>18）:-18
// 开始查找，如果没有匹配字符时，记录其位置
// 直到找到匹配字符，开始输出记录的新字符
// 然后 计算出匹配字符的长度与位置，
// 并根据其区间输出其位置
static unsigned _do_compress （byte *in unsigned in_len byte *out unsigned *out_len）
{
	static long wrkmem [16384L];
	register byte *ip;
	byte *op;
	byte *in_end = in + in_len;
	byte *ip_end = in + in_len -3;
	byte *ii;			// 指向开始编码的位置
	byte **dict = （byte **）wrkmem;
	op = out;
	ip = in;
	ii = ip;
	ip += 4;
        for（;;）
	{
		register byte *m_pos;
		unsigned m_off;
		unsigned m_len;
		unsigned dindex;	// hashkey（ip[0] ip[1] ip[2] ip[3]）
		dindex = （（0x21*（（（（（（（unsigned）（ip[3]）<<6）^ip[2]）<<5）^ip[1]）<<5）^ip[0]））>>5） & 0x3fff;
		m_pos = dict [dindex];
		if（（（unsigned）m_pos < （unsigned）in） ||
			（m_off = （unsigned）（（unsigned）ip-（unsigned）m_pos） ） <= 0 ||
			m_off > 0xbfff）						// 0xc000 48kb
			goto literal;
		if（m_off <= 0x0800 || m_pos[3] == ip[3]）		// 回指长度小于2Kb
			goto try_match;

		
		dindex = （dindex & 0x7ff ） ^ 0x201f;		// 处理冲突第二次hash
		m_pos = dict[dindex];
		if（（unsigned）（m_pos） < （unsigned）（in） ||
			（m_off = （unsigned）（ （int）（（unsigned）ip-（unsigned）m_pos））） <= 0 ||
			m_off > 0xbfff）
		    goto literal;
		if （m_off <= 0x0800 || m_pos[3] == ip[3]） // 回指长度小于2Kb
			goto try_match;					// 第三个字节相等
		goto literal;

		
try_match:	// m_pos[0]m_pos[1]m_pos[2]都匹配成功时继续比较
		if（*（unsigned short*）m_pos == *（unsigned short*）ip && m_pos[2]== ip[2]）
			goto match;
		
literal:		// 匹配不成功时或者无记录
		dict[dindex] = ip;	// 记录字符串为ip[0]ip[1]ip[2]ip[3]的地址
		++ip;
		if （ip >= ip_end）
			break;
		continue;
match:	// 在得到匹配长度与位置之前先输出未匹配的字符
		dict[dindex] = ip;	// 更新，字符匹配时的位置（未编码）
		if（ip - ii > 0）		// 存在新字符
		{
			register unsigned t = ip - ii;		// t:新字符的数目（未匹配的）
			
			if （t <= 3）					// 新字符数目<3时
				op[-2] |= （byte）t;			// 对两个保留字元赋值
			else if（t <= 18）			// 新字符数目<18时
				*op++ = （byte）（t - 3）;
			else
			{
				register unsigned tt = t - 18;
				*op++ = 0;
				while（tt > 255）	// 构建新位元组
				{
					tt -= 255;
					*op++ = 0;
				}
				*op++ = （byte）tt;
			}
			do
			{	
				*op++ = *ii++; 		// ii指向开始匹配的位置（未编码）
			}while （--t > 0）;		// 输出 t个新字符
		}
		ip += 3;			// 跳过与m_pos[0]  m_pos[1] m_pos[2]的比较
		if（m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
			m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ ）
		{
			--ip;
			m_len = ip - ii;			// 得到重复长度<=8
			
			if（m_off <= 0x0800 ）		//  回指长度小于2kb
			{
				--m_off;		// m_off与m_len在输出时都减1
				//	m_off在第一位元组（byte）占三位m_off&7 小于8
				*op++ = （byte）（（（m_len - 1） << 5） | （（m_off & 7） << 2））;
				*op++ = （byte）（m_off >> 3）;	// 去除已用的低3位
			}
			else
				if （m_off <= 0x4000 ）	// 回指长度小于16kb
				{
					-- m_off;
					*op++ = （byte）（32 | （m_len 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       9645  2009-06-17 09:25  lzo.cpp

     文件    2473803  2009-06-15 09:15  lzo.pdf

----------- ---------  ---------- -----  ----

              2483448                    2