📚 课程目录第2章差分算法基础

差分算法基础：bsdiff、hdiffpatch、xdelta 原理

差分算法，说白了就是找两个文件之间的「不一样」。

我刚开始做嵌入式 OTA 的时候，总觉得差分不就是 diff 嘛，直接打补丁就行了。后来踩了坑才发现——嵌入式设备的差分升级，核心就三个字：省空间。ROM 就那么几 MB，网络带宽也有限，你生成的补丁包要是比全量包还大，那还不如直接整包升级呢。

今天咱们就聊聊三种主流差分算法：bsdiff、hdiffpatch、xdelta。它们各有各的脾气，选对了，升级效率翻倍；选错了，调试起来能让你怀疑人生。

为什么需要不同的差分算法？

你想想看，一个 10MB 的固件，只改了一行代码，生成的补丁包应该多大？理想情况是几 KB。但实际呢？

文本文件（比如配置文件、脚本）：改动通常很小，但位置可能到处跑。
二进制文件（比如编译后的固件、库文件）：改一行代码，整个函数的地址都变了，二进制差异可能很大。
压缩文件（比如 .zip、.gz）：内部结构复杂，直接差分效果很差。

所以，没有一种算法能通吃所有场景。我个人的习惯是：先看文件类型，再选算法。

  核心观点：差分算法的本质是「找最长公共子串」+「编码差异」。不同算法的区别在于怎么找、怎么编码。

bsdiff 算法原理

bsdiff 是 Colin Percival 在 2003 年提出的，专门针对二进制文件。它的核心思路很巧妙：把文件分成「匹配块」和「差异块」。

bsdiff 的工作流程

构建后缀数组：对旧文件建立后缀数组（Suffix Array），用于快速查找最长匹配子串。
扫描新文件：用旧文件的后缀数组，在新文件中找最长匹配片段。
生成差异流：匹配的部分用「复制」指令，不匹配的部分用「插入」指令。
压缩输出：最后用 bzip2 压缩差异流，生成补丁文件。

我记得有一次做路由器固件升级，旧固件 8MB，新固件只改了 3 个函数。用 bsdiff 生成的补丁只有 120KB。我当时还不太信，特意解压看了下——确实只记录了那几处差异。

适用场景：固件升级、二进制库更新、大型可执行文件差分。
缺点：内存消耗大（需要加载整个旧文件到内存），不适合资源受限的嵌入式设备。

bsdiff 的数学本质

bsdiff 的核心是最长公共子串（LCS）的变种。它不追求全局最优，而是用贪心策略找局部最长匹配。这样做的好处是速度快，坏处是补丁包可能不是最小。

// bsdiff 核心伪代码
function bsdiff(old_file, new_file):
    suffix_array = build_suffix_array(old_file)
    patch = []
    pos = 0
    while pos < len(new_file):
        match_len = find_longest_match(suffix_array, new_file[pos:])
        if match_len > 0:
            patch.append(COPY, pos, match_len)
            pos += match_len
        else:
            patch.append(INSERT, new_file[pos])
            pos += 1
    return compress(patch)

hdiffpatch 算法原理

hdiffpatch 是 bsdiff 的「升级版」，由 Google 的工程师改进而来。它主要解决了两个问题：内存占用高和对大文件支持不好。

hdiffpatch 的改进点

分块处理：把大文件切成固定大小的块（默认 64KB），逐块差分。这样内存占用可控。
增量哈希：用滚动哈希（Rabin-Karp）代替后缀数组，查找速度更快。
差异编码优化：对差异数据用更紧凑的编码方式，减少补丁体积。

我曾在一次车机系统升级中用过 hdiffpatch。车机固件有 500MB，bsdiff 直接内存溢出了。换成 hdiffpatch 后，内存占用控制在 200MB 以内，补丁包大小也只比 bsdiff 大了 5% 左右。嗯，这个 trade-off 我觉得值。

注意：hdiffpatch 的分块策略可能导致跨块的匹配被拆散，补丁包会比 bsdiff 略大。但内存受限场景下，这是必要的牺牲。

xdelta 算法原理

xdelta 走的是另一条路——它基于VCDIFF（RFC 3284）标准，更通用，也更轻量。

xdelta 的核心机制

滑动窗口：在旧文件上开一个滑动窗口（默认 64KB），在新文件中查找匹配。
哈希索引：对窗口内的数据建立哈希表，加速匹配查找。
指令编码：用 ADD、COPY、RUN 三种指令描述差异。
流式输出：边扫描边输出，不需要加载整个文件到内存。

xdelta 最大的优势是流式处理。我做过一个测试：对一个 2GB 的数据库文件做差分，bsdiff 直接挂了，hdiffpatch 用了 1.2GB 内存，xdelta 只用了 128MB。虽然补丁包大了 10%，但在服务器端升级场景下，内存比带宽贵多了。

  一句话总结：
  bsdiff：补丁最小，但吃内存。
hdiffpatch：内存和补丁大小的平衡点。
xdelta：内存最省，适合大文件和流式场景。

三种算法对比

特性	bsdiff	hdiffpatch	xdelta
算法基础	后缀数组 + bzip2	滚动哈希 + 分块	滑动窗口 + VCDIFF
内存消耗	高（需加载整个文件）	中（分块处理）	低（流式处理）
补丁大小	最小	较小	中等
适用场景	小文件、二进制固件	中等文件、嵌入式	大文件、流式升级
标准支持	无标准	无标准	RFC 3284

差分算法的核心流程

下面这张图展示了三种算法的共性流程。说白了，不管算法怎么变，套路都是一样的：找匹配 → 编码差异 → 压缩输出。

如何选择？我的经验

做了这么多年差分升级，我总结了一套选择策略：

嵌入式设备（内存 < 64MB）：优先 xdelta。流式处理不占内存，虽然补丁大一点，但设备跑得动才是王道。
服务器端（内存充足）：用 bsdiff。补丁最小，节省带宽。我曾经给一个 500MB 的二进制库做差分，bsdiff 补丁只有 3MB，传输时间从 10 秒降到 0.5 秒。
中等设备（内存 128MB~512MB）：hdiffpatch 是平衡点。补丁比 bsdiff 大 5%~10%，但内存消耗只有 bsdiff 的 1/3。
压缩文件（.zip、.gz）：别直接用差分算法。先解压，再差分，最后重新压缩。我见过有人直接对 .zip 做差分，补丁包比原文件还大。

避坑指南：我曾经在一个项目里直接用 bsdiff 对加密固件做差分，结果补丁包几乎和全量包一样大。为什么？因为加密后的数据是伪随机的，根本找不到匹配。记住：差分算法对加密数据无效。如果固件加密了，要么在加密前做差分，要么用全量升级。

小结

三种算法，三种哲学：

bsdiff：追求极致压缩，不惜内存。
hdiffpatch：在内存和压缩之间找平衡。
xdelta：轻量、流式、通用。

没有最好的算法，只有最合适的场景。你选哪个，取决于你的设备有多少内存、网络带宽多大、文件有多大。嗯，这就是差分算法的「不可能三角」——补丁大小、内存消耗、处理速度，你最多只能优化两个。