 |
| 图 1 LZMA软件算法性能测试图Fig. 1 Performance testing image of software-based LZMA algorithm |
| 图选项 |
在LZMA压缩中,数据流都是比特形式的,数据流被分成不同种类的数据包,经过区间编码后变成限定区间内的某一个数据后输出.如表 1所示,在LZMA算法中共有7种数据类型,为了将资源消耗控制在可接受的范围内,本文限定LZMA压缩的数据格式仅为前2种. 表 1 LZMA文件包数据类型Table 1 Data types in LZMA packages
| 数据包(bit) | 包名称 | 描述 |
| 0+ASCII | Lit | 新字符 |
| 1+0+len+dis | Match | 重复字串 |
| 1+1+0+0 | ShortRep | 与之前出现的字符一样 |
| 1+1+0+1+len | LongRep[0] | DIS与上一次一样 |
| 1+1+1+0+len | LongRep[1] | DIS与倒数第2次一样 |
| 1+1+1+1+0+len | LongRep[2] | DIS与倒数第3次一样 |
| 1+1+1+1+1+len | LongRep[3] | DIS与倒数第4次一样 |
表选项
2 硬件设计根据LZMA的压缩流程,本文将实现电路划分为3个部分:LZ77压缩控制器、区间编码控制器和数据读出控制器.如图 2所示,LZ77压缩控制器将写入的数据进行第1次压缩,并将压缩后的编码数据流向后传输;区间编码控制器按照既定压缩编码进一步压缩数据;数据读出控制器将区间编码控制器输出的数据拼接成更合理的数据格式,以适应外部高速总线,并在数据读出控制器中添加了数据缓冲存储,保证了外部高速总线的高利用率.
 |
| 图 2 LZMA硬件电路结构图Fig. 2 Structure image of LZMA hardware circuit |
| 图选项 |
2.1 LZ77压缩控制器如图 3所示,LZ77压缩控制器包括:数据读入缓存、Hash表存储模块和LZ77压缩算法控制模块.
 |
| 图 3 LZ77压缩控制器电路结构Fig. 3 Circuit structure of LZ77 compress controller |
| 图选项 |
数据读入缓存:采取了乒乓RAM的方式对需要压缩的数据进行读取.当一个数据块中的数据正在被压缩时,通过握手信号通知外部总线,向另一个数据块存储区域中写入下一个将压缩的数据信息,通过交替的向数据读入缓存中写入数据,保证LZ77压缩算法控制模块不需要等待数据,实现不间断地对数据进行处理.Hash表存储模块:存储已编码字符的信息.一系列的测试结果[10]表明在搜索深度为4时,LZ77压缩算法的效率已经达到极限范围.因此,设计中没有采用两个RAM实现多级链表(以往的目的是减少资源),而是使用4个Read-First模式的RAM级联,这样可以在同一个读周期内读取多个Hash值,减少多次搜索对RAM进行操作的时间,从而达到加速的目的;并且可以根据搜索深度的配置使能相关的RAM.LZ77压缩算法控制模块:产生上述两个模块的控制信号,对数据流按照LZ77算法进行压缩.图 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中区间分配Table 2 Interval distribution in RANGE_RAM
| 地址 | 参数名称 | 大小 |
| 0x_xxxx_xxxx_xxxx | litprobs | 6 144 |
| 10_0000_xxxx_xxxx | isMatch | [0∶10][0∶3] |
| 10_0001_xxxx_xxxx | isRep | [0∶10] |
| 10_0010_xxxx_xxxx | p_low | [0∶127] |
| 10_0011_xxxx_xxxx | p_mid | [0∶127] |
| 10_0100_xxxx_xxxx | p_high | [0∶255] |
| 10_0101_xxxx_xxxx | posSlotEncoder | [0∶3][0∶63] |
| 10_0110_xxxx_xxxx | posEncoders | [0∶113] |
| 10_0111_xxxx_xxxx | posAlignEncoder | [0∶15] |
| 10_1000_0000_0000 | choice1 | ------ |
| 10_1000_0000_0001 | choice2 | ------ |
表选项
图 6所示是区间编码算法控制模块工作的简要流程图,各个状态进行的操作以及状态间跳转关系如下所述.
 |
| 图 6 区间编码控制器状态转变Fig. 6 State transition of range encoder controller |
| 图选项 |
1) CHOOSE:根据缓存中的LZ77编码选择进一步编码的方式,当前指针对应字符是新字符时,则跳转到LIT_ENC状态下;当前指针对应字符是新字符,且上一状态FLAG_repeat信号有效时,则跳转到LITMATCHED_ENC状态下;当FLAG_repeat信号有效时,即当前指针为首地址的字符串为重复字串,则跳转到LEN_ENC状态;当所有的编码结束后则跳转到FLUSH状态下.2) LIT_ENC:对新字符进行压缩编码,首先对isMatch进行编码,进一步的根据litprobs和当前的NEW_cha进行区间编码,编码完成后重新跳回到CHOOSE状态.其中litprobs按照如下的关系计算:litprobs=PREV_BYTE5*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压缩电路端口列表Table 3 Ports lists of LZMA compression circuit
| 信号 | 位宽 | 有效 | 描述 |
| SYS_clk | 1 | ------ | 系统时钟 |
| SYS_reset | 1 | 低电平 | 系统复位 |
| DMA_INIT_OK | 1 | 上升沿 | 接口初始化完成 |
| Comp_en | 1 | 高电平 | 压缩使能信号 |
| DMA_RAM_wr_en | 1 | 高电 | 数据读入缓存使能 |
| DMA_in_addr | [11:0] | ------ | 数据读入缓存地址 |
| DMA_in_data_in | [63:0] | ------ | 数据读入 |
| DMA_in_size | [15:0] | ------ | 写入的数据块大小 |
| DMA_in_eof | 1 | 高电平 | 最后一个数据块 |
| DMA_out_start | 1 | 上升沿 | 开始读出数据 |
| DMA_out_size | [15:0] | ------ | 读取数据块的大小 |
| SEND_OUT | [63:0] | ------ | 读取的数据 |
| DMA_out_eof | 1 | 高电平 | 读取完毕,压缩结束 |
表选项
3 测试与性能图 9是本文提出的LZMA压缩算法硬件实现的一种典型应用系统,LZMA作为系统的一个协处理器,当进行数据压缩时,PC通过PCIE高速总线接口由DMA_1向LZMA压缩电路中写入待压缩的数据,当完成数据的压缩后,将数据缓存到DMA_2中,经由PCIE向PC请求数据存储,将压缩的数据以LZMA的标准格式存储到磁盘中的指定位置[14].在压缩的过程中PC只需要在压缩的初期对源文件和目标文件进行指定的配置即可,不会大量占用CPU资源;并且只在需要数据总线时才会请求独占数据总线,不会影响系统中其他应用的正常运行.
 |
| 图 9 LZMA硬件电路典型应用Fig. 9 Typical applications of LZMA hardware circuit |
| 图选项 |
选取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压缩算法存在的问题,同时也大大的降低了功耗.表 4 LZMA算法硬件实现电路性能测试表Table 4 Performance testing table of hardware implementation circuit of LZMA algorithm
| 文件名 | 压缩带宽/(Mb·s-1) | |
| 软件 | 硬件 | |
| 1.doc | 9.548 | 101.424 |
| 1.txt | 52.501 | 601.578 |
| 11.txt | 18.426 | 604.513 |
| 21.txt | 0.000 | 329.628 |
| 31.txt | 0.000 | 21.333 |
| 4.doc | 10.614 | 52.906 |
| Lz77.cpp | 4.166 | 79.061 |
| LZ77.v | 11.978 | 169.536 |
| bib | 10.440 | 66.123 |
| book1 | 10.986 | 51.274 |
| book2 | 13.962 | 60.465 |
| geo | 11.705 | 37.720 |
| news | 15.872 | 59.873 |
| obj1 | 5.728 | 57.348 |
| obj2 | 17.955 | 74.424 |
| paper1 | 7.266 | 63.054 |
| paper2 | 9.597 | 58.213 |
| paper3 | 9.523 | 56.130 |
| paper4 | 3.620 | 57.273 |
| paper5 | 3.273 | 59.550 |
| paper6 | 10.440 | 64.403 |
| pic | 34.224 | 170.327 |
| progc | 6.572 | 70.932 |
| progl | 9.845 | 92.035 |
| progp | 13.689 | 101.155 |
| trans | 14.979 | 92.456 |
| 平均 | 12.189 | 125.105 |
表选项
4 结 束 语本文在分析LZMA压缩算法的基础上,提出了一种基于FPGA实现的LZMA压缩算法硬件电路,经实验验证表明:1) 与其他现有的数据硬件压缩方式相比拥有更高的压缩率;2) 在取得等同压缩速率的同时能够更为有效地节约有限的数据带宽,更加符合大数据处理中对于存储和传输带宽的需求;3) 本文通过合理利用FPGA中的双端口RAM、流水线结构等实现LZMA硬件电路,其压缩速率比软件LZMA算法的压缩速率提高了10倍;4) 完全兼容标准的7zip文件格式,可以灵活地集成到其他的系统中.到目前为止,只是完成了基于FPGA的验证,并且所提出的LZMA算法硬件实现方式中,区间编码控制器按照比特方式进行编码,因此编码效率较低,没有完全体现LZ77压缩控制器的性能.今后将进一步提升区间编码控制器的性能,并选取合适的工艺库,采用片上集成的硬件电路来验证所提出的LZMA算法的硬件实现方式的性能.
参考文献
| [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. |
| Click to display the text | |
| [3] | Klausman. Gzip,Bzip2 and LZMA compared[EB/OL].US:CEST,2008[2014-03-10].http://blog.i-no.de/archives/2008/05/08/. |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [5] | Ziv J,Lempel A. Universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory,1977,IT-23(3):337-343. |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [12] | Xilinx. Xilinx FPGA[EB/OL].US:Xilinx,2011[2014-03-10].http://www.xilinx.com/products/silicon-devices/fpga/index.htm. |
| Click to display the text | |
| [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 |
| Click to display the text | |
| [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. |
| Click to display the text | |
| [15] | Calgary Corpus. Calgary corpus database[EB/OL].US:Calgary Corpus,1987[2014-03-10].http://en.wikipedia.org/wiki/Calgary_Corpus. |
| Click to display the text |
