LZMA壓縮算法FPGA硬件實現(xiàn)

李冰，張林，劉勇

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

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

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

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

1 LZMA算法

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

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

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

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

表1 LZMA文件包數(shù)據(jù)類型Table1 Data types in LZMA packages

2 硬件設(shè)計

根據(jù)LZMA的壓縮流程，本文將實現(xiàn)電路劃分為3個部分:LZ77壓縮控制器、區(qū)間編碼控制器和數(shù)據(jù)讀出控制器.

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

圖2 LZMA硬件電路結(jié)構(gòu)圖Fig.2 Structure image of LZMA hardware circuit

2.1 LZ77壓縮控制器

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

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

圖3 LZ77壓縮控制器電路結(jié)構(gòu)Fig.3 Circuit structure of LZ77 compress controller

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

圖4 LZ77_FSM狀態(tài)跳轉(zhuǎn)圖Fig.4 State transition image of LZ77_FSM

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

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

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

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

5)LZ77_COMPLETE:當(dāng)壓縮位置等于或者超出了壓縮數(shù)據(jù)塊大小的時候，則跳轉(zhuǎn)到該狀態(tài)，若此時數(shù)據(jù)交換接口通知已完成數(shù)據(jù)壓縮，則跳轉(zhuǎn)到INIT狀態(tài)，否則跳轉(zhuǎn)到WAIT_SIZE狀態(tài).

6)LAST_BYTE:當(dāng)前壓縮的位置為最后一個字節(jié)，直接進行新字符輸出，并且不對字典進行相關(guān)的更新，跳轉(zhuǎn)到LZ77_COMPLETE狀態(tài).

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

8)NEW:跳轉(zhuǎn)到該狀態(tài)下，表示當(dāng)前處理的是一個新字符，輸出信號 FLAG_new和 NEW_char;若上次輸出的是重復(fù)字串編碼，此時輸出信號 FLAG_new_after_repeat和 NEW_char.

2.2 區(qū)間編碼控制器

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

圖5 區(qū)間編碼控制電路結(jié)構(gòu)圖Fig.5 Structure image of range encoder controller circuit

表2 RANGE_RAM中區(qū)間分配Table2 Interval distribution in RANGE_RAM

圖6所示是區(qū)間編碼算法控制模塊工作的簡要流程圖，各個狀態(tài)進行的操作以及狀態(tài)間跳轉(zhuǎn)關(guān)系如下所述.

1)CHOOSE:根據(jù)緩存中的LZ77編碼選擇進一步編碼的方式，當(dāng)前指針對應(yīng)字符是新字符時，則跳轉(zhuǎn)到LIT_ENC狀態(tài)下;當(dāng)前指針對應(yīng)字符是新字符，且上一狀態(tài)FLAG_repeat信號有效時，則跳轉(zhuǎn)到 LITMATCHED_ENC狀態(tài)下;當(dāng)FLAG_repeat信號有效時，即當(dāng)前指針為首地址的字符串為重復(fù)字串，則跳轉(zhuǎn)到LEN_ENC狀態(tài);當(dāng)所有的編碼結(jié)束后則跳轉(zhuǎn)到FLUSH狀態(tài)下.

2)LIT_ENC:對新字符進行壓縮編碼，首先對isMatch進行編碼，進一步的根據(jù)litprobs和當(dāng)前的NEW_cha進行區(qū)間編碼，編碼完成后重新跳回到CHOOSE狀態(tài).其中l(wèi)itprobs按照如下的關(guān)系計算:

圖6 區(qū)間編碼控制器狀態(tài)轉(zhuǎn)變Fig.6 State transition of range encoder controller

litprobs=PREV_BYTE?5*0x300

3)LITMATCHED_ENC:用于對重復(fù)字串后的新字符進行壓縮編碼，編碼根據(jù)PREV_BYTE、MATCH_BYTE和當(dāng)前的NEW_char進行區(qū)間編碼，編碼完成后重新跳回到CHOOSE狀態(tài)下.

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

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

6)posEncoder:根據(jù) posSlot計算 footerBits，base和posReduced;并且編碼posReduced，編碼完成后跳轉(zhuǎn)到CHOOSE狀態(tài)下.其中footerBits，base和posReduced按照如下的關(guān)系計算:

footerBits=((posSlot?1)－1)

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

posReduced=pos-base

7)DIRECTBITS_ENC和 posAlignEncoder:根據(jù) posSlot計算 footerBits，base 和 posReduced;并且編碼posReduced低四位的值，編碼完成后跳轉(zhuǎn)到CHOOSE狀態(tài).

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

9)BIT_ENC:按照比特進行編碼，當(dāng)區(qū)間值小于0xFFFFFF時，跳轉(zhuǎn)到ShiftLow狀態(tài)中，并且此時記憶當(dāng)前的狀態(tài).

10)ShiftLow:當(dāng)區(qū)間下邊界小于0xFF000000或大于0xFFFFFFFF時，輸出區(qū)間的低八位作為區(qū)間編碼，當(dāng)完成輸出后跳回到之前記憶的狀態(tài)中繼續(xù)執(zhí)行.

2.3 數(shù)據(jù)讀出控制器

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

圖7 數(shù)據(jù)讀出控制電路結(jié)構(gòu)圖Fig.7 Structure image of read-out controller circuit

數(shù)據(jù)讀出需要滿足的條件:

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

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

2.4 LZMA壓縮電路結(jié)構(gòu)

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

圖8 LZMA硬件電路結(jié)構(gòu)圖Fig.8 Structure image of LZMA hardware circuit

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

3 測試與性能

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

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

圖9 LZMA硬件電路典型應(yīng)用Fig.9 Typical applications of LZMA hardware circuit

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

4 結(jié)束語

本文在分析LZMA壓縮算法的基礎(chǔ)上，提出了一種基于FPGA實現(xiàn)的LZMA壓縮算法硬件電路，經(jīng)實驗驗證表明:

1)與其他現(xiàn)有的數(shù)據(jù)硬件壓縮方式相比擁有更高的壓縮率;

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

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

4)完全兼容標(biāo)準(zhǔn)的7zip文件格式，可以靈活地集成到其他的系統(tǒng)中.

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

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壓縮算法研究與實現(xiàn)［D］.桂林:桂林理工大學(xué)，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，F(xiàn)PGA 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.