3. 双分区核心概念

bsdiff 这个名字，在差分升级领域基本就是绕不开的存在。我最早接触它是在做嵌入式 OTA 方案选型的时候，当时对比了好几种算法，最后还是选了 bsdiff 作为核心引擎。为什么？说白了，它在「差分包大小」和「运行效率」之间找到了一个很不错的平衡点。

这一章，我们就来拆解 bsdiff 的三个核心模块：核心思想、后缀数组构建、差异与补丁生成。嗯，这部分内容有点硬核，但我会尽量用工程化的语言讲清楚。

bsdiff 的核心思想：最长公共子串匹配

bsdiff 的本质，就是在新旧两个二进制文件之间，找到尽可能多的相同片段。你想想看，固件升级通常只是改了几个函数、加了几行代码，大部分内容其实没变。如果能把这些没变的部分「复用」起来，那差分包就能做得很小。

具体怎么做？bsdiff 的思路是：

1. 把旧文件的所有子串索引起来，构建一个快速查找结构
2. 遍历新文件，在旧文件中找最长的匹配片段
3. 记录匹配位置和长度，剩下的就是差异数据

我在项目中遇到过一个问题：如果新旧文件差异很大（比如换了整个协议栈），bsdiff 的压缩率会明显下降。这时候我会建议先用二进制对比工具看一下相似度，低于 30% 就别硬上 bsdiff 了，直接全量升级反而更省事。

后缀数组构建：让匹配查找变快

要找最长公共子串，最笨的办法是把旧文件的每个位置都和新文件比一遍——复杂度 O(n²)，一个 1MB 的固件就要比 10¹² 次，显然不现实。

bsdiff 用了一个经典的数据结构：后缀数组（Suffix Array）。它把旧文件的所有后缀按字典序排好，这样查找任意子串就变成了二分查找，复杂度降到 O(log n)。

后缀数组长什么样？

假设旧文件内容是 "banana"，它的所有后缀是：

位置	后缀
0	banana
1	anana
2	nana
3	ana
4	na
5	a

排序后的后缀数组（存储的是起始位置）：

位置: [5, 3, 1, 0, 4, 2]
对应:  a, ana, anana, banana, na, nana

有了这个数组，要查找 "ana" 这个子串，直接在排序后的后缀里二分查找就行，很快。

差异与补丁生成：从匹配到差分包

后缀数组建好了，接下来就是生成差分包。bsdiff 的流程大致分三步：

1. 扫描新文件，对每个位置，在后缀数组中找最长匹配
2. 输出控制信息：匹配的偏移量、匹配长度、不匹配的差异数据
3. 压缩输出：用 bzip2 把控制信息和差异数据压缩成最终的 .bspatch 文件

控制信息的格式

bsdiff 的补丁文件包含三个部分：

数据段	内容	说明
控制块	匹配长度、不匹配长度、新文件偏移增量	用于指导合并过程
差异块	新旧文件的字节差（异或或减法）	只存不匹配的部分
额外块	新文件中完全新增的字节	旧文件中没有对应内容

我举个例子，假设旧文件是 "hello world"，新文件是 "hello there world"：

• 匹配部分："hello "（位置 0，长度 6）和 "world"（位置 12，长度 5）
• 差异部分："there " 是新增的，存在额外块里
• 控制块记录：第一次匹配长度 6，不匹配长度 6，偏移增量 6

bsdiff 整体流程

下面这张图把整个流程串起来了，你可以对照着看：

工程落地中的几个坑

bsdiff 原理听起来不复杂，但真正落地到嵌入式系统里，有几个地方特别容易出问题：

• 内存爆炸：后缀数组需要 4 倍于旧文件大小的内存（每个 int32 占 4 字节）。1MB 的旧文件就要 4MB 内存，很多 MCU 没有这个条件。我做过一个方案，把旧文件分块处理，每块 256KB，内存占用降到 1MB 以内。
• 大端小端问题：bsdiff 的补丁文件默认是小端字节序。如果你的目标平台是大端（比如某些网络处理器），合并时一定要做字节序转换。我曾经因为这个原因，调试了整整两天才发现是字节序没对。
• 压缩器选择：bsdiff 默认用 bzip2 压缩，但 bzip2 的解压速度在低端 MCU 上很慢。我建议换成 LZMA 或 zlib，压缩率差不多，但解压速度快很多。

小结