複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/LZO/3828255
複製
複製成功

LZO

鎖定
LZO 是致力於解壓速度的一種數據壓縮算法，LZO 是 Lempel-Ziv-Oberhumer 的縮寫。這個算法是無損算法，參考實現程序是線程安全的。 實現它的一個自由軟件工具是lzop。最初的庫是用 ANSI C 編寫、並且遵從 GNU通用公共許可證發佈的。LZO 有用於 Perl、Python 以及 Java 的各種版本。代碼版權的所有者是 Markus F. X. J. Oberhumer。
外文名
LZO
致力於
解壓速度
類    別
數據壓縮算法，
全    稱
Lempel-Ziv-Oberhumer

目錄

  1. 1 產品特點
  2. 2 C語言壓縮算法
  3. 3 C語言解壓縮算法

LZO產品特點

LZO 庫實現了許多有下述特點的算法：
* 解壓簡單，速度非常快。
* 解壓不需要內存。
* 壓縮相當地快。
* 壓縮需要 64 kB 的內存。
* 允許在壓縮部分以損失壓縮速度為代價提高壓縮率，解壓速度不會降低。
* 包括生成預先壓縮數據的壓縮級別，這樣可以得到相當有競爭力的壓縮比。
* 另外還有一個只需要 8 kB 內存的壓縮級別。
* 算法是線程安全的。
* 算法是無損的。
LZO 支持重複壓縮以及原地解壓。
LZO 是塊壓縮算法——壓縮解壓成塊的數據。壓縮與解壓所用塊的大小必須一樣。
LZO 將數據塊壓縮成匹配數據（滑動字典）與非匹配文字的序列。LZO 對於較長的匹配數據以及較長的非匹配文字序列有專門的處理，這樣對於高度冗餘的數據能夠取得很好的效果，並且對於不可壓縮的數據也能得到可以接受的效果。
當處理不可壓縮數據的時候，LZO 將每個 1024 字節的輸入數據塊擴展 16 字節。
據報道 LZO 也在 AIX、 ConvexOS、IRIX、Mac OS、Palm OS、 PS1（PlayStation）、Solaris、SunOS、TOS (Atari ST) 以及 VxWorks 上得到實現。

LZOC語言壓縮算法

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 - 2));
goto m3_m4_offset;
}
else // 回指長度大於16時
{
m_off -= 0x4000;
*op++ = (byte)(16 | ((m_off & 0x4000) ＞＞ 11) | (m_len - 2));
goto m3_m4_offset;
}
}
else // 重複長度大於8時
{
{
byte *end = in_end;
byte *m = m_pos + 9; // 從m_pos[9]開始比較
while (ip ＜ end && *m == *ip)
m++, ip++;
m_len = (ip - ii);
}
if(m_off ＜= 0x4000) // 回指長度小於16kb
{
--m_off;
if (m_len ＜= 33) // 可用5bit表示時
*op++ = (byte)(32 | (m_len - 2));
else
{
m_len -= 33;
*op++ = 32;
goto m3_m4_len;
}
}
else // 回指長度大於16kb ,小於48 kb
{
m_off -= 0x4000;
if(m_len ＜= 9)
*op++ = (byte)(16|((m_off & 0x4000) ＞＞ 11) | (m_len - 2));
else
{
m_len -= 9;
*op++ = (byte)(16 | ((m_off & 0x4000) ＞＞ 11));
m3_m4_len:
while (m_len ＞ 255)
{
m_len -= 255;
*op++ = 0;
}
*op++ = (byte)m_len;
}
}
m3_m4_offset:
*op++ = (byte)((m_off & 63) ＜＜ 2);
*op++ = (byte)(m_off ＞＞ 6);
}
ii = ip; // 下次匹配的開始位置
if (ip ＞= ip_end)
break;
}
*out_len = op - out;
return (unsigned) (in_end - ii);
}

LZOC語言解壓縮算法

int _stdcall compress(byte *in, unsigned in_len, byte *out)
{
byte *op = out;
unsigned t,out_len;
if (in_len ＜= 13)
t = in_len;
else
{
t = _do_compress (in,in_len,op,&out_len);
op += out_len;
}
if (t ＞ 0) // t: 未編碼的字符大小,即新字符的數目
{
byte *ii = (byte*)in + in_len - t; // 未編碼的開始地址
if (op == (byte*)out && t ＜= 238)
*op++ = (byte) ( 17 + t );
else
if (t ＜= 3) // 新字符數目＜3時
op[-2] |= (byte)t ;
else
if (t ＜= 18) // 新字符數目＜18 時
*op++ = (byte)(t-3);
else
{
unsigned tt = t - 18;
*op++ = 0;
while (tt ＞ 255)
{
tt -= 255;
*op++ = 0;
}
*op++ = (byte)tt;
}
do
{
*op++ = *ii++;
}while (--t ＞ 0); // 輸出t個新字符
}
*op++ = 17; // 結束編碼標誌
*op++ = 0;
*op++ = 0;
return (op - (byte*)out); // 返回編碼後的長度
}
int _stdcall decompress(byte *in, unsigned in_len, byte *out)
{
register byte *op; // 輸出臨時緩存區
register byte *ip;
register unsigned t;
register byte *m_pos;
byte *ip_end = (byte*)in + in_len;
op = out;
ip = in;
if(*ip ＞ 17)
{
t = *ip++ - 17;
if (t ＜ 4)
goto match_next;
do *op++ = *ip++; while (--t ＞ 0);
goto first_literal_run;
}
for(;;)
{
t = *ip++; // 得到新字符的數目(t+3)
if (t ＞= 16) // 新字符數目(t+3) ＞ 18時
goto match;
if (t == 0) // 新字符數目大於18時
{
while (*ip == 0)
{
t += 255;
ip++;
}
t += 15 + *ip++; // 得到具體新字符數目大小(t+3)
}
// 獲取t新字符,每次以4個為單位
* (unsigned *) op = * ( unsigned *) ip; // 獲取sizeof(unsigned)個新字符
op += 4;
ip += 4;
if (--t ＞ 0) // 新字符數目:t+4-1 = t + 3,已處理了4個
{
if (t ＞= 4)
{
do
{
// 獲取sizeof(unsigned)個新字符,即4個,以4個為單位
* (unsigned * ) op = * ( unsigned * ) ip;
op += 4;
ip += 4;
t -= 4;
} while (t ＞= 4);
if (t ＞ 0) // 不足一個單位時,且t＞0
{
do
{
*op++ = *ip++;
}while (--t ＞ 0);
}
}
else
{
do
{
*op++ = *ip++;
}while (--t ＞ 0);
}
}
first_literal_run:
t = *ip++; // 判斷是否是重複字符編碼
if (t ＞= 16) // 是重複字符編碼
goto match;
m_pos = op - 0x0801;
m_pos -= t ＞＞ 2;
m_pos -= *ip++ ＜＜ 2;
*op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
goto match_done;
for(;;)
{
match:
// 根據第一單元組來判斷其解壓種類
if (t ＞= 64) // 回指長度小於2Kb
{
// int match_len = (*ip++ ＜＜ 3) | ((t ＞＞ 2) & 7) + 1;
// m_pos= op -match_len; //得到匹配位置
m_pos = op - 1; //
m_pos -= (t ＞＞ 2) & 7; // 得到第一個位元組的distance
m_pos -= *ip++ ＜＜ 3; //得到匹配位置
t = (t ＞＞ 5) - 1; // 得到第一個位元組的len - 1
goto copy_match;
}
else if (t ＞= 32) // 回指長度大於2Kb ＜ 16kb
{
t &= 31;
if (t == 0)
{
while (*ip == 0)
{
t += 255;
ip++;
}
t += 31 + *ip++;
}
m_pos = op - 1;
m_pos -= (* ( unsigned short * ) ip) ＞＞ 2;
ip += 2;
}
else if (t ＞= 16) // 回指長度大於16 Kb,或者結束標誌
{
m_pos = op;
m_pos -= (t & 8) ＜＜ 11; // 獲得第一個單元組的distance
t &= 7; // 獲取第一個單元組的len
if (t == 0)
{
while (*ip == 0)
{
t += 255;
ip++;
}
t += 7 + *ip++;
}
m_pos -= (* ( unsigned short *) ip) ＞＞ 2;
ip += 2;
if (m_pos == op) // 判斷是否為結束標誌
goto eof_found;
m_pos -= 0x4000;
}
else
{
m_pos = op - 1;
m_pos -= t ＞＞ 2;
m_pos -= *ip++ ＜＜ 2;
*op++ = *m_pos++; *op++ = *m_pos;
goto match_done;
}
if (t ＞= 6 && (op - m_pos) ＞= 4)
{
* (unsigned *) op = * ( unsigned *) m_pos;
op += 4;
m_pos += 4;
t -= 2;
do
{
* (unsigned *) op = * ( unsigned *) m_pos;
op += 4;
m_pos += 4;
t -= 4;
}while (t ＞= 4);
if (t ＞ 0)
do
{
*op++ = *m_pos++;
}while (--t ＞ 0);
}
else
{
copy_match:
*op++ = *m_pos++; // 獲得前兩個匹配字符
*op++ = *m_pos++;
do
{
*op++ = *m_pos++;
}while (--t ＞ 0); // 獲得剩餘的匹配字符
}
match_done:
t = ip[-2] & 3; // 獲取保留位,當新字符數目＜=3時
if (t == 0) // 保留位未使用時,即新字符數目＞3
break;
match_next:
do
{
*op++ = *ip++;
}while (--t ＞ 0);
t = *ip++; // 下一個匹配單元
}
}
eof_found:
if (ip != ip_end)
return -1;
return (op - (byte*)out); // 返回解碼後的長度
}