LZMA壓縮算法FPGA硬件實現

李冰，張林，劉勇

(1.東南大學 集成電路學院，南京210018;2.東南大學 成賢學院，南京210018)

隨著信息和通信技術的迅猛發展，龐大的數據必須進行有效的壓縮，才能減少數據交換量，最大限度地利用有限的數據傳輸帶寬.無損壓縮要求對壓縮的數據進行重構(解壓縮)后原來的數據完全相同，具有高保真性的無損壓縮被大量應用到服務器和工作站等大數據處理系統中，IBM和百度等公司均對其做過積極研究.LZMA壓縮算法是LZ77壓縮算法的一個改進版本，由Pavlov于1998年發明，目前在7zip壓縮算法中被作為默認的壓縮算法［1-2］.

雖然LZMA能夠提供較高的壓縮率，但處理過程中需要大量的隨機訪問存儲器(RAM，Random Access Memory)，并且會耗費較多CPU資源.對海量數據進行處理時，長時間占用大量CPU資源，使得在執行LZMA數據壓縮的同時進行其他操作變成了難題.

目前一個高性能FPGA中包含了上千個獨立的雙端口RAM塊，一個或多個的內嵌處理器以及海量的可配置資源.盡管這些資源相比CPU的工作頻率要慢很多，但卻可以提供高性能的并行運算，從而使得加速LZMA壓縮算法成為了可能.雖然國內外已有眾多的關于數據無損壓縮加速的電路實現方案，但卻不能在支持高壓縮帶寬的同時，提供很好的壓縮比.本文主要針對LZMA算法的FPGA硬件實現進行了研究，在高速壓縮的同時提供更好的壓縮比例.

1 LZMA算法

LZMA壓縮算法的結構與Deflate算法極其相似［3-4］，只是將其中的Huffman編碼替代成了區間編碼，值得注意的是區間編碼是一種基于整數運算的概率編碼，其壓縮效果十分接近數據的熵值.在LZMA算法中，首先由LZ77壓縮算法在搜索緩存(search buffer)中尋找與前向緩存(look-ahead buffer)中匹配最長的字符串，然后輸出一個關于(DIS，LEN，LIT)的標識.其中，DIS代表了 lookahead buffer中與search buffer中相匹配的兩組數據首個字節之間的距離，最大的值取決于search buffer的大小;LEN代表了最大的匹配長度，通常是一個較小的數值;LIT代表下一個字符，通常是一個ASCII編碼值［5-7］.當LZ77壓縮算法完成對數據的第1次壓縮后，區間編碼根據不同的輸出數據流采用不同的壓縮策略，以便解壓的時候識別［8］.

如圖1所示，是一臺核心為 Core i3-2100 CPU@3.1 GHz，內存為4 GB的工作站全負荷運算時，LZMA-SDK_4.26［9］的數據吞吐測試結果曲線圖，其平均的壓縮速率僅為10～20 Mb/s.

圖1 LZMA軟件算法性能測試圖Fig.1 Performance testing image of software-based LZMA algorithm

在LZMA壓縮中，數據流都是比特形式的，數據流被分成不同種類的數據包，經過區間編碼后變成限定區間內的某一個數據后輸出.如表1所示，在LZMA算法中共有7種數據類型，為了將資源消耗控制在可接受的范圍內，本文限定LZMA壓縮的數據格式僅為前2種.

表1 LZMA文件包數據類型Table1 Data types in LZMA packages

2 硬件設計

根據LZMA的壓縮流程，本文將實現電路劃分為3個部分:LZ77壓縮控制器、區間編碼控制器和數據讀出控制器.

如圖2所示，LZ77壓縮控制器將寫入的數據進行第1次壓縮，并將壓縮后的編碼數據流向后傳輸;區間編碼控制器按照既定壓縮編碼進一步壓縮數據;數據讀出控制器將區間編碼控制器輸出的數據拼接成更合理的數據格式，以適應外部高速總線，并在數據讀出控制器中添加了數據緩沖存儲，保證了外部高速總線的高利用率.

圖2 LZMA硬件電路結構圖Fig.2 Structure image of LZMA hardware circuit

2.1 LZ77壓縮控制器

如圖3所示，LZ77壓縮控制器包括:數據讀入緩存、Hash表存儲模塊和LZ77壓縮算法控制模塊.

數據讀入緩存:采取了乒乓RAM的方式對需要壓縮的數據進行讀取.當一個數據塊中的數據正在被壓縮時，通過握手信號通知外部總線，向另一個數據塊存儲區域中寫入下一個將壓縮的數據信息，通過交替的向數據讀入緩存中寫入數據，保證LZ77壓縮算法控制模塊不需要等待數據，實現不間斷地對數據進行處理.Hash表存儲模塊:存儲已編碼字符的信息.一系列的測試結果［10］表明在搜索深度為4時，LZ77壓縮算法的效率已經達到極限范圍.因此，設計中沒有采用兩個RAM實現多級鏈表(以往的目的是減少資源)，而是使用4個Read-First模式的RAM級聯，這樣可以在同一個讀周期內讀取多個Hash值，減少多次搜索對RAM進行操作的時間，從而達到加速的目的;并且可以根據搜索深度的配置使能相關的RAM.LZ77壓縮算法控制模塊:產生上述兩個模塊的控制信號，對數據流按照LZ77算法進行壓縮.

圖3 LZ77壓縮控制器電路結構Fig.3 Circuit structure of LZ77 compress controller

圖4所示為LZ77壓縮算法控制模塊中狀態機的狀態跳轉圖，在該狀態機中主要包括以下的8個狀態.

圖4 LZ77_FSM狀態跳轉圖Fig.4 State transition image of LZ77_FSM

1)INIT:LZ77壓縮算法控制器進行復位的周期，用于對Hash表存儲模塊進行初始化，該狀態同步輸出區間編碼控制器的初始化信號.

2)WAIT_DMA:LZ77壓縮算法控制模塊等待外部接口信號握手信號，當握手信號有效時進行下一步操作，否則在該狀態下繼續等待.

3)WAIT_SIZE:從總線上讀取數據，用于獲取輸入數據塊的大小.

4)LZ77_BEGIN:根據壓縮的當前位置向look-ahead buffer中填充新字符，并對前3個字節進行Hash變換，根據Hash存儲模塊的返回值區分當前的是新字符還是重復字符串.

5)LZ77_COMPLETE:當壓縮位置等于或者超出了壓縮數據塊大小的時候，則跳轉到該狀態，若此時數據交換接口通知已完成數據壓縮，則跳轉到INIT狀態，否則跳轉到WAIT_SIZE狀態.

6)LAST_BYTE:當前壓縮的位置為最后一個字節，直接進行新字符輸出，并且不對字典進行相關的更新，跳轉到LZ77_COMPLETE狀態.

7)REPEAT:跳轉到該狀態下，表示是一個重復字串，在該狀態下進行字符串的匹配，首先讀取當前指針所在區間的8 B數據，并且按照指針對齊進行匹配，在這個地方有可能只能匹配1 B，而后的過程中從數據讀入緩存中每次讀取8 B的數據(本設計中總線寬度是64，所以設定數據讀入緩存的數據寬度也為64，即8 B)，與 look-ahead buffer中的數據進行比對，并根據比對結果決定是否繼續;在該過程中根據搜索深度進行相應次數的搜索，并在匹配的同時對Hash表存儲模塊中的數據進行更新;當找尋到最佳匹配長度時則生成相應的FLAG_repeat，LEN，DIS信息輸出(信號MATCH_BYTE和PREV_BYTE是區間編碼需要的).

8)NEW:跳轉到該狀態下，表示當前處理的是一個新字符，輸出信號 FLAG_new和 NEW_char;若上次輸出的是重復字串編碼，此時輸出信號 FLAG_new_after_repeat和 NEW_char.

2.2 區間編碼控制器

在LZ77壓縮控制器輸出壓縮的編碼后由區間編碼控制器進一步對數據流進行二次壓縮［11］，如圖5所示為區間編碼控制器的結構圖，其中區間編碼算法控制模塊用于進一步的壓縮和編碼，RANGE_RAM模塊則是用于存儲相關的編碼概率信息，關于 RANGE_RAM區間分配如表2所示.

圖5 區間編碼控制電路結構圖Fig.5 Structure image of range encoder controller circuit

表2 RANGE_RAM中區間分配Table2 Interval distribution in RANGE_RAM

圖6所示是區間編碼算法控制模塊工作的簡要流程圖，各個狀態進行的操作以及狀態間跳轉關系如下所述.

1)CHOOSE:根據緩存中的LZ77編碼選擇進一步編碼的方式，當前指針對應字符是新字符時，則跳轉到LIT_ENC狀態下;當前指針對應字符是新字符，且上一狀態FLAG_repeat信號有效時，則跳轉到 LITMATCHED_ENC狀態下;當FLAG_repeat信號有效時，即當前指針為首地址的字符串為重復字串，則跳轉到LEN_ENC狀態;當所有的編碼結束后則跳轉到FLUSH狀態下.

2)LIT_ENC:對新字符進行壓縮編碼，首先對isMatch進行編碼，進一步的根據litprobs和當前的NEW_cha進行區間編碼，編碼完成后重新跳回到CHOOSE狀態.其中litprobs按照如下的關系計算:

圖6 區間編碼控制器狀態轉變Fig.6 State transition of range encoder controller

litprobs=PREV_BYTE?5*0x300

3)LITMATCHED_ENC:用于對重復字串后的新字符進行壓縮編碼，編碼根據PREV_BYTE、MATCH_BYTE和當前的NEW_char進行區間編碼，編碼完成后重新跳回到CHOOSE狀態下.

4)LEN_ENC:對重復長度LEN進行壓縮編碼.首先針對isMatch和isRep進行編碼，進一步地根據LEN值選擇choice1或choice2進行編碼，并且同時確定采用LOW，MID和HIGH中的一種編碼，編碼完成后跳轉到posSlot_ENC狀態下.

5)posSlot_ENC:對DIS進行變換，并對返回值posSlot進行編碼.根據 DIS變換的返回值posSlot有選擇地進行狀態跳轉:當4≤posSlot＜14時，跳轉到posEncoder狀態;當posSlot≥14時，則跳轉到DIRECTBITS_ENC和posAlignEncoder狀態;若 posSlot不滿足上述情況，跳回 CHOOSE狀態.

6)posEncoder:根據 posSlot計算 footerBits，base和posReduced;并且編碼posReduced，編碼完成后跳轉到CHOOSE狀態下.其中footerBits，base和posReduced按照如下的關系計算:

footerBits=((posSlot?1)－1)

base=((2|(posSlot＆1))?footerBits)

posReduced=pos-base

7)DIRECTBITS_ENC和 posAlignEncoder:根據 posSlot計算 footerBits，base 和 posReduced;并且編碼posReduced低四位的值，編碼完成后跳轉到CHOOSE狀態.

8)Flush:最后進行區間編碼器編碼輸出.

9)BIT_ENC:按照比特進行編碼，當區間值小于0xFFFFFF時，跳轉到ShiftLow狀態中，并且此時記憶當前的狀態.

10)ShiftLow:當區間下邊界小于0xFF000000或大于0xFFFFFFFF時，輸出區間的低八位作為區間編碼，當完成輸出后跳回到之前記憶的狀態中繼續執行.

2.3 數據讀出控制器

LZMA壓縮后的數據是按照字節輸出的，需要進一步將數據進行處理，轉換成適合在外部數據總線上傳輸的格式.圖7所示是將字節型數據組包成64 b位寬的數據讀出控制器.數據讀出控制器中添加了數據讀出緩存，與數據讀入緩存一樣，其中的數據讀出緩存中使用了乒乓方式對壓縮后的數據進行讀出，使壓縮可以不間斷地執行;只有當數據滿足可傳輸的條件時，控制器才會通知外部接口對數據進行讀出操作，這樣不需一直占用外部總線用以數據傳輸，可以有效地提高外部總線利用率.

圖7 數據讀出控制電路結構圖Fig.7 Structure image of read-out controller circuit

數據讀出需要滿足的條件:

1)一個數據緩存裝置中數據已存儲滿，輸出握手信號，通知外部接口可以從SEND_OUT數據總線上讀出數據，同時輸出本次讀出數據的大小;

2)當前對于輸入文件的壓縮已經結束，不管當前的數據存儲裝置中數據是否已滿，都將數據全部讀出，輸出握手信號，通知外部接口從SEND_OUT數據總線上讀出數據，同時輸出本次讀出數據的大小，并且通過壓縮完成信號，通知外部接口本次壓縮已經結束.

2.4 LZMA壓縮電路結構

圖8所示的LZMA壓縮電路是由上述3個子模塊組成，圖中相關信號定義和描述如表3所示.模塊采用硬件Verilog開發，使用Virtex-6 FPGA ML605開發套件［12-13］作為實驗平臺，能夠運行的最高頻率為159 MHz.

圖8 LZMA硬件電路結構圖Fig.8 Structure image of LZMA hardware circuit

表3 LZMA壓縮電路端口列表Table3 Ports lists of LZMA compression circuit

3 測試與性能

圖9是本文提出的LZMA壓縮算法硬件實現的一種典型應用系統，LZMA作為系統的一個協處理器，當進行數據壓縮時，PC通過PCIE高速總線接口由DMA_1向LZMA壓縮電路中寫入待壓縮的數據，當完成數據的壓縮后，將數據緩存到DMA_2中，經由PCIE向PC請求數據存儲，將壓縮的數據以LZMA的標準格式存儲到磁盤中的指定位置［14］.在壓縮的過程中PC只需要在壓縮的初期對源文件和目標文件進行指定的配置即可，不會大量占用CPU資源;并且只在需要數據總線時才會請求獨占數據總線，不會影響系統中其他應用的正常運行.

選取Virtex-6 FPGA實驗平臺，測試了本文中LZMA算法硬件實現電路的功能和性能，所設計的硬件電路綜合后的最大主頻為159 MHz，集成了PCIE接口與 DMA功能，設定工作頻率為125 MHz，采用 Calgary Corpus標準測試文件［15］和一些其他文本文件測試;與之相比的是在一臺核心為Intel Corei3-2100 CPU@3.10 GHz工作站上全負荷運行的軟件LZMA算法.表4中的測試數據表明，在獲取同等壓縮率的同時，LZMA算法硬件實現電路取得了更快的壓縮速率，平均的壓縮速率約比基于軟件的LZMA壓縮算法快了10倍，以時鐘作為衡量標準時，相比軟件單時鐘可以處理高達200倍的數據.測試表明所設計的LZMA算法硬件實現電路不僅有效解決了現有軟件LZMA壓縮算法存在的問題，同時也大大的降低了功耗.

圖9 LZMA硬件電路典型應用Fig.9 Typical applications of LZMA hardware circuit

表4 LZMA算法硬件實現電路性能測試表Table4 Performance testing table of hardware implementation circuit of LZMA algorithm

4 結束語

本文在分析LZMA壓縮算法的基礎上，提出了一種基于FPGA實現的LZMA壓縮算法硬件電路，經實驗驗證表明:

1)與其他現有的數據硬件壓縮方式相比擁有更高的壓縮率;

2)在取得等同壓縮速率的同時能夠更為有效地節約有限的數據帶寬，更加符合大數據處理中對于存儲和傳輸帶寬的需求;

3)本文通過合理利用FPGA中的雙端口RAM、流水線結構等實現LZMA硬件電路，其壓縮速率比軟件LZMA算法的壓縮速率提高了10倍;

4)完全兼容標準的7zip文件格式，可以靈活地集成到其他的系統中.

到目前為止，只是完成了基于FPGA的驗證，并且所提出的LZMA算法硬件實現方式中，區間編碼控制器按照比特方式進行編碼，因此編碼效率較低，沒有完全體現LZ77壓縮控制器的性能.今后將進一步提升區間編碼控制器的性能，并選取合適的工藝庫，采用片上集成的硬件電路來驗證所提出的LZMA算法的硬件實現方式的性能.

References)

［1］ Salomon D.Data compression:the complete reference［M］.4th ed.London:Springer，2007:241-246.

［2］ Pavlov I.7z format［EB/OL］.US:Igor Pavlov，2013［2014-03-10］.http://www.7-zip.org/7z.html.

［3］ Klausman.Gzip，Bzip2 and LZMA compared［EB/OL］.US:CEST，2008［2014-03-10］.http://blog.i-no.de/archives/2008/05/08/.

［4］ Rigler S，Bishop W，Kennings A.FPGA-based lossless data compression using Huffman and LZ77 algorithms［C］//Electrical and Computer Engineering.Canada:CCECE，2007:1235-1238.

［5］ Ziv J，Lempel A.Universal algorithm for sequential data compression［J］.IEEE Transactions on Information Theory，1977，IT-23(3):337-343.

［6］ Ranganathan N，Henriques S.High-speed VLSI designs for Lempel-Ziv-based data compression［J］.IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing，1993，40(2):96-106.

［7］ Shcherbakov I，Weis C，Wehn N.A high-performance FPGA-based implementation of the LZSS compression algorithm［C］//Data Compression Conference(DCC).Washington，DC:IEEE，2012:449-453.

［8］ Martin G N N.Range encoding:an algorithm for removing redundancy from a digitized message［C］//IERE Conference Proceedings.London:IERE，1979，43:187-197.

［9］ Pavlov I.LZMA SDK［EB/OL］.US:Igor Pavlov，2013［2014-03-10］.http://www.7zip.org/sdk.html.

［10］ 孫圣.一種基于FPGA的Defalte壓縮算法研究與實現［D］.桂林:桂林理工大學，2010.Sun S.A research and implementation of Deflate compression algorithm on FPGA［D］.Guilin:Guilin University of Technology，2010(in Chinese).

［11］ Shcherbakov I，Weis C，When N.A parallel adaptive range coding compressor:algorithm，FPGA prototype，evaluation［C］//Data Compression Conference(DCC).Piscataway，NJ:IEEE，2012，119-128.

［12］ Xilinx.Xilinx FPGA［EB/OL］.US:Xilinx，2011［2014-03-10］.http://www.xilinx.com/products/silicon-devices/fpga/index.htm.

［13］ Xilinx.ML605 Hardware User Guide［EB/OL］.US:Xilinx，2011［2014-03-10］.http://www.xilinx.com/support/documentation/boards_and_kits/ug534.pdf

［14］ Leavline E J，Singh D A A G.Hardware implementation of LZMA data compression algorithm［J］.International Journal of Applied Information Systems(IJAIS)，2013，5(4):449-453.

［15］ Calgary Corpus.Calgary corpus database［EB/OL］.US:Calgary Corpus，1987［2014-03-10］.http://en.wikipedia.org/wiki/Calgary_Corpus.