兰州做网站的,网站策划书主题,南宁网站建设兼职,长春网站建设及推广1. 简介
因为MCU的内存和算力的限制#xff0c;那些对内存消耗大或算力需求大的压缩算法就不适合在MCU中使用。适用于MCU的压缩算法主要有#xff1a;RLE、LZ77、Huffman、LZO、DEFLATE、LZ4。
2. 算法
2.1. RLE
RLE(Run Length Encoding)#xff0c;也称为行程编码那些对内存消耗大或算力需求大的压缩算法就不适合在MCU中使用。适用于MCU的压缩算法主要有RLE、LZ77、Huffman、LZO、DEFLATE、LZ4。
2. 算法
2.1. RLE
RLE(Run Length Encoding)也称为行程编码压缩算法是一种无损压缩算法。算法特点简单、易实现。使用RLE压缩方法可以将 RRRRRGGBBBBBBABCD 压缩为 5R2G6B1A1B1C1D。基于RLE算法升级可以将RRRRRGGBBBBBBABCD可以压缩为b’\x85R\x82G\x86B\x03ABCD’0x85表示后面有5个相同的字符0x03表示后面有3个不连续的字符。 RLE的实现非常简单针对一些图片颜色少或重复字符多的文件有非常好的压缩率RLE的适用场景比较少通用压缩率较差。
2.2. LZ77
LZ77是一种基于字典的算法它将长字符串也称为短语编码成短小的标记用小标记代替字典中的短语从而达到压缩的目的。LZ77算法的压缩率、速度、内存消费都是中等但是代码复杂度较低适用于MCU的使用。
2.3. LZO
LZO压缩算法采用(重复长度L指回距离D)代替当前已经在历史字符串中出现过的字符串。LZO致力于解压速度不同的参数下的LZO压缩率不同。LZO内存消耗中等解压速度较快压缩速度较快但是代码复杂度较低适用于Bootloader等追求压缩率和解压速度的场景。
2.4. Huffman
霍夫曼(Huffman)编码使用变长编码表对源符号进行编码其中变长编码表是通过一种评估来源符号出现机率的方法得到的出现机率高的字母使用较短的编码反之出现机率低的则使用较长的编码这便使编码之后的字符串的平均长度、期望值降低从而达到无损压缩数据的目的。霍夫曼编码使用的编码表使用霍夫曼树来进行存储让出现概率最高的编码最容易查找以提升解码速度。霍夫曼编码算法的压缩率分布在20%-90%因为要扫描整个数据来构建霍夫曼树所以其压缩速度较慢且需要一定的内存来存储编码表但是解压速度较快。霍夫曼的算法复杂度较简单。
2.5. DEFLATE
DEFLATE是同时使用了LZ77算法与哈夫曼编码Huffman Coding的一个无损数据压缩算法。DEFLATE压缩与解代码可以在自由、通用的压缩库zlib上找到。DEFLATE算法压缩速度、解压速度均处于中等却有着比较好的压缩率所以是zlib、gzip使用的主要压缩算法。DEFLATE的算法复杂度较高但是性能表现优秀适用于比较大型的MCU系统。
2.6. LZ4
LZ4是一种LZ系列压缩算法着重于压缩和解压的速度压缩率相对较低。LZ4压缩率较低算法复杂度和内存消耗中等但是压缩和解压速度尤其是解压速度远超其他算法。因为其综合性能优秀在Linux、Android中的内存压缩技术一般使用LZ4压缩算法。LZ4 HC有着更好的压缩率但是算法复杂度大幅提升且压缩速度也大幅减慢但是依然有着很好的解压速度适合Bootloader这种应用场景。LZ4的内存消耗从几百字节到几十K字节。
3. 基准测试
3.1. 工具用法
RLE ● 测试文件
I:\LinuxRLE.exe d:\a.exe
d:\a.exe
Orignal Size:132096-Compressed Size:125400
Compressed rate:94%● 测试目录
I:\LinuxRLE.exe E:\ATLDemo\Demo\Debug
E:\ATLDemo\Demo\Debug\ATLProject1.exe
Orignal Size:9160192-Compressed Size:7105584
Compressed rate:77%
E:\ATLDemo\Demo\Debug\ATLProject1.map
Orignal Size:19710649-Compressed Size:16943928
Compressed rate:85%Huffman ● 测试文件
I:\LinuxHuffman.exe d:\a.exe
d:\a.exe
Orignal Size:132096-Compressed Size:123772
Compressed rate:93%● 测试目录
I:\LinuxHuffman.exe E:\ATLDemo\Demo\Debug
E:\ATLDemo\Demo\Debug\ATLProject1.exe
Orignal Size:9160192-Compressed Size:7695483
Compressed rate:84%
E:\ATLDemo\Demo\Debug\ATLProject1.map
Orignal Size:19710649-Compressed Size:15878850
Compressed rate:80%LZ77
I:\Linuxlzbench18.exe -elz4 d:\a.exe
lzbench 1.8 (64-bit Windows) Assembled by P.Skibinski
Compressor name Compress. Decompress. Compr. size Ratio Filename
memcpy 35490 MB/s 35924 MB/s 132096 100.00 a.exe
lz4 1.9.2 616 MB/s 4388 MB/s 91011 68.90 a.exe
done... (cIters1 dIters1 cTime1.0 dTime2.0 chunkSize1706MB cSpeed0MB)LZO
I:\Linuxlzbench18.exe -elzo1 d:\a.exe
lzbench 1.8 (64-bit Windows) Assembled by P.Skibinski
Compressor name Compress. Decompress. Compr. size Ratio Filename
memcpy 35442 MB/s 36160 MB/s 132096 100.00 a.exe
lzo1 2.10 -1 150 MB/s 433 MB/s 90130 68.23 a.exe
lzo1 2.10 -99 70 MB/s 415 MB/s 85293 64.57 a.exe
done... (cIters1 dIters1 cTime1.0 dTime2.0 chunkSize1706MB cSpeed0MB)LZ4
I:\Linuxlzbench18.exe -elz4 d:\a.exe
lzbench 1.8 (64-bit Windows) Assembled by P.Skibinski
Compressor name Compress. Decompress. Compr. size Ratio Filename
memcpy 35085 MB/s 34689 MB/s 132096 100.00 a.exe
lz4 1.9.2 615 MB/s 4388 MB/s 91011 68.90 a.exe
done... (cIters1 dIters1 cTime1.0 dTime2.0 chunkSize1706MB cSpeed0MB)I:\Linuxlzbench18.exe -elz4hc d:\a.exe
lzbench 1.8 (64-bit Windows) Assembled by P.Skibinski
Compressor name Compress. Decompress. Compr. size Ratio Filename
memcpy 34462 MB/s 35944 MB/s 132096 100.00 a.exe
lz4hc 1.9.2 -1 79 MB/s 3851 MB/s 81847 61.96 a.exe
lz4hc 1.9.2 -2 79 MB/s 3840 MB/s 81847 61.96 a.exe
lz4hc 1.9.2 -3 69 MB/s 3862 MB/s 81207 61.48 a.exe
lz4hc 1.9.2 -4 63 MB/s 3885 MB/s 80896 61.24 a.exe
lz4hc 1.9.2 -5 59 MB/s 3885 MB/s 80750 61.13 a.exe
lz4hc 1.9.2 -6 56 MB/s 3896 MB/s 80650 61.05 a.exe
lz4hc 1.9.2 -7 53 MB/s 3908 MB/s 80604 61.02 a.exe
lz4hc 1.9.2 -8 51 MB/s 3919 MB/s 80586 61.01 a.exe
lz4hc 1.9.2 -9 47 MB/s 3943 MB/s 80568 60.99 a.exe
lz4hc 1.9.2 -10 29 MB/s 3919 MB/s 80454 60.91 a.exe
lz4hc 1.9.2 -11 22 MB/s 3931 MB/s 80442 60.90 a.exe
lz4hc 1.9.2 -12 20 MB/s 3896 MB/s 80420 60.88 a.exe
done... (cIters1 dIters1 cTime1.0 dTime2.0 chunkSize1706MB cSpeed0MB)DEFLATE
I:\Linuxlzbench18.exe -elibdeflate d:\a.exe
lzbench 1.8 (64-bit Windows) Assembled by P.Skibinski
Compressor name Compress. Decompress. Compr. size Ratio Filename
memcpy 35711 MB/s 36420 MB/s 132096 100.00 a.exe
libdeflate 1.3 -1 92 MB/s 382 MB/s 69917 52.93 a.exe
libdeflate 1.3 -2 88 MB/s 387 MB/s 69425 52.56 a.exe
libdeflate 1.3 -3 85 MB/s 391 MB/s 69207 52.39 a.exe
libdeflate 1.3 -4 81 MB/s 394 MB/s 69085 52.30 a.exe
libdeflate 1.3 -5 70 MB/s 411 MB/s 68098 51.55 a.exe
libdeflate 1.3 -6 67 MB/s 408 MB/s 68034 51.50 a.exe
libdeflate 1.3 -7 62 MB/s 409 MB/s 67972 51.46 a.exe
libdeflate 1.3 -8 22 MB/s 413 MB/s 67138 50.83 a.exe
libdeflate 1.3 -9 17 MB/s 403 MB/s 66693 50.49 a.exe
libdeflate 1.3 -10 16 MB/s 401 MB/s 66627 50.44 a.exe
libdeflate 1.3 -11 13 MB/s 400 MB/s 66604 50.42 a.exe
libdeflate 1.3 -12 10 MB/s 407 MB/s 66598 50.42 a.exe
done... (cIters1 dIters1 cTime1.0 dTime2.0 chunkSize1706MB cSpeed0MB)3.2. 脚本测试
脚本是基于Cygwin环境执行的shell脚本。用法如下
26/01/2024 11:15.41/drives/i/Linux/compression_test.sh
请输入待测目录
e:\ATLDemototal size 297101065 , total compressed size: 210777636
RLE compression rate: 70%total size 297101065 , total compressed size: 205327668
Huffman compression rate: 69%total size 297059235 , total compressed size: 109202247
LZ4 compression rate: 36%total size 296918510 , total compressed size: 115966722
LZO compression rate: 39% 4. 总结
4.1. 性能
● 综合压缩率排名DEFLATE LZ4HC LZO LZ77 Huffman LZ4 RLE。 ● 压缩速度排名LZ4 LZO RLE LZ77 DEFLATE Huffman LZ4HC。 ● 解压速度排名RLE LZ4LZ4HC Huffman LZO DEFLATE LZ77。 ● 算法复杂度排名RLE Huffman LZ77 LZ4 LZO LZ4HC DEFLATE。 ● 算法内存消耗排名RLE LZ4 LZO LZ77 Huffman DEFLATE LZ4 HC。
4.2. 应用场景
不同的压缩算法有不同的应用场景。
高压缩率压缩速度慢但是解压速度快的算法适用于Bootloader。高压缩率可以节省ROM空间高解压速度对Boot速度影响小。因为是外部工具压缩压缩速度不影响Bootloader的功能。适用于此场景的压缩算法有lzo、lz4hc。追求压缩率且算力和内存资源充足并且压缩和解压均不错的算法选择DEFLATE。有一定的压缩率(50%)追求压缩和解压速度且算法相对简单优先LZ4再选择LZ77再先LZO.在一定的压缩率(50%)的基础上追求算法简单优先LZ77。 4.3. LZ77 vs LZ4 ● 如果LZ77的算法复杂度为100则LZ4的为130。压缩和解压C代码LZ77在400行左右LZ4在500行左右。 ● 如果LZ77的内存消耗为100则LZ4的内存消耗为50。LZ77的内存消耗十几K到几十KLZ4的内存从几百字节到十几K字节。 ● 如果LZ77的压缩速度为100则LZ4的压缩速度为700。 ● 如果LZ77的解压速度为100则LZ4的解压速度为800。 总结LZ4的综合性能远优于LZ77。这也是LZ4应用于Linux和Android内存压缩的重要原因。
4.3. 代码
代码
