请选择 进入手机版 | 继续访问电脑版

硬汉嵌入式论坛

 找回密码
 立即注册
查看: 7320|回复: 5
收起左侧

[embOS] 【技术贴】解读SEGGER最新一篇博文《适用于MCU的高效压缩算法,DEFLATE,LZMA,LZJU90,LZ4和SMCS的性能PK》

[复制链接]

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105914
QQ
发表于 2018-1-17 15:05:04 | 显示全部楼层 |阅读模式
SMCS名词解释:Small Microcontroller Compression Scheme 微控制器压缩方案,文章中SEGGER将自己搞的解压缩算法称之为SMCS。

SEGGER之所以可以一直在嵌入式领域保持领头羊,是因为我们不满足现有方案,we can always do better!当前我们自己的压缩库emCompress可以实现:
1. 超快速解压缩
2. 高压缩比(压缩前大小/压缩后大小)
3. 占用空间小
4. 简单易用
使用SMCS可以像DEFLATE无算压缩一样高效,简单几个状态就可以实现高压缩比,超快速的压缩。

一、为什么做这个?
在讨论我们的链接器和压缩库emCompress的未来的方向时,我们研究了可以改进的所有地方和可以改进emCompress的可能性,并将改进后的emCompress应用到我们自己的链接器SEGGER Linker里面。公司的宗旨是能使用自己的产品肯定使用自己的产品。这里将其放到链接器里面,作用是将压缩到Flash中的数据,在系统上电后复制到RAM区。当我们改进emCompress时,我们也改进了SEGGER Linker。

二、LZSS算法,无处不在
标准压缩方案(如DEFLATE,LZMA,LZJU90和LZ4)使用LZSS风格的内核将输入字符串解析为文字和匹配流。所有这些算法之间的主要区别在于文字的编码的方式以及由于这种编码而对匹配的距离和长度的限制。

标准编码算法简介:
基于LZSS的编码器需要使用额外的压缩方案来减少文字,距离和长度:
(1)简单的二进制编码不会减少文字,距离和长度,完全依赖解析器来检测冗余。
(2)DEFLATE使用两个独立的动态霍夫曼编码,一个编码长度,另一个编码距离。
(3)LZJU90使用两个面向位的前缀编码,用于距离和未压缩文字长度。
(4)LZ4使用面向字节的前缀编码来计算距离和未压缩文字长度。
(5)LZMA使用一个单一的范围编码器对文字,距离和长度进行编码,在编码时动态调整其概率模型。

现在让我们来看看那个更适合MCU。

1. Plain Binary压缩算法
固定宽度的二进制来编码距离和长度不会产生出色的结果,但速度快,解压缩时不需要额外的状态存储器,因此它不符合“良好的压缩”要求。

2.  DEFLATE压缩算法
DEFLATE提供了很好的压缩效果,解压缩只需要几KB的RAM。不幸的是,使用两个霍夫曼编码进行解压缩相当复杂,这两个霍夫曼编码本身是用典型霍夫曼编码编码的。 这是一个聪明的解决方案来压缩匹配距离和长度,它甚至压缩文字,LZ4和LZJU90没有。指定DEFLATE的最小匹配长度为三个字节。 按理说,相比长度为3字节的匹配,2字节的匹配更多。 通过实验,使用非标准的最小匹配长度为2而不是3会导致更差的压缩,所以默认是最好的选择。我们可以将DEFLATE作为一个候选对象,但解码过程非常复杂(大约800行C代码)。

3. LZMA压缩算法
毫无疑问,LZMA提供优秀的压缩。它的最小匹配长度为2, 能够有效地压缩需要非常大的表,从6KB到6MB。不幸的是,解码器需要保持与编码器相同的模型,所以解码也需要从6KB到6MB。这不仅是内存不足,解码器也非常复杂,不适合汇编编码:emCompress中的LZMA解码器大约有1000行代码,不包括emCompress库代码。单单解码器的复杂性足以立即拒绝,因为太复杂而且巨耗RAM。它所做的是证明两个字节与高效编码的最小匹配比三个字节的最小匹配压缩更好。

4. LZJU90压缩算法
该方案使用长度和距离的前缀编码,而文字未压缩。距离和长度的前缀编码方案是不同的,被调整到有限的匹配长度(3到256)和距离(1到32255)。虽然LZJU90很简单,而且代码量也很小,不需要复杂的解码器状态,但压缩效率不如DEFLATE,这是我们的目标之一。 因此,我们必须拒绝LZJU90作为候选,但它确实为新方案提供了基础。

5. LZ4压缩算法
LZ4针对速度进行了优化,牺牲了压缩能力:最小匹配长度为4,因此不可能生成良好压缩的图像。它不需要额外的复杂的解码状态,并有一个简单的解码器。 但是对于我们来说,LZ4的字节前缀编码方案可能被拒绝,因为它不符合“优秀的压缩”要求。当然,必须有一个使用LZSS方案的现代编码器,而且在超小解码代码量的情况下可以达到非常好的压缩效果。

6. SMCS压缩算法
通过上面几个方案的介绍,实现一个高效的压缩方案如下:
(1)发现短匹配比长匹配要常见得多,而LZMA则表现出极好的压缩效果,最小匹配长度为两个字节。因此,我们需要两个字节的最小匹配长度,而不是三个或四个,以尽可能多地找到可能的匹配,并有效地编码短匹配。
(2)没有复杂的区间编码器或霍夫曼编码,因为它们将大的RAM状态引入到解码器中,同时增加了解码器的复杂性,因此ROM占用空间更大。
(3)编码无限长度和距离必须是可能的,以便复制远距离匹配。
(4)LZJU90的前缀编码方案提供了相当好的长度和距离压缩,但有限的前缀编码不适用于两字节的最小长度和无限的长度以及距离值。
(5)对于随机二进制数据(例如机器码),压缩文本不应该是必需的,并且我们假定文字数据的每个字节具有相等的发生概率。这是一个假设,但是一个有效的假设。

我们决定在我们的SMCS算法中使用受LZJU90启发的前缀编码。匹配长度为2到4个字节,这是非常常见的,特别是高密度(只有两个比特)编码,长度更长,使用修改的前缀编码,其中“继续/结束”标志是中缀而不是前缀,并且始终存在(不像LZJU90)。距离编码具有为这些值优化的相似风格的前缀编码。使用一组标准的基准输入,其中一些从SEGGER链接器中的典型链接目标代码中提取出来,我们决定采用一个能够提供出色结果的方案。下面是SEGGER Linker的一个例子,当压缩大约50K在RAM中运行的代码和数据时,结果如下:
LZMA:       30,704 bytes,   60.4% of original
DEFLATE:  32,592 bytes,   64.1% of original
SMCS:       32,878 bytes,   64.7% of original
LZJU90:     34,793 bytes,  68.4% of original
LZ4:          38,175 bytes,  75.1% of original


尽管这是一个单一的样本,但它让每个方案的测试都有代表性。当然,一些压缩算法在特殊数据方面会表现的很好,而另外一些压缩算法则不太好。然而,SMCS实现了与DEFLATE相媲美的整体压缩,同时更简单并且需要更小的解码器状态。 SMCS和DEFLATE的交易地点取决于输入数据,但在相同的数据集中通常在1%以内,0.5%是常见的。虽然SMCS并不像LZMA那样高效,但是由源代码复杂程度要低一个数量级,并且不需要以KB甚至MB为单位测量解码状态来进行高效压缩。

三、下一代SMCS
通过调整找到匹配的字符串解析器,有可能进一步提高SMCS的压缩效率,尽管通过主流编码获取灵感仍然是快速和有效的。 但没有用心努力,不可能有效地找到最佳的编码。对字符串解析器,压缩器和我们在这里没有描述的编码格式还有一些其他的调整,没有什么是革命性的,这些都进行了优化后,最终的优化效果就非常明显了。

四、总结:
SMCS压缩良好,解码速度快,只需要将几个字的解码器状态需要保存。 它具有比LZJU90和LZ4更好的压缩比,并且与DEFLATE相媲美。SMCS非常适合目标体积最小的解压缩,并将被添加到Embedded Studio的SEGGER链接器和启动代码中,用于启动过程中将常量和代码复制到RAM中,以及压缩软件emCompress。

评分

参与人数 1金币 +10 收起 理由
在水一方 + 10 很给力!

查看全部评分

回复

使用道具 举报

0

主题

38

回帖

38

积分

新手上路

one is enough

积分
38
发表于 2018-3-9 17:27:07 | 显示全部楼层
mark!~~辛苦硬汉了~
one is enough
回复

使用道具 举报

0

主题

1

回帖

1

积分

新手上路

积分
1
发表于 2022-6-8 11:40:21 | 显示全部楼层
问一下老师   “SMCS”这个压缩算法的源码哪里可以找到?
回复

使用道具 举报

5

主题

196

回帖

211

积分

高级会员

积分
211
发表于 2022-6-8 23:11:05 | 显示全部楼层
之前基于GCC/Clang做了一套类似的固件压缩跟加载机制,常见的rw image压缩比在20%左右,固件的二进制可以减少几K到几十K不等的空间:https://github.com/AlexYzhov/rwcompression
补完文档单独发个贴跟大家分享一下。
回复

使用道具 举报

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105914
QQ
 楼主| 发表于 2022-6-9 09:03:20 | 显示全部楼层
bf53721 发表于 2022-6-8 11:40
问一下老师   “SMCS”这个压缩算法的源码哪里可以找到?

SEGGER这个源码没有开源。
回复

使用道具 举报

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105914
QQ
 楼主| 发表于 2022-6-9 09:03:28 | 显示全部楼层
alexyzhov 发表于 2022-6-8 23:11
之前基于GCC/Clang做了一套类似的固件压缩跟加载机制,常见的rw image压缩比在20%左右,固件的二进制可以减 ...

谢谢分享。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|Archiver|手机版|硬汉嵌入式论坛

GMT+8, 2024-3-29 00:23 , Processed in 0.220600 second(s), 26 queries .

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2023, Tencent Cloud.

快速回复 返回顶部 返回列表