了解更多开源请访问：51CTO开源基础软件社区https://ost.51cto.com【科技DNA】【智能场景】*********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************场景自驾/AR语音信号流视频GPU渲染科学，云计算内存缩减科学医学影像数据库服务器应用人工智能图像文本传输GAN媒体压缩图像压缩文件同步数据库系统通用数据技术点云压缩稀疏快速傅立叶变换有损视频压缩网格压缩动态选择压缩关于算法框架无损压缩分层数据压缩医学图像压缩无损通用压缩人工智能图像压缩短字符串压缩GAN压缩在线多粒度蒸馏图像压缩文件传输压缩快速随机存取字符串压缩高吞吐量并行无损压缩开源项目Draco/基于深度学习算法/PCL/OctNetSFFTAV1/H.266编码/H.266解码/VP9MeshOpt/Draco战神LZ4HCompressDICOMBrotliRAISRAIMCSOMGDOpenJPEGrsyncFSSTndzip简介：随着高品质多媒体业务的增多，数据压缩成为电子设备使用存储的必须。多年来，移动通信和视频服务的质量不断提高，传输和存储数据的需求呈爆炸式增长。对大容量存储和传输的需求增长速度至少是存储和传输容量增长速度的两倍。本文将介绍基于LZ4的改进算法和针对移动设备优化的硬件结构。应用场景1、移动通信2、移动设备的视频业务约束近年来，随着物联网等场景的不断发展，一些问题也逐渐暴露出来，如嵌入式设备上的CPU主频、电源和其他资源都是有限的；对于一些设备来说，或许可以通过更换更高时钟频率的时钟和更大容量的电池来解决问题，但对于手机等嵌入式移动设备来说，则需要满足便携、轻薄等需求，体积有限，供电也因此受限。因此，需要一种基于硬件的压缩方法来解决这个问题。该方案的解决方案基于字典，自适应压缩方法均源于Lempel-Ziv算法，LZ4是最快的压缩算法之一。但下面我们将介绍一种先进的算法和硬件架构，提高了压缩率和速度。为了获得更高的压缩比，该算法采用变长格式，而LZ4采用定长格式。实验结果表明，该架构可以实现3.84Gbps的压缩吞吐量和4的压缩比。通过这种方式，我们基于硬件的架构提高了低功耗移动设备的内存性能和电池寿命。LZ4分析LZ4是LZ77的变种算法，是Collet在2011年提出的固定（fixed）和面向字节（byte-oriented）的算法。LZ4的缩放数据如图所示，由令牌（Token)、文字长度(Literallength)、偏移量(Offset)和匹配长度(Matchlength)。LZ4与LZ77的相似之处在于它有一个由搜索缓冲区和前瞻缓冲区组成的滑动窗口。LZ4在先前未压缩的数据流中搜索重复数据，并用索引替换它。LZ4使用哈希表来匹配数据，提高了压缩速度。令牌（Token）是一个字节长，其中前4个字节是字面量长度（LiteralLength），接下来的4个字节是匹配长度（MatchLength）。Token[3:0]表示匹配长度，表示0~15的文本长度。Token[7:4]表示文字长度，是一个比较不重要的位，匹配长度从0到15.如果Token[7:4]的值为0，则表示没有文本。如果Token[7:4]的值为15，则表示字面量长度必须多出一个0到255的字节来表示字面量的全长。如果Token[3:0]的值为0，则表示最小匹配长度为4，称为minmatch。因此，Token[3:0]的取值从0到15，表示匹配长度取值从4到19。如果Token[3:0]的取值为15，则匹配长度的字节数较多。字面长度当Token[7:4]值为15时，字面长度为多出来的字节。如果文字长度为0~254，则没有更多字节。如果文字长度为255，则在下一个文字长度中生成更多字节。偏移量（Offset）占2个字节，小端格式，表示要复制的匹配位置。偏移值为1表示当前位置为1个字节。最大偏移量为65535。匹配长度（MatchLength）类似于上面提到的LiteralLength。当Token[3:0]达到最大可能值15时，额外的字节将添加到匹配长度中。总结LZ4总是分配2个字节作为偏移量（MatchLength），但实际上这对压缩比的性能影响不大。LZ4算法最初是为通用处理器上的软件实现而提出的，因此在某些硬件上实现LZ4存在一定的约束条件。ImprovedLZ4本文作者对LZ4数据格式的序列和哈希计算进行了改进。通过指定压缩单元的大小，可以优化哈希表的大小。将压缩单元大小设置为4KB可优化内存页面并节省内存。数据格式这里，作者更改了LZ4的表头（Header）和偏移量（Offset）。下图分别是改进后的LZ4和LZ4格式。HeaderTokenLiteralLengthLiteralsOffsetMatchLength2Bytes1Byte0-nBytes0-LBytes1-2Bytes0-nBytesTokenLiteralLengthLiteralsOffsetMatchLength-----1Byte0-nBytes0-LBytes2Bytes0-n每个压缩单元开头的字节包含压缩后的大小（CompressedSize)和原始标志(RawFlag)。如果压缩后的数据大小大于原始数据大小，原始标志（RawFlag）会被标记为1，原始数据会在头部（Header）后添加，压缩符号不会添加，解压是处理器也不需要解压缩压缩单元。在数据根本没有压缩的最坏情况下，RawFlag会使解压缩器更快。在最坏的情况下，压缩单元大小会添加到原始数据的标头大小中。偏移量（Offset）偏移量（Offset）由大小标志（SizeFlag）和偏移量大小（OffsetSize）组成。大小标志是最重要的位。如果sizeflag值为0，offsetsize使用7位，即{offset[7],offset[6:0]}。如果sizeflag值为1，offsetsize使用15位，即{offset[15],offset[14:0]}。偏移大小指示匹配位置，最大偏移大小值为32768。可变偏移字节长度使我们的方法比LZ4具有更好的压缩率。哈希计算哈希函数的目的是将任意大小的数据映射到固定大小的数据。对于匹配检测，使用哈希表的搜索算法比其他算法快得多。理想的哈希表大小是输入数据位乘以压缩单元的大小（以字节为单位）。但是，由于哈希表的大小是有限的，因此哈希计算输入的位数比输入的位数要少。哈希计算的性能取决于不同输入产生相同结果的频率。LZ4的哈希计算算法基于斐波那契哈希原理，计算公式如下：上式中的IN为32位值，LZ4的哈希计算公式在硬件上实现复杂，且计算周期长。于是作者改进了hash计算公式，公式如下：这里压缩单元大小为4KB，改进后的公式屏蔽了12位，32位的输入只需要使用位运算就可以映射到12位。因此，很小的硬件资源就足以计算出改进的哈希计算公式，而且只需要一两个周期。建议的硬件架构通用模块作者在这里提出了一个建议的硬件架构。它主要由核心模块（压缩模块和解压模块）和高级微控制器总线架构（AMBA）接口组成，实现应用处理器的互连。核心模块通过高级外围总线(APB)与处理器通信控制信号。输入数据和输出数据通过高级可扩展总线(AXI)进行处理。下图为整体硬件架构：下表描述了各模块的个数、面积和总面积。ModuleQuantityAreaTotalArea(mm2)Compress10.013200.01320Decompress10.013450.01345HashTable20.005150.01029SRAM80.006520.05215AXI(DMA)10.011870.01187APB10.001330.01187APB10.001330.01187APB10.001330.01187APB10.001330.01187APB10.001330.01187APB10.001330.01187APB10.001330.01187APB10.013450.01345HashComputingRAMCompressionModuleS由和streamgeneration组件组成，下图是压缩模块的架构图。为了避免数据输入瓶颈，压缩模块将输入数据写入8个独立的SRAM。然后压缩器从SRAM移位寄存器中读取128位数据。对于每4个字节的输入数据，哈希计算模块计算哈希值，读取哈希表进行比较，更新索引。如果在哈希表中搜索到计算出的哈希，则移动到该位置并开始匹配字节。当匹配长度大于4时，因为hash值已经从前面的文本计算出来了，此时可以跳过hash计算。在压缩单元最后一次数据处理后，压缩器检查压缩后的大小是否大于原始大小。如果大于原始大小，压缩模块会设置原始标志（RawFlag）到头部（Header）并输出原始数据。压缩内存数据时，对于未压缩的页面，只有页眉被写入输出。在这种情况下，CPU会在解压时读取到header中的原始标志（RawFlag），并执行memcpy解压模块。解压模块比压缩模块简单。它主要由SRAM控制组件、流分析组件和缓存组件组成。.解析器流通过从SRAM读取输入数据来解析标头和每个符号。Literalsbycopyingtheliterallength从输入数据中获得的匹配部分是通过从已经解压的数据中的偏移量匹配长度来复制的。如果与当前数据的偏移距离太近，则后续流水线可能不会写入数据。所以有一个缓冲区用来保存还没有写入的数据。实验和结果在这里，作者将所提出的设计与原始LZ4进行了比较，并显示了压缩率和压缩速度之间的关系以及各种数据类型，包括二进制数据、文本数据、Android应用程序包、字体数据、JPEG图像和HTML页面数据。本实验室中建议的设计在400MHz处理环境中运行。数据的吞吐量还取决于总线条件，在考虑总线条件的情况下，还要考虑整个模块的压缩率。由图【压缩比与压缩速度的关系】可以看出，压缩比与压缩速度呈线性关系。较低的压缩率意味着大部分输入字节都被处理，因此压缩率较慢。反之，当压缩率快时，会跳过一些匹配的字节，压缩率会提高。一般来说，压缩率取决于压缩率，压缩率也与压缩率成正比。由于LZ4中有加速选项，加速值越高，压缩越快；相应地，压缩率会降低。下面是将以上两图与LZ4的加速方案进行对比的实验。总结本文提出了一种改进的LZ4算法和硬件结构。可变长度偏移量、优化的哈希算法和硬件流水线都可以提高压缩率和比率。该设计可实现高达3.84Gbps的压缩吞吐量和高达4的压缩比。其压缩速度比LZ4算法快4%，压缩率比LZ4算法高5%，但最大时钟频率比LZ4慢。所提出的硬件架构可以针对移动设备环境进行优化，因此它不仅可以用于压缩移动设备的内部存储，还可以用于压缩RAM，有望提高内存性能。硬件架构还支持低电流驱动和低功耗驱动，以提高电池寿命。了解更多开源信息，请访问：51CTO开源基础软件社区https://ost.51cto.com。
