4、差分包生成工具：bsdiff、hdiffpatch、xdelta3 与自定义工具开发
好，咱们进入第四章。这一章很实在，就是讲工具。你想想看，差分升级的核心是“算出差分”，那谁来算？就是这几个工具。
我个人习惯把差分工具分成两派：一派是开源社区的经典轮子，另一派是商业或半商业的专用方案。今天咱们把主流的几个都过一遍，最后再聊聊——如果这些现成的都不满足你，怎么自己造一个？
本章核心脉络： 先掌握 bsdiff、hdiffpatch、xdelta3 这三个主流工具的使用方法和适用场景，再理解自定义差分工具的设计思路。最终目标是：你能根据项目需求，选对工具，甚至能动手改造。
4.1 bsdiff：经典但吃内存
bsdiff 是 Colin Percival 在 2003 年提出的算法。说实话，它很老，但至今仍是嵌入式差分领域的标杆。为什么？因为它生成的差分包足够小。
它的核心思路是：用后缀排序找到新旧文件的最长公共子串，然后只记录差异。这个算法在压缩率上几乎无敌，但代价也很大——内存占用跟文件大小成正比，而且是好几倍。
我曾经踩过的坑： 在一个只有 64MB RAM 的嵌入式设备上，试图对 20MB 的固件做 bsdiff。结果呢？内存直接爆了。bsdiff 在生成差分包时，需要同时加载新旧两个文件到内存，还要维护一个巨大的后缀数组。所以，如果你的设备内存小于固件大小的 5 倍，我建议你慎重考虑 bsdiff。
使用方式很简单：
# 生成差分包
bsdiff old_firmware.bin new_firmware.bin patch.bsdiff
# 应用差分包
bspatch old_firmware.bin updated_firmware.bin patch.bsdiff参数就三个：旧文件、新文件、输出补丁。没什么花哨的选项。嗯，这里要注意：bspatch 在目标设备上运行时，同样需要大量内存。它会把旧文件和补丁都加载进来，然后重建新文件。
| 特性 | bsdiff |
|---|---|
| 压缩率 | 极高（通常 5%-15%） |
| 生成内存 | O(旧文件大小 + 新文件大小) × 5~8 |
| 应用内存 | O(旧文件大小 + 补丁大小) |
| 适用场景 | 服务器端生成，资源充足的设备 |
4.2 hdiffpatch：速度与压缩率的平衡点
如果你觉得 bsdiff 太吃内存，那 hdiffpatch 是个不错的替代。它由腾讯的工程师开发，专门针对嵌入式场景做了优化。
我记得第一次用 hdiffpatch 是在一个智能家居项目上。设备只有 32MB 内存，固件 12MB。bsdiff 跑不起来，但 hdiffpatch 稳稳的。它用了 HDiff 算法，本质上是一种基于哈希的差异匹配，速度比 bsdiff 快很多，内存占用也小。
# 生成差分包
hdiffz old_firmware.bin new_firmware.bin patch.hdiff
# 应用差分包
hpatchz old_firmware.bin patch.hdiff updated_firmware.binhdiffpatch 支持压缩选项，默认用 zlib。你可以通过参数调整压缩级别，在速度和大小之间做取舍。
我的建议： 如果你的设备内存小于 64MB，优先考虑 hdiffpatch。它在压缩率上只比 bsdiff 差 5%-10%，但内存占用能降低 60% 以上。说白了，这是嵌入式场景下最稳妥的选择。
| 特性 | hdiffpatch |
|---|---|
| 压缩率 | 较高（通常 10%-20%） |
| 生成内存 | O(旧文件大小 + 新文件大小) × 2~3 |
| 应用内存 | O(旧文件大小 + 补丁大小) × 1.5 |
| 适用场景 | 中等资源嵌入式设备 |
4.3 xdelta3：流式处理的王者
xdelta3 是 RFC 3284 VCDIFF 标准的一个实现。它的最大特点是支持流式处理——你不需要把整个文件加载到内存，可以一边读一边算。
你想想看，这对嵌入式设备意味着什么？意味着你可以处理比内存大得多的文件。我在一个网络摄像头项目里用过 xdelta3，固件 50MB，设备内存只有 16MB。bsdiff 和 hdiffpatch 都无能为力，但 xdelta3 跑得稳稳的。
# 生成差分包
xdelta3 -e -s old_firmware.bin new_firmware.bin patch.xdelta3
# 应用差分包
xdelta3 -d -s old_firmware.bin patch.xdelta3 updated_firmware.bin参数说明：-e 表示编码（生成补丁），-d 表示解码（应用补丁），-s 指定源文件。
xdelta3 还支持二级压缩，你可以用 -S 参数指定压缩算法，比如 -S lzma 能得到更小的补丁，但速度会慢一些。
| 特性 | xdelta3 |
|---|---|
| 压缩率 | 中等（通常 15%-30%） |
| 生成内存 | 可配置，最低 O(窗口大小) |
| 应用内存 | 可配置，最低 O(窗口大小) |
| 适用场景 | 大文件、内存受限设备 |
4.4 自定义差分工具开发思路
好，聊完现成的工具，咱们说说怎么自己造一个。你可能会问：有现成的为什么还要自己写？
原因很简单：现实项目往往有特殊需求。比如你的固件是加密的，或者你的文件系统是定制的，又或者你需要把差分算法集成到 bootloader 里——这时候现成工具就不够灵活了。
自定义差分工具的核心思路，说白了就是三步：
- 分块：把新旧文件切成固定大小的块（比如 4KB 或 16KB）。
- 匹配：用哈希或滚动哈希找到新旧块之间的对应关系。
- 编码：记录匹配块的偏移和长度，以及不匹配块的原始数据。
我简单画一下这个流程：
具体实现时，有几个关键点：
- 哈希函数：推荐用 Rabin-Karp 滚动哈希，计算快，适合滑动窗口。
- 匹配策略：贪心匹配最简单，但压缩率一般；最长匹配压缩率好，但算法复杂。
- 编码格式：建议用 TLV（Type-Length-Value）结构，解析简单，扩展性好。
一个小技巧： 如果你不想从零开始，可以在 xdelta3 的源码基础上改。它的 VCDIFF 编码器是模块化的，你只需要替换它的匹配算法，就能做出一个定制版的差分工具。我在一个项目里就是这么干的，省了不少时间。
4.5 工具选型对比总结
最后，我把这三个工具放在一起做个对比，方便你根据项目需求快速决策：
| 对比维度 | bsdiff | hdiffpatch | xdelta3 |
|---|---|---|---|
| 压缩率 | ★★★★★ | ★★★★☆ | ★★★☆☆ |
| 生成速度 | ★★☆☆☆ | ★★★★☆ | ★★★★★ |
| 内存占用 | ★★☆☆☆ | ★★★★☆ | ★★★★★ |
| 流式支持 | 否 | 有限 | 是 |
| 嵌入式友好 | ★★☆☆☆ | ★★★★☆ | ★★★★★ |
| 推荐场景 | 服务器端、资源充足 | 中等资源设备 | 大文件、内存受限 |