4. hdiffpatch 算法原理：设计思路、压缩感知、增量编码、内存优化
hdiffpatch 这套算法，说实话是我在嵌入式差分升级领域里用得最顺手的一套工具。它不像 bsdiff 那样吃内存，也不像 xdelta 那样对旧版本依赖太强。我个人习惯把它叫做「轻量级差分三件套」——设计思路、压缩感知、增量编码、内存优化，这四个点串起来，就是一套完整的差分升级方案。
4.1 设计思路：从「全量替换」到「增量修补」
传统的固件升级，说白了就是把整个新固件包下载下来，覆盖掉旧的。这在几十 KB 的年代还行，现在动辄几 MB、十几 MB 的固件，OTA 升级就成了噩梦。hdiffpatch 的设计思路很直接：只传输变化的部分。
它的核心思想可以拆成三步：
- 分块比对：把旧固件和新固件切成固定大小的块（默认 64KB），逐块做哈希匹配。
- 差异提取：找到匹配的块就直接引用旧固件里的数据，没匹配到的块就作为新增数据存下来。
- 增量编码：对差异部分做压缩编码，进一步缩小补丁体积。
我在项目中遇到过一个问题：有些芯片的 Flash 只有 256KB，新固件 300KB，全量升级根本塞不下。用了 hdiffpatch 之后，补丁包只有 40KB 左右，配合双备份升级策略，稳稳当当。
关键指标对比
| 方案 | 补丁大小 | 内存占用 | 适用场景 |
|---|---|---|---|
| 全量升级 | 100% | 低 | 首次烧录、小固件 |
| bsdiff | 5%-15% | 高（O(n)） | PC、服务器端 |
| hdiffpatch | 8%-20% | 低（O(1)） | 嵌入式、IoT 设备 |
4.2 压缩感知：不是所有数据都值得压缩
你想想看，固件里有些数据是高度随机的——比如加密后的密钥、传感器校准参数。对这些数据做压缩，不仅压不下去，还浪费 CPU 时间。hdiffpatch 引入了一个「压缩感知」机制，说白了就是先判断数据是否可压缩，再决定要不要压缩。
它的判断逻辑很简单：
- 熵值检测：计算数据块的熵值，如果熵值接近 8（即完全随机），直接跳过压缩。
- 快速试压缩：对前 1KB 数据做一次快速 LZSS 压缩，如果压缩率低于 5%，放弃压缩。
- 自适应阈值：根据目标芯片的算力动态调整压缩阈值。比如 Cortex-M0 上阈值设高一点，减少压缩开销。
我曾经踩过一个坑：有一款传感器固件，每次升级都要传输 200KB 的校准表。校准表是随机数生成的，根本压不动。后来加了压缩感知，直接跳过压缩，补丁生成时间从 12 秒降到了 0.8 秒。
小技巧：如果你的固件里包含大量随机数据（如加密密钥、证书），建议在生成补丁前先做一次「可压缩性预检」，能省不少时间。
4.3 增量编码：让补丁更小、更聪明
增量编码是 hdiffpatch 的精髓。它不像 bsdiff 那样用后缀数组做全局匹配，而是用一种叫「滑动窗口 + 哈希链」的局部匹配策略。这样做的好处是内存占用极低——只需要两个 64KB 的窗口缓冲区。
编码流程大致是这样的：
- 窗口对齐：从旧固件和新固件的起始位置各取一个 64KB 窗口。
- 哈希匹配：对新窗口里的每个 4 字节片段计算哈希，去旧窗口的哈希表里找匹配。
- 最长匹配扩展：找到匹配后，向前向后扩展，找到最长的连续匹配段。
- 编码输出：匹配段输出为「偏移量 + 长度」的引用指令，不匹配段输出为原始数据。
嗯，这里要注意：匹配的最小长度是 4 字节。小于 4 字节的匹配不值得做，因为引用指令本身就要占 2-3 个字节，还不如直接存原始数据。
// 增量编码的伪代码示例
void hdiff_encode(uint8_t *old_data, uint32_t old_len,
uint8_t *new_data, uint32_t new_len) {
uint32_t old_pos = 0, new_pos = 0;
while (new_pos < new_len) {
// 尝试在旧数据中匹配
uint32_t match_len = find_match(old_data, old_len,
new_data + new_pos,
new_len - new_pos);
if (match_len >= 4) {
// 输出引用指令
output_copy(old_pos, match_len);
new_pos += match_len;
} else {
// 输出原始数据
output_literal(new_data[new_pos]);
new_pos++;
}
}
}
4.4 内存优化：嵌入式设备的生存之道
嵌入式设备的内存通常只有几十到几百 KB，差分升级算法如果太吃内存，根本跑不起来。hdiffpatch 在内存优化上做了几件事：
- 流式处理：不把整个旧固件和新固件加载到内存，而是分块流式读取。旧固件从 Flash 直接读，新固件从 OTA 缓冲区流式接收。
- 哈希表复用：哈希表只维护当前窗口的数据，窗口滑动时，旧哈希条目被新条目覆盖，不需要额外分配内存。
- 零拷贝输出：补丁输出直接写到目标 Flash 区域，不经过中间缓冲区。这个在 STM32 的 QSPI Flash 上效果特别明显。
我记得有一次在 ESP32 上做差分升级，默认配置下内存占用只有 12KB。对比 bsdiff 动辄几百 KB 的内存需求，hdiffpatch 简直就是为 MCU 量身定做的。
避坑指南：我曾经在内存只有 8KB 的芯片上跑 hdiffpatch，结果哈希表冲突率太高，匹配效率暴跌。后来把窗口大小从 64KB 降到 16KB，内存占用降到 4KB，匹配速度反而上来了。所以，窗口大小不是越大越好，要根据实际内存容量做调整。
4.5 整体流程框架图
下面这张图展示了 hdiffpatch 从输入到输出的完整流程。我建议你把它保存下来，后面讲实战的时候会反复用到。
从图上你可以看到，整个流程是线性的，没有复杂的递归或回溯。这也是 hdiffpatch 能在低端 MCU 上跑起来的原因——算法复杂度是 O(n)，空间复杂度是 O(1)。
4.6 实战中的几个关键参数
最后，我整理了一份参数调优表。这些参数我在多个项目里验证过，你可以直接拿来用：
| 参数 | 默认值 | 推荐范围 | 说明 |
|---|---|---|---|
| 窗口大小 | 64KB | 8KB - 128KB | 内存紧张时调小，匹配精度要求高时调大 |
| 最小匹配长度 | 4 字节 | 4 - 16 字节 | 调大可以减少补丁大小，但增加计算量 |
| 压缩阈值 | 5% | 3% - 10% | 低于此压缩率则跳过压缩 |
| 哈希表大小 | 4096 | 1024 - 8192 | 越大匹配越快，但内存占用也大 |
嗯，这些参数不是死的。我建议你在项目初期先用默认值跑一遍，然后根据实际的内存和 CPU 负载做微调。记住一个原则：嵌入式差分升级，稳定性和内存占用优先于压缩率。