基于FPGA的miniLZO解压缩算法实现

邓计才 尹红霞

摘 要： miniLZO解压缩算法是一种轻量级的无损解压缩算法，广泛应用于网络传输中。为提高解压速度，降低传输延迟，该文充分利用FPGA的并行性，设计高速缓存方案和基于状态机的解压缩方案，实现了miniLZO的硬件解压缩算法。该硬件解压缩算法在Xilinx公司XC7K325T FPGA芯片上进行了工程实现，测试结果显示，最高吞吐率可达到164 MB/s。该硬件解压缩方案速度快、功能完备、便于移植，具有较强的工程实用性。

关键词： miniLZO； FPGA； 解压缩算法； 网络传输； 高速缓存； 状态机

中图分类号： TN919?34 文献标识码： 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是一个开源的无损压缩C语言库，是致力于解压速度的一种数据压缩算法，其程序是线性安全的，LZO压缩和解压缩因其比较迅速且占用内存小等特点，广泛应用于网络传输中。miniLZO是一种轻量级的压缩和解压缩库，它是基于LZO压缩和解压缩算法实现的。LZO虽然功能强大，但是编译后的库文件较大，而miniLZO编译后的库则小于5 Kbit，因此miniLZO是为那些仅需要简单压缩和解压缩功能的程序而设计。

FPGA采用流水线与并行运算，在数据处理中具有高效灵活的特点，适用于硬件的解压缩的实现[1?2]。基于FPGA的硬件解压缩方案具有速度快、处理能力强的优点，因此得到了人们的重视。本文首先对miniLZO算法进行简单分析，然后根据解压缩算法原理设计出可移植的FPGA电路，并进行测试与验证，最后对全文进行总结。

1 miniLZO算法

LZO压缩算法在压缩过程中会采用特定的算法判断当前字符串是否会在历史字符串（已经处理过的字符串）中出现过，如果出现过（定义为重复字符），则计算重复字符串的长度和指回距离，采用（重复长度，指回距离）代替当前的重复字符串。这里的重复长度是指，后出现的字符串与先出现的字符串中连续相同部分的长度；指回距离是指，先后两个字符串之间相隔的距离（每个字符为一个单位），如果没有出现过，就定义为新字符，则首先输出新字符的个数，再输出新字符。例如待处理的字符串为“ABCDEFGHABCDEFJKLM”，压缩算法逐个处理字符，处理“ABCDEFGH”时没有发现重复字符；处理到“ABCDEF”时发现这些字符在历史字符串中已经出现过，计算重复长度为6，指回距离为8，则用（6，8）代替“ABCDEF”；处理到“JKLM”时没发现重复字符。字符串到此处理完毕，则整个字符被压缩成（08）H ABCDEFGH（6，8）（04）H JKLM，其中H表示16进制。

判断字符是否出现过需要通过Hash计算建立待处理字符串与字符串索引的对应关系。首先将Hash计算结果作为地址，然后将索引值作为数据存储在字典中（字典为一块单独的数据存储空间），在处理字符中只需要计算hash值即可，在字典中读取Hash对应的数据是否有字符索引值，完成此操作之后，再通过索引值读取对比字符串进行比对，从而实现了重复字符的判断。miniLZO的hash操作通常较为简单，Hash函数为：

miniLZO解压缩是直接将miniLZO的编码数据通过相反的操作，根据接收到的数据判断是新字符还是重复字符。若为新字符判断新字符个数，读取新字符并输出；若为重复字符则计算重复长度和指回距离，读取已经处理的字符并输出，直至处理到字符结束。解压缩处理流程图见图2。

2 解压缩算法实现

根据miniLZO的解压缩流程，本文将FPGA实现电路规划为3个部分，数据处理模块，解压缩模块、数据保存模块等。

数据处理模块主要实现对外部数据总线的数据交换，暂停需要解压缩的数据，为后端模块提供数据供应。解压缩模块则根据读取的数据分离出新字符与重复字符，数据保存模块对重复字符进行处理，最后保存解压缩后的数据[3]。miniLZO解压缩硬件电路结构图如图3所示。

2.1 数据处理模块

数据处理模块主要包含两个模块，即输入缓存模块和高速缓存模块。输入缓存模块主要存储外部数据总线输出过来的数据，为解压缩模块提供数据。高速缓存模块主要是临时存放待解压数据，用于提高处理时间[4]。

为了实现数据的高速传输，本设计采用双端口Dual?RAM实现输入缓存模块，可同时读写数据，只要写入/读取地址不指向同一地址便不会出现错误，亦可实现RAM未保存满即可开始解压缩操作，提高了解压缩速率[5]，本设计中RAM大小设为4 kB，其中I/O宽度为64 bit，深度为512 bit。双端口RAM虽然有存量空间可足够大的优点，但缺点是读取数据需要一定的时延。以XILINX公司的双端口RAM为例，第一个周期内读取时钟的上升沿到来时，读取地址需要处于稳定的状态；下一个周期，数据会输出到数据线上；第三个周期才能读取数据的有效采样，即数据的真正输出延时一个时钟周期。这对解压缩速率来说是不能容忍的。基于此，本文设计了高速缓存模块，类似于内存与Cache的关系，高速缓存模块从RAM读取数据并缓存，供后端使用[6?8]。

根据解压缩数据处理特点，后端解压缩处理模块一次最多处理4 B（即32 bit）数据，且处理地址从0开始递加，不会出现地址跳跃读取现象。例如第一次读取addr至addr+3的4 B，则下一次读取的数據4个字节有5种可能：addr至addr+3，addr+1至addr+4，addr+2至addr+5，addr+3至addr+6，addr+4至addr+7。高速缓存模块会提前缓存这5种可能的数据，供后端第二次读取。后端第二次读取完成后，高速缓存模块继续更新缓存内数据供后端第三次读取，从而提高了数据读取速率。高速缓存块缓存内容如表1所示。设计中使用的缓存大小为20 B，采用寄存器实现，即在Verilog中声明为reg类型。

2.2 解压缩模块的实现

根据miniLZO压缩算法编码规则，读取到的编码数据需要进行判断，判断是否为新字符或重复字符，并计算出新字符个数、重复字符的重复长度与指回距离。读取到的编码数据如表2所示。

状态跳转图如图4所示。

Dis_new_data：判断新字符个数，若新字符个数编码中有8h00，则转入New_com_255状态。若没有则可直接确定新字符个数，转向Out_new_char状态。

New_com_255：判断有多少个8h00，每一个8h00表示新字符个数增加255个。

Out_new_char：根据判断的新字符个数，读取新字符并输出，直到新字符输出完毕。

Dis_rep_data：根据重复字符编码规则，计算重复长度与指回距离。若重复字符编码个数大于4 B，则转向rep_com_255后转再转向rep _255_after，判断重复长度与指回距离。若重复字符编码个数小于等于4 B，则可直接判断出重复长度与指回距离并输出。根据miniLZO算法规则，若新字符个数小于等于3时，新字符个数是插入到重复编码字符的保留位中的，此状态下需要判断保留位中是否有数据，若有数据，则确定下一个新字符个数后，读取新字符后直接输出新字符，若没有数据则读取新字符后进入Dis_new_rep状态。

rep_com_255：根据重复字符编码中8h00的个数判断重复长度。

rep _255_after：判断重复长度与指回距离后输出，并进入Rd_4bytes状态。

2.3 数据保存模块

该部分主要是将解压缩的数据进行保存，该模块工作流程图如图5所示。

根据读取的数据，判断新字符还是重复字符。若是新字符，则直接储存在RAM中，若是重复字符，则根据重复长度与指回距离计算出开始地址与结束地址，在已经保存过的RAM中读取数据，再保存当前地址，即完成了重复字符的解压缩过程[9?10]。同时本模板中使用的RAM宽度为8 B（即64 bit），而每次需要保存的数据长度不确定。为了保证存储数据的连贯性，对需要保存的数据重新组合，使其达到64 bit满足RAM存储数据的要求。

3 测试与性能

本设计有5个外部接口，其中indata为待解压缩数据的输入端口，decomp_over为解压缩完成标识，outdata为解压缩后的数据输出端口。其中数据端口设计为64 bit。实测性能见表3，在工作时钟频率为150 MHz时吞吐率可达到164 MB/s。

4 结 语

本文设计了miniLZO解压缩算法在FPGA的实现电路，对各模块进行了测试验证。从验证结果来看，该设计功能完备，结构合理，满足设计要求。且该设计具有一般性、便于移植等特点，在工作时钟频率为150 MHz时吞吐率可达到164 MB/s，具有较强的工程实用性。

参考文献

[1] 翁天阳，庄宇，于玮，等.基于HPS和FPGA的图像压缩感知编解码系统[J].电子技术应用，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实现[J].半导体光电，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的视频无损压缩算法研究与实现[D].杭州：浙江工業大学，2013.

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

[4] 兰向宇.基于FPGA的数据压缩缓存系统研究[D].西安：西安电子科技大学，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的无损图像压缩算法实现[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] 陶文泽，韦宏卫，张洪群.基于FPGA的并行RICE解码技术研究与实现[J].计算机工程与科学，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解压缩算法的设计和实现[D].西安：西安电子科技大学，2016.

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

[9] 张玉书.数据压缩与加密的协调性研究[D].重庆：重庆大学，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.