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

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

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

　　1.1 LZO壓縮算法壓縮原理

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

　　1.2 LZO壓縮算法編碼

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

　　2 LZO壓縮算法硬件設計與加速方案

　　2.1 LZO壓縮算法硬件結構

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