一种改进型LZ4压缩算法的硬件实现系统

摘要

本发明公开了一种改进型LZ4压缩算法的硬件实现系统，提供了超过目前现有的LZ系列无损压缩算法的处理速度，非常适合于高带宽数据压缩场合。本发明的一种改进型LZ4压缩算法的实现方法采用全范围逐字散列的方法，改进了原始LZ4算法中，对匹配字符串内部不进行散列表录入的缺陷。本发明还公开了实现该算法的一种硬件实现系统，利用该硬件电路实现改进型LZ4压缩算法，可以发挥出该压缩算法的最大性能。压缩速度超过目前现有的LZ系列无损压缩算法，为在高带宽数据处理过程中使用LZ压缩算法提供了可能。

说明书

技术领域

本发明涉及计算机数据无损压缩技术，尤其涉及一种改进型LZ4压缩算法的 硬件实现系统。

背景技术

随着计算机和网络技术的飞速发展，互联网每天产生的数据量正呈现爆发增 长的态势，如何存储不断产生的海量数据，如何提高存储器利用效率，正成为存 储系统设计者的一大难题。

自两位以色列研究者J.Ziv和A.Lempel在1977年提出了LZ77压缩算法以 来，各种基于字典匹配的LZ压缩算法的变体相继被提出，其中包括 LZ78,LZW,LZO,LZSS等。大部分基于LZ77的变体被广泛用于文本和位图的无 损压缩，其压缩编码的效率可以很大程度上逼近信源的信息熵值。然而大部分 LZ算法及其变体的压缩和解压缩的平均速度仅200～600MBps已经不能适应现代 计算机设备中动辄1GBps以上的总线带宽。于是提出了一种压缩解压缩速度远 高于目前无损压缩解压缩算法的LZ变体算法——LZ4。

LZ4压缩算法的速度优势在于其建立字典的过程中，减少了计算散列值和更 新散列表单元的次数，并且，在输出编码方面采用直接编码的方式，减小了算法 输出过程中的延迟。但正是由于LZ4压缩算法降低散列表更新次数以提高压缩 速度的做法，导致LZ4压缩算法的压缩率会比其他基于LZ变体的压缩算法要差 一些。然而，目前所有的对LZ4压缩算法的评估都是建立在软件实现的基础上， 由于CPU架构的限制，并没有体现出LZ4压缩算法的速度优势，并且，LZ4压 缩算法本身有一定的改进空间，以在不显著影响其压缩速度的情况下提升其压缩 率。

并且，软件压缩系统会占用大量的CPU资源，且压缩过程是串行执行，处 理效率低下，数据压缩造成的延迟比较大，拖慢了数据访问速度。

发明内容

本发明所要解决的技术问题在于改进原始的LZ4压缩算法，主要体现在采 用全范围逐字散列的方法，改进了原始LZ4算法中，对匹配字符串内部不进行 散列表录入的缺陷。原始LZ4算法这样设计的原因是由于软件录入散列表的过 程会大量消耗cpu资源，所以在匹配串内部字符不会被录入散列表，而改进型 LZ4算法是基于硬件电路优化的，可以将匹配串内部的字符也录入散列表，这样 的做法可以提升LZ4压缩算法的压缩率。使其在不显著增加额外的延迟的情况 下使压缩率有所提升，并且采用硬件电路实现该改进型LZ4压缩算法。

本发明具体采用以下技术方案解决上述技术问题：

一种改进型LZ4压缩算法的硬件实现系统，通过硬件实现系统实现待压缩 文件的全范围逐字散列的LZ4压缩算法；所述硬件实现系统包括数据输入模块、 字符串拼接模块、滑动字典模块、绝对地址产生模块、地址转换模块、散列表模 块以及主控模块；

所述数据输入模块用于读取待压缩文件的数据块，并暂存在FIFO中，等待 后级模块的读取；

所述字符串拼接模块由两组移位寄存器构成；用于从FIFO中读取待压缩文 件中的数据，并将读入的字符与之前3个字符组合成一个新的4字节字符串对数 据进行拼接，等待所述散列表模块或所述主控模块的数据读取请求；

所述滑动字典模块包含用于存储当前的字典以及紧邻字典的数据的存储器； 用于接收所述字符串拼接模块拼接完成的数据，并将其依次存入所述存储器中更 新滑动字典；

所述绝对地址产生模块包括地址累加电路，用于对文件中的每个字符产生独 一无二的32位绝对地址；

所述地址转换模块包含地址减法电路，用于将来自所述绝对地址产生模块产 生的32位绝对地址转换成适用于所述滑动字典模块中的滑动字典寻址的16位相 对地址；

所述散列表模块包含一个用于存储散列表数据的存储器和一个用于计算散 列地址的逻辑运算电路；用于在更新过程中从所述字符串拼接模块中读取拼接好 的4字节字符串，并通过逻辑运算电路计算字符串的散列地址，将该4字节字符 串对应的在数据块中的绝对首地址存入存储器中散列地址对应的存储单元中；

所述主控模块用于接收所述字符串拼接模块的4字节字符串作为当前字符 串，并将其发送给散列表模块计算散列地址；读取散列表中对应散列地址中的内 容，并根据散列表中对应散列地址中的内容根据所述地址转换模块转换的相对地 址读取滑动字典模块中的4字节字符串，并与当前字符串比对，输出匹配信息与 未匹配信息。

所述滑动字典模块包含一个位宽32bit，深度32KB，总容量128KB的存储 器，用于存储当前的64KB字典以及紧邻字典的数据，用地址指针调度的方式实 现滑动的功能。

所述散列地址的计算过程为用32位二进制值乘以0～2³²之间的黄金分割系 数，然后保留第31位到第17位，得到15位散列地址。

所述通过硬件实现系统实现待压缩文件的全范围逐字散列的LZ4压缩算法 包括以下步骤：

步骤1、初始化散列表和滑动字典，所有散列表存储单元内容全部初始化成 0，滑动字典初始化首地址和尾地址重合；

步骤2、从待压缩文件中读入4字节字符串，计算该字符串散列地址，并将 该字符串在文件中的绝对首地址存入散列表中该字符串散列地址的对应单元；在 读入过程中，将所述字符串存入滑动字典中；

步骤3、从待压缩文件中读入一个后续字符，将读入的字符与之前3个字符 组合成一个新的4字节字符串并计算其散列地址；在读入过程中，将所述字符存 入滑动字典中直至滑动字典达到设定大小并不断进行更新；

步骤4、利用散列表查找滑动字典中是否存在新的4字节字符串的匹配字符 串，如果有匹配，则跳至步骤5，并保存当前字符串的散列映射关系；如果没有 匹配，则返回步骤3，同时计算匹配距离，且无匹配字符串长度加1并输出无匹 配字符；

步骤5、从待压缩文件中读入一个后续字符，读入过程中将读入的字符与之 前3个字符组合成一个新的4字节字符串，计算其散列地址并将散列映射关系保 存至散列表中；从滑动字典中读出步骤3的匹配字符串的后续字符；将读入的字 符与该后续字符作比较，如果匹配，那么重复本步骤；否则计算匹配字符串长度， 返回步骤4；

步骤6、将步骤4和步骤5得到的无匹配字符串长度、无匹配字符串、匹配 字符串长度以及匹配距离编码成压缩后的数据格式，输出到压缩目标文件中；同 时，判断待压缩文件是否结束，如果未结束，则返回步骤3；如果已结束，则结 束压缩过程。

所述步骤3中滑动字典的设定大小为64KB。

所述步骤6中的编码：假设在扫描待处理区域字符的过程中，通过散列表找 到了在滑动字典中的匹配串，并且获得了匹配串的首地址，则该匹配串长度为N， 用当前处理字符的地址减去匹配串首地址得到有匹配字符串相对于滑动字典中 的匹配串的偏移量O，用当前处理字符的地址减去滑动字典尾地址即无匹配字符 串长度M；如果M和N均小于等于15，则将M和N拼接成一个8位编码，其 中M和N各占用4位；如果M超过15，则增加一个8位编码的无匹配串长度 的附加字节来表示多出的计数值；如果N超过15，则增加一个有匹配串长度附 加字节来表示多出的计数值；然后将M个无匹配字符直接输出到编码中，最后 输出16位的有匹配字符串的偏移量O以及可选的无匹配串长度附加位。

相比现有技术，本发明具有以下有益效果：

本发明设计了一种压缩速度高于现有的LZ系列无损压缩算法，采用全范围 逐字散列的方法，改进了原始LZ4算法中，对匹配字符串内部不进行散列表录 入的缺陷。使其在不显著增加额外的延迟的情况下使压缩率有所提升，并且采用 硬件电路实现该改进型LZ4压缩算法。该算法适用于对压缩速度和处理带宽要 求很高的场合，并且保证压缩率不劣于现有压缩算法；

本发明采用全硬件实现该压缩算法，相比较软件实现的方式，硬件电路可以 同时处理压缩过程中的多个步骤，压缩过程造成的延时更低，处理性能更强，并 且硬件实现的压缩系统可以有效的降低数据中心服务器的CPU载荷。更有利于 本发明算法的运行。

附图说明

图1为本发明的一种改进型LZ4压缩算法流程图；

图2为本发明的一种改进型LZ4压缩算法的数据处理过程示意图；

图3为本发明的一种改进型LZ4压缩算法的输出编码格式示意图；

图4为本发明的实施例中硬件电路各模块连接关系示意图。

具体实施方式

下面结合附图对本发明的技术方案进行详细说明：

图1为本发明的一种改进型LZ4压缩算法流程图；如图1所示，本发明的 一种改进型LZ4压缩算法，包括以下步骤：

步骤1、初始化散列表和滑动字典，所有散列表存储单元内容全部初始化成0，滑 动字典初始首地址和尾地址重合，即滑动字典容量为0；由于硬件电路初始化时， 滑动字典的大小为0，之后逐个处理后续的字符，被处理过的字符也会逐步成为 滑动字典的一部分，直到滑动字典容纳的连续字符达到64KB；

步骤2、从待压缩文件中读入首个4字节字符串，提取该字符串的32位ASCII码；

步骤3、用32位二进制值乘以0～2³²之间的黄金分割系数，然后保留第31位到第 17位，得到15位散列地址；

步骤4、通过散列地址找到散列表中的对应单元，将当前4字节字符串的在文件中 的绝对首地址存入该单元中以更新对应散列地址的存储内容；绝对首地址指的是 以文件的第一个字符为0地址，计算出的四个字符中第一个字符的偏移地址；对 应的相对首地址指的是以字典头部第一个字符为0地址，计算出的偏移地址；

步骤5、再从外部文件中读入一个后续字符；

步骤6、将读入新的字符与之前读入的4字节字符串的后3个字符组合成一个新的4 字节字符串；

步骤7、利用新的4字节字符串，通过与首个字符串同样的散列函数计算散列地址；

步骤8、从散列表中，散列地址对应的单元中读出相应的存储内容，在处理外部 数据的同时进行，散列表的更新也是在处理外部数据的同时进行的；

步骤9、将步骤8读出的存储内容作为读取滑动字典内容的地址，从滑动字典中取 出对应地址的4字节字符串；

步骤10、将从滑动字典中读取出的字符串与新的字符串进行对比，如果字符串内 容一致，则跳转到步骤11继续执行，如果不一致，则跳转到步骤4继续执行，同 时计算匹配距离，并使无匹配长度自增1，并将步骤5读出的字符存入无匹配字符 暂存区；

步骤11、将散列表中与步骤6产生字符串的散列地址对应的散列表单元内容更新 为步骤6产生的字符串在文件中的绝对首地址；

步骤12、从滑动字典中读出后续字符；

步骤13、从外部文件中读入一个后续待匹配字符；将读取到的字符与之前处理的 4字节字符串后3个字节拼接成一个新的4字节字符串，并计算出该字符串对应的 散列地址，将计算得到的散列地址对应的散列表单元内容更新为本步骤产生的新 的4字节字符串在文件中的绝对首地址；

步骤14、将步骤12和步骤13读出的字符进行比较，如果字符一致，则跳转到步骤 15继续执行，如果字符不一致，计算匹配字符串长度，同时在滑动字典中是否存 在新的4字节字符串的匹配字符串，返回步骤10；

步骤15、使有匹配长度自增1，返回步骤12；

步骤16、将步骤10和步骤14得到的无匹配字符串长度，无匹配字符串，有匹配字 符串长度，有匹配字符串绝对首地址相对于字典中匹配的字符串的绝对首地址之 间的偏移量进行编码；

步骤17、将步骤16编码的压缩数据存入已压缩数据存储区；

步骤18、判断待压缩文件是否结束，如果文件未结束，则跳转到步骤19继续执行， 如果文件以结束，则结束压缩过程；

步骤19、将步骤13读入的字符拼接到之前处理的字符串尾部3个字符的后面，形 成4字节字符串并计算其散列地址，并跳转到步骤4继续执行。

图2为本发明的一种改进型LZ4压缩算法的数据处理过程示意图，如图2所示， 整个待压缩源文件中，以滑动字典为界，滑动字典左边是已处理区域，包含所有 已处理的字符，滑动字典右边是待处理区域，包含所有待处理字符。其中，滑动 字典的位置由字典首地址指针与字典尾地址指针来表示，在已处理的字符少于 64KB时，滑动字典的大小随处理字符数量增加，而在已处理字符多于64KB时， 滑动字典随着处理字符的增加而逐渐右移。散列表中包含32K个存储单元，每个 单元用于存储4字节字符串的32位绝对首地址，散列表对应当前滑动字典中的4 字节字符串，散列映射关系是使用黄金分割系数乘以当前32位字符串的ASCII码 值，然后取结果中二进制位的第31位到第17位作为散列表的地址，这种映射关系 用于快速的按内容查找匹配串在滑动字典中所处的位置。

编码过程(这样编码的原因是尽可能减少编码后的数据所占据的存储空间) 可以按照图2和图3共同描述如下：假设在扫描待处理区域字符的过程中，通过散 列表找到了在滑动字典中的匹配串，并且获得了匹配串的首地址，并且，该匹配 串长度为N，用当前处理字符的地址减去匹配串首地址得到有匹配字符串相对于 字典中的匹配串的偏移量O；因为滑动字典的最大尺寸是64KB，并且滑动字典 尾部是紧贴着待处理字符的，用当前处理字符的地址减去字典尾地址即无匹配字 符串长度M，如果M和N均小于等于15，则将M和N拼接成一个8位编码，其中M 和N各占用4位，如果M超过15，则增加一个8位编码的无匹配串长度的附加字节 来表示多出的计数值，如果N超过15，则增加一个有匹配串长度附加字节来表示 多出的计数值，然后将M个无匹配字符直接输出到编码中，最后输出16位的有匹 配字符串的偏移量O以及可选的无匹配串长度附加位，综上所述，编码格式如图 3所示，其中，m为无配串长度附加字节长度，n为有配串长度附加字节长度，

图4为本发明的实施例中硬件电路各模块连接关系示意图，其中包含数据输 入模块、字符串拼接模块、绝对地址产生模块、地址转换模块、滑动字典模块、 散列表模块以及主控模块，所有模块均是以硬件电路的方式实现。

其中数据输入缓存模块，用于从处理装置外部文件中读取待压缩数据块，并 暂存在先进先出队列(FIFO)中，等待后级模块的读取；

字符串拼接模块，用于从数据输入缓存中接收数据块中连续的数据，并按照 主控制模块提供的匹配进程状态信息实时改变数据读取和拼接方式，也就是主控 模块提供现在匹配进行到了哪一个步骤，从数据输入模块读取4个Byte的数据 中，已经处理了几个Byte，是否需要从数据输入模块继续读取后续的4个Byte； 然后该字符串拼接模块将上一个4Byte数据中剩余未处理的Byte与下一个读入 的4Byte数据中的部分Byte拼接成一个完整的4Byte数据，送给主控模块，以 适应来自后级散列表模块或主控模块的不同类型的数据读取请求。字符拼接模块 主要由两组移位寄存器构成，分别为byte4_shift和byte4_data移位寄存器；其中 byte4_shift移位寄存器为按字节移位的移位寄存器，byte4_data移位寄存器为按 双字移位的移位寄存器；字符拼接模块从外部match_fifo中读取数据，并将分别 按照字节或双字为单位移位在byte4_shift或byte4_data移位寄存器中进行移位， byte4_svalid和byte4_dvalid是上述两个数据移位寄存器的输出数据有效指示信 号；

散列表模块，在更新过程中，从字符串拼接模块中读取4字节为单位的字符 串，并且将32位字符串ASCII码值乘以0～2³²之间的黄金分割系数并保留从第 17位到第31位之间的15位二进制值，作为散列表的地址，将该4字节字符串 对应的在待压缩文件的数据块中的绝对首地址存入散列地址对应的存储单元中， 在读取过程中，利用输入4字节字符串ASCII码值计算散列地址，然后读取对 应散列地址的存储单元内容并送到下级模块，同时将当前散列表存储单元中的内 容更新为最新的4字节字符串的绝对首地址。散列表模块中包含一个用于存储散 列表数据的32K深度，32bit位宽的存储器和一个用于计算散列地址的逻辑运算 电路，该运算电路使用输入的4Byte数据hash_idata来计算散列地址，先从对应 散列地址的存储器单元中读出原先存储的hash_oaddr数据，并将输入的新数据 hash_iaddr存入该存储单元；

绝对地址产生模块，由于每个字符在文件中的位置是独一无二的，所以为了 区分文件中的每个字符，需要对文件中的每个字符产生独一无二的绝对地址，并 且，该绝对地址还能够表明字符与字符之间的相对位置关系。该模块中包含地址 累加电路，使用来自滑动字典模块提供的32bit地址head_addr来生成32bit绝对 地址abs_addr_in；

地址转换模块，将来自绝对地址产生模块的32位绝对地址转换成适用于滑 动字典模块中的64KB字典寻址的16位相对地址，这里的地址转换模块是用于 生成字典中各个字符的相对存储地址，是写入字典的地址。该地址转换模块中 包含地址减法电路，使用来自滑动字典模块的32bit地址head_addr和来自主控 模块的32bitabs_addr_out地址生成地址范围在16bit以内的滑动字典读写地址 relate_raddr和relate_waddr，供滑动字典使用；

滑动字典模块，接收来自外部的数据，将其依次存入内部环形存储器中，并 且通过主控模块提供的匹配进程状态信息，从字符串拼接模块中读取数据并按照 地址自增顺序依次存入内部环形存储器中，该模块工作过程中实时调整滑动字典 中用于字典功能的连续存储区域在环形存储器中的首地址和尾地址，并记录当前 正在处理的字符地址，并同时接收来自主控模块的读字典绝对地址经由地址转换 模块转换而成的相对地址。滑动字典中包含一个位宽32bit，深度32KB，总容量 128KB的存储器，用于存储当前的64KB滑动字典以及紧邻滑动字典的数据，用 地址指针调度的方式实现滑动的功能，凡是属于滑动字典范围内的字符串都会在 散列表中有对应关系，每完成一段压缩编码后，主控模块使用move_distance信 号来控制滑动字典的滑动距离，然后再启动一次新的匹配和编码过程；

主控模块，用于协调各模块的工作，并读取各模块工作的状态信息和产生控 制信号，负责待匹配数据与字典数据之间的比对以及相应的压缩编码的产生。主 控模块从散列表模块、滑动字典模块、绝对地址产生模块以及字符串拼接模块中 读取如图4所示的状态信号，然后根据当前各模块电路的状态来控制压缩编码过 程的进行，并输出针对其它电路的控制信号。

综上所述，本发明可实现一种基于字典匹配的快速压缩算法，该算法可以在 相同的计算机环境下以高于目前其他压缩算法的速度处理高带宽输入数据，并且 保证了一定的压缩率。在采用本发明所示的一种实施例中的硬件结构实现该改进 型LZ4压缩算法时，可以发挥出该压缩算法的最大性能。

以上所述仅为本发明的较佳实施方式，本发明的保护范围并不以上述实施方 式为限，但凡本领域普通技术人员根据本发明所揭示内容所作的等效修饰或变化， 皆应纳入权利要求书中记载的保护范围内。