电子产品世界

　　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压缩算法的压缩率。

关键词： LZO FPGA LZSS RAM 压缩算法