基于FPGA的LZO实时无损压缩的硬件设计

1 LZO压缩算法基本原理分析
1.1 LZO压缩算法压缩原理
LZO压缩算法采用(重复长度L，指回距离D)代替当前已经在历史字符串中出现过的字符串，其中，重复长度是指，后出现的字符串与先出现的字符串中连续相同部分的长度;指回距离是指，先后两个相同字符串之间相隔的距离(每个字节为一个单位);如果没出现过(定义为新字符)，则首先输出新字符的个数，再输出新字符。例如，待处理的字符串为“ABCDEFGHABCDEFJKLM”，压缩算法逐个处理字符，处理ABCDEFGH时没发现重复字符;处理到ABCDEF时发现这些字符在历史字符串中已经出现过，计算重复长度为6，指回距离(当前A离历史A的距离)为8，则用(6,8)代替ABCDEF;处理到JKLM时没发现重复字符，字符串到此处理完毕，则整个字符串被压缩成：(08)h ABCDEFGH(6,8)(04)h JKLM，其中h表示16进制。
1.2 LZO压缩算法编码
LZO压缩后的数据需要经过特定的格式进行编码，如图2所示， LZO压缩算法这样做的目的有两方面：调整LZO压缩率，使得LZO适合压缩重复长度短，但指回距离较长的数据;使得解压缩过程更加简单，解压缩速度更快，且不需要额外的内存。

2 LZO压缩算法硬件设计与加速方案
2.1 LZO压缩算法硬件结构
如图3(A)给出了一种LZO压缩算法的硬件结构，其中输入缓存模块：用于缓存DMA传输的待压缩数据，为高速缓存模块提供数据源用以进行压缩操作;高速缓存模块：临时缓存待压缩数据，为LZSS压缩模块提供待压缩数据，初始化时提前写入一定量的数据;LZSS模块：对待压缩数据进行压缩处理;字典模块：存储压缩过程中产生的压缩信息，例如历史字符串的索引信息，这样便可为后续数据压缩提供历史字符串信息;LZO编码模块：对LZSS压缩后的数据按照LZO编码格式进行编码，并将编码数据组包成固定长度的数据包，方便总线通讯;输出缓存模块：缓存编码后的数据，为DMA读操作提供压缩后的数据源;Avalon总线接口：按照Avalon总线规范对LZO压缩算法模块进行封装，为后续集成SOPC提供准备。

2.2 LZO压缩算法硬件加速方案
(1)分离双端口RAM
为了加速LZO压缩算法字符串的比对过程，本文提出如图3(B)所示的分离双端口RAM的结构，图中的多路选择器1用于将待压缩数据交替式写入双端口RAM1和双端口RAM2之一中，多路选择器2用于将读取的数据交替式输出。例如，现有字符ABCDEFGHIJ要存入双端口RAM中，具体如下：ABCD通过多路选择器1被写入RAM1中的data1处，EFGH通过多路选择器1被写入RAM2中的data2处，IJ通过多路选择1被写入data3，此时LZO压缩算法模块需要读取字符串BCDE，则在读取RAM1中data1处的BCD的同时读取RAM2中data2处的E，即给RAM1读地址的同时可以给RAM2读地址，这样同一时刻可以读2处地址对应的内容。相比于一般性双端口RAM结构，本结构可以实现一次完成读取操作。做进一步扩展可得出如下结论：若RAM的宽度为W，则读取字符数在2W以内时，采用分离双端口RAM结构可以一次完成读取操作;则读取字符数在2~2W以内时，采用一般性双端口RAM结构可能要读两次。当然，不仅RAM的宽度可以增加，RAM的个数也可以增加，当RAM的宽度和RAM个数越大时，完成读操作只需一次的可能性就越大。
(2)块标记
LZO压缩算法在压缩每个数据块之前都要对字典模块进行初始化为0的操作，即对RAM进行写0操作，然而写0操作会耗费若干个周期。若字典模块深度为16K，即RAM的深度为16K，当进行写0操作时至少花费16K个周期。通常解决此类问题的一种方法是采用乒乓操作的方式，即用两个字典来交替处理。为了解决初始化带来的时间花费和资源消耗的问题，本文提出一种如图3(C)所示的块标记字典结构，该结构主要包括：LZSS压缩控制模块，用于产生压缩信息，即字符索引及字符所对应的Hash值;flag产生模块，用于产生0或者1两种flag标识，表示是当前数据块还是历史数据块;信息合并模块，用于将字符索引和flag标识进行合并，然后存入字典模块。整个结构的工作原理可归纳如下：flag标识0或1表示是当前数据块或历史数据块，如压缩第一个数据块时标识为0，压缩第二个数据块时标识为1，压缩第三个数据块时标识为0，压缩第四个数据块时标识为1，如此进行反复;LZSS压缩控制模块产生字符索引然后与flag进行合并共同存入通过字符计算出的Hash值对应的地址处。例如，现假设已经压缩到第二个数据块，则根据上面的工作原理可知，当前的标识应该为1，在压缩时取出字典中的信息并判断第一个bit位，如果第一个bit位为0则说明该压缩信息是历史数据块，压缩信息无效;如果第一个bit位为1则说明可能是当前数据块(因为也有可能是很久以前的数据块)，根据压缩信息取出相应字符进行比对确认。
综上所述，块标记字典结构具有如下特点：无需初始化操作，避免了初始化过程带来的时间花费;摒弃了乒乓操作的思想，节省了乒乓操作带来的大量资源的消耗;该结构在片上资源紧缺的情况下是最优的选择。
(3)字典分离
软件在实现LZO压缩算法过程中，当碰撞发生时，LZO压缩算法会进行第二次Hash操作，该次Hash操作在第一次Hash操作的基础上进行偏移。为了提升LZO压缩算法的压缩率，本文提出一种如图3(D)所示的字典分离的结构，当Hash碰撞发生时，LZO压缩算法进行第二次Hash操作，但第二次Hash操作对应的字符串索引不再存入第一个字典中，而是单独开辟一块RAM空间进行存储。字典分离结构的总存储空间增加了字典2的大小，这样在压缩文件的过程中，文件的压缩信息量也会增加。可见，该结构可以改进LZO压缩算法的压缩率。
3 LZO压缩系统集成与测试验证
3.1 LZO压缩系统硬件结构
如图4(A)为LZO压缩系统SOPC硬件结构，内层虚线表示FPGA，虚线内的模块有相应的代码或硬件电路构成，外层虚线表示DE2开发板，开发板提供了相应的资源。图中：PC机通过下载线将待压缩的数据传送至DE2开发板上的SDRAM，数据经压缩后再经下载线回传至PC机;Nios II处理器负责与用户交互，对待压缩数据进行管理，控制整个SOPC的正常工作;JTAG-UART用于设计过程中的软件和硬件调试;DMA控制器用于高速数据传输，它将片外SDRAM中的待压缩数据传送到LZO压缩算法模块，将LZO压缩算法模块中被压缩后的数据传送到片外SDRAM中;LZO压缩算法模块用于对用户传输过来的数据进行压缩，它与片外SRAM进行通讯;LCD控制器用于控制LCD的显示，LCD可显示LZO压缩文件开始与结束，增加用户交互的可视性，例如显示待压缩文件的大小，压缩后的文件大小等;PIO控制LED指示灯的亮与灭，LED灯可用于指示LZO压缩文件开始与结束，增加用户交互的可视性;On-chip memory用于存储系统启动时的软硬件配置等信息;SDRAM控制器用于控制SDRAM与系统数据的交换;SDRAM用于存储指令和数据;SRAM用于存储LZO压缩算法过程中产生的压缩信息，在硬件设计中扮演字典的角色，采用片外SRAM的原因是考虑到FPGA片内资源可能不够使用;以上所有涉及到的模块均采用Avalon总线规范进行数据通信，它们共同挂载到数据总线上，Avalon总线具有自身的仲裁结构、地址分析等功能，易于用户集成开发。

3.2 开发板简介
测试与验证平台如图4(B)所示的DE2开发板，该开发板上的核心芯片为Altera公司的Cyclone II EP2C35 FPGA。选择该开发板作为测试平台主要基于以下考虑：拥有足够的片外存储资源(SDRAM 8MB、SRAM 512KB);拥有较丰富的片上逻辑资源(35K LEs);拥有丰富的可用于调试的外设(LCD、7-segment-displays);支持 Nios II嵌入式软核;成本较低。
3.3 测试结果及对比
针对LZO压缩算法模块和集成后的系统进行板级测试，一方面验证算法模块及集成后的系统的功能正确性，另一方面测试分析算法模块及集成后系统的性能。测试内容包括：数据压缩率(压缩后的文件大小/压缩前的文件大小)，数据压缩速率(单个周期内处理的字节数)。
通过图5(A)可知，压缩率提升最大的是1.pdf文件，提升最小的是7.mp3文件(音频文件已经采用音频压缩算法压缩过了)，除去最大值和最小值后取平均值，则压缩率提升为1.37%;通过图5(B)不难发现，压缩速率提升最快的为2.txt文件，提升最慢的为10.dll文件，除去最大值和最小值后取平均值，则压缩速率提升为4.81倍。