基于FPGA的LZO實(shí)時(shí)無(wú)損壓縮的硬件設(shè)計(jì)

　　本文通過(guò)對(duì)多種壓縮算法作進(jìn)一步研究對(duì)比后發(fā)現(xiàn)，LZO壓縮算法是一種被稱為實(shí)時(shí)無(wú)損壓縮的算法，LZO壓縮算法在保證實(shí)時(shí)壓縮速率的優(yōu)點(diǎn)的同時(shí)提供適中的壓縮率。如圖1(A)給出了Linux操作系統(tǒng)下常見(jiàn)開(kāi)源壓縮算法的壓縮速率的測(cè)試結(jié)果，LZO壓縮算法速率極快;如圖1(B)給出了Gzip壓縮算法和LZO壓縮算法的壓縮率測(cè)試結(jié)構(gòu)，從圖中可以看出，LZO壓縮算法可以提供平均約50%的壓縮率。

　　1 LZO壓縮算法基本原理分析

　　1.1 LZO壓縮算法壓縮原理

　　LZO壓縮算法采用(重復(fù)長(zhǎng)度L，指回距離D)代替當(dāng)前已經(jīng)在歷史字符串中出現(xiàn)過(guò)的字符串，其中，重復(fù)長(zhǎng)度是指，后出現(xiàn)的字符串與先出現(xiàn)的字符串中連續(xù)相同部分的長(zhǎng)度;指回距離是指，先后兩個(gè)相同字符串之間相隔的距離(每個(gè)字節(jié)為一個(gè)單位);如果沒(méi)出現(xiàn)過(guò)(定義為新字符)，則首先輸出新字符的個(gè)數(shù)，再輸出新字符。例如，待處理的字符串為“ABCDEFGHABCDEFJKLM”，壓縮算法逐個(gè)處理字符，處理ABCDEFGH時(shí)沒(méi)發(fā)現(xiàn)重復(fù)字符;處理到ABCDEF時(shí)發(fā)現(xiàn)這些字符在歷史字符串中已經(jīng)出現(xiàn)過(guò)，計(jì)算重復(fù)長(zhǎng)度為6，指回距離(當(dāng)前A離歷史A的距離)為8，則用(6,8)代替ABCDEF;處理到JKLM時(shí)沒(méi)發(fā)現(xiàn)重復(fù)字符，字符串到此處理完畢，則整個(gè)字符串被壓縮成：(08)h ABCDEFGH(6,8)(04)h JKLM，其中h表示16進(jìn)制。

　　1.2 LZO壓縮算法編碼

　　LZO壓縮后的數(shù)據(jù)需要經(jīng)過(guò)特定的格式進(jìn)行編碼，如圖2所示， LZO壓縮算法這樣做的目的有兩方面：調(diào)整LZO壓縮率，使得LZO適合壓縮重復(fù)長(zhǎng)度短，但指回距離較長(zhǎng)的數(shù)據(jù);使得解壓縮過(guò)程更加簡(jiǎn)單，解壓縮速度更快，且不需要額外的內(nèi)存。

　　2 LZO壓縮算法硬件設(shè)計(jì)與加速方案

　　2.1 LZO壓縮算法硬件結(jié)構(gòu)

　　如圖3(A)給出了一種LZO壓縮算法的硬件結(jié)構(gòu)，其中輸入緩存模塊：用于緩存DMA傳輸?shù)拇龎嚎s數(shù)據(jù)，為高速緩存模塊提供數(shù)據(jù)源用以進(jìn)行壓縮操作;高速緩存模塊：臨時(shí)緩存待壓縮數(shù)據(jù)，為LZSS壓縮模塊提供待壓縮數(shù)據(jù)，初始化時(shí)提前寫入一定量的數(shù)據(jù);LZSS模塊：對(duì)待壓縮數(shù)據(jù)進(jìn)行壓縮處理;字典模塊：存儲(chǔ)壓縮過(guò)程中產(chǎn)生的壓縮信息，例如歷史字符串的索引信息，這樣便可為后續(xù)數(shù)據(jù)壓縮提供歷史字符串信息;LZO編碼模塊：對(duì)LZSS壓縮后的數(shù)據(jù)按照LZO編碼格式進(jìn)行編碼，并將編碼數(shù)據(jù)組包成固定長(zhǎng)度的數(shù)據(jù)包，方便總線通訊;輸出緩存模塊：緩存編碼后的數(shù)據(jù)，為DMA讀操作提供壓縮后的數(shù)據(jù)源;Avalon總線接口：按照Avalon總線規(guī)范對(duì)LZO壓縮算法模塊進(jìn)行封裝，為后續(xù)集成SOPC提供準(zhǔn)備。