【ELT.ZIP】OpenHarmony 啃论文俱乐部——电子设备软件更新压缩

2022 年 5 月 22 日
本文字数：7107 字
阅读完需：约 23 分钟

本文出自ELT.ZIP团队，ELT<=>Elite(精英)，.ZIP 为压缩格式，ELT.ZIP 即压缩精英。
成员：
上海工程技术大学大二在校生
合肥师范学院大二在校生
清华大学大二在校生
成都信息工程大学大一在校生
黑龙江大学大一在校生
华南理工大学大一在校生
我们是来自6个地方的同学，我们在OpenHarmony成长计划啃论文俱乐部里，与华为、软通动力、润和软件、拓维信息、深开鸿等公司一起，学习和研究操作系统技术…

@[toc]

【往期回顾】

【本期看点】

HCompress在多层存储环境中大放光彩
揭秘消费类电子设备软件更新压缩算法
AIMCS如何压缩短字符串

【技术 DNA】

【智慧场景】

引言

现实场景

许多消费类产品在市场上流行起来，其中就有类似物联网设备的消费类电子产品。随着消费类电子设备的数量和种类急剧增加，各种软件也开始流行，比如我们常见的微信、抖音。在我们的手机上，经常会出现手机系统需要更新或者某个软件需要更新的情况，这些更新都是通过与互联网连接实现的。但是互联网的带宽有限，而且用户对更新占用时间也有一定的要求，所以如何快速的传输数据并应用更新是一个问题。

图 1 手机系统更新

(a) IPhone 更新

(b) 手机的软件更新

随着 ECU 软件的复杂性和规模的增加，车辆中电气控制单元 (ECU) 中的错误也在增加。联网车辆需要 ECU 软件或安全功能的升级功能。因此，在汽车出场后需要具备通过无线（Over the Air, OTA）重新编程 ECU 的软件功能。因为在软件更新的过程中可能无法驾驶汽车而汽车联网的带宽又非常有限，OTA 更新最重要的问题是减少更新时间。

图 2 车载 ECU 更新

(a) 通过 OTA 进行车载 ECU 升级

(b) 车载 ECU 软件更新系统概述

问题

对于手机等消费类电子设备的更新，可以总结出两个要求：
减少新旧版本之间的代码差异，这是对基于差分压缩算法的更新方案而言，减少代码差异即意味着需要传输和下载的数据量减少。
减少闪存的写入页数，以减少设备设备不可使用的时间。这既要求下载的数据量小，还要求能够快速地将下载好的数据应用到设备上，通常对应数据解压和闪存写入所需的时间。
对于车载 ECU，又有以下需求：
减少软件更新时间，这是压缩算法主要解决的问题。
保证软件更新的完整性。在许多情况下，ECU 软件控制车辆运行，所以为了安全考虑需要完整性。
将软件更新的的风险降到最低。因为通过 OTA 更新时数据可能会被👂窃👂听👂和操纵。
还有一些其他问题将会在下文具体算法中阐述。

相关算法

基于差分压缩算法的解决方案

在进行软件更改时，很多情况下会删除和添加一些代码，如图 1 所示。也有很多情况是更改了一些代码。但是，可以通过删除旧代码并添加新代码来处理这种情况。因此，如下图所示，二进制差分更新可以用两个命令实现。

图 3 二进制差分

更加具体的实现方式可以由下面介绍的增量表示格式解释

增量表示格式

我们用以下五种命令的迭代使用实现增量表示的具体过程：

DATA 命令当新旧版本的内容完全不同时，需要对新数据进行描述。 DATA 命令本身代表即将到来的数据的大小，然后是指定长度的数据。
SKIP 命令新版本和旧版本的内容和地址位置相同的部分可以通过 SKIP 命令一起表示。这指定了不需要在闪存中覆盖的部分的大小。
COPY 命令新旧版本仅在代码位置不对齐时不同的部分可以使用 COPY 命令表示。可以通过从旧版本移动数据的位置来创建新版本；指定要复制的数据的起点和大小。
FORCED-FLUSH 命令此命令指定将数据写入闪存，与 RAM 中的增量相对应的数据写入闪存。执行此命令后，我们保证不会有 COPY 命令试图引用已被覆盖为相应旧版本的内存。
END 命令这表明已经到达增量的末端。

下面通过一个例子直观的感受上述命令的使用：

图 4 新旧软件版本之间的差异实例

第一块代码没有发生改变，所以需要使用 SKIP 命令跳过，而且需要指定跳过的部分的大小，这里为0x100；新版本在第一块和第二块中新加了一块代码，由于是旧版本不存在的内容，所以用 DATA 命令添加，大小为0x30；接下来用 COPY 命令将旧版本的第二块代码拷贝过来，起点为0x1100，大小为0x100；接下来还是用 COPY 命令把旧版本的第三块代码拷贝过来，起点为0x1250，大小为0x100。所以用命令表示上图为：

SKIP 0x100DATA 0x30, 这里是需要写入的代码COPY 0x1100, 0x100COPY 0x1250, 0x100

复制代码

所以要将旧版本更新为新版本，用这样一段代码即可完成表示，且实际的增量主要由 SKIP 命令、COPY 命令和 DATA 命令的个数决定

。如果设 SKIP，COPY 和 DATA 的次数分别为 s，c 和 d，命令本身可以用一个字节表示，位置信息需要 a 个字节，大小信息需要 n 个字节，而 DATA 的数据长度其实可以由写入的代码的长度决定，假设平均新增的代码长度为 l，那么增量代码占用的大小为：

d s i z e = (a + n + 1) c + (n + 1) s + (l + 1) d

RSYNC

下面我们介绍一种常用的利用增量思想的文件同步算法——rsync。该算法应用于同步两个相似的文件，主要思想为，通过一些方法找到文件中变化的部分，只传输有差异的数据，从而大大减小数据传输时间。

问题

如果我们要同步的文件只想传不同的部分，我们就需要对两边的文件做diff，但是这两个问题在两台不同的机器上，无法做 diff。如果我们做diff，就要把一个文件传到另一台机器上做diff，但这样一来，我们就传了整个文件，这与我们只想传输不同部的初衷相背。于是我们就要想一个办法，让这两边的文件见不到面，但还能知道它们间有什么不同。rsync算法解决的就是这个问题。

算法描述

假设我们有 A 和 B 两台计算机，A 可以访问文件 X，B 可以访问文件 Y，X 和 Y 两个文件的内容是相似的。

B 将文件 Y 依次拆分为互不重叠的大小为 S 字节的块，最后一块大小可以小于 S；
对于 Y 的每一个块，计算两个校验和：32位的弱“滚动”校验和与128位的强MD5校验和；
B 将这些校验和发送给 A；
A 搜索 X 文件以查找长度为 S 的块（任意偏移量），这些块与 Y 一样有对应的弱校验和、强校验，具体过程可以在rsync 的核心算法里找到；
A 向 B 发送构建 X 的指令，指令可能是对文件 Y 块的引用，也可能是一些文本数据。仅针对与 Y 的任何块不匹配的 X 部分发送文本数据。

最终结果是获取 X 的副本，但 Y 中找不到 X 片段（加上校验和和块索引的少量数据）通过链接发送，该算法也只需要一次往返。

BPE 算法及其改进

BPE（Byte Pair Encoding，字节对编码） 是一种基于字典的数据压缩算法，可以与差分压缩相结合应用于软件更新的数据压缩和解压。

图 5 使用 BPE 更新消费类设备中的软件
如上图所示，先通过比较新旧版本的代码获得二进制差分数据，然后通过 OTA 等无线方式发送到目标设备。在设备中，先将旧版本解压（旧版本的代码存储在闪存中，在需要时从闪存中解压至 RAM），这个过程速度很快，然后将二进制差分数据应用到旧版本的代码中获得新本的代码，最后将新版本的代码压缩，存储到闪存，这是一个很慢的过程，而且由 BPE 算法的实现过程决定。
BPE 的过程是通过迭代实现的：在当前文本中寻找出现次数最多的字节对，然后用一个字节将其替换，要求是这个字节在之前的文中不存在，将这一替换应用至整个文本，然后重复执行。BPE 算法的输出是压缩后的数据和用于提取的字典。下面用一个例子展示这一过程：

压缩的结果为“XZZEFYEFFG”和对应的字典{"Z": "YD", "Y": "XC", "X": "AB"}

之前提到在压缩新版本的代码会耗费大量时间，所以出现了一种改进的算法，想法非常巧妙：通过 BPE 算法过程我们可以看出构建字典时寻找出现次数最多的字节对是导致算法时间复杂度大的原因，如果省去这一过程，就可以快速压缩。所以，我们在向设备发送二进制差分数据的同时把新版本代码的字典也发过去，这样在设备上获得新版本代码后可以使用这个字典快速压缩。而且，这个字典可以由开发端压缩一遍新版本代码获得。下图表示的是改进后的代码：
图 6 使用改进的 BPE 更新消费类设备中的软件

基于字典压缩算法的解决方案

上面的 BEP 是基于字典压缩的解决方案的一个例子，但是对于车载 ECU 的软件更新，还有其他的问题需要考虑。手机、平板等消费类电子设备的 RAM 空间普遍较大，但是普通的 ECU 却没有足够的 RAM，在某些情况下 RAM 的大小小于闪存擦除块的大小，这是很难将差分技术用到此类 ECU。
在基于差分/增量的压缩方案中，虽然发送的差分数据较小，但是如果需要把旧版本的代码从闪存中读取至 RAM 中应用差分数据得到新版本代码，这个过程要求 RAM 有足够的空间存储闪存擦除块大小的数据，因此，对于 RAM 大小小于闪存擦除块的 ECU，差分数据/增量无法应用到旧版本的代码上，也就无法更新。

图 7 RAM 和擦数块大小的关系
RAM 的大小小于擦除块的大小有两种情况，1）RAM 太小，2）擦除块太大，对于第 2 种情况，可以应用压缩技术，因为压缩的数据可以在 RAM 上展开。接下来我们先需要较小工作空间的几种压缩算法。

几种压缩算法的比较

表一典型压缩算法的比较

表一显示了四个压缩算法的典型类型。在此表中，我们从压缩比、所需工作内存和扩展（解压缩）速度三个方面对算法进行了比较。Bzip2是一种著名的通用的好的压缩算法，用于 bsdiff。Deflate和LZMA2以其良好的压缩比和扩展速度而闻名。BPE是扩展速度最快的算法之一。这是一些典型的算法，也有许多类似的算法。

bzip2由块排序和 Huffman 编码组成，它有较好的压缩比，但是需要的工作内存较大，不符合我们的目的；
Deflate由 LZ77 和 Huffman 编码组成，它的压缩比比 bzip2 差，但是工作内存和扩展速度都很好；
LZMA2基于 LZ77 和区间编码，需要时间来编码；我们尝试评估它们是否可用于 ECU。用这些算法对样本代码数据进行压缩，示例目标软件是TOPPERS/ASP，ARM 版本为 1.9.0。表二显示了每种算法压缩前后的数据量。其中，LZMA2 压缩比最佳。Bzip2 和 Deflate 可以理解为具有相同的压缩比。BPE 的压缩比没有其他的好。

表二压缩前后的数据量

图 8 显示了每种算法的压缩比和所需的工作内存。从这个图中可以看出，BPE 需要的工作内存最少。但是，它的压缩比是最差的。从这个结果来看，Deflate 适用于具有 RAM 大小限制的 ECU。

图 8 工作内存大小和压缩比

Deflate 算法的改进

Deflate 算法解压过程所需的工作内存取决于压缩数据量，因此，如图 9 所示的分割压缩可能会减少工作内存。压缩数据由独立压缩的分割压缩数据组成。每个压缩数据的大小取决于工作内存的大小。但是，划分数据会涉及时间开销，因此，应该评估速度和内存之间的权衡。

图 9 划分数据压缩<br>

对工作内存和压缩比的评估

对于分割压缩，根据工作内存的大小和压缩比评估了 Deflate。图 10 和图 11 展示的是对一个软件两个版本进行 Deflate 解压时的工作内存和压缩比情况。

图 10 每个压缩数据量限制的工作内存大小和压缩比：TOPPERS/ASP，版本 1.7.0

图 11 每个压缩数据量限制的工作内存大小和压缩比：TOPPERS/ASP，版本 1.9.0

从图中数据可以看出，最佳情况下的压缩比（压缩比越大越好）需要 480 KB 的工作内存。

对传输时间的评估

比较压缩数据和未压缩数据的传输时间。用 10 个 ECU 做实验，假设其中一部分 ECU 无法通过增量算法进行更新。设更新数据的数据量为

U_{s i z e}

，CAN 的比特率为

N e t_{b i t r a t e}

，传输所需的时间为 T，则：

T = \frac{U _{s i z e}}{N e t _{b i t r a t e}}

我们假设 TOPPERS/ASP 的 1.7.0 版本更新到 1.9.0 版本，并且 CAN 比特率为 500 Kbps 进行评估。如图 12 所示，压缩和未压缩数据之间的差异随着无法通过增量更新的 ECU 数量线性增加。

图 12 传输时间的比较

在评估环境中，无法通过增量更新并通过压缩更新的所有 ECU 的传输时间是可以通过增量更新的所有 ECU 的传输时间的五倍。

基于相同字典的改进算法

图 13 通过压缩数据进行软件更新

图 13 显示了使用通用压缩技术更新设备的流程。更新的代码被下载并存储在 RAM 中。提取后，数据被写入到被清除的擦除块上。在这种情况下，可以通过对整个过程的不同部分重复这个过程来更新大量的代码。

在上面的讨论中，我们发现基于 LZ77 的 Deflate 适用于对更新数据进行压缩，下面我们会讨论基于 LZ77 的另一种算法——Zstandard。

算法

LZ77 将字符串位置和长度替换为相同字符串先前出现的详细信息。如果没有类似的字符串，则不替换。搜索字符串的区域称为窗口，它会逐渐滑动。字典由引用的字符串组成。
图 14 显示了所提出的方法，它是原始 LZ77 的改进版本。在出厂前，旧版本的代码会写入闪存中。旧版本是压缩的，用于提取的字典也写在闪存上，并随旧版本一起提供。

图 14 常规方法（构建新词典）和改进方法（使用旧词典）的数据压缩

当需要软件更新时，将使用旧词典压缩软件的新版本，该词典与旧版本一起保存在附带的设备上。在压缩数据下发后，如图 14 所示，对旧版本进行压缩。将第二个字符串“ABC”替换为词典中第一个字符串“ABC”的位置和长度。
提取和压缩的词典的格式应该不同，用于压缩的词典应该有索引等。但是，在本研究中，两个不同格式的词典被视为同一个词典，因为它们只是格式不同。
在图 14 中，字符串“ABC”在预设词典（旧词典）中。然后，将新代码中引用字符串“ABC”的符号替换为“ABC”。使用这种方法，压缩比小于常规方法，如图 14 下部所示。新符号“D”被添加到旧版本中。预设字典中没有符号“D”，但是传统的压缩方法生成一个新的字典，其中包含符号“D”，可以获得更好的压缩比。
没有词典的压缩数据必须使用我们提出的方法下载，必须使用常规方法下载带有新字典的压缩数据。这是两种方法之间的权衡。此外，所提出的方法需要额外的闪存。闪存的大小也是两种方法之间的权衡。

图 15 软件更新的流程
图 15 表示软件更新从初始装运到在目标设备上生成新软件的流程。我们将发货版本定义为旧版本。软件更新表示旧版本已被新版本替换。出厂前，旧版本在工厂通过基于 LZ77 的算法进行压缩。然后，从压缩数据中提取用于提取的字典部分。未压缩的软件代码和用于提取的词典都写在出厂设备的闪存上，此词典用在之后于提取新数据。
在软件更新期间，新版本在工厂使用旧词典进行压缩。下载不带词典的压缩软件，在目标设备上，使用闪存上的（旧）字典从 RAM 中提取新软件。擦除块上的旧代码被擦除，RAM 上的新代码被写入到块上。

实验与评估

实验

将改进算法应用于 Toppers软件中的Advanced Standard Profile内核，我们准备了四个版本，编号从 1.9.0 到 1.9.3。每个版本的二进制代码大小如表三所示。

表三用于评估的数据

将 1.9.0 看作最初的版本，测量传统方法和我们提出的方法的压缩比和多次更新的压缩比。

评估

压缩比

表四显示了使用常规方法和改进的方法对每个版本进行压缩后的压缩比。预设字典的大小为 31304 字节。这本词典包括所有字符串和索引。因此，其大小大于原始数据的大小。
使用所提出的方法压缩比非常有效；但是，它需要额外的闪存空间。这是权衡。如果闪存太小，字典的大小就会受到限制。在这些情况下，短长度的字符串或仅被引用几次的字符串被省略以减小字典的大小。但是，数据的大小比原始方法的结果要大。

表四比较压缩比

多次更新

设备的软件更新可能会重复应用。对于 PC 或手机软件，新版本会多次发布。因此，我们应该假设会有多个更新。如果使用二进制差分技术，则没有问题，因为连续版本之间的差异通常很小。然而，我们提出的方法使用初始版本的字典。因此，差异与版本号成比例地变大。也就是说，更新数据与版本号成比例地变得更加重要。
表四显示压缩比的增加是线性的。然而，在某些情况下，更新时间可能并不重要。图 16 显示了版本号和字典压缩比之间的关系。