无损数据压缩算法的FPGA实现本科毕业论.doc

毕业设计（论文）报告纸 编号 南京航空航天大学毕业设计题 目无损数据压缩算法的FPGA实现学生姓名梅发强学 号041220318学 院电子信息工程学院专 业信息工程班 级0412206指导教师刘伟强 副教授二一六年五月 毕业设计（论文）报告纸南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：无损数据压缩算法的FPGA实现）是本人在导师的指导下独立进行研究所取得的成果。尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。作者签名： 年 月 日 （学号）： 无损数据压缩算法的FPGA实现摘 要随着信息技术的快速发展，数据量呈现爆炸性增长，因此数据压缩越来越受到人们的重视。目前，无损压缩算法大多数都是基于软件方式的实现，但是这在很多场合下已经不能满足高速数字系统的要求，所以基于硬件方式的实现成为了新的研究热点。目前已有LZ77、LZ78及LZW等算法的硬件实现，但是都存在搜索窗口较小，压缩率较低，速度较慢等缺陷。本文出于硬件实现的考虑，对LZ4算法进行了适当的修改，基于FPGA进行实现，经实测发现其压缩率和速度都得到了显著提升。关键词：无损压缩， LZ4， Verilog， FPGA FPGA Implementation of Lossless Data CompressionAbstractWith the rapid development of information technology, the amount of data presents explosive growth. Therefore, more and more attention has been paid to the data compression. Up to date, most of lossless compression algorithms are realized in software. However, software implementation in many occasions cannot meet the real time requirements of high-speed system. The hardware implementation of data compression algorithms is becoming a research hotspot. Nowadays, there are hardware implementations of the lossless data compression algorithms such as LZ77, LZ78, LZW etc. But they have defects including small search window, low compression rate, and slow processing speed. In this thesis, for the consideration of the hardware implementation, the LZ4 algorithm is appropriately modified to be implemented on Xilinx FPGA KC 705 evaluation board, which offers higher compression rate and speed.Key Words：Lossless compression; LZ4; Verilog; FPGA目 录摘 要iAbstractii第一章 引 言11.1 课题研究背景及意义11.2 本文研究内容和结构安排2第二章 基本原理和常用算法32.1 数据信息量、熵和冗余度介绍32.2 LZ系列算法概述32.3 LZ4算法简介4第三章 LZ4无损压缩算法原理53.1 数据流格式53.2 官方LZ4格式53.3 修改后的LZ4格式73.4 算法流程73.4.1 hash表73.4.2 匹配算法83.4.3 流操作83.5 解压93.5.1 官方LZ4格式解压流程93.5.2 修改后的LZ4格式解压流程9第四章 LZ4无损压缩算法硬件实现方案114.1 方案一114.1.1 硬件框图114.1.2 算法流程124.1.3 硬件调试时序图134.1.4 压缩速度计算144.2 方案二144.2.1 硬件框图144.2.2 算法流程144.2.3 硬件调试时序图164.2.4 压缩速度计算164.3 方案三164.3.1 硬件框图164.3.2 算法流程174.3.3 硬件调试时序图184.3.4 压缩速度计算184.4 各方案优缺点分析194.4.1 资源消耗比较194.4.2 压缩速度比较194.4.3 最佳方案选择19第五章 LZ4无损压缩算法硬件实现215.1 LZ4核总体框架215.2 LZ4压缩验证结构图225.3 LZ4核内部模块功能说明225.4 LZ4核性能27第六章 LZ4无损压缩算法硬件实现功能测试296.1 测试框架图296.2 数据测试表格296.3 与已有的LZ系列的实现对比30第七章 LZ4解压缩算法硬件实现317.1 LZ4解压核总体框架317.2 LZ4解压验证结构图317.3 LZ4解压核内部模块功能说明327.3.1输入模拟FIFO327.3.2数据解压控制模块337.3.3输出控制模块347.3.4输出RAM模块347.4 LZ4解压核输出速度计算34第八章 总结36参 考 文 献37致 谢38 v 第一章 引 言1.1 课题研究背景及意义随着信息时代的到来，人们对数据越来越依赖，数据交换量日益增大，海量数据带来的大规模数据处理也变得更加复杂。将数据进行有效的压缩能够减少存储所需的空间以及最大限度地利用有限的通信带宽。而且，经过压缩的数据在一定程度上是对原始数据的加密，从而更加地提高数据的安全性1。数据压缩通常分为无损压缩和有损压缩。图像、视频、音频等不是十分注重细节的数据大多数都采用有损压缩技术，用于此类应用场景的有MPEG，H.263，H.264等当今流行的压缩技术23。但是像程序、电子档案等类似的需要完全可以复原的重要信息，就必须采用无损压缩技术，用于这种要求解压缩后的数据与原始数据完全一致的场合的常见算法有LZ77、LZSS、GZIP、BZIP2、RAR等。人们对无损压缩技术的研究已经有很长的一段时间，其中LZ系列的压缩算法和最小冗余度构造算法Huffman算法属于最重要的无损压缩技术。现在流行的压缩技术基本上都是由这些算法衍生而来45。但是，当今很多压缩解压方案都是基于软件方式的实现。采用软件方式的压缩解压存在一个致命的弱点，那就是过多地消耗宝贵的CPU资源而且速度慢。特别是当压缩解压大量数据时，占有的CPU资源是非常大的，而且由于CPU采用的指令工作方式使得速度很慢，另外系统非常不稳定，很难满足一些特殊环境下的应用要求。所以，如何有效提高压缩算法的效率，减少庞大数据量压缩解压给CPU和内存带来的压力成为了现在压缩解压技术的主要发展方向。现代VLSI技术的发展使得采用硬件方式来实现压缩解压成为可能。用专用硬件提供压缩解压可以解决上述软件压缩解压所存在的缺点。即它可以：l、提高了压缩解压的速度，有利于实时性处理；2、节省了宝贵的CPU资源。因为硬件方式相比软件方式实现的速度快很多，依靠电路实现不需要循环的指令计算，而且能够采取并行的实现方式，这样降低了资源和能源的消耗。如今已经有不少采用硬件方式的压缩解压方案在信息产业的各个环节被应用，具有长远的发展前景67。1.2 本文研究内容和结构安排本文主要研究LZ4算法流程、硬件实现、以及算法优化。通过对现有的LZ4文献以及官方的C程序，了解并掌握LZ4算法的压缩和解压原理。在对LZ4算法足够了解后，将算法细分成几个步骤得出算法流程图。通过算法流程图，将整个算法细分成许多子模块，每个子模块实现一个简单的功能，通过流程控制将每个模块关联起来，最后实现每个子模块都处于同时工作状态，提高压缩速度，实现并行处理功能。本文章节内容安排如下：第一章主要介绍LZ4算法的FPGA高速实现的研究背景，介绍了数据压缩的历史与现状，并明确了本文的研究内容；第二章分析了数据压缩原理，表明了什么样的数据才能压缩，并对LZ系列算法做了一个大概的介绍。第三章对LZ4无损压缩算法原理进行了详细的介绍，包括LZ4数据格式以及LZ4算法流程。第四章提供了三个LZ4无损压缩算法的硬件实现方案，并详细介绍了每个方案的实现流程以及每个方案的优缺点，同时对其性能做出了详细的比较。第五章介绍了LZ4无损压缩算法硬件实现程序的结构以及每个模块的功能，同时给出了在kintex7 kc705开发板上运行的到的一些资源消耗信息。第六章是对LZ4无损压缩算法的硬件实现做的一些数据测试，计算了其压缩率，并将它的压缩速度与市场上的一些产品做比较。第七章是根据压缩算法而做的解压算法的FPGA实现，其中详细介绍了解压流程以及解压程序中每个模块的功能。第八章是对整个论文的总结。第二章 基本原理和常用算法数据压缩的前提是数据可以被压缩。从信息论中可以知道什么样的数据压缩后会变小，什么样的数据压缩后占据空间反而会变大。根据数据的信息量、熵和冗余度可以计算出压缩后的最小体积，但是由于算法原理、数据格式不同会导致始终达不到理论值。不过可以通过理论来知道为何数据可以被压缩，也可以通过这些理论来指导数据压缩的实现。2.1 数据信息量、熵和冗余度介绍信息量是指一个随机事件的不确定性，通常用熵来表示。信息论量度信息的基本出发点，是把获得的信息看作用以消除不确定性的东西，因此信息数量的大小，可以用被消除的不确定性的多少来表示。一个消息的可能性越小，其信息就越多；消息的可能性越大，其信息就越少。信息论中把一个事件（如字符）所携带的信息量定义为8：（2.1）其中P（Xi）为实践发生（字符Xi）的概率。将信息所有可能事件的信息量进行平均，就得到信息的熵。信源X的信息熵(Entropy) H(x)定义为8：（2.2）信源经常由于事件相关或概率分布不均匀等原因，而使实际的熵小于其最大熵，这样就产生了信息的冗余。冗余度R定义为：（2.3）2.2 LZ系列算法概述LZ系列算法起源于两位以色列研究者J.Ziv和A.Lempel在1977年发布的LZ77数据压缩的通用算法，该算法与Huffman及算术编码更加有效，通过不断的发展演变最后提出了很多改进算法，比如1978年由二人提出的改进算法LZ78以及1984年T.A.Welch提出的LZW算法等。这些衍生改进的算法统称为LZ系列算法。LZ77、LZSS、LZ78、LZW算法都是通过创建字典进行压缩的算法，LZ77和LZSS里的词典是指当前数据是否在以前出现过的数据中出现过，出现过就用出现过的字符的位置代替当前数据，而不同的是LZ78以及LZW是将出现过的数据进行编码，如果当前数据在以前出现过，则用编码代替当前数据。LZ4算法也是由LZ77算法衍生而来，不同的是LZ4算法更加注重与压缩和解压的速度，用最少的步骤实现匹配查找与编码，从而提高压缩速度。2.3 LZ4算法简介LZ4算法也属于LZ系列算法，其主要概念与LZ77算法一致。LZ4与LZ77算法一样，拥有一个滑动窗口以及一个预读缓存区域。LZ4的预读缓存区域为4个字节，而滑动窗口的大小可以根据实际需要进行修改。预读缓存区是用来保留当前输入数据的前4个字节，将这4个字节进行hash计算后，判断当前字节是否在滑动窗口中出现过，若在滑动窗口中出现过则可以进行匹配，继续往后查找匹配，查找结束后将当前字节与之前出现过的字节处的距离表示当前这一段数据，然后通过相应的格式组合成一个序列。而整个LZ4压缩后的文件就是有许多个类似的序列组合而成。第三章 LZ4无损压缩算法原理LZ4无损数据压缩是当今最快的压缩算法，当然不是指只要用LZ4压缩算法就会比其他算法实现更快，而是指这个算法的流程更少，使用更少的步骤来完成整个流程，这样压缩算法的速度在相同条件下自然就比其他算法更加快速。以下介绍了整个LZ4无损压缩算法的原理，包括压缩后的数据格式。为了实现流输入，在后面介绍了修改后的LZ4无损压缩算法原理以及压缩后的数据格式。3.1 数据流格式下图给出了LZ4压缩后的数据流格式10，其中前面4Byte是表示这个文件是什么格式，通常是一个特定的数字来代表其是LZ4压缩文件，后面的3-15Byte用来表示整个数据流的大小。中间的Block就是一个个数据块了，这是压缩文件的主体。其后的4个字节都是0，用来表示数据结束。Stream checksum则是一个校验码，也可以去掉。 图3.1 数据流格式简图3.2 官方LZ4格式LZ4的格式如下911：（1）数据格式每一个输入的数据块可以压缩成若干个序列，每个序列都包含有令牌（token）、字符串（literals）、字符串长度（literal length）、偏移量（offset）以及匹配长度（match length）。每个序列格式如图3.29所示： 图3.2 数据格式（2）token高4位代表不可匹配字符长度，当不可匹配字符长度大于等于15时高4位为15；当不可匹配字符长度小于15时，高4位就等于不可匹配字符长度。低4位代表匹配字符长度，当匹配字符长度大于等于19时低4位为15；当匹配字符长度小于19时，低4位等于匹配字符长度减去4。（3）literal length如果token高4位为小于15，则该值为0，且不会输出到压缩文件里，表示未压缩数据长度等于token高4位的值；如果token高4位等于15，表示不可压缩数据大于等于15，此时该值等于未压缩数据长度减去15后的大小。若token高4位等于15，则需要在该序列后添加一个字节来表示完整的长度值。每一个添加的字节取值范围为0到255。这样，两个位置的值组合共同表示完整的长度。若附加的一字节数据还是不能表示完整的长度，则继续在后面添加一个字节，以此类推。（4）literals该序列为未压缩的数据，由原数据复制得到，该数据跟在token和literal length后面。（5）offset当输入的数据经查找发现之前出现过相同的数据时，此处的数据将会被压缩，而offset的值表示这两处相同数据之间的偏移量。该序列有一个规则，即0是一个无效值，不能使用，1代表“当前位置减一个字节”。offset用小头结构表示，最大值为65525。（6）match length表示匹配数据的长度。匹配数据的最小值为4，因此，若token后4位的值为0，则意味着实际匹配的数据为4个字节，若token后4位的值为15，则意味着实际匹配的数据为19字节。匹配长度若超出15，采取的措施和literal length里面采取的方法一致。（7）最后一个序列规则1）压缩序列的最后5个字节必须是literals。2）不能匹配最后12个字节的数据。因此一个文件的最后一个序列至少有12个字节数据应被压缩为literals。3）最后一个序列匹配长度为0，offset为0。3.3 修改后的LZ4格式（1）数据格式由于在硬件实现的时候，由于是高速流操作，输入数据需要在几个时钟内判断是否匹配，判断结束后不可匹配数据需要立即输出到缓存中。若按照原来的格式，则必须先计算出不可匹配字符长度，然后再将不可匹配字符输出，这样数据输出的时间开销将变大，因此会减小压缩速度。所以通过改变数据格式来提高压缩速度。修改后的数据格式如下：说明：token、offset的格式与标准格式一致。 图3.3 修改后的LZ4数据格式（2）length of literals当token高4位小于15时，literal length为0字节。当token高4为为15时，literal length为2个字节，位于不可匹配字符中第16、17个字节，字符长度大小为literal length中以前一个字节为高8位和后一个字节为低8位组合成的一个16位的数据。（3）match length当token低4位小于15时，match length为0字节，实际匹配长度为token后四位加4。当token低4为15时，match length为2个字节，位于offset后两个字节，实际匹配长度大小为match length中以前一个字节为高8位和后一个字节为低8位组合成的一个16位的数据、token后四位和4相加的结果。3.4 算法流程3.4.1 hash表LZ4通过计算哈希值建立哈希表来查找匹配字符串。这个哈希表的映射关系为(key, value)：key是4个字节的二进制数。value为这4个字节在数据块中的位置。选择哈希表的大小时要根据实际要求作出选择：1）如果侧重压缩比，则可以将哈希表设置大一些。2）如果更看重压缩速度，则哈希表应该适中，以便于能装入L1 cache。哈希表使用的内存默认值为16KB，能装进L1 cache，这也是LZ4压缩速度快的一个原因。当前主流的Intel X86 L1 Data Cache为32KB，所以哈希表的大小最好不要超过32KB。Hash值计算采用整数哈希算法。2654435761U是2到232的黄金分割素数，2654435761 / 4294967296 = 0.618033987。计算哈希值时，输入为4个字节的二进制数，输出可以分为2字节值、4字节值两种哈希值。3.4.2 匹配算法匹配算法执行步骤：1）令当前的地址为ip，它的哈希值为h。2）令下个地址为forwardIp，它的哈希值为forwardH (下个循环赋值给ip、h)。3）按照哈希值h，获取哈希表中的值ref。3.1）ref为初始值，没有匹配，继续往下查找。3.2）ref不为初始值，有匹配。3.2.1）如果ref不在滑动窗口内，放弃当前值，继续向下查找。3.2.2）如果ref对应的4个字节和ip对应的4个字节不一样，是冲突，继续向下查找匹配。3.3.3）如果ref在滑动窗口内，且对应的4个字节一样，表明找到了match，退出匹配查找。4） 保存ip和h的对应关系。3.4.3 流操作流操作循环步骤：1）读取4字节，根据hash算法计算hash值。2）读取hash表的地址，写入当前地址，调用匹配算法查询是否匹配。3）若查找到了匹配则向后继续查找计算匹配长度，否则返回第一步读取后4个字节继续查找。4）若匹配且后向匹配完成，接着将计算好了的数据写入输出缓存中5）当前序列输出完成后，返回第一步读取后4字节查找下一个匹配。如果地址移动到了最后5个字节，则采取相应的算法规则，最后5个字节单独作为一个序列不进行匹配。3.5 解压3.5.1 官方LZ4格式解压流程以下为官方LZ4格式解压流程11：1）读取magic number判断文件格式，若是LZ4格式的进入解压程序，否则退出。2）读取stream describe判断文件大小，确定末尾地址3）读取第一个序列的token，即stream describe后一个字节。若token高4位为15，则继续向后读取后一个字节，若该字节为255，则继续往下直到读取到第一个小于255的字节为止，不可匹配字符长度就是这些所有字节的值求和再加上15。若token高4位小于15，说明不可匹配字符长度就等于token高4位的值。4）确定不可匹配字符长度后，将不可匹配字符复制到输出缓存中。5）根据不可匹配字符长度计算出offset的位置，读取offset的俩个字节，将其拼接成一个16位的数据，根据offset确定匹配的位置。6）若token低4位为15，则从offset的两个字节后读取一个字节，若该字节为255则继续读取下一个，直到不为255为止，这时匹配字符长度就等于这些字节求和后再加上19。若token低4位小于15，说明可匹配字符长度等于token低4位的值再加上4。7）确定匹配字符长度后，从匹配的位置处开始向后拷贝字符，拷贝字符的长度和匹配字符的长度一致。8）待拷贝完成后，读取下一个token，按照上述规则继续往下解压直到解压到末尾地址结束。3.5.2 修改后的LZ4格式解压流程以下为修改后的LZ4格式解压流程1）读取magic number判断文件格式，若是LZ4格式的进入解压程序，否则退出。2）读取stream describe判断文件大小，确定末尾地址3）读取第一个序列的token，即stream describe后一个字节。若token高4位为15，则从token开始向后数15个字节，第16、17个字节便是literal length。将第16、17个字节合并成一个16位的数据literal length，不可匹配字符长度就等于literal length加上15。若token高4位小于15，说明不可匹配字符长度就等于token高4位的值。4）确定不可匹配字符长度后，将不可匹配字符复制到输出缓存中。5）根据不可匹配字符长度计算出offset的位置，读取offset的俩个字节，将其拼接成一个16位的数据，根据offset确定匹配的位置。6）若token低4位为15，则从offset的两个字节后读取两个字节，将这两个字节合并成一个16位的数据match length，不可匹配字符长度就等于match length加上19。若token低4位小于15，说明可匹配字符长度等于token低4位的值再加上4。7）确定匹配字符长度后，从匹配的位置处开始向后拷贝字符，拷贝字符的长度和匹配字符的长度一致。8）待拷贝完成后，读取下一个token，按照上述规则继续往下解压直到解压到末尾地址结束。第四章 LZ4无损压缩算法硬件实现方案本章节提出了三个不同的硬件实现方案，每个方案都有各自的侧重点，方案一简单，方案二提高速度的同时减少RAM资源消耗，方案三压缩速度快。每一个方案都通过仿真验证，其性能也通过仿真测试过，以下就是方案的具体描述。4.1 方案一4.1.1 硬件框图与官方无损压缩算法不同的是添加了一个32位64K地址的RAM块，用这个RAM块来存储与hash值对应的32位字节，在进行匹配判断的时候不需要再返回在输入缓存中读取hash表中的地址对应的32位数据，可以直接从该RAM块读出后判断比较。这样做的好处在于省去了冲突带来的额外时间开销，同时可以减少查找匹配的步骤提高压缩速度。方案一的硬件模块分为输入缓存、ip控制、移位寄存器等9个模块，通过ip控制将输入缓存中的数据读出传送给移位寄存器，而移位寄存器将数据变成32位数据传输给核心控制模块进行hash计算、匹配查找的操作，直到查找到匹配后，读出匹配处的地址，根据地址读出缓存中该地址后的数据，然后继续后向匹配查找。在查找的同时将不可匹配字符传输给输出控制，通过字符长度模块计算不可匹配字符长度然后传给输出控制。在查找到匹配之后，通过匹配长度模块计算匹配长度，将匹配长度传给输出模块。输出模块根据接收到的数据组合后输出到输出缓存中完成压缩操作。以下为方案一的硬件框图： 图4.1 方案一硬件框图下面将具体介绍方案一的算法流程。4.1.2 算法流程（1）方案一核心算法流程如下：1）启动压缩时，通过ip控制，每个时钟ip加一，同时控制移位寄存器移位，当ip等于4时停止，同时停下移位寄存器移位。2）一个时钟后hash计算得出hash值。同时hash表以及4字节存储空间写输入使能。3）再过一个时钟，读出hash表中的地址Ref以及4字节存储空间中的4个字节U32Ref。同时写入当前的ip值以及移位寄存器输出的32位数据U32ip。若Ref小于当前ip值且不为0，同时U32Ref等于U32ip则说明当前4个字节与地址在Ref处的4个字节相同，启动匹配程序进入步骤5，否则进入步骤4。4）hash表以及4字节存储空间允许输入，发脉冲信号给ip控制，使ip加1,同时控制移位寄存器移动一位，若ip未移动到倒数第5个字节时回到步骤2。若ip移动到倒数第5个字节时跳到步骤8。5）通过Ref控制读出位于Ref处匹配4字节后的相应字节。6）判断dRef与dip是否相等，若相等，控制Ref与ip加1后回到步骤5；否则进入步骤7。若ip移动到倒数第5个字节时不论dRef与dip是否相等都跳到步骤8。7）一个序列查找完成，增加ip，控制移位寄存器，使移位寄存器中不再有前面的匹配字符，然后回到步骤2，开始查找下一个序列。8）剩余数据生成一个单独的序列，offset为0，匹配长度为0。（2）token、offset、match length以及literal length计算流程:l token：核心控制处于步骤7且步骤7刚结束时，若不可匹配字符小于15，则用token高4位表示不可匹配字符大小，否则token高4位为15；若可匹配字符小于19，则用token低4位等于可匹配字符大小减4，否则token高4位为15。l Offset：核心控制处于步骤5时，offset等于ip减去Ref。l literal length：核心控制处于步骤2到步骤4时，通过对控制ip模块的脉冲计数，获得不可匹配字符的大小，若其小于15则literal length为0，且不输出。若不可匹配字符的大小大于15时，literal length等于不可匹配字符的大小减去15。l match length：核心控制处于步骤5到步骤7时，通过对控制ip模块的脉冲计数，获得可匹配字符的大小，若其小于19则match length为0，且不输出。（3）输出控制算法流程1）复位后等待第一个序列完成。2）第一个序列完成后，依次写入token、literal length、literal、offset、match length。3）等待，当前序列完成后返回第2步直到结束。4.1.3 硬件调试时序图如图4.2所示，该图是方案一的核心控制逻辑的硬件调试时序图。图4.2 方案一硬件调试时序图其中，ip_go是控制ip移动的脉冲信号，每一个脉冲都使ip移动一个字节。state是用于匹配查找状态切换标志，每个时钟加一。hash_ip是hash值。4.1.4 压缩速度计算该LZ4压缩核主频是150MHz。由时序图可以看出查找匹配时每3个状态，ip加1，也就是每3个时钟ip加1。而找到匹配后每2个状态ip加1，也就是ip每2个时钟加1。按照极限情况计算。最小压缩速度：当全不可匹配时，由上述分析可知ip移动速度大约是150MHz/s除以3得50MByte/s。最大压缩速度：当几乎全可匹配时，由上述分析可知ip移动速度大约是150MHz/s除以2得75MByte/s。4.2 方案二4.2.1 硬件框图与方案一不同的是，方案二需要优化硬件结构，缩短时序，同时去掉那个32位64k地址的RAM块，通过返回读取缓存中的数据然后再进行冲突判断，这样做的好处在于减少了RAM资源的消耗，可以使程序消耗更少的资源。但是由于需要返回读取数据，可能会因为冲突造成大量的时间开销，从而降低压缩速度。同时由于冲突的影响会导致程序工作时的压缩速度极不稳定。下图给出了方案二的硬件框图： 图4.3 方案二硬件框图下面将介绍方案二的算法流程。4.2.2 算法流程（1）方案二核心算法流程：1）启动压缩时，通过ip控制，每个时钟ip加一，同时控制移位寄存器移位，当ip等于4时启动hash计算得出hash值。同时hash表以及4字节存储空间写输入使能。2）一个时钟后继续计算hash值。同时读出hash表中的地址Ref以及4字节存储空间中的4个字节U32Ref。同时写入当前的ip值以及移位寄存器输出的32位数据U32ip。若Ref小于当前ip值且不为0则说明当前4个字节与地址在Ref处的4个字节有可能相同，启动冲突判断程序进入步骤3；否则继续。若ip大于输入数据大小减5后的结果则跳到步骤7。3）通过Ref控制读出位于Ref处匹配的4个相应的字节。进入步骤4。4）判断U32ip与Ref处4个字节是否相等，相等则进入步骤5，否则返回步骤2。5）移动Ref到匹配的4字节后一字节处，判断dRef与dip是否相等，若相等，控制Ref与ip加1后继续判断；否则进入步骤6。若ip大于输入数据大小减5后的结果则跳到步骤7。6）一个序列查找完成，增加ip，控制移位寄存器，使移位寄存器中不再有前面的匹配字符，然后回到步骤2,开始查找下一个序列。7）剩余数据生成一个单独的序列，offset为0，匹配长度为0。（2）token、offset、match length以及literal length计算流程l token：核心控制处于步骤6且步骤6刚结束时，若不可匹配字符小于15，则用token高4位表示不可匹配字符大小，否则token高4位为15；若可匹配字符小于19，则用token低4位等于可匹配字符大小减4，否则token高4位为15。l Offset：核心控制处于步骤3时，offset等于ip减去Ref。l literal length：核心控制处于步骤2时，通过对控制ip模块的控制信号时长进行计数，获得不可匹配字符的大小，若其小于15则literal length为0，且不输出。若不可匹配字符的大小大于15时，literal length等于不可匹配字符的大小减去15。l match length：核心控制处于步骤5和步骤6时，通过对控制ip模块的控制信号时长进行计数，获得可匹配字符的大小，若其小于19则match length为0，且不输出。（3）输出控制算法流程1）复位后等待第一个序列完成。2）第一个序列完成后，依次写入token、literal length、literal、offset、match length。3）等待，当前序列完成后返回第2步直到结束。4.2.3 硬件调试时序图如图4.4所示是方案二的核心控制逻辑的硬件调试时序图。图4.4 方案二硬件调试时序图其中，Ip_go是控制ip移动的使能信号，只要ip_go为1则每一个时钟都使ip移动一个字节。State是用于返回读取匹配的4字节的状态切换标志，每个时钟加一。Hash_ip是hash值。4.2.4 压缩速度计算该LZ4压缩核的主频为140MHz。由硬件调试时序图可以看出，一个序列至少包含9个空闲时钟。最小压缩速度：由于冲突数量并不可预测，所以最低速度无法通过计算获得，只能通过估计大概数值。hash表为64k大小，按照每个序列都会遇到冲突，同时可压缩与不可压缩各一半，则压缩速度为：140*8/18=62.2MByte/s。最大压缩速度：当没有冲突时且压缩产生的序列越少时速度越大，按照极限计算，只有一个序列，且无冲突，则最大速度为140MByte/s。通过对测试文件的仿真计算得到，仿真文件的压缩速度为75MByte/s符合计算范围。4.3 方案三4.3.1 硬件框图方案三的结构结合了以上两个方案，同样需要优化硬件结构，缩短时序。但是和方案一一样，添加一个32位64k地址的RAM块，这样就可以有效的避免冲突带来的额外时间开销，但是对硬件资源消耗较大。下图为方案三硬件框图： 图4.5 方案三硬件图下面将介绍方案三算法流程。4.3.2 算法流程（1）核心算法流程1）启动压缩时，通过ip控制，每个时钟ip加一，同时控制移位寄存器移位，当ip等于4时启动hash计算得出hash值。同时hash表以及4字节存储空间写输入使能。2）一个时钟后继续计算hash值。同时读出hash表中的地址Ref以及4字节存储空间中的4个字节U32Ref。同时写入当前的ip值以及移位寄存器输出的32位数据U32ip。若Ref小于当前ip值且不为0，同时U32Ref等于U32ip则说明当前4个字节与地址在Ref处的4个字节相同，启动匹配程序进入步骤3；否则继续。若ip大于输入数据大小减5后的结果则跳到步骤4。3）移动Ref到匹配的4字节后一字节处，判断dRef与dip是否相等，若相等，控制Ref与ip加1后继续判断；否则进入步骤2。若ip大于输入数据大小减5后的结果则跳到步骤4。4）剩余数据生成一个单独的序列，offset为0，匹配长度为0。（2）token、offset、match length以及literal length计算流程l token：核心控制处于步骤2且步骤2已经执行3个时钟时，若不可匹配字符小于15，则用token高4位表示不可匹配字符大小，否则token高4位为15；若可匹配字符小于19，则用token低4位等于可匹配字符大小减4，否则token高4位为15。l offset：核心控制处于步骤3开始时，offset等于ip减去Ref。l literal length：核心控制处于步骤2时，通过对控制ip模块的控制信号时长进行计数，获得不可匹配字符的大小，若其小于15则literal length为0，且不输出。若不可匹配字符的大小大于15时，literal length等于不可匹配字符的大小减去15。l match length：核心控制处于步骤3 时，通过对控制ip模块的控制信号时长进行计数，获得可匹配字符的大小，若其小于19则match length为0，且不输出。（3）输出控制算法流程1）复位后开始查找匹配后第4个时钟起将不可匹配字符从缓存中输入到输出缓存中。2）等到查找到匹配后此时由于匹配检测的延时恰好将不可匹配字符全部从缓存中写入到输出缓存，然后立即将offset写入到输出缓存中，若不可匹配字符大于等于15则按照规则立即写入literal length，若小于15，则不用写literal length。3）等到后向匹配查找结束后，若匹配字符长度大于等于19则接在offset后面写入match length，若匹配字符长度小于19，则不用写match length。4）在后向匹配查找结束后第三个时钟写入token，然后回到第一步开始写入下一个序列的不可匹配字符。4.3.3 硬件调试时序图如图4.6所示为核心控制逻辑的硬件调试时序图。图4.6 方案三硬件调试时序图其中，literal_ip_go是当查找匹配时控制ip移动的使能信号，只要literal_ip_go为1则每一个时钟都使ip移动一个字节。而当literal_ip_go为0时间隔一个时钟就启动匹配控制ip移动。4.3.4 压缩速度计算该LZ4压缩核的主频为140MHz。由硬件调试时序图中ip的变化可以看出，一个序列只包含1个空闲时钟。最小压缩速度：由于一个序列只包含1个空闲时钟，当序列最多时速度最慢，则按照不可压缩与可压缩各占一半，以及每个序列包含4个不可匹配字符与4个可匹配字符计算，则最小速度为140*8/9=124.4MByte/s。最大压缩速度：只要单位时间内产生的序列越少，压缩速度越快。则按照极限计算，全是不可匹配字符或者几乎全是可匹配字符的情况下，压缩速度接近于140MByte/s。4.4 各方案优缺点分析4.4.1 资源消耗比较由于LZ4核对RAM块的消耗最大，所以只要RAM足够其余资源也就满足消耗。方案一：占用RAM大小为521kByte；方案二：占用RAM大小为256kByte；方案三：占用RAM大小为320kByte；4.4.2 压缩速度比较由上述分析可得：方案一：压缩速度为5075MByte/s；方案二：压缩速度大约为62.2140MByte/s；方案三：压缩速度为124.4140MByte/s；4.4.3 最佳方案选择下表给出了三种方案的优缺点比较：表4.1 各方案优缺点比较特点优点缺点方案一添加一个宽32位深64k的RAM表存储与hash表中对应的32位的4字节，检测是否匹配或冲突时可直接输出比较，减少时序。硬件易于实现，每次循环完成hash值计算、判断。占用资源多，速度慢。方案二去掉宽32位深64k的RAM表，返回匹配处，读取匹配的4个字节与当前4个字节进行比较查找冲突。减少hash计算开销，采用流水线形式，计算hash值的同时输入数据，不用输入数据后再等待hash计算检测冲突后执行下一步，提高速度。占用资源少，可以实现更多的核并行使用。时序变长，最低压缩速度无法保证。方案三添加一个宽32位深32k的RAM表存储与hash表中对应的32位的4字节，检测是否匹配或冲突时可直接输出比较，减少时序。减少hash计算开销，采用流水线形式，计算hash值的同时输入数据，不用输入数据后再等待hash计算检测冲突后执行下一步，提高速度。占用资源不算多，压缩速度快且稳定不受冲突的影响。硬件实现比较困难，时序紧凑对于原来的官方格式，没有足够的时间进行处理计算。由表4.1可以看出，在速度与资源上，方案三的优势比较大，对应缺点可以通过更改LZ4输出格式来解决，具体格式见第2.3节。第五章 LZ4无损压缩算法硬件实现通过以上章节描述，确定选择方案三后，通过kintex7 kc705开发板来实现并验证方案三的功能与性能，下面主要介绍硬件实现各个模块的功能。5.1 LZ4核总体框架想要输入数据开始压缩之前将复位信号rst1置0，input_en和wea_ip置1，然后输入数据以及数据地址，每个数据对应一个地址，输入结束后，将input_en和wea_ip置0，当all_end为1时表示可以输出数据，数据大小为op，将op之内的数据通过out_dop输出，out_op是其对应的地址。下图给出了LZ4核总体框架：图5.1 LZ4核总体框架接口说明如下表：表5.1 接口说明接口名称输入输出说明ip_ininput输入数据地址dip_ininput输入数据input_eninput输入使能（1有效）wea_ipinput缓存写入使能（1有效）rst1input复位（1有效）out_opinput输出数据地址out_dopoutput输出数据Opoutput压缩后的数据大小all_endoutput压缩完成标志（1有效）5.2 LZ4压缩验证结构图下图给出了LZ4压缩验证结构图： 图5.2 LZ4压缩验证结构图添加数据接口用做输入输出，便于对数据进行功能性验证，将压缩后的数据通过数据接口传回电脑处理。5.3 LZ4核内部模块功能说明（1）ip控制模块图5.3 ip控制模块框图此模块功能为：对ip执行加1和复位运算。说明：当复位信号有效时，ip为0。当信号go为1时，对ip执行加1运算。（2）移位寄存器控制模块移位寄存器控制模块如下图所示：图5.4 移位寄存器控制模块框图移位寄存器功能为：将从输入缓存中读取的数据通过移位寄存变成32位的数据，便于核心控制模块中计算hash值等运算。说明：当复位信号有效时，U32为0。当信号go为1时，对U32执行加移位运算，dat_4是U32的前8位。（3）Ref控制模块图5.5 Ref控制模块框图功能：实现对Ref的写入、复位、以及加1计算。说明：rst是复位信号，复位后Ref为0。如果Ref_write为1，则Ref等于Ref1；如果Ref_write为0，则Ref从当前数值开始执行加1运算。（4） hash表生成与流程控制模块图5.6 核心控制模块框图功能：实现hash值计算、实现hash表写入读出、输出ip控制信号ip_go、输出移位寄存器控制信号、控制Ref的写入、查找匹配判冲突、判断匹配长度、计算偏移量offset判断ip是否移动到末尾。说明：通过U32ip计算出ash值，再据hash值执行对hash表的写入读出，若当前地址与hash表中的地址之差小于64k则表示hash表中的地址有效，若大于64k则表示hash表中的地址无效，写入当前地址再计算下一个数据的hash值重复上面的步骤。当hash表中的地址有效时，比较该地址起往后的4个字节与U32ip是否相同，若相同则代表匹配，不同则重复上述步骤直到匹配。查找到匹配后再计算偏移量。同时在查找过程中通过不同状态控制ip_go、Ref_write、U32ip_go等控制外围模块实现相应的功能，使得查找匹配继续往下进行。（5）token计算模块图5.