差分升级 OTA

在传统 OTA升级流程中，固件包往往是整个镜像。哪怕进行压缩后，体积也会比较大，因此在一些低带宽场景下会有较大的传输压力。

为了解决下载速度慢与固件体积大的问题，后续提出了差分升级方案，例如bsdiff、xdelta、hdiffpatch等差分算法。

1. 差分与全量的区别

1.1 全量流程

对于传统的全量升级流程，大致可以概括为：

1. 编译生成固件。

2. 对固件进行签名、压缩。

3. 发布版本。

对于设备端，则是接收完整固件，然后进行校验和升级。

1.2 差分流程

对于差分升级，在生成新固件后，需要先将新固件与旧固件进行比较，提取差异点，再将这些差异点制作成固件包。因此，差分包中只包含本次版本相较旧版本新增或变更的内容，所以差分升级也称为增量升级。

后续流程与传统 OTA 差别不大，仍然包括签名、压缩、发布，甚至由于差异包足够小，在某些场景下可以不再压缩。

在设备端升级时，则是根据差异包对旧固件进行增删改，从而还原出新固件。

2. 主流开源的差分算法

2.1 bsdiff

核心思想：通过后缀数组，将旧文件所有子串进行排序；在扫描新文件时，可以快速定位最长匹配片段，仅保存差异部分与引用关系。

下面以一个字符串示例进行解释：

• 旧文件：abcdabef

• 新文件：abcdxabef

2.1.1 构建索引：对旧文件按后缀进行字典排序，生成后缀数组

字符串长度为 8，因此一共有 8 个后缀，即从每个字符开始直到末尾的子串。

字典序规则如下：

• 从左到右逐个比较字符的 ASCII 码，字符小的排在前面。

• 如果某个后缀是另一个后缀的前缀，那么较短的那个排在前面。

先按首字母分组：

• 首字母 a：索引 0（abcdabef）、索引 4（abef）

• 首字母 b：索引 1（bcdabef）、索引 5（bef）

• 首字母 c：索引 2（cdabef）

• 首字母 d：索引 3（dabef）

• 首字母 e：索引 6（ef）

• 首字母 f：索引 7（f）

对首字母相同的组继续比较：

• a组：

  • abcdabef vs abef

  • 第 1 字符：a = a

  • 第 2 字符：b = b

  • 第 3 字符：c vs e，因为 c < e，所以 abcdabef < abef

  • 顺序为：索引 0 -> 4

• b组：

  • bcdabef vs bef

  • 第 1 字符：b = b

  • 第 2 字符：c vs e，因为 c < e，所以 bcdabef < bef

  • 顺序为：索引 1 -> 5

其余分组只有一个元素，因此天然有序。

按字典序从小到大列出后缀，并记录它们的起始索引：

后缀数组（Suffix Array）就是这些起始索引按排名顺序组成的数组：

2.1.2 扫描新文件，查找最长匹配块

新字符串长度为 9，因此索引范围为 0~8。初始化一个指针：i = 0。

第 1 步：从位置 i = 0 开始匹配

取新文件从 i = 0 开始的子串 abcdxabef，需要在旧文件中找到最长公共前缀。

如何利用后缀数组查找最长匹配？

想找以 a... 开头的匹配，就在 SA（Suffix Array，后缀数组）中找到所有以 a 开头的后缀，即：排名 1（索引 0）和排名 2（索引 4）。

分别比较两个候选：

候选 A：旧文件索引 0，对应字符串 abcdabef

逐字节与新文件比较：

得到匹配长度为 4。

候选 B：旧文件索引 4，对应字符串 abef

逐字节比较：

匹配长度为 2。

因此，最长匹配长度为 4，来自旧文件位置 pos = 0，匹配内容为 abcd。

第 2 步：输出指令并移动指针

发现匹配长度 len = 4，bsdiff 会输出一条 COPY 指令：

表示从旧文件偏移 0 处复制 4 个字节。

匹配结束后，新文件指针 i 从 0 移动到 4。

第 3 步：处理不匹配位置（i = 4）

此时新文件 new[4] 是字符 x。

在旧文件中尝试匹配从 x 开始的后缀，但旧文件中没有任何以 x 开头的后缀，因此最长匹配长度为 0。

这时 bsdiff 会输出 ADD 指令，也可理解为 INSERT：

表示将单个字节 x 直接作为 extra 数据加入。

然后指针 i 从 4 移动到 5。

第 4 步：从位置 i = 5 继续匹配

新文件从索引 5 开始的子串为 abef。

再次在后缀数组中查找以 a 开头的后缀。这里候选依然是索引 0 和索引 4。虽然索引 0 之前已经参与匹配，但 bsdiff 并不禁止重复引用旧文件中的位置。

比较候选旧索引 4 的字符串 abef：

完全匹配，长度为 4。

于是输出：

表示从旧文件偏移 4 处复制 4 个字节。

此时指针 i 从 5 移动到 9，已经到达新文件末尾，扫描结束。

最终生成的指令序列为：

2.1.3 生成 diff 与 extra 块

需要将指令序列转换为 bsdiff 实际存储的控制流。其控制流由一系列三元组组成，每个三元组含义如下：

• x：本次从旧文件中匹配的字节数，也就是COPY的长度。

• y：本次从 extra 块中读取的额外字节数，也就是ADD的长度。

• z：本次匹配结束后，旧文件指针需要向前移动的距离，即相对于当前指针的偏移，用于跳过已经匹配的旧数据。

旧文件指针初始化为 0。每处理完一个条目后，指针会先执行 += x，然后再额外加上 z。其中 z 是有符号整数，因此可以为负。

确定 z 的规则

在 bsdiff 的原始算法中，当找到一个匹配块后：

• 新文件指针前进 x 字节。

• 旧文件指针也前进 x 字节。

但有时你希望下一次匹配从旧文件的其他位置开始，而不是紧接着当前匹配块的末尾，此时就需要通过 z 来调整。

对于 COPY 指令，通常 z 设置为：

在这个简单顺序扫描的示例中，z 几乎总为 0，因为没有刻意让旧文件指针发生跳跃。

逐条分析如下：

条目 1：COPY 0,4

• 从旧文件偏移 0 匹配 4 字节。

• 旧文件指针从 0 移动到 4。

• 下一个条目是 ADD，不消耗旧文件数据。

• 再下一个匹配条目需要从旧文件偏移 4 开始，而当前旧文件指针正好是 4。

• 因此此处 z = 0。

条目 2：ADD 'x'

• 匹配长度 x = 0。

• 额外长度 y = 1。

• 旧文件指针不变，因为没有读取旧文件。

• 下一个匹配期望从偏移 4 开始，而当前旧指针已经是 4。

• 因此 z = 0。

条目 3：COPY 4,4

• 匹配长度 x = 4。

• 额外长度 y = 0。

• 匹配后旧文件指针从 4 移动到 8。

• 没有后续条目，因此 z 通常也设为 0。

于是控制流三元组序列为：

注意：实际 bsdiff 对最后一个条目的 z 并不敏感，但通常也会设为 0。

生成 diff 块

diff 块由每个匹配条目的“旧文件字节 XOR 新文件字节”顺序拼接而成。

条目 1：x = 4，旧字节取自 old[0..3] = "abcd"，新字节取自 new[0..3] = "abcd"。

逐字节异或：

因此 diff 块增加：

条目 2：匹配长度 x = 0，没有 diff 数据。

条目 3：x = 4，旧字节取自 old[4..7] = "abef"，新字节取自 new[5..8] = "abef"。

异或结果同样全为 0，因此 diff 块再增加：

最终 diff 块为：

也就是 8 字节，全为 0。

生成 extra 块

extra 块由每个 ADD 指令中无法匹配的新文件原始字节顺序拼接而成。

条目 2 中：

• y = 1

• 字节为 x，ASCII 为 0x78

因此最终 extra 块为：

也就是 1 个字节。

最终的差分包结构为：

2.1.4 差分包还原

解压后得到控制流、diff块、extra块。

依次处理每个三元组：

1. 从旧文件当前位置读取 x 字节，与 diff 块中接下来的 x 字节异或，得到新文件数据。

2. 从 extra 块中读取 y 字节，直接追加到新文件。

3. 旧文件指针执行 += x + z，为下一次读取做准备。

按照上面的例子还原：

最终得到：

2.1.5 bsdiff 的思考与原理哲学

如果只看表面，bsdiff 像是在做一件很“机械”的事：找匹配、写控制块、保存 diff 和 extra。但从算法哲学上看，它其实体现了一种很鲜明的设计取向：尽量把“变化”压缩到最小，把“不变”表达得尽可能精确。

这种思路背后有三个很重要的判断。

第一，版本升级中的大多数字节其实并没有真正“消失”，它们只是发生了位移、替换或局部修改。

bsdiff 的核心不是问“新文件是什么”，而是问：

这就是为什么它要花较大代价去构建后缀数组、寻找全局长匹配。它相信：只要匹配找得足够好，补丁就会非常小。

第二，bsdiff 不是直接存“新文件内容”，而是在存“旧文件如何被修正成新文件”。

这里最有代表性的不是 extra 块，而是 diff 块。

diff 块的意义在于：

• 如果一段数据整体结构没变，只是某几个字节不同，直接存整段新数据很浪费。

• 更合理的方式是保留旧数据，只存“需要修正的差值”。

所以从思想上讲，bsdiff 是在把“新版本”分解为两部分：

• 一部分是“旧版本仍然有效的骨架”。

• 另一部分是“附着在骨架上的微小修正”。

这是一种非常偏“信息论”的视角：补丁不是第二份文件，而是一份关于变化的信息。

第三，bsdiff 愿意用更重的编码计算，换取更小的传输成本。

• bsdiff 更像在说：我可以编码得慢一点、复杂一点，但补丁包要尽可能小。

所以如果从工程哲学上概括，bsdiff 更像一种：

的策略。

这也解释了它为什么特别适合 OTA、固件升级、移动端分发等对流量敏感的场景。在这些场景中，CPU 多做一点事往往可以接受，但多传几兆数据的代价却非常真实。

再往深一层看，bsdiff 的价值不只在“补丁更小”，还在于它隐含了一种工程观：

• 网络通常比 CPU 更昂贵。

• 发布系统最需要优化的是“变化量”，不是“最终量”。

• 真正高质量的升级系统，不是重复发送完整状态，而是高精度描述状态转移。

因此，bsdiff 的哲学可以概括为一句话：

不去重新发送一个新世界，而是尽量精确地描述，旧世界需要怎样变化，才能抵达新世界。

2.2 xdelta（xdelta3）算法详解

xdelta 是一系列开源二进制差分工具的统称，其中最成熟、使用最广泛的是 xdelta3。

它的核心思想可以概括成一句话：把旧文件当作字典，在扫描新文件时不断寻找“可以直接复用”的字节串，再把重建过程编码成 ADD、COPY、RUN 三类指令，最终按 VCDIFF / RFC 3284 格式输出。

与 bsdiff 更强调“后缀数组 + 全局最长匹配”不同，xdelta3 更像一个“面向差分场景的字典压缩器”：

• 它不追求绝对最优匹配。

• 它追求的是在压缩率、速度、内存占用之间取得更好的工程平衡。

• 它天然适合大文件、流式处理和标准化补丁格式。

下面按“名词解释 -> 处理流程 -> 具体算例”的顺序展开。

2.2.1 先把几个关键名词讲清楚

在阅读 xdelta3 时，最容易混淆的是“规范里的概念”和“实现里的概念”。先统一术语。

1. source（源文件 / 参考字典）

通常就是旧文件。编码器会尽量把新文件中与它相同的内容表示成“从这里复制”。

2. target（目标文件）

就是要恢复出来的新文件。差分包真正描述的是“如何把它构造出来”。

3. window（窗口）

无论是源文件还是目标文件，都可以按窗口处理。窗口的意义是：

• 控制内存占用。

• 支持流式编码和流式解码。

• 让超大文件不必一次性全部装入匹配结构。

4. literal（字面量）

指在字典里找不到合适匹配、只能原样写入的数据。它最终会变成 ADD 指令的数据载荷。

5. match（匹配块）

指在源文件或当前目标窗口已生成部分中找到的相同字节串。它最终通常会被编码成 COPY。

6. instruction（指令）

VCDIFF 只定义三种基本动作：

7. VCDIFF

这是 RFC 3284 规定的标准差分格式。它只规定“差分包应该怎样存”，并不强制编码器必须采用哪一种匹配算法。

所以要区分两层：

• VCDIFF 解决的是“格式问题”。

• xdelta3 解决的是“怎么找匹配、怎么生成这些指令”的实现问题。

2.2.2 xdelta3 的总体处理框架

把整个过程抽象起来，xdelta3 大致分为三层：

1. 窗口化（Windowing）
   把目标文件切成若干窗口，每个窗口独立生成一个增量窗口记录。

2. 字符串匹配（String Matching）
   在每个窗口内，用哈希表快速定位与源文件或目标前缀相同的字节串。

3. 指令编码（Instruction Coding）
   将匹配结果转成 ADD / COPY / RUN，再按 VCDIFF 规范写入数据区、指令区和地址区。

可以画成下面这个流程：

最后把多个 VCDIFF Window 顺序拼接起来，就得到完整的差分文件。

2.2.3 第一步：窗口化（Windowing）

xdelta3 不要求一次性把整个目标文件全部放进内存。它会把目标文件切成若干个窗口，每个窗口独立编码。

可以把它理解成：

这样做有两个直接好处：

第一，内存可控。

当 winsize = 8 MB 时，编码器的主要工作集大致围绕这个窗口展开，而不是整个目标文件。

第二，支持流式处理。

解码器不必先看到整个差分包，只要按顺序读每个窗口，就能边读边还原目标文件。

当然，窗口化也有代价：如果一段本来很长的匹配恰好被窗口边界切开，就可能变成两条较短的 COPY，压缩率会略有下降。所以工程里常常会在 8 MB ~ 64 MB 之间选一个折中值。

2.2.4 第二步：字符串匹配

xdelta3 不像 bsdiff 那样先构建完整后缀数组，而是更接近哈希驱动的快速匹配器。它的基本想法是：

1. 从当前位置取一个固定长度的小片段，作为“指纹”。

2. 计算这个片段的哈希值。

3. 用哈希值到源文件或目标已生成区中快速查找候选位置。

4. 对候选位置做逐字节比对，延长出真正的最长匹配。

5. 根据匹配长度和收益，决定生成 COPY 还是继续积累成 ADD。

2.2.4.1 滚动哈希在这里做什么

假设当前固定取 L = 4 个字节作为哈希种子。为了说明原理，先看一个简化公式：

其中：

• B 是一个基数，例如 257

• M 是模数，用来限制哈希值范围

如果当前窗口从 abcd 右移一位，变成 bcdx，那么无需从头重算，只要把最左边的 a 的贡献移除、再把新字符 x 加进来即可。这就是“滚动哈希”的意义：相邻位置的哈希可以增量更新，代价接近 $O(1)$。

举一个更直观的数值例子。把字符按 ASCII 看成整数：

• a = 97

• b = 98

• c = 99

• d = 100

取一个简化演示参数：B = 257，M = 1000。

那么：

继续向右滑动得到 bcdx，编码器会基于前一个哈希快速更新，而不是重新从头扫描全部 4 个字符。

这一步的意义不是“保证哈希完全无冲突”，而是“快速缩小候选范围”。真正是否匹配，后面还要逐字节验证。

2.2.4.2 哈希表怎么帮助找匹配

编码器会维护一个哈希表，大致可以理解为：

例如在源文件中：

如果按 4 字节种子建立索引，可能得到：

当目标文件扫描到某个位置时，只要先计算当前位置 4 字节种子的哈希值，再去对应桶里找候选偏移，然后逐字节比对、向两侧扩展，就能找到一段较长匹配。

所以哈希表做的是：

• 快速定位候选位置，不是直接给出最终答案。

• 真正的匹配长度，仍然靠后续字节比较确认。

2.2.4.3 三类常见匹配来源

在实现层面，可以把 xdelta3 常见的匹配来源理解成三类：

其中“小匹配”非常重要，它意味着 xdelta3 不只是“引用旧文件”，还可以“引用自己刚刚生成的新数据”。这在日志、文本、配置文件等存在局部重复的场景里很有用。

2.2.5 第三步：把匹配结果变成指令

扫描目标窗口时，编码器实际看到的是两类块：

• 匹配块：在字典里找到可复用内容。

• 字面量块：暂时找不到可复用内容，只能原样输出。

然后把它们翻译成 VCDIFF 指令：

• 匹配块 -> COPY

• 字面量块 -> ADD

• 连续重复字节 -> RUN

例如目标串为：

而旧文件是：

那么一种自然的编码方式就是：

如果编码器不使用 RUN，也可能退化成：

前者通常更紧凑，因为只需存一个字节 z，不必存 4 个原始字节。

2.2.6 指令为什么还要再优化一次

初步扫描得到的指令流，往往并不是最省空间的。编码器通常还会做一轮本地优化，典型规则包括：

1. 合并相邻 ADD

可以合并成：

2. 合并相邻 COPY

如果两段地址刚好连续，可以直接合并成：

3. 把长重复字节转换成 RUN

可以优化成：

4. 短 COPY 反而可能改回 ADD

如果 COPY 只有 2~3 个字节，却还要额外存一个地址，那么“地址开销 + 指令开销”可能比直接存原始数据还大。此时把短 COPY 改成 ADD 反而更划算。

因此，xdelta3 并不是“找到匹配就一定发 COPY”，它还会考虑这条指令到底值不值得。

2.2.7 VCDIFF 是如何存储这些指令的

在 VCDIFF 中，一个目标窗口不会简单地按“指令、数据、指令、数据”交错存放，而是通常拆成三个区：

它们分别负责：

1. Data Section

存放 ADD 和 RUN 需要用到的原始字节。

2. Instruction Section

存放指令类型及其长度信息。

3. Address Section

存放 COPY 使用的地址。

这种“三元分离”的好处是很明显的：

• 原始数据集中存储，更容易压缩。

• 指令类型和长度的分布更规律，编码效率更高。

• 地址具有很强局部性，单独存放更容易继续压缩。

2.2.7.1 统一地址空间是什么

COPY 不仅可以引用源文件，还可以引用当前目标窗口已经写出的内容。为此，VCDIFF 在逻辑上把它们拼成一个统一地址空间：

假设：

• 源窗口 S = abcdabef

• 当前目标窗口前缀已经生成了 abcdx

那么逻辑空间可以理解为：

这样一来：

• 地址 0~7 指向源窗口。

• 更大的地址则可以指向目标窗口已生成部分。

这就是为什么 COPY 能同时实现“从旧文件复制”和“从新文件前缀复制”。

2.2.7.2 地址模式为什么还能省空间

COPY 真正占空间的，不只是长度，还有地址。如果每次都把地址当作 32 位整数原样写出，补丁会膨胀得很快。

所以 VCDIFF 对地址又做了一层编码优化，常见模式有：

• SELF：直接写绝对地址。

• HERE：写相对当前位置的距离。

• NEAR：写相对最近若干地址缓存的偏移。

• SAME：如果和缓存中的地址完全相同，用更短表示法。

例如，假设上一次 COPY 用了地址 1000，这次用地址 1004。

• 如果直接写绝对地址，需要编码 1004。

• 如果用 NEAR，只需编码“相差 4”。

显然第二种更省空间。

2.2.7.3 128 进制编码（7-bit 变长整数）

VCDIFF 中很多数值都不是固定 4 字节存储，而是采用变长整数编码。规则是：

• 每个字节低 7 位存数值。

• 最高位表示“后面是否还有字节”。

例如十进制 300：

所以它可以拆成两部分：

• 低位部分 44

• 高位部分 2

编码后可写成：

解释如下：

• 0xAC = 0x2C | 0x80，低 7 位是 44，最高位 1 表示后面还有字节。

• 0x02 的最高位是 0，表示结束。

这类编码对大量小整数非常有利，因为很多长度值、地址增量值都远小于 128，通常只要 1 个字节就能表示。

2.2.8 一个完整示例：abcdabef -> abcdxabef

下面用一个具体例子，把上面的概念全部串起来。

已知：

• old = "abcdabef"

• new = "abcdxabef"

为了便于讲解，做两个简化假设：

1. 整个字符串都放在一个目标窗口里。

2. 编码器允许把长度 4 的匹配作为有效 COPY。

注意：真实 xdelta3 在不同压缩级别、不同候选搜索和本地优化策略下，最终指令可能略有不同；这里选的是最容易把算法讲清楚的一种路径。

2.2.8.1 建立源文件索引

先对旧文件按长度 4 的种子建立哈希索引：

于是哈希表里至少会记录这两项关键信息：

2.2.8.2 从左到右扫描目标文件

目标串是：

第 1 次查找：位置 i = 0

取 4 字节种子：

查哈希表命中源文件偏移 0，继续向后扩展：

比较到第 5 个字符时：

• old[4] = 'a'

• new[4] = 'x'

匹配中断，因此最长匹配长度为 4。生成：

此时输出缓冲区内容为：

扫描指针前进到：

第 2 次查找：位置 i = 4

当前位置字符是：

以 x 开头的长度 4 种子在源文件中找不到合适候选，因此这里不能生成 COPY，只能把它先放进字面量缓冲区：

扫描指针继续前进到：

第 3 次查找：位置 i = 5

现在取 4 字节种子：

查哈希表命中源文件偏移 4，逐字节验证后发现完整匹配长度为 4，因此先把前面积累的字面量吐出，再发 COPY：

所以整个窗口的一组自然指令序列就是：

2.2.8.3 还原过程怎么验证

解码时按指令执行：

拼接得到：

这就完成了目标文件重建。

2.2.8.4 这些内容在 VCDIFF 中会怎么放

对于上面的三条指令，可以粗略理解为：

Data Section

因为只有 ADD 需要直接携带原始字节。

Instruction Section

这里只强调“操作和长度”，不直接放 COPY 的地址。

Address Section

分别对应两条 COPY 指令的地址。

2.2.9 为什么同一个例子有时会出现 ADD 5 + COPY 4

如果你去看真实编码器输出，会发现同一个例子不一定总是得到：

有时也可能得到：

原因在于：

• 编码器使用的最小匹配长度不同。

• 某些模式会偏向更长种子匹配。

• 本地优化阶段会重新评估“发 COPY 是否比 ADD 更划算”。

也就是说，xdelta3 的本质不是生成唯一答案，而是在约束条件下生成一组足够优的重建指令。

对于教学来说，COPY 4 + ADD 1 + COPY 4 更容易看清扫描和匹配的过程；对于真实编码器来说，ADD 5 + COPY 4 也完全可能是合法且合理的输出。

2.2.10 xdelta3 的思考与原理哲学

如果说 bsdiff 的哲学更接近“极致地挖掘全局相似性”，那么 xdelta3 的哲学则更接近：不要执着于最优答案，而要用足够好的局部决策，构造一个可流式、可扩展、可工业化落地的差分系统。

它背后的思路可以从四个角度理解。

第一，差分不仅是一个压缩问题，还是一个系统问题。

从纯算法视角看，我们当然希望匹配越长越好、补丁越小越好；但真实工程里还要同时面对：

• 文件可能非常大。

• 内存可能受限。

• 编码和解码可能需要流式执行。

• 补丁格式可能需要跨平台、跨实现兼容。

因此 xdelta3 的重点不只是“找最优匹配”，而是把整个问题拆成：

• 窗口化处理

• 快速匹配

• 统一指令格式

• 可预测的解码流程

这是一种非常工程化的思想：先让系统稳定可运行，再在这个框架里尽量逼近更好的压缩率。

第二，xdelta3 相信“局部好决策的累计”比“追求全局最优”更容易落地。

它使用哈希、候选桶、逐字节扩展、局部优化，背后的意思其实是：

这种思想非常像很多现实系统的设计原则：

• 数据库不会穷举所有执行计划，而是用代价模型快速近似。

• 压缩器不会全局穷举所有切分方式，而是用启发式策略找局部最优。

• 调度器也很少追求绝对最优，而更重视稳定、可预测、可扩展。

换句话说，xdelta3 的哲学不是“数学上的最漂亮”，而是“工程上的最可信”。

第三，VCDIFF 体现的是“算法与格式解耦”的思想。

这一点非常关键。

xdelta3 作为实现，可以不断调整：

• 哈希函数怎么选

• 候选匹配尝试多少次

• 窗口多大

• 小匹配是否激进启用

但最后输出仍然是标准 VCDIFF。这说明它把两个层面切得很清楚：

• 上层实现可以演进。

• 下层交换格式保持稳定。

这其实是一种很成熟的软件架构思想。只有把“内部算法”和“外部协议”分开，生态才能长期兼容。

第四，xdelta3 体现的是“状态重用”而不是“状态重建”的思维。

它看到一个新文件时，不会先把它当成一个全新的对象，而是先问：

这是一种很有代表性的系统观：

• 缓存是在复用旧状态。

• 增量编译是在复用旧状态。

• 增量同步、日志回放、快照恢复，本质上也都在复用旧状态。

从这个角度看，xdelta3 不只是一个差分算法，它更像“增量系统设计”在文件分发领域的一次具体落地。

所以如果把 xdelta3 的原理哲学压缩成一句话，可以这样概括：

不追求一次性求出最完美的新文件描述，而是把新文件看成旧状态的连续演化，用标准化、可流式、可复用的方式，把这次演化可靠地编码出来。

这也是为什么 xdelta3 在很多实际场景里会显得非常“顺手”：它也许不是最极致的，但它往往是最像一个成熟工程系统的差分方案。

2.3 HDiffPatch 算法详解

HDiffPatch 是 housisong 开源的一套 C/C++ 二进制差分与补丁库，命令行工具通常表现为：

• hdiffz：负责生成差分包。

• hpatchz：负责应用补丁并恢复新文件。

如果用一句话概括它的定位，那么可以说：HDiffPatch 试图在 bsdiff 的高压缩率、xdelta3 的高工程效率，以及嵌入式 / 小内存场景的现实约束之间，找到一个更均衡的落点。

与 bsdiff、xdelta3 相比，它有两个非常鲜明的特点：

• 它把“匹配出的相同区域”抽象成 Cover，并围绕 Cover 做整套优化。

• 它从一开始就把“内存模式”和“流式模式”都视为一等公民，而不是只为大内存桌面环境设计。

下面按“名词解释 -> 总体流程 -> 双模式匹配 -> Cover 优化 -> 补丁编码 -> 完整算例”的顺序展开。

2.3.1 先把几个关键名词讲清楚

在 HDiffPatch 中，最核心的概念不是 COPY 指令，也不是 VCDIFF 窗口，而是 Cover。

1. Cover（覆盖线）

Cover 表示“新旧文件之间一段完全相同的区域”。可以把它理解为：

一个 Cover 至少包含三个关键信息：

这和 COPY oldPos, length 在语义上几乎等价，只不过 HDiffPatch 更强调这是“一条覆盖关系”，而不只是单条指令。

2. 覆盖区与非覆盖区

把所有 Cover 放到新文件上看，会把新文件切成两类区域：

• 覆盖区：可以从旧文件中找到对应数据。

• 非覆盖区：旧文件里没有对应内容，只能把新数据本身写进补丁。

3. Additive Diff（加法差分）

HDiffPatch 的一个核心思想是：对覆盖区，不一定直接存“原始新字节”，而是存“旧字节到新字节的差值”。

可以写成：

这里的加法一般可理解为按字节模 256 的加法。

它的意义在于：

• 如果新旧字节完全相同，那么 diffByte = 0。

• 如果大量字节只发生了很小的变化，那么差值序列往往更容易压缩。

所以 HDiffPatch 不是简单地说“这段可以从旧文件复制”，而是更细致地说：

4. newDataDiff（新增数据区）

对于完全无法覆盖的区域，补丁中就需要直接保存原始新字节。这些数据通常会进入数据区，由补丁时直接填入。

5. 双模式匹配

HDiffPatch 在生成补丁时，一般有两条主要路径：

• -m：内存模式，强调更高质量匹配。

• -s：流式模式，强调更低内存消耗与更好的大文件适应性。

这两种模式最后都会落到同一个核心目标：找到尽可能有价值的 Cover 集合。

2.3.2 HDiffPatch 的总体处理框架

从宏观上看，HDiffPatch 的工作流可以拆成 5 步：

1. 建立旧文件查询结构
   在内存模式下通常是后缀数组，在流式模式下更偏块索引与哈希结构。

2. 扫描新文件，发现候选 Cover
   找到新旧文件之间可能相同的区域。

3. 优化 Cover 集合
   对候选 Cover 做延长、分裂、合并、筛选。

4. 编码补丁
   存储 Cover 元数据、差值数据和新增原始数据，并可进一步压缩。

5. 应用补丁
   hpatchz 读取旧文件和补丁，按 Cover 顺序重建新文件。

可以画成下面这样：

这个框架和前面的两个算法有相似之处：

• 像 bsdiff 一样，它非常重视高质量匹配。

• 像 xdelta3 一样，它又非常重视大文件和有限内存下的实际可用性。

2.3.3 核心数据抽象：为什么 HDiffPatch 特别强调 Cover

bsdiff 更像在围绕“控制块 + diff 块 + extra 块”组织信息。

xdelta3 更像在围绕“ADD / COPY / RUN 指令流”组织信息。

而 HDiffPatch 更像是在围绕“匹配关系图”组织信息。它首先关心的问题是：

一旦这个问题回答清楚，后面的编码只是把 Cover 集合和差值数据写出来。

从这个角度看，Cover 实际上承担了两层职责：

• 语义职责：描述新旧文件的对应关系。

• 压缩职责：为后续差值编码和元数据压缩提供骨架。

因此，HDiffPatch 的算法质量很大程度上取决于：

• 是否能找到足够长、足够密集的 Cover。

• 是否能把这些 Cover 优化成“真正值得保留”的集合。

2.3.4 内存模式（-m）：后缀数组 + 高精度匹配

当新旧文件都能装入内存时，HDiffPatch 会走更精细的匹配路径。它的思路和 bsdiff 有亲缘关系，但整体目标更偏“高质量 Cover 搜索”。

2.3.4.1 为什么要构建后缀数组

假设旧文件是：

它的所有后缀为：

把这些后缀按字典序排序后，就得到后缀数组。后缀数组的意义是：把“找某个子串在旧文件中的最佳匹配位置”变成一个可以快速二分逼近的问题。

也就是说，面对新文件当前位置的子串，编码器无需暴力和旧文件每个位置逐一比较，而是可以：

1. 在后缀数组中找到字典序最接近的候选。

2. 在候选附近继续比较，找到真正的最长匹配。

2.3.4.2 在新文件上如何发现 Cover

假设扫描到新文件偏移 i，此时编码器会：

1. 取出 new[i...] 作为待匹配串。

2. 在旧文件后缀数组中查找最接近的候选位置。

3. 对候选位置做逐字节比较，算出匹配长度。

4. 如果长度达到阈值，就形成一个候选 Cover(oldPos, newPos, length)。

例如：

当 newPos = 0 时，会很自然地发现：

因为 abcd 这一段是完全相同的。

当扫描到 newPos = 5 时，又会发现：

因为 abef 也能在旧文件中找到对应区域。

2.3.4.3 为什么还要检查相邻候选

后缀数组查出来的“最接近候选”不一定就是最佳匹配。因为字典序最接近并不总等于实际字节匹配最长。

因此工程实现中通常不会只看单个候选，而会适当查看它附近的若干邻居，再比较谁的匹配长度更长、收益更高。

这个细节很重要，因为它体现了 HDiffPatch 的一个特点：它不只是在找“能匹配”的位置，而是在找“值得形成 Cover”的位置。

2.3.5 流式模式（-s）：块匹配 + 滚动哈希 + 低内存处理

当文件太大，无法把新旧文件全部装入内存时，HDiffPatch 会走流式路径。

这条路径的关键不是“逐字节全局精确搜索”，而是：

• 先按块建立旧文件索引。

• 再对新文件做滑动扫描。

• 用滚动哈希快速定位可能命中的块。

• 命中后再做更细的验证和扩展。

2.3.5.1 旧文件如何分块

假设块大小为 blockSize，旧文件会被切成一系列定长块：

然后对每个块计算校验值，并建立映射：

这样做的目的，是把“可能相同的区域”先缩小到块级别，而不是一上来就做逐字节比对。

2.3.5.2 为什么滚动哈希特别适合流式扫描

在新文件中，窗口每向右滑动一个字节，都需要重新判断“当前位置这一块，是否和旧文件某块相同”。

如果每次都重新计算整块校验值，成本会很高。

滚动哈希的优势就在这里：

• 窗口从 i 滑到 i+1 时，哈希可以增量更新。

• 因此每次滑动的代价接近 $O(1)$。

这让流式模式在大文件上仍然能保持较高扫描速度。

2.3.5.3 为什么还需要布隆过滤器或其他预筛结构

流式模式下，真正昂贵的不是“哈希命中”本身，而是命中后的逐字节验证。

如果命中候选太多，而大部分又是误命中，那么性能会迅速下降。

因此类似布隆过滤器这样的预筛结构就很有价值：

• 它不能保证“命中就一定存在”。

• 但它能很快判断“这个候选大概率不存在”。

这样做的意义是：尽量把昂贵的精确比较留给少量真正可疑的候选。

2.3.5.4 流式模式找到 Cover 后会发生什么

一旦块级匹配成立，算法通常不会停在块大小上，而是会继续向前、向后扩展，尽量把一条短块命中延长成一条更长的 Cover。

所以即使流式模式的起点是“按块找”，最终输出的仍然是“覆盖线”。

这也意味着：

• -m 和 -s 的搜索路径不同。

• 但它们最终交给编码器的核心对象是相同的：Cover 集合。

2.3.6 Cover 为什么还要做二次优化

初始匹配得到的 Cover 集合，通常只是“能用”，并不一定“最省补丁”。

因为每一条 Cover 除了带来收益，也会带来成本：

• 要存 oldPos

• 要存 newPos

• 要存 length

• 覆盖区本身还可能需要差值数据

如果一条 Cover 太短、太碎、地址跳得太远，那么它的元数据开销可能会超过收益。

因此 HDiffPatch 会对 Cover 做多轮优化。

2.3.6.1 延长（Extend）

如果当前已经找到一条匹配，算法通常会继续往左右尝试扩展，看能不能把相邻的相同字节也并入这条 Cover。

原因很直接：

• 一条长 Cover 的元数据成本，通常小于多条短 Cover 的总元数据成本。

2.3.6.2 分裂（Split）

不是所有长 Cover 都值得完整保留。

有时一条 Cover 虽然很长，但：

• 地址跨度太大，导致位置编码成本上升。

• 中间夹着变化剧烈的小片段。

• 保持整条 Cover 反而不利于后续差值编码。

这时把它拆成两条或多条较小 Cover，反而可能让整体补丁更小。

2.3.6.3 合并（Merge）

如果两条 Cover 足够接近，甚至在新旧文件上映射关系几乎共线，那么它们就可能被合并。

例如：

两者满足：

这说明它们在映射关系上处于同一条“平移线”上，合并后常常更省元数据。

2.3.6.4 筛选（Selection）与成本模型

最终不是所有 Cover 都会留下。HDiffPatch 的关键判断是：

可以把这种思想抽象成一个收益模型：

如果 benefit > 0，说明这条 Cover 值得保留；如果收益不足，就宁可把这段当作新增数据直接写进补丁。

这一步非常重要，因为它决定了 HDiffPatch 不会盲目追求“Cover 越多越好”，而是追求：

真正能让最终补丁更小的 Cover。

2.3.7 HDiffPatch 的补丁是怎么编码的

当最优 Cover 集合确定后，补丁文件大致会包含三类信息：

1. Cover 元数据

用于描述每条 Cover 的：

• 旧文件起点 oldPos

• 新文件起点 newPos

• 覆盖长度 length

这些位置值通常不会原样整型平铺，而会尽量采用增量编码（delta encoding），因为相邻 Cover 的位置往往具有局部性。

2. 覆盖区差值数据

对于被 Cover 覆盖的区域，补丁中可以存一段差值数据：

如果很多字节完全不变，那么这部分差值就会出现大量 0，在编码层面会形成非常规则的数据分布。

3. 非覆盖区原始数据

新文件中那些不在任何 Cover 里的区间，需要直接把原始新字节放进补丁。

所以从结构上看，HDiffPatch 补丁不是单纯的“复制指令流”，而更像：

2.3.7.1 为什么 Additive Diff 有利于编码

假设某个 Cover 覆盖的 16 个字节完全没变，那么它对应的差值序列就是：

这说明 HDiffPatch 的一个核心收益点在于：它不仅减少了必须显式存储的新数据量，还把覆盖区的数据组织成了更规则、更容易编码的形式。

2.3.8 补丁应用：hpatchz 如何恢复新文件

应用补丁时，hpatchz 需要做的事情反而比生成补丁更直接：

1. 读取 Cover 元数据。

2. 按 Cover 定位旧文件对应区域。

3. 读出旧字节，并叠加覆盖区差值。

4. 对于 Cover 之间的空洞区域，直接从补丁数据区取出原始新字节填入。

5. 按顺序把所有片段拼起来，就得到完整新文件。

如果把覆盖区的一条记录写成：

那么应用时的含义就是：

• 先从旧文件 100..107 取出 8 个字节。

• 再对第 3 个字节加上 1，其他字节保持不变。

• 最终把修正后的 8 个字节写到新文件 120..127。

所以 hpatchz 并不是盲目“复制旧文件片段”，而是在做：

2.3.9 一个完整示例：abcdabef -> abcdxabef

下面用和前两节一致的例子，演示 HDiffPatch 的一条典型处理路径。

已知：

• old = "abcdabef"

• new = "abcdxabef"

为便于讲解，这里采用内存模式思路，并假设长度 4 的匹配已经足够形成 Cover。

2.3.9.1 第一步：发现 Cover

对旧文件建立查询结构后，扫描新文件可以发现两段明显匹配：

Cover 1

所以得到：

Cover 2

所以得到：

而新文件中间那个 x：

无法在旧文件中找到可用覆盖，因此它属于非覆盖区。

2.3.9.2 第二步：检查 Cover 是否可合并

现在有两条 Cover：

检查它们是否共线：

因为：

说明它们不是同一条平移关系，不能直接合并成一条更长 Cover。

2.3.9.3 第三步：生成覆盖区差值和新增数据

对 Cover 1 而言：

逐字节差值为：

即：

对 Cover 2 而言：

差值同样为：

未覆盖区域只有 1 个字节：

2.3.9.4 第四步：补丁中实际保存什么

因此这个例子的补丁核心上会包含：

Cover 元数据

覆盖区差值数据

非覆盖区原始数据

因为覆盖区差值全为 0，所以这一段在补丁表示中会非常规整。

2.3.9.5 第五步：应用补丁还原

还原时按顺序执行：

1. 读 Cover 1，从旧文件取 abcd，加上全 0 差值，得到 abcd。

2. 读非覆盖区原始数据，写入 x。

3. 读 Cover 2，从旧文件取 abef，加上全 0 差值，得到 abef。

最终结果为：

这样就完成了新文件重建。

2.3.10 HDiffPatch 的思考与原理哲学

如果说：

• bsdiff 更像“尽一切可能逼近最小补丁”。

• xdelta3 更像“围绕标准格式构建高效工程系统”。

那么 HDiffPatch 的哲学更像：把高质量匹配能力、低内存运行能力、补丁可压缩性，统一到同一个框架里。

它背后最值得注意的，不只是“它用了哪些算法”，而是它如何组织这些算法。

第一，它把“匹配”与“编码”明确分层。

先找到好的 Cover，再考虑怎么编码 Cover、差值和新增数据。这种分层让它既能用后缀数组，也能用流式哈希，而不需要推翻整个补丁格式。

第二，它强调的不是单次最优，而是整体收益最优。

一条 Cover 不是因为“能匹配”就被保留，而是因为“保留它后，整体补丁更值”。这背后是非常典型的工程成本模型思维。

第三，它把小内存场景视为核心约束，而不是附加优化。

很多差分算法在大内存环境里表现很好，但一旦进入 OTA、IoT、嵌入式、边缘设备场景，问题就变成：

HDiffPatch 从设计上就认真回答了这个问题，所以它不是“先做出一个算法，再想办法裁剪”，而是“一开始就承认资源受限是真实前提”。

第四，它体现的是“状态映射 + 状态修正”的增量思想。

它既不像纯复制模型那样只关注“这段能不能复用”，也不像纯原始写入模型那样只会存新字节，而是同时考虑：

• 哪些区域可以映射到旧文件。

• 哪些区域需要少量差值修正。

• 哪些区域必须作为新字节直接存储。

所以从思想上讲，HDiffPatch 是把“复用”和“修正”结合得最明显的一类方案。

如果把它的原理哲学压缩成一句话，可以写成：

不是单纯追求最小补丁，也不是单纯追求最快匹配，而是在真实内存约束下，尽可能多地复用旧状态，并把必须表达的新变化压缩成最容易编码的一种形式。

这也是为什么 HDiffPatch 常常会被看作介于 bsdiff 和 xdelta3 之间、但又自成体系的一类方案：它不是折中得模糊，而是把多个目标有意识地组织到了同一个工程框架里。

2.4 总结

前面分别分析了 bsdiff、xdelta3 和 HDiffPatch 的内部机制。到了这里，可以把三者放到同一张坐标系里看：它们都在解决“如何利用旧文件尽量低成本地重建新文件”这个问题，但选择的重点完全不同。

如果只看表面，它们的输出形式不同、匹配方式不同、内存模型不同；但从更深层的角度看，它们其实分别代表了三种不同的优化哲学：

• bsdiff：优先逼近最小补丁。

• xdelta3：优先构建稳定、标准化、工程友好的增量系统。

• HDiffPatch：优先在压缩率、内存占用、补丁可落地性之间取得均衡。

2.4.1 三种算法的核心差异总览

这张表最重要的不是记住“谁更快、谁更小”，而是要看出：三者优化的目标函数不同。

也就是说，它们并不是“谁先进谁落后”的关系，而是：

• 同样是增量更新，但目标权重不同。

• 同样是重用旧文件，但重用方式不同。

• 同样是描述状态变化，但描述粒度不同。

2.4.2 三种算法各自的优点与局限

先分别收束一下。

bsdiff 的优点

• 擅长挖掘远距离、全局性的相似结构。

• 对很多二进制版本升级场景，补丁体积往往很有竞争力。

• 对“流量比 CPU 更贵”的场景非常有吸引力。

bsdiff 的局限

• 构建后缀数组和全局搜索的成本较高。

• 编码速度通常不占优势。

• 内存压力相对明显，对超大文件和小内存设备不够友好。

可以把 bsdiff 理解成一种“为补丁体积而生”的算法：它最擅长回答的问题不是“怎么最快生成补丁”，而是“怎么把补丁尽量做小”。

xdelta3 的优点

• 指令流模型清晰，结构标准化程度高。

• 窗口化思想让它更适合处理大文件。

• 速度、内存、格式通用性之间有较好的平衡。

• 既能复用旧文件，也能复用当前目标窗口已生成内容。

xdelta3 的局限

• 在很多场景里，补丁尺寸未必能压到 bsdiff 那么小。

• 它更依赖局部启发式决策，因此结果更偏“足够优”而不是“逼近最优”。

• 如果窗口或候选匹配策略不理想，压缩率可能受影响。

可以把 xdelta3 理解成一种“为通用工程系统而生”的算法：它不是单一指标最激进的，但常常是整体表现最稳的。

HDiffPatch 的优点

• 同时考虑匹配质量、内存约束、补丁表示效率。

• Cover 抽象很强，便于后续做延长、分裂、合并、筛选等优化。

• 能把“旧状态复用”和“局部差值修正”结合起来。

• 对 OTA、嵌入式、小内存、大文件场景特别有现实意义。

HDiffPatch 的局限

• 整体结构比前两者更复杂，理解成本更高。

• 其优势往往体现在综合平衡，而不是某一个单项指标的绝对第一。

• 如果场景本身并不受内存约束，它的复杂设计未必总能体现全部价值。

可以把 HDiffPatch 理解成一种“为真实部署环境而生”的算法：它关心的不是理想条件下谁最漂亮，而是谁在受限资源下还能稳定工作。

2.4.3 如果站在 OTA 场景里，应该怎样理解它们

对于 OTA 来说，真正关键的问题通常不是“这个算法在论文里是否优雅”，而是下面这几个：

1. 补丁能否足够小，降低带宽成本？

2. 生成补丁的代价是否可接受？

3. 设备端能否在可控内存内完成补丁应用？

4. 整个升级系统是否稳定、可验证、可量产？

如果按这几个问题反推：

当你最在乎补丁体积时，bsdiff 往往最值得优先考虑。

它适合：

• 移动网络成本高。

• 版本差异相对局部。

• 服务端有足够资源做离线生成。

当你最在乎实现成熟度、标准格式与通用工程性时，xdelta3 往往更顺手。

它适合：

• 需要标准化增量格式。

• 文件较大，窗口化处理价值明显。

• 你更重视整体可维护性，而不是极限补丁大小。

当你不仅关注补丁大小，还必须认真面对设备端内存和真实部署限制时，HDiffPatch 往往更有现实意义。

它适合：

• 嵌入式或 IoT 设备。

• 补丁应用端 RAM 很紧张。

• 文件很大，或者升级链路必须支持更严格的资源约束。

所以从 OTA 实践角度看，最重要的不是“哪一个理论上最好”，而是：

2.4.4 我的思考：这三类算法分别代表了三种工程世界观

如果把这一章再往上抽象一层，我认为这三种算法其实不只是三种技术方案，它们更像三种工程世界观。

bsdiff 代表的是“变化应该被精确刻画”。

它相信：只要我们足够认真地寻找全局匹配，就能把真正需要传输的变化压缩到很小。这是一种非常典型的“用更多计算换更少传输”的思想。

xdelta3 代表的是“变化应该被标准化地表达”。

它强调窗口、字典、指令流和统一格式，说明它更关心“怎样把变化写成一个稳定、通用、可重复实现的系统”。它不是最偏执地追求最优，但它非常重视可移植、可扩展、可工程化。

HDiffPatch 代表的是“变化必须在真实约束中被表达”。

它一开始就承认：设备可能很弱、内存可能很小、文件可能很大、补丁必须真的能落到产线。这种思路更接近工业现场，而不是理想实验室。

所以如果让我用一句更主观的话来总结：

• bsdiff 像一个追求极致的算法工程师。

• xdelta3 像一个重视体系化和标准化的平台工程师。

• HDiffPatch 像一个长期面对设备约束和上线问题的系统工程师。

它们没有谁“完全替代”谁。恰恰相反，它们一起说明了一件事：

差分算法的本质，从来不只是找相同和不同；更重要的是，在给定资源约束下，选择一种最合理的方式去表达版本之间的演化。

这也是为什么在实际项目里，算法选型从来不应该只看单一指标。真正成熟的决策，往往要同时看：

• 带宽是否昂贵。

• 服务端生成时延是否敏感。

• 终端内存是否受限。

• 文件规模是否巨大。

• 升级系统是否需要标准化和长期维护。

当这些问题都摆到台面上以后，你会发现：

没有“绝对最好的差分算法”，只有“最适合当前系统约束的差分算法”。