基于FPGA的LZO实时无损压缩的硬件设计FPGA/ASIC技术

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

1.2LZO压缩算法编码

LZO压缩后的数据需要经过特定的格式进行编码，如图2所示，LZO压缩算法这样做的目的有两方面：调整LZO压缩率，使得LZO适合压缩重复长度短，但指回距离较长的数据;使得解压缩过程更加简单，解压缩速度更快，且不需要额外的内存。

2.1LZO压缩算法硬件结构

2.2LZO压缩算法硬件加速方案

为了加速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）块标记

（3）字典分离

软件在实现LZO压缩算法过程中，当碰撞发生时，LZO压缩算法会进行第二次Hash操作，该次Hash操作在第一次Hash操作的基础上进行偏移。为了提升LZO压缩算法的压缩率，本文提出一种如图3（D）所示的字典分离的结构，当Hash碰撞发生时，LZO压缩算法进行第二次Hash操作，但第二次Hash操作对应的字符串索引不再存入第一个字典中，而是单独开辟一块RAM空间进行存储。字典分离结构的总存储空间增加了字典2的大小，这样在压缩文件的过程中，文件的压缩信息量也会增加。可见，该结构可以改进LZO压缩算法的压缩率。

3LZO压缩系统集成与测试验证

3.1LZO压缩系统硬件结构

3.2开发板简介

3.3测试结果及对比

针对LZO压缩算法模块和集成后的系统进行板级测试，一方面验证算法模块及集成后的系统的功能正确性，另一方面测试分析算法模块及集成后系统的性能。测试内容包括：数据压缩率（压缩后的文件大小/压缩前的文件大小），数据压缩速率（单个周期内处理的字节数）。