基于FPGA的miniLZO解壓縮算法實(shí)現(xiàn)

鄧計(jì)才 尹紅霞

摘 要： miniLZO解壓縮算法是一種輕量級的無損解壓縮算法，廣泛應(yīng)用于網(wǎng)絡(luò)傳輸中。為提高解壓速度，降低傳輸延遲，該文充分利用FPGA的并行性，設(shè)計(jì)高速緩存方案和基于狀態(tài)機(jī)的解壓縮方案，實(shí)現(xiàn)了miniLZO的硬件解壓縮算法。該硬件解壓縮算法在Xilinx公司XC7K325T FPGA芯片上進(jìn)行了工程實(shí)現(xiàn)，測試結(jié)果顯示，最高吞吐率可達(dá)到164 MB/s。該硬件解壓縮方案速度快、功能完備、便于移植，具有較強(qiáng)的工程實(shí)用性。

關(guān)鍵詞： miniLZO； FPGA； 解壓縮算法； 網(wǎng)絡(luò)傳輸； 高速緩存； 狀態(tài)機(jī)

中圖分類號： TN919?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號： 1004?373X（2018）22?0106?04

Abstract： The miniLZO decompression algorithm is a lightweight lossless decompression algorithm， which is widely used in network transmission. The high?speed cache scheme and the decompression scheme based on the state machine are designed in this paper by making full use of the parallelism of the FPGA to implement the miniLZO hardware decompression algorithm， so as to improve the decompression speed and reduce transmission delay. Engineering implementation of the hardware decompression algorithm is performed on the XC7K325T FPGA chip of Xilinx Company. The test results show that the maximum throughput of the algorithm can reach 164 MB/s， and the hardware decompression scheme has fast speed， complete function， and is easy to be transplanted， which has a strong engineering practicability.

Keywords： miniLZO； FPGA； decompression algorithm； network transmission； high?speed cache； state machine

0 引 言

LZO是一個(gè)開源的無損壓縮C語言庫，是致力于解壓速度的一種數(shù)據(jù)壓縮算法，其程序是線性安全的，LZO壓縮和解壓縮因其比較迅速且占用內(nèi)存小等特點(diǎn)，廣泛應(yīng)用于網(wǎng)絡(luò)傳輸中。miniLZO是一種輕量級的壓縮和解壓縮庫，它是基于LZO壓縮和解壓縮算法實(shí)現(xiàn)的。LZO雖然功能強(qiáng)大，但是編譯后的庫文件較大，而miniLZO編譯后的庫則小于5 Kbit，因此miniLZO是為那些僅需要簡單壓縮和解壓縮功能的程序而設(shè)計(jì)。

FPGA采用流水線與并行運(yùn)算，在數(shù)據(jù)處理中具有高效靈活的特點(diǎn)，適用于硬件的解壓縮的實(shí)現(xiàn)[1?2]?；贔PGA的硬件解壓縮方案具有速度快、處理能力強(qiáng)的優(yōu)點(diǎn)，因此得到了人們的重視。本文首先對miniLZO算法進(jìn)行簡單分析，然后根據(jù)解壓縮算法原理設(shè)計(jì)出可移植的FPGA電路，并進(jìn)行測試與驗(yàn)證，最后對全文進(jìn)行總結(jié)。

1 miniLZO算法

LZO壓縮算法在壓縮過程中會(huì)采用特定的算法判斷當(dāng)前字符串是否會(huì)在歷史字符串（已經(jīng)處理過的字符串）中出現(xiàn)過，如果出現(xiàn)過（定義為重復(fù)字符），則計(jì)算重復(fù)字符串的長度和指回距離，采用（重復(fù)長度，指回距離）代替當(dāng)前的重復(fù)字符串。這里的重復(fù)長度是指，后出現(xiàn)的字符串與先出現(xiàn)的字符串中連續(xù)相同部分的長度；指回距離是指，先后兩個(gè)字符串之間相隔的距離（每個(gè)字符為一個(gè)單位），如果沒有出現(xiàn)過，就定義為新字符，則首先輸出新字符的個(gè)數(shù)，再輸出新字符。例如待處理的字符串為“ABCDEFGHABCDEFJKLM”，壓縮算法逐個(gè)處理字符，處理“ABCDEFGH”時(shí)沒有發(fā)現(xiàn)重復(fù)字符；處理到“ABCDEF”時(shí)發(fā)現(xiàn)這些字符在歷史字符串中已經(jīng)出現(xiàn)過，計(jì)算重復(fù)長度為6，指回距離為8，則用（6，8）代替“ABCDEF”；處理到“JKLM”時(shí)沒發(fā)現(xiàn)重復(fù)字符。字符串到此處理完畢，則整個(gè)字符被壓縮成（08）H ABCDEFGH（6，8）（04）H JKLM，其中H表示16進(jìn)制。

判斷字符是否出現(xiàn)過需要通過Hash計(jì)算建立待處理字符串與字符串索引的對應(yīng)關(guān)系。首先將Hash計(jì)算結(jié)果作為地址，然后將索引值作為數(shù)據(jù)存儲(chǔ)在字典中（字典為一塊單獨(dú)的數(shù)據(jù)存儲(chǔ)空間），在處理字符中只需要計(jì)算hash值即可，在字典中讀取Hash對應(yīng)的數(shù)據(jù)是否有字符索引值，完成此操作之后，再通過索引值讀取對比字符串進(jìn)行比對，從而實(shí)現(xiàn)了重復(fù)字符的判斷。miniLZO的hash操作通常較為簡單，Hash函數(shù)為：

miniLZO解壓縮是直接將miniLZO的編碼數(shù)據(jù)通過相反的操作，根據(jù)接收到的數(shù)據(jù)判斷是新字符還是重復(fù)字符。若為新字符判斷新字符個(gè)數(shù)，讀取新字符并輸出；若為重復(fù)字符則計(jì)算重復(fù)長度和指回距離，讀取已經(jīng)處理的字符并輸出，直至處理到字符結(jié)束。解壓縮處理流程圖見圖2。

2 解壓縮算法實(shí)現(xiàn)

根據(jù)miniLZO的解壓縮流程，本文將FPGA實(shí)現(xiàn)電路規(guī)劃為3個(gè)部分，數(shù)據(jù)處理模塊，解壓縮模塊、數(shù)據(jù)保存模塊等。

數(shù)據(jù)處理模塊主要實(shí)現(xiàn)對外部數(shù)據(jù)總線的數(shù)據(jù)交換，暫停需要解壓縮的數(shù)據(jù)，為后端模塊提供數(shù)據(jù)供應(yīng)。解壓縮模塊則根據(jù)讀取的數(shù)據(jù)分離出新字符與重復(fù)字符，數(shù)據(jù)保存模塊對重復(fù)字符進(jìn)行處理，最后保存解壓縮后的數(shù)據(jù)[3]。miniLZO解壓縮硬件電路結(jié)構(gòu)圖如圖3所示。

2.1 數(shù)據(jù)處理模塊

數(shù)據(jù)處理模塊主要包含兩個(gè)模塊，即輸入緩存模塊和高速緩存模塊。輸入緩存模塊主要存儲(chǔ)外部數(shù)據(jù)總線輸出過來的數(shù)據(jù)，為解壓縮模塊提供數(shù)據(jù)。高速緩存模塊主要是臨時(shí)存放待解壓數(shù)據(jù)，用于提高處理時(shí)間[4]。

為了實(shí)現(xiàn)數(shù)據(jù)的高速傳輸，本設(shè)計(jì)采用雙端口Dual?RAM實(shí)現(xiàn)輸入緩存模塊，可同時(shí)讀寫數(shù)據(jù)，只要寫入/讀取地址不指向同一地址便不會(huì)出現(xiàn)錯(cuò)誤，亦可實(shí)現(xiàn)RAM未保存滿即可開始解壓縮操作，提高了解壓縮速率[5]，本設(shè)計(jì)中RAM大小設(shè)為4 kB，其中I/O寬度為64 bit，深度為512 bit。雙端口RAM雖然有存量空間可足夠大的優(yōu)點(diǎn)，但缺點(diǎn)是讀取數(shù)據(jù)需要一定的時(shí)延。以XILINX公司的雙端口RAM為例，第一個(gè)周期內(nèi)讀取時(shí)鐘的上升沿到來時(shí)，讀取地址需要處于穩(wěn)定的狀態(tài)；下一個(gè)周期，數(shù)據(jù)會(huì)輸出到數(shù)據(jù)線上；第三個(gè)周期才能讀取數(shù)據(jù)的有效采樣，即數(shù)據(jù)的真正輸出延時(shí)一個(gè)時(shí)鐘周期。這對解壓縮速率來說是不能容忍的?；诖?，本文設(shè)計(jì)了高速緩存模塊，類似于內(nèi)存與Cache的關(guān)系，高速緩存模塊從RAM讀取數(shù)據(jù)并緩存，供后端使用[6?8]。

根據(jù)解壓縮數(shù)據(jù)處理特點(diǎn)，后端解壓縮處理模塊一次最多處理4 B（即32 bit）數(shù)據(jù)，且處理地址從0開始遞加，不會(huì)出現(xiàn)地址跳躍讀取現(xiàn)象。例如第一次讀取addr至addr+3的4 B，則下一次讀取的數(shù)據(jù)4個(gè)字節(jié)有5種可能：addr至addr+3，addr+1至addr+4，addr+2至addr+5，addr+3至addr+6，addr+4至addr+7。高速緩存模塊會(huì)提前緩存這5種可能的數(shù)據(jù)，供后端第二次讀取。后端第二次讀取完成后，高速緩存模塊繼續(xù)更新緩存內(nèi)數(shù)據(jù)供后端第三次讀取，從而提高了數(shù)據(jù)讀取速率。高速緩存塊緩存內(nèi)容如表1所示。設(shè)計(jì)中使用的緩存大小為20 B，采用寄存器實(shí)現(xiàn)，即在Verilog中聲明為reg類型。

2.2 解壓縮模塊的實(shí)現(xiàn)

根據(jù)miniLZO壓縮算法編碼規(guī)則，讀取到的編碼數(shù)據(jù)需要進(jìn)行判斷，判斷是否為新字符或重復(fù)字符，并計(jì)算出新字符個(gè)數(shù)、重復(fù)字符的重復(fù)長度與指回距離。讀取到的編碼數(shù)據(jù)如表2所示。

狀態(tài)跳轉(zhuǎn)圖如圖4所示。

Dis_new_data：判斷新字符個(gè)數(shù)，若新字符個(gè)數(shù)編碼中有8h00，則轉(zhuǎn)入New_com_255狀態(tài)。若沒有則可直接確定新字符個(gè)數(shù)，轉(zhuǎn)向Out_new_char狀態(tài)。

New_com_255：判斷有多少個(gè)8h00，每一個(gè)8h00表示新字符個(gè)數(shù)增加255個(gè)。

Out_new_char：根據(jù)判斷的新字符個(gè)數(shù)，讀取新字符并輸出，直到新字符輸出完畢。

Dis_rep_data：根據(jù)重復(fù)字符編碼規(guī)則，計(jì)算重復(fù)長度與指回距離。若重復(fù)字符編碼個(gè)數(shù)大于4 B，則轉(zhuǎn)向rep_com_255后轉(zhuǎn)再轉(zhuǎn)向rep _255_after，判斷重復(fù)長度與指回距離。若重復(fù)字符編碼個(gè)數(shù)小于等于4 B，則可直接判斷出重復(fù)長度與指回距離并輸出。根據(jù)miniLZO算法規(guī)則，若新字符個(gè)數(shù)小于等于3時(shí)，新字符個(gè)數(shù)是插入到重復(fù)編碼字符的保留位中的，此狀態(tài)下需要判斷保留位中是否有數(shù)據(jù)，若有數(shù)據(jù)，則確定下一個(gè)新字符個(gè)數(shù)后，讀取新字符后直接輸出新字符，若沒有數(shù)據(jù)則讀取新字符后進(jìn)入Dis_new_rep狀態(tài)。

rep_com_255：根據(jù)重復(fù)字符編碼中8h00的個(gè)數(shù)判斷重復(fù)長度。

rep _255_after：判斷重復(fù)長度與指回距離后輸出，并進(jìn)入Rd_4bytes狀態(tài)。

2.3 數(shù)據(jù)保存模塊

該部分主要是將解壓縮的數(shù)據(jù)進(jìn)行保存，該模塊工作流程圖如圖5所示。

根據(jù)讀取的數(shù)據(jù)，判斷新字符還是重復(fù)字符。若是新字符，則直接儲(chǔ)存在RAM中，若是重復(fù)字符，則根據(jù)重復(fù)長度與指回距離計(jì)算出開始地址與結(jié)束地址，在已經(jīng)保存過的RAM中讀取數(shù)據(jù)，再保存當(dāng)前地址，即完成了重復(fù)字符的解壓縮過程[9?10]。同時(shí)本模板中使用的RAM寬度為8 B（即64 bit），而每次需要保存的數(shù)據(jù)長度不確定。為了保證存儲(chǔ)數(shù)據(jù)的連貫性，對需要保存的數(shù)據(jù)重新組合，使其達(dá)到64 bit滿足RAM存儲(chǔ)數(shù)據(jù)的要求。

3 測試與性能

本設(shè)計(jì)有5個(gè)外部接口，其中indata為待解壓縮數(shù)據(jù)的輸入端口，decomp_over為解壓縮完成標(biāo)識(shí)，outdata為解壓縮后的數(shù)據(jù)輸出端口。其中數(shù)據(jù)端口設(shè)計(jì)為64 bit。實(shí)測性能見表3，在工作時(shí)鐘頻率為150 MHz時(shí)吞吐率可達(dá)到164 MB/s。

4 結(jié) 語

本文設(shè)計(jì)了miniLZO解壓縮算法在FPGA的實(shí)現(xiàn)電路，對各模塊進(jìn)行了測試驗(yàn)證。從驗(yàn)證結(jié)果來看，該設(shè)計(jì)功能完備，結(jié)構(gòu)合理，滿足設(shè)計(jì)要求。且該設(shè)計(jì)具有一般性、便于移植等特點(diǎn)，在工作時(shí)鐘頻率為150 MHz時(shí)吞吐率可達(dá)到164 MB/s，具有較強(qiáng)的工程實(shí)用性。

參考文獻(xiàn)

[1] 翁天陽，莊宇，于瑋，等.基于HPS和FPGA的圖像壓縮感知編解碼系統(tǒng)[J].電子技術(shù)應(yīng)用，2017，43（5）：90?93.

WENG Tianyang， ZHUANG Yu， YU Wei， et al. Image compressed sensing coding and reconstruction system based on HPS and FPGA [J]. Application of electronic technique， 2017， 43（5）： 90?93.

[2] 趙元黎，陳鵬云.壓縮傳感圖像重建算法的FPGA實(shí)現(xiàn)[J].半導(dǎo)體光電，2016，37（4）：596?600.

ZHAO Yuanli， CHEN Pengyun. FPGA implementation of compressed sensing image reconstruction algorithm [J]. Semiconductor optoelectronics， 2016， 37（4）： 596?600.

[3] 汪磊.基于FPGA的視頻無損壓縮算法研究與實(shí)現(xiàn)[D].杭州：浙江工業(yè)大學(xué)，2013.

WANG Lei. Research and implementation of FPGA?based lossless video compression algorithms [D]. Hangzhou： Zhejiang University of Technology， 2013.

[4] 蘭向宇.基于FPGA的數(shù)據(jù)壓縮緩存系統(tǒng)研究[D].西安：西安電子科技大學(xué)，2015.

LAN Xiangyu. Research on data compression caching system based on FPGA [D]. Xian： Xidian University， 2015.

[5] ZHAO Xia， LI Bing. Implementation of the LZMA compression algorithm on FPGA [C]// Proceedings of International Conference on Electron Devices and Solid?State Circuits. [S.l.]： IEEE， 2017： 1?2.

[6] 范文晶，王召利，王惠娟，等.基于FPGA的無損圖像壓縮算法實(shí)現(xiàn)[J].電子科技，2016，29（11）：126?128.

FAN Wenjing， WANG Zhaoli， WANG Huijuan， et al. Implementation of lossless image compression algorithm based on FPGA [J]. Electronic science and technology， 2016， 29（11）： 126?128.

[7] 陶文澤，韋宏衛(wèi)，張洪群.基于FPGA的并行RICE解碼技術(shù)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué)，2017，39（6）：1118?1125.

TAO Wenze， WEI Hongwei， ZHANG Hongqun. An FPGA?based parallel RICE decoder [J]. Computer engineering & science， 2017， 39（6）： 1118?1125.

[8] 陳大莉.基于FPGA的GZIP解壓縮算法的設(shè)計(jì)和實(shí)現(xiàn)[D].西安：西安電子科技大學(xué)，2016.

CHEN Dali. A design and implementation of GZIP decompression algorithm based on the FPGA [D]. Xian： Xidian University， 2016.

[9] 張玉書.數(shù)據(jù)壓縮與加密的協(xié)調(diào)性研究[D].重慶：重慶大學(xué)，2014.

ZHANG Yushu. Study on the coordination of data compression and encryption [D]. Chongqing： Chongqing University， 2014.

[10] YAN J， YUAN J， LEONG P H W， et al. Lossless compression decoders for bitstreams and software binaries based on high?level synthesis [J]. IEEE transactions on very large scale integration systems， 2017， 25（10）： 2842?2855.