3、bsdiff算法详解：bsdiff的工作原理、bsdiff的匹配策略、bsdiff的优缺点分析
好，咱们进入正题。bsdiff 这个算法，在 OTA 差分领域可以说是「老大哥」级别的存在。我记得 2018 年刚接手一个车机项目时，供应商给的差分包动不动就 200MB，后来我换成 bsdiff，直接压到 30MB 以内。嗯，今天我就把它的底裤扒干净。
3.1 bsdiff 的工作原理
bsdiff 的核心思想其实很简单：找到新旧两个二进制文件之间的最长公共子串，然后只记录差异部分。但它的实现方式非常巧妙，不是逐字节比较，而是用了一种叫「后缀排序」的技术。
说白了，bsdiff 把旧文件的所有后缀字符串排了个序，然后拿着新文件去这个排序后的「字典」里查。查到了，就记录一个「从旧文件第 X 字节开始，复制 Y 个字节」的指令。查不到，就直接把新字节写进去。
整个流程分三步走：
- 构建后缀数组：对旧文件的所有后缀进行排序，生成一个索引表。这一步最耗时，但只做一次。
- 扫描匹配：遍历新文件，在后缀数组中二分查找最长匹配。匹配到的部分用
COPY指令，没匹配到的用INSERT指令。 - 生成补丁：把指令序列和插入的新数据压缩打包，形成最终的差分包。
核心公式：差分包大小 ≈ 新文件大小 - 旧文件与新文件的公共部分大小 + 控制信息开销
我在项目中遇到过一个问题：旧文件如果被修改过（比如升级过程中断电），后缀数组就全废了，生成的差分包会异常大。所以，一定要保证旧文件的完整性。
3.2 bsdiff 的匹配策略
bsdiff 的匹配策略，我总结为「贪心 + 回溯」的组合拳。你想想看，如果单纯贪心，每次只找最长匹配，那遇到局部最优解就卡住了。bsdiff 是怎么解决的？
它的策略是这样的：
- 最小匹配长度：默认 8 字节。小于 8 字节的匹配直接放弃，因为记录指令的开销比存原始数据还大。
- 滑动窗口：匹配时不是固定位置，而是允许在旧文件中前后偏移最多 4096 字节。这能应对代码中插入或删除少量字节的情况。
- 回溯优化：如果当前匹配长度超过 128 字节，bsdiff 会尝试向前回溯，看看能不能合并多个小匹配为一个大连贯匹配。
举个例子，旧文件有 100 字节，新文件在中间插了 10 字节。bsdiff 会这样处理：
旧文件: [0-49][50-99]
新文件: [0-49][A][B][C]...[50-99]
匹配结果:
COPY 0, 50 // 复制旧文件 0-49 字节
INSERT 10 // 插入新加的 10 字节
COPY 50, 50 // 复制旧文件 50-99 字节你看，它把插入和复制分开了。这就是 bsdiff 的高明之处——不追求完美匹配，而是追求整体压缩率最优。
我的经验：在车机固件中，如果新旧版本之间只有函数内部的少量修改（比如改了个条件判断），bsdiff 的匹配率能达到 95% 以上。但如果涉及全局变量重排或结构体字段顺序调整，匹配率会骤降到 60% 以下。这时候我建议先用工具做一次「符号重排」再跑 bsdiff。
3.3 bsdiff 的优缺点分析
没有银弹。bsdiff 很强，但也不是万能的。我把它掰开揉碎了讲给你听。
| 维度 | 优点 | 缺点 |
|---|---|---|
| 压缩率 | 极高，尤其对二进制文件（如 ELF、BIN）效果显著，通常能压到原大小的 5%-15% | 对文本文件（如 JSON、XML）压缩率一般，不如直接 gzip |
| 内存消耗 | 生成补丁时只需加载旧文件，新文件可以流式读取 | 构建后缀数组需要 O(n) 内存，n 为旧文件大小。1GB 的旧文件大约需要 5GB 内存 |
| 时间性能 | 应用补丁非常快，O(n) 时间复杂度，适合车机端 | 生成补丁极慢，O(n log n) 甚至 O(n²) 在最坏情况下。我见过一个 500MB 的固件，在服务器上跑了 40 分钟 |
| 鲁棒性 | 对字节对齐不敏感，能处理任意二进制差异 | 对文件结构变化敏感，比如 ELF 文件的节区表重排会导致匹配率暴跌 |
曾经踩过的坑：有一次我把 bsdiff 直接用在车机内核镜像上，结果差分包只有 8MB，心里美滋滋。结果刷进去后系统起不来。查了两天才发现——bsdiff 把内核的校验和字段也当成普通数据匹配了，导致解压后校验失败。从那以后，我养成了一个习惯：对包含校验和、签名、时间戳的字段，先做「零化处理」再跑差分。
3.4 什么时候该用 bsdiff？
我个人习惯这样判断：
- 适合用：固件大小 100MB 以上，新旧版本差异小（修改率 < 20%），且服务器端计算资源充足。
- 不适合用：固件小于 10MB，或者新旧版本几乎重写（修改率 > 50%），这时候直接全量推送更划算。
- 慎用：车机端内存小于 256MB 的设备，因为应用补丁时需要同时加载旧文件、补丁和新文件，内存峰值可能翻倍。
嗯，bsdiff 就讲到这里。下一节我会讲它的改进版——hdiffpatch，以及如何在车规级场景下做工程化落地。你先把 bsdiff 的原理吃透，后面才好理解那些花里胡哨的优化技巧。