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

　　本文通过对多种压缩算法作进一步研究对比后发现，LZO压缩算法是一种被称为实时无损压缩的算法，LZO压缩算法在保证实时压缩速率的优点的同时提供适中的压缩率。如图1(A)给出了Linux操作系统下常见开源压缩算法的压缩速率的测试结果，LZO压缩算法速率极快;如图1(B)给出了Gzip压缩算法和LZO压缩算法的压缩率测试结构，从图中可以看出，LZO压缩算法可以提供平均约50%的压缩率。

　　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提供准备。