2、差分算法基础：bsdiff、hdiffpatch、xdelta 原理与选型
聊差分升级，绕不开的就是核心算法。说白了，算法就是差分引擎的“心脏”。你选什么算法，直接决定了补丁包能打多小、生成速度多快、设备端能不能跑得动。
我最早接触差分升级时，第一反应是：“不就是 diff 嘛，Linux 下 diff 命令不就能比？” 后来才发现，嵌入式场景下的差分算法，跟文本 diff 完全是两码事。我们面对的是二进制固件，动不动几十 MB，而且设备端的 RAM 和 Flash 都抠得很紧。
今天我就把主流的三个算法——bsdiff、hdiffpatch、xdelta——掰开揉碎讲清楚。它们各自怎么工作的？优缺点在哪？实际项目中怎么选？
2.1 bsdiff 算法原理
bsdiff 是二进制差分领域的“老大哥”。2003 年由 Colin Percival 提出，至今仍是很多 OTA 方案的首选。它的核心思路是：利用后缀排序找相似块，再用 bzip2 压缩差异。
具体流程分三步：
- 后缀数组构建：对新旧两个二进制文件做后缀排序，找出所有公共子串。这一步最耗时，复杂度 O(n log n)。
- 差异编码：把旧文件中匹配到的部分标记为“复制”，没匹配到的部分标记为“插入”。生成一个中间差异文件。
- bzip2 压缩：对差异文件做二次压缩，进一步缩小体积。
我在项目中遇到过一个问题：bsdiff 生成的补丁包确实小，但生成时间太长了。有一次给一个 32MB 的固件做差分，在 PC 上跑了将近 3 分钟。你想想看，如果产线每天要生成几百个版本，这个时间成本就很高了。
2.2 hdiffpatch 算法原理
hdiffpatch 是 bsdiff 的“改良版”。它由国内开发者提出，专门针对嵌入式场景做了优化。核心改进点在于：用哈希匹配替代后缀排序，大幅降低内存和计算开销。
它的工作流程：
- 分块哈希：将旧文件分成固定大小的块（如 64KB），对每个块计算哈希值。
- 快速匹配：在新文件中用同样的哈希算法查找匹配块。匹配速度比后缀排序快一个数量级。
- 差异编码 + 可选压缩：差异部分可以用 zlib 或 lzma 压缩，也可以不压缩。
我记得第一次用 hdiffpatch 时，最直观的感受就是“快”。同样一个 32MB 的固件，bsdiff 要 3 分钟，hdiffpatch 只要 20 秒。而且合并端的内存开销只有 bsdiff 的一半左右。
但代价是什么？压缩率。hdiffpatch 生成的补丁包通常比 bsdiff 大 10%~30%。说白了，就是用体积换速度。
| 对比项 | bsdiff | hdiffpatch |
|---|---|---|
| 匹配算法 | 后缀排序 | 哈希匹配 |
| 生成速度 | 慢 | 快（约 5~10 倍） |
| 补丁包大小 | 小（基准） | 大 10%~30% |
| 合并端内存 | 高（2x 旧固件） | 中（1x 旧固件 + 补丁） |
| 适用平台 | PC/服务器 | 嵌入式 Linux / RTOS |
2.3 xdelta 算法原理
xdelta 走的是另一条路——它基于 VCDIFF 标准（RFC 3284）。这个标准定义了一种通用的二进制差分格式，xdelta 是它的一个经典实现。
它的核心机制是“滑动窗口 + 指纹匹配”：
- 滑动窗口：在旧文件上开一个固定大小的窗口（默认 64KB），窗口内计算每个位置的指纹。
- 指纹匹配：在新文件中用同样的窗口滑动，查找指纹匹配的位置。匹配到的就是“复制指令”，没匹配到的就是“添加指令”。
- 指令流编码：复制和添加指令组成一个指令流，最终输出为 VCDIFF 格式的补丁文件。
xdelta 最大的优势是标准化。VCDIFF 是 IETF 标准，很多工具链原生支持。而且它的合并端实现非常轻量，我曾在只有 128KB RAM 的 MCU 上跑过 xdelta 的合并逻辑，勉强能跑。
但 xdelta 的压缩率一般，比 bsdiff 差，跟 hdiffpatch 差不多。而且它对“大偏移量”的匹配效率不高——如果新旧固件中相同内容的位置变化很大，xdelta 的滑动窗口可能找不到匹配。
2.4 算法选型对比
选型时，我习惯从三个维度来评估：压缩率、生成开销、合并开销。下面这张表是我在实际项目中总结的参考数据：
| 维度 | bsdiff | hdiffpatch | xdelta |
|---|---|---|---|
| 压缩率（越小越好） | ★★★★★ | ★★★★ | ★★★ |
| 生成速度 | ★★ | ★★★★★ | ★★★★ |
| 合并端内存 | ★★ | ★★★★ | ★★★★★ |
| 合并端 CPU | ★★★ | ★★★★ | ★★★★★ |
| 标准化程度 | 低（私有格式） | 低（私有格式） | 高（RFC 3284） |
我个人的选型建议：
- 如果你做的是手机、平板、网关等大内存设备，对补丁包大小极度敏感——选 bsdiff。生成慢一点没关系，反正是在服务器上跑。
- 如果你做的是 IoT 设备、智能家居、工业控制器，RAM 在 256KB~2MB 之间——选 hdiffpatch。它在压缩率和内存开销之间取得了很好的平衡。
- 如果你做的是 MCU 级别的设备，RAM 只有几十 KB，或者你需要跟第三方系统对接——选 xdelta。标准化意味着兼容性好，合并端也足够轻量。
2.5 算法核心流程对比图
下面这张 SVG 图展示了三种算法的核心流程对比，方便你直观理解它们的差异：
2.6 我的选型决策流程
最后，分享一个我在项目中实际使用的选型决策流程。每次接到差分升级需求，我都会按这个步骤走一遍：
- 先看设备端 RAM：如果 RAM < 256KB，直接排除 bsdiff。如果 RAM < 64KB，只能选 xdelta。
- 再看补丁包大小要求：如果 OTA 带宽很贵（比如 NB-IoT、卫星通信），优先 bsdiff 或 hdiffpatch。
- 然后看生成环境：如果是在 CI/CD 流水线里自动生成，生成时间不能超过 30 秒，那 hdiffpatch 是首选。
- 最后看标准化需求：如果需要跟第三方系统交换补丁文件，或者设备端有多个厂商的芯片，选 xdelta（VCDIFF 标准）。
嗯，这套流程帮我避过不少坑。有一次客户坚持要用 bsdiff，结果设备端 RAM 只有 512KB，合并时频繁崩溃。后来换成 hdiffpatch，问题就解决了。所以选型这事，真不能只看压缩率一个指标。