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.