3. bsdiff算法详解：bsdiff的历史、核心数据结构（后缀数组、哈希表）、差异计算流程
好，咱们今天来聊聊bsdiff。说实话，在OTA差分升级这个领域，bsdiff绝对是个绕不开的经典算法。我最早接触它是在2012年，当时做一个物联网网关的远程升级，压缩率死活下不来，后来换成bsdiff，效果立竿见影。
3.1 bsdiff的历史：一个老牌算法的前世今生
bsdiff是Colin Percival在2003年提出的。嗯，你没看错，二十多年前的东西了。但它的设计思想至今仍在影响很多现代差分算法。
Colin当时的目标很明确：生成尽可能小的补丁包。他借鉴了bzip2的压缩思路，但核心创新在于——用后缀数组来高效匹配新旧文件中的相同片段。
我个人觉得，bsdiff最厉害的地方不是它有多快，而是它能在极小的补丁体积和可接受的运行时间之间找到平衡。我在一个资源受限的MCU项目上试过，生成补丁花了3分钟，但补丁大小只有原始固件的5%。值不值？太值了。
核心观点： bsdiff不是最快的差分算法，但它在补丁压缩率上长期处于第一梯队。对于嵌入式OTA来说，补丁大小往往比生成时间更重要。
3.2 核心数据结构：后缀数组
后缀数组是bsdiff的基石。说白了，它就是将一个字符串的所有后缀按字典序排序后，记录下每个后缀的起始位置。
举个例子，假设旧固件内容是 "banana"：
后缀列表：
0: banana
1: anana
2: nana
3: ana
4: na
5: a
排序后：
5: a
1: anana
3: ana
0: banana
4: na
2: nana
后缀数组 SA = [5, 1, 3, 0, 4, 2]为什么要搞这么复杂？因为有了后缀数组，我们就能在O(log n)时间内找到任意子串在旧文件中的所有出现位置。你想想看，新固件里有一段代码，我们想知道它在旧固件里有没有出现过，用后缀数组一查就知道。
我在项目中遇到过一个问题：旧固件有2MB，新固件有2.1MB，如果用暴力匹配找相同片段，复杂度是O(n²)，根本跑不动。但用后缀数组，生成时间从几小时降到了几十秒。
避坑指南： 后缀数组的构建算法有很多种，bsdiff用的是SA-IS算法，时间复杂度O(n)。我曾经试过用简单的倍增法替代，结果在1MB以上的文件上慢得离谱。所以，不要自己瞎改核心算法。
3.3 核心数据结构：哈希表
后缀数组解决了「找相同片段」的问题，但bsdiff还需要一个东西来快速定位——哈希表。
bsdiff的哈希表其实是一个链式哈希，它把旧文件中每个可能的匹配位置都存下来。具体来说：
- 哈希表的key是某个固定长度（通常是8字节）的哈希值
- value是旧文件中所有出现该哈希值的位置列表
为什么需要哈希表？因为后缀数组虽然能查，但每次查询都要做二分查找，对于大量的小片段匹配来说，开销还是有点大。哈希表可以做到O(1)的查找，虽然会有哈希冲突，但整体效率高得多。
嗯，这里要注意：bsdiff的哈希表不是用来替代后缀数组的，而是配合使用。哈希表负责快速找到候选匹配位置，后缀数组负责在这些候选中找到最长的匹配。
| 数据结构 | 作用 | 时间复杂度 |
|---|---|---|
| 后缀数组 | 查找最长公共子串 | O(log n) |
| 哈希表 | 快速定位候选位置 | O(1) 平均 |
3.4 差异计算流程：bsdiff到底怎么工作的？
好了，有了后缀数组和哈希表这两个工具，我们来看看bsdiff的完整工作流程。我把它拆成三步：
第一步：扫描新文件，寻找匹配
bsdiff会从左到右扫描新文件。对于新文件中的每个位置，它尝试在旧文件中找到最长的匹配片段。
具体做法是：
- 取新文件当前位置开始的8字节，计算哈希值
- 在哈希表中查找所有候选位置
- 对每个候选位置，用后缀数组找到最长匹配
- 选择最长的那个匹配
为什么会这样设计？因为哈希表能快速缩小范围，后缀数组能精确找到最长匹配。两者缺一不可。
第二步：生成差异指令
找到匹配后，bsdiff会生成三种指令：
- INSERT：新文件中有，旧文件中没有的数据，直接插入
- COPY：新文件和旧文件相同的数据，只记录位置和长度
- DIFF：新文件和旧文件相似但不完全相同的数据，记录差异字节
我刚开始学bsdiff时，一直不理解为什么要有DIFF指令。后来在一个项目中，旧固件和新固件只有几个字节的差异，如果用INSERT+COPY，补丁反而更大。DIFF指令就是专门处理这种情况的。
注意： DIFF指令不是简单的「新数据减旧数据」，而是用了一种叫字节级差分编码的技术。它会把相似的数据压缩成很小的差异信息。我曾经踩过一个坑：以为DIFF就是做减法，结果自己实现了一个版本，补丁大小反而膨胀了3倍。
第三步：压缩输出
bsdiff最后一步是把所有指令序列用bzip2压缩。为什么用bzip2而不是gzip？因为bzip2在压缩率上更优，虽然慢一点，但补丁包更小。
我个人习惯是：如果设备端解压能力有限，可以考虑换成lzma或者zstd。但默认的bzip2在大多数场景下已经够用了。
3.5 一个完整的差异计算示例
为了让你更直观地理解，我举个简单的例子：
旧文件: "Hello, world! This is version 1.0"
新文件: "Hello, world! This is version 2.0"
bsdiff的处理过程：
1. 扫描到 "Hello, world! This is version "，发现完全匹配 → COPY指令
2. 扫描到 "1.0" vs "2.0"，发现不匹配 → DIFF指令（差异只有1个字节）
3. 最终补丁包含：1个COPY指令 + 1个DIFF指令
补丁大小：大约只有原始文件的10%你想想看，如果不用差分算法，直接传整个新文件，那得浪费多少带宽？
3.6 bsdiff的局限性
说了这么多优点，我也得泼点冷水。bsdiff不是万能的：
- 内存占用高：后缀数组需要存储整个旧文件的所有后缀索引，对于大文件来说，内存消耗是O(n)。我在一个只有64KB RAM的MCU上试过，根本跑不起来。
- 生成速度慢：尤其是构建后缀数组那一步，对于10MB以上的文件，可能需要几分钟。
- 不适合流式处理：bsdiff需要一次性加载整个旧文件和新文件到内存，不能边接收边处理。
我曾经在一个项目中，旧固件有50MB，MCU只有256KB RAM。bsdiff根本没法用，最后换成了xdelta3。所以，选算法一定要看硬件条件。
总结： bsdiff是嵌入式OTA差分升级的经典算法，核心在于后缀数组+哈希表的组合。它生成的补丁体积小，但内存和计算开销大。适合资源丰富的网关、服务器端生成补丁，设备端只负责应用补丁的场景。
下一章我会讲bsdiff的变种和改进算法，包括如何降低内存占用、如何提高生成速度。如果你在实际项目中遇到过bsdiff的坑，欢迎交流。