一种基于GZIP 的压缩与高效解压系统
2021-05-12袁兴峰
李 博,袁兴峰,李 隆
(合肥工业大学电子科学与应用物理学院,安徽合肥 230009)
在一些嵌入式系统中,系统的正常工作需要大量的数据支持,数据量的大小和数据的传递速度直接影响了工作系统的成本和性能。采用数据压缩的方法可以很好地缓解数据量巨大给嵌入式系统带来的压力。但是,在一般压缩与解压系统中无法满足对任意段数据的解压和提取[1-3],即如果需要压缩包中的某段数据时,必须对所有数据进行解压[4-6]。这种做法将降低解压效率和系统性能。文中提出了一种优化的压缩与解压系统,提高了解压的效率,降低了数据传输对带宽的压力。
1 系统构架
该文完成的是一种软件压缩硬解压的数据压缩与解压系统。数据压缩是利用压缩软件完成的,解压是在FPGA 端离线进行的,系统并不需要关注软件压缩时的耗时,如液晶仪表显示系统[7-8]和识别系统[9-11]等。在软件压缩端,需要关注的是压缩数据和校验码生成的正确性。在硬件解压端,需要关注解压的正确性、速度和效率。系统框架图如图1 所示。
图1 系统构架
据图1 可以看到数据首先通过PC 端进行软件压缩,在压缩过程中保证数据的准确性。数据压缩完成后,将压缩后的数据烧录至嵌入式系统中的存储器件如flash 等。至此,数据完成了压缩与存储。之后的操作脱离PC 端,数据的解压操作将在嵌入式系统中进行,系统运行步骤如下所示:
1)嵌入式系统发出指令和地址到硬件数据解压模块;
2)硬件解压模块接收指令和地址,将地址转化为压缩后数据存储的地址;
3)硬件解压模块根据指令和转化后地址从存储器件中取出压缩数据;
4)硬件解压模块接收从存储器件返回的压缩数据,并进行解压;
5)硬件解压模块将解压后的数据输出到嵌入式系统,供其使用。
经过上述流程,可在嵌入式系统中对压缩后的存储数据有效地进行解压。
2 基于软件的数据压缩处理
2.1 DEFLATE压缩算法
DEFLATE 压缩算法是一种无损压缩算法,由LZ77 和Huffman 两部分组成[3]。
LZ77 算法是一种基于字典查找的压缩算法。在一个文件中往往存在大量重复出现的字符串,有效地消除这些冗余的字符串,可以达到压缩效果。在压缩过程中,数据可以放入两个窗口中,第一个窗口为已处理数据,第二个窗口为未处理数据,可以将已处理数据窗口中的数据看做字典。在未处理数据窗口中,将找到与已处理数据窗口中匹配长度最长的数据字符串,用一对有用的信息来描述这串字符串,这对有用的信息往往是相对距离和匹配长度。通过这对信息,就可以快速且准确找到它所匹配的数据。将文件中的所有数据经过两个窗口处理[12],即可完成LZ77 压缩。
经过LZ77 算法处理后的数据依然存在很大的压缩空间。DEFLATE 压缩算法的Huffman 编码[5]部分对经过LZ77 算法压缩后的数据进行进一步压缩。Huffman 编码也是无损压缩算法的一种[13]。其核心思想是对文件中的数据进行重新编码,给出现频率高的字符赋予码长较短的编码,给出现频率低的字符赋予码长较长的编码,以此来达到平均码长最短的效果。
2.2 数据压缩流程与数据结构设计
压缩后的数据,按照固定的方式进行排序,这样有利于硬件解压的实现。通过压缩算法的介绍,可以明显地看出,DEFLATE 压缩算法利用了数据前后的关联性。因此,数据的解压也必须是对一个完整的数据包进行解压[6]。一个系统在提取数据时,可能从内存中的任何一个位置开始,考虑到系统的兼容性和解压的效率,可以首先将原始数据分为固定大小的数据包,然后,对这些数据包依次进行压缩。当需要内存中间某段数据时,不必从头开始进行解压,只需要通过解析地址提取出包含需要信息的一个或者几个压缩包进行解压即可。下面将以一个16 kB的原始数据包为例,并配合压缩软件流程图对压缩数据的格式进行说明。
压缩软件流程图如图2 所示。首先将待压缩数据以16 kB 为一个压缩包进行切割,最后不满16 kB的数据包用0 进行补齐。然后,依次将数据包送入压缩函数进行压缩。在一个数据包进行压缩后,需要判断压缩后的数据量比未压缩前是否变小,如果没有,即此数据包不进行压缩添加校验码后直接输出,如果变小了,即此数据包进行压缩并在添加校验码后进行输出。之后,需要将此数据包的基本信息添加到查找表中,信息中包括是否压缩、存放位置、压缩后数据大小。为了方便查找表信息的记录,压缩后的数据需要进行1 kB 对齐操作。最后,需要判断处理的数据包是否为最后一个数据包,如果不是,则重复上述流程对剩余数据包进行处理,如果是,则软件压缩流程结束。通过软件压缩流程操作后,得到按照固定格式排放的压缩数据和查找表。
图2 压缩软件流程图
压缩后数据结构图如图3 所示。在压缩后数据结构中,前256 kB 用来保存查找表信息,文中规定一个16 kB 的数据包的数据是否压缩,存储大小,起始位置信息记录到4个字节中,通过这种方式,256 kB查找表最多可记录1 GB 的原始数据经压缩数据后的信息。查找表信息后存放压缩后数据,每个数据包包含校验包头、压缩处理后,数据以及4 字节的校验码。
图3 压缩后数据结构图
2.3 Zlib函式库介绍
Zlib 是提供数据压缩功能的函式库[13],此函式库为自由软件,使用Zlib 授权。Zlib 支持DEFLATE 算法,可以通过配置参数,实现上文介绍的LZ77 和静态Huffman 压缩算法流程。通过Zlib 函式库,可以对上述算法流程进行快速且可靠的开发。
3 基于硬件的数据解压模块设计
通过软件压缩系统,得到了压缩数据包。数据包中包含了解压需要的查找表和压缩后数据。在硬件端,需要将查找表的信息进行解析,根据查找表的信息,查询压缩数据包的大小位置以及压缩方式,通过解压策略对数据进行正确的解压,并保证解压出的数据与原始数据的一致性。
3.1 解压策略
在压缩过程中,数据首先经过LZ77 算法处理,再经过Huffman 算法处理,得到压缩后数据[14]。对于压缩数据包的解压过程,与此过程相反。首先,需要对压缩数据包进行静态Huffman 解压,之后需要进行LZ77 算法解压。经过两次数据处理,即可得到解压后与原数据相同的数据。
静态Huffman 的解压策略如下:需要处理的数据是完整的压缩数据包,数据包中包含的数据是经过静态Huffman 编码之后的数据。在解压时,每一段不同的二进制编码都可能代表着一个原始数据、一个长度数据或者一个距离数据。解压过程需要依赖静态Huffman 表[1]。首先,对照字符-长度Huffman编码表[1],对其进行解码。在这一步中,可能得到的结果有两种:第一种是通过解码得到一个字符数据,此时需要将此数据记录下来,并且设置标志位以表示此位为一个原始字符;第二种是通过解码得到一个长度数据,设置一个标志位以表示此位为一个匹配长度信息,同时还包含了另一个重要信息:在此位置的下一个数据是一个匹配距离编码。因此,在对此位的下一组二进制数进行解码时,需要使用距离编码表[1]中的映射关系进行解码。通过上述解码过程,即可对原始数据压缩包进行静态Huffman 解压操作,并且生成LZ77 解压流程所需数据。
经过Huffman 解压后的数据主要包含两部分,一部分是需要进行解压的数据,另一部分是这段数据的标志位。此阶段的解压需要两部分信息共同操作完成。在进行解压时,首先需要根据标志位置判断此数据时原始字符数据还是长度数据。如果是字符数据,则直接进行输出;如果是长度数据,需要同时读取此数据位的下一个数据,即与此长度信息相匹配的距离数据。根据长度距离信息对进行匹配数据,将对应数据复制到此长度距离信息对位置,即可完成LZ77 解压。在解压完成后会产生一个校验码,若此校验码和压缩时所产生的校验码一致,则表明压缩数据包读取无误,数据已进行正确解压。否则,则表明压缩数据包读取有误,此次数据解压结果错误[15]。
3.2 解压的硬件实现
解压流程在FPGA 平台实现,硬件解压结构图如图4 所示。
图4 硬件解压结构图
数据解压模块首先需要接收到原始数据地址信息和指令,通过地址解析模块后,即可将原始地址信息解析为压缩后的数据包地址信息。这部分的逻辑如下:计算需要提取的数据在原始数据包中的位置。将该位置信息进行解析,根据解析值提取相应的查找表信息即可明确相应压缩数据包的位置、数据包大小、是否压缩。根据上述信息即可得索引压缩包地址。
从存储器件读入的压缩数据包首先需要进入静态Huffman 解压模块。在进行Huffman 解压时,需要根据静态Huffman 解压表对相应的数据进行查找处理。主要硬件思想:输入足够的数据位首先需要判断查找到的数据是字符还是长度,如果是字符数据,即可将其存储至字符和长度FIFO 中并附加一位标识位0,表明此数据为字符,拼接在数据的最高位。如果是长度数据,需要根据静态Huffman 字符-长度编码表[1]进行解码,将解析出来的长度数据同样存储到字符和长度FIFO 中并附加一位标识位1,标识此数据为长度数据。如果在字符-长度编码表中未找到相匹配的数据,即可对数据进行距离静态Huffman表[1]的解压,将距离数据存储到存储距离FIFO 中。当解析出停止标识位后,静态Huffman 解压结束[16]。
在LZ77 解压模块,根据解压策略可知,需要根据一个字典进行解压,因此,需要一块RAM 进行存储字典数据。主要硬件思想:LZ77 会向字符和距离FIFO 申请数据,得到数据后首先需要根据数据最高位即标识位判断数据是字符数据还是长度数据,如果是字符数据即标识位为0,对数据进行输出,同时还需要将数据写入字典RAM 中,对字典进行更新。如果是长度数据即标识位为1,需要向距离FIFO 中申请一个距离数据,根据此长度距离数据对在RAM中进行查找数据,长度和距离即可表示为数据在RAM 中存储的地址。RAM 的大小,应该与LZ77 压缩时已处理数据窗口的大小一致。
RAM 的存储策略:假设一个指针指向最先进来的数据,距离数据的判断即为与此指针位置的距离。在找到匹配数据后,需要将相应的数据进行复制输出,同时用这段数据更新RAM 中的字典数据。
4 系统实现与验证
系统的压缩部分实现平台为Visual Studio 2012,在此平台上可以根据Zlib 函式库,结合上述压缩流程开发出压缩软件。系统的解压部分通过ISE 和modelsim 进行设计和联合仿真验证,并在spartan6-xc6slx16上进行实现。
在硬件解压端,首先需要进行静态Huffman 解压。静态Huffman 解压模块接口中,clk 为工作时钟,频率为125 MHz。经过静态Huffman 解压操作,需要向字符长度FIFO 传输写指令(即模块中literal_length_wr)和距离FIFO 中的写指令(即模块中的distance_out_wr),对应于上述两个写指令的分别是输出的字符和长度的组合数据(literal_length_out)和距离数据(distance)。Bit_cost 信号表示一次静态Huffman 解压操作具体消耗的位宽,由于不同的数据消耗位宽不同,需要通过此信号判断下一次解压的起始位置。Unzip_done 信号是当检查到连续出现七位零数据时进行拉高,表示此次数据压缩包静态Huffman 解压操作完成。
经过静态Huffman 解压之后,利用存储在两个FIFO 中的数据即可进行LZ77 解压操作。LZ77 解压模块接口中,unzip_data_en 为解压数据输出使能,unzip_data 为解压数据输出端口,dis_fifo_empty 信号是从距离FIFO 中输入到LZ77 解压模块的信号,表示此FIFO 中是否有数据,dis_fifo_rd 是从距离FIFO中读数据的使能信号,dis_fifo_data 表示从距离FIFO中读到的数据。len_fifo_empty 信号是从字符长度FIFO 中输入到LZ77 解压模块的信号,表示此FIFO中是否有数据,len_fifo_rd 是从字符距离FIFO 中读数据的使能信号,len_fifo_data 表示从字符长度FIFO中读到的数据。
通过上述流程,在进行上板验证之前,先经过beyond compare 对比软件,将原始数据包和经过软件压缩和硬件解压之后的数据进行对比。两边数据完全一致,验证了系统逻辑的正确性。
实物验证图如图5 所示,图(a)为原始数据显示图片,图(b)为经过压缩和解压处理后得到验证图。此次验证在FPGA 实验板上进行,通过液晶屏进行显示。
图5 实物验证图
在验证功能的正确性之后,需要验证压缩率。测试结果如表1 所示,不同文件(图像纹理)的压缩率不同。因为系统使用的压缩算法是由静态Huffman 和LZ77 组合而成,这两种算法虽然都可以完成无损压缩,但是在压缩率上是不定的,压缩效果的好坏与原始数据的结构和不同字符出现的频率有关。而且在压缩数据包中,存在一个32 kB 的查找表,所占空间大小固定。原始数据量越大,压缩效果越好。
表1 压缩效果对比数据
表2 为传输数据量对比表。使用测试向量与表1 相同。其中系统传输数据量为嵌入式系统解压出数据中任意连续的16 kB 数据时所需要从存储器件中读取的数据量。一般系统是指直接使用GZIP 算法进行压缩[1],其中Huffman 算法设定为使用静态Huffman 算法。一般系统传输数据量即为压缩包总量,该文系统传输数据量为可能的最大传输量。解压效率为目标数据量在解压出的总数据量所占比重。
表2 系统性能对比表
通过表2 可以得到:第一点,在解压数据中连续16 kB 数据时,该文系统的数据传输量远低于一般系统,有效缓解了数据传输的带宽压力;第二点,该系统的解压效率普遍达到50%,远高于一般系统,有效减少了系统的无用功,提高了系统性能;第三点,有效解压数据量占原始数据量越小,一般系统的解压效率越低,该文系统可根据数据需求量进行分块传输,减少了有效解压数据量对解压效率的影响。
5 结束语
该文首先讲解了所使用压缩算法的基本原理和改进方法,并提出相应的解压策略和其硬件实现思想。然后,实现了基于Visual Studio 2012 平台的压缩功能和基于FPGA 的解压功能。在压缩时按照固定格式排列并生成了查找表,为稳定地进行解压操作提供了保证。在解压侧,利用FPGA 的并行性,进行快速且准确的解压操作。最后,通过实验验证了该文系统的解压效率高于一般系统,以及高效解压的稳定性。