3. bsdiff 算法原理：核心思想、后缀排序、差异编码与合并策略

bsdiff 这个名字，做差分升级的工程师应该都不陌生。它是目前二进制差分领域应用最广的算法之一，很多 OTA 方案底层都在用它。说实话，我第一次接触 bsdiff 时，第一反应是——这玩意儿怎么这么复杂？又是后缀数组又是 BWT 的。但真正啃下来之后，你会发现它的设计思路其实非常清晰。

这一章，我就带你拆解 bsdiff 的四个核心模块：核心思想、后缀排序、差异编码和合并策略。每个部分我都会结合项目中的实际踩坑经历来讲，希望能帮你少走弯路。

3.1 核心思想：把「找相同」变成「找最长匹配」

bsdiff 的核心思想，说白了就是一句话：在新文件中找到与旧文件最长的连续匹配片段，然后只记录差异部分。

你可能会问：这不就是 diff 吗？嗯，传统文本 diff 是按行比较的，但二进制文件没有「行」的概念。bsdiff 的做法是：

  • 把旧文件的所有后缀排序，构建一个索引结构
  • 然后在新文件中逐字节扫描，在索引中查找最长匹配
  • 匹配上的部分用「复制旧数据」指令表示
  • 没匹配上的部分用「插入新数据」指令表示

我当年第一次实现 bsdiff 时，犯过一个低级错误——没考虑内存对齐。结果在 ARM Cortex-M4 上跑出来的补丁包，解压时直接 hardfault。后来才意识到，bsdiff 的匹配算法对内存访问模式很敏感，尤其是嵌入式平台，一定要保证输入缓冲区是 4 字节对齐的。

核心公式：

补丁大小 ≈ 未匹配的新数据 + 匹配位置的偏移量编码

匹配越长，补丁越小。bsdiff 的优化目标就是最大化匹配长度。

3.2 后缀排序：bsdiff 的「索引引擎」

后缀排序是 bsdiff 最核心也最耗时的部分。它的任务是把旧文件的所有后缀按字典序排列，生成一个后缀数组（Suffix Array）。

举个例子，假设旧文件内容是 banana：

后缀 排序后
banana a
anana ana
nana anana
ana banana
na na
a nana

有了这个后缀数组，在新文件中扫描时，就可以用二分查找快速定位最长匹配。bsdiff 用的是 QSufSort 算法，时间复杂度 O(n log n)，空间复杂度 O(n)。

我的经验：在资源受限的嵌入式设备上，后缀排序的内存占用是个大问题。旧文件 1MB，后缀数组就要 4MB（每个 int 4 字节）。我曾经在只有 8MB RAM 的平台上做差分，结果排序阶段直接 OOM。后来改用分块排序 + 外部排序才搞定。

3.3 差异编码：如何高效记录「不一样」

找到匹配之后，剩下的就是差异部分了。bsdiff 的差异编码分为两种：

  1. 控制块（Control Block）：记录匹配的偏移量和长度
  2. 差异块（Diff Block）：记录新数据与旧数据的字节级差异

控制块的结构是这样的：

struct bsdiff_control {
    int32_t diff_len;      // 差异数据的长度
    int32_t copy_len;      // 从旧文件复制的长度
    int32_t seek_offset;   // 在旧文件中的偏移调整量
};

差异块则用 XOR 或减法来编码。bsdiff 默认用的是 XOR 编码：

diff_byte = new_byte ^ old_byte;

为什么用 XOR？因为对于大部分相似的二进制文件，差异字节中会有大量 0x00 或小数值，XOR 后的数据熵更低，更容易被后续的压缩算法（如 bzip2）压缩。

注意：bsdiff 的差异编码是有损的吗？不是。XOR 是可逆操作，合并时再做一次 XOR 就能恢复原始数据。但要注意，如果旧文件和新文件差异过大（比如超过 50%），bsdiff 的补丁大小反而可能超过全量更新。我遇到过客户抱怨补丁太大，一查发现新旧固件换了文件系统格式，差异率高达 80%。这种情况下，bsdiff 并不合适。

3.4 合并策略：从补丁到新文件的「逆过程」

合并是 bsdiff 的逆过程，也是 OTA 升级中在设备端执行的部分。合并策略的核心逻辑如下：

  1. 读取控制块，获取 diff_len 和 copy_len
  2. 从差异块中读取 diff_len 字节，与旧文件对应位置做 XOR，写入新文件
  3. 从旧文件中复制 copy_len 字节到新文件（位置由 seek_offset 调整）
  4. 重复直到新文件生成完毕

伪代码大概是这样的：

while (有新数据) {
    // 处理差异部分
    for (i = 0; i < diff_len; i++) {
        new_data[pos] = old_data[pos] ^ diff_data[i];
        pos++;
    }
    // 处理复制部分
    memcpy(new_data + pos, old_data + copy_pos, copy_len);
    pos += copy_len;
    copy_pos += copy_len + seek_offset;
}

这里有个细节：seek_offset 可以为负。这意味着复制源可以回退到旧文件的更早位置，实现类似「滑动窗口」的效果。我在调试一个 2MB 的固件升级时，发现合并速度特别慢，后来定位到是 seek_offset 频繁为负导致大量随机访问。优化方案是把旧文件预读到内存中，用指针操作代替文件 seek。

3.5 整体流程：一张图看懂 bsdiff

下面这张 SVG 图展示了 bsdiff 从生成补丁到合并的完整流程：

bsdiff 算法核心流程 bsdiff 算法核心流程 旧文件 新文件 后缀排序 最长匹配查找 差异编码 (XOR) 补丁文件 合并策略 新文件输出 生成阶段：旧文件 → 后缀排序 → 匹配查找 → 差异编码 → 补丁文件 合并阶段：补丁文件 + 旧文件 → 合并策略 → 新文件输出

3.6 性能对比：bsdiff 与其他差分算法

我在项目中对比过几种主流差分算法，这里列个表供你参考：

算法 补丁大小 生成速度 合并速度 内存占用 适用场景
bsdiff 最小 慢 中等 高 (O(n)) 服务器端生成，设备端合并
hdiffpatch 中等 中等 快 中等 嵌入式设备
xdelta 较大 快 快 低 实时差分

我的建议：如果你的 OTA 服务器性能足够，设备端 RAM 也充裕（比如 64MB 以上），bsdiff 是最优选择。但如果设备只有 16MB RAM，我建议用 hdiffpatch 或者自己裁剪 bsdiff 的合并端，去掉后缀排序部分，只保留合并逻辑。

3.7 避坑指南：bsdiff 实战中的常见问题

  • 大文件 OOM：旧文件超过 100MB 时，后缀数组需要 400MB+ 内存。我曾经在 256MB RAM 的服务器上跑 bsdiff，直接 swap 爆满。解决方案是分块处理，或者用 mmap 映射文件。
  • 合并速度慢：seek_offset 为负导致大量随机访问。优化方法：把旧文件预读到内存，或者用 readahead 预取。
  • 补丁过大：新旧文件差异率超过 50% 时，bsdiff 的补丁可能比全量更新还大。建议设置阈值，超过阈值自动切换为全量更新。
  • 平台兼容性：bsdiff 的 int32_t 假设 32 位有符号整数。在 64 位平台上要注意文件大小超过 2GB 时的溢出问题。
← 上一章 📖 返回目录 下一章 →