4. 存储与分区设计
好，我们进入第四章。前面聊了 bsdiff 的核心思路，这一章我带你看看 hdiffpatch 是怎么做的。说实话，我第一次接触 hdiffpatch 时，第一反应是——这玩意儿比 bsdiff 聪明不少。
hdiffpatch 的全称是 Hierarchical DIFF/PATCH，核心思想就一个字：分层。它把差分过程拆成多个层次，每一层干一件事，互不干扰。这种设计哲学，说白了就是「分而治之」的工程化落地。
4.1 设计哲学：分层与渐进
bsdiff 的做法是「一次匹配，全局编码」。hdiffpatch 不一样，它把匹配和编码拆成多个阶段，每个阶段只处理特定粒度的数据。
我个人习惯把 hdiffpatch 的分层策略总结成三句话：
- 粗匹配层：先找大块相同区域，比如整个函数、整段配置数据
- 细匹配层：在大块之间，找小块相同区域，比如变量名、常量值
- 编码层：把匹配结果用紧凑的格式写进补丁文件
为什么要这么干？你想想看，如果两个版本之间，大部分代码都没变，只是改了几个函数实现。bsdiff 会花大量时间在全局搜索上，而 hdiffpatch 先锁定大块不变区域，再在变化区域里找小匹配，效率高得多。
核心设计哲学：
- 分层匹配：粗粒度 → 细粒度，逐步缩小搜索范围
- 渐进编码：先编码大块匹配，再编码小块差异
- 局部优先：优先利用局部性原理，减少全局搜索开销
我在项目中遇到过一个问题：一个固件从 v1.0 升级到 v1.1，改动量不到 5%，但 bsdiff 生成的补丁居然有原始固件的 30% 大小。后来换成 hdiffpatch，补丁直接降到 8%。原因就是 bsdiff 在全局匹配时，把很多本可以合并的小匹配拆散了，而 hdiffpatch 的分层策略保住了大块匹配的完整性。
4.2 匹配策略：从粗到细的渐进式搜索
hdiffpatch 的匹配过程分两步走，我画了张图帮你理解：
你看，粗匹配层先干脏活累活，把大块相同区域找出来。细匹配层只处理粗匹配剩下的「残差区域」，工作量小很多。
4.2.1 粗匹配：哈希 + 滑动窗口
粗匹配阶段，hdiffpatch 用了一个很实用的技巧——滚动哈希。它在新旧版本上同时滑动一个 64 字节的窗口，计算哈希值。如果哈希值相同，就认为这个窗口内的数据匹配上了。
具体步骤是这样的：
- 建立索引：对旧版本所有 64 字节块的哈希值建索引
- 扫描新版本：对新版本每个 64 字节块计算哈希，查索引
- 扩展匹配：找到匹配后，向两边扩展，直到不匹配为止
- 记录结果：记录匹配块的起始位置和长度
避坑指南：我曾经在粗匹配阶段踩过一个坑——哈希冲突。滚动哈希虽然快，但冲突率不低。后来我加了一层「确认检查」：哈希匹配后，再逐字节比对一次。虽然多了点开销，但避免了误匹配导致的补丁膨胀。嗯，这个坑值得你记住。
4.2.2 细匹配：后缀数组 + 局部搜索
粗匹配结束后，新旧版本都剩下一些「未匹配区域」。这些区域通常很小，但包含真正的差异。细匹配就在这些区域里找小块的相同数据。
hdiffpatch 在细匹配层用了后缀数组。为什么不用哈希了？因为未匹配区域小，后缀数组的 O(n log n) 构建时间可以接受，而且匹配精度更高。
细匹配的最小匹配长度是 4 字节。为什么是 4？我个人的经验是：小于 4 字节的匹配，编码开销比直接存差异还大，得不偿失。
4.3 编码策略：紧凑的补丁格式
匹配完了，怎么把结果写进补丁文件？hdiffpatch 的编码策略很讲究，它把补丁分成三个部分：
| 补丁段 | 内容 | 编码方式 |
|---|---|---|
| 控制段 | 操作序列（COPY / ADD / DIFF） | 变长整数 + 偏移量 |
| 差异段 | 新旧版本的逐字节差异 | XOR 或差值编码 |
| 新增段 | 新版本独有的数据 | 原始字节 + 长度前缀 |
控制段是补丁的「骨架」，它告诉 patcher：这里要 COPY 旧版本的哪一段，那里要 ADD 一段新数据，或者这里要 APPLY 一段差异。
hdiffpatch 用变长整数来编码控制段。变长整数的好处是：小数字只占 1 个字节，大数字才占多个字节。补丁里大部分偏移量和长度都是小数字，所以整体压缩率很高。
编码策略的关键点：
- COPY 操作：只编码「旧版本偏移 + 长度」，不存数据
- ADD 操作：编码「长度 + 新数据」，用于新增内容
- DIFF 操作：编码「长度 + 差异字节」，用于修改内容
- 变长整数：小数字 1 字节，大数字自动扩展
4.4 与 bsdiff 的对比
好，到了大家最关心的环节——hdiffpatch 和 bsdiff 到底差在哪？我直接给你一张对比表：
| 对比维度 | bsdiff | hdiffpatch |
|---|---|---|
| 匹配策略 | 全局后缀数组，一次匹配 | 分层匹配，粗→细渐进 |
| 最小匹配长度 | 通常 8 字节 | 粗匹配 64 字节，细匹配 4 字节 |
| 内存占用 | O(n)，n 为旧版本大小 | O(m)，m 为未匹配区域大小 |
| 补丁大小 | 大改动时更优 | 小改动时更优 |
| 生成速度 | 慢（后缀数组构建） | 快（分层减少搜索范围） |
| 适用场景 | 源码级差分 | 二进制固件、配置数据 |
你看，bsdiff 和 hdiffpatch 没有绝对的优劣，只有场景适配的问题。bsdiff 在源码级差分（比如文本文件）上表现很好，因为源码的重复模式多，后缀数组能充分利用。而 hdiffpatch 在二进制固件上更胜一筹，因为固件里大量数据是「整体搬移」的，分层匹配正好抓住这个特点。
注意：不要盲目迷信某个算法。我在一个项目中试过 bsdiff 和 hdiffpatch，结果完全相反——bsdiff 补丁 2MB，hdiffpatch 补丁 500KB。但换了一个项目，bsdiff 反而更小。所以，用数据说话，跑一遍 benchmark 再决定。
4.4.1 内存对比：一个实际案例
我记得有一次，客户要求在 256KB RAM 的 MCU 上做差分升级。bsdiff 生成补丁时，内存峰值到了 1.2MB，直接爆了。换成 hdiffpatch，内存峰值只有 180KB，顺利通过。
为什么会这样？bsdiff 需要把整个旧版本加载到内存里建后缀数组。而 hdiffpatch 的分层策略，让它只需要在内存里保留「当前处理窗口」的数据，未匹配区域小，内存自然就小。
4.4.2 补丁大小对比：谁更小？
补丁大小取决于改动模式。我总结了一个经验法则：
- 改动分散（比如改了几十个函数）：bsdiff 更优，因为后缀数组能找到全局最优匹配
- 改动集中（比如只改了一个模块）：hdiffpatch 更优，因为分层策略保住了大块匹配
- 新增大量数据：两者差不多，新增数据无法匹配，补丁大小主要取决于新增量
嗯，这里要注意：补丁大小不是唯一指标。生成时间、内存占用、打补丁速度，都要综合考虑。我见过有人为了省 10% 的补丁大小，把生成时间从 5 秒拖到 5 分钟，这在 CI/CD 流水线里根本不可接受。
4.5 小结
hdiffpatch 的设计哲学，说白了就是「别一上来就干全局匹配，先分层，再渐进」。粗匹配用哈希快速扫一遍，细匹配用后缀数组精准定位，编码用变长整数压缩。这套组合拳，在二进制固件差分场景下特别有效。