差分算法基础：从全量到差分的思维转变

各位同学，今天我们来聊聊差分算法。说实话，我刚入行做OTA那会儿，觉得全量升级挺香的——简单粗暴，不容易出错。直到有一次，我在一个车机项目里遇到了存储空间不足的问题，才真正意识到差分算法的价值。

那是个什么情况呢？一个ECU的flash只有2MB，但固件版本从v1.0升级到v1.1，全量包就有1.8MB。用户的车机里还存着导航数据、音乐文件……根本塞不下。后来我改用差分算法，升级包压缩到了200KB，问题迎刃而解。

好，我们正式进入正题。

什么是差分算法

差分算法，说白了就是「只传变化的部分」。你想想看，两个版本的固件，大部分代码其实是一样的。比如你修复了一个bug，可能只改了3个函数，其他99%的代码都没动。那为什么要把整个固件重新传一遍呢？

差分算法的核心思路是：

• 在服务器端：对比新旧两个版本，找出差异，生成一个「差分包」
• 在车端：用旧版本加上差分包，还原出新版本

这个过程，有点像拼图。旧版本是已经拼好的部分，差分包是缺失的那几块，拼起来就是完整的新版本。

差分算法的数学原理

嗯，这里我尽量讲得通俗一点。差分算法的数学基础，其实就两个核心操作：

1. 差异检测

怎么找出两个文件的不同？最经典的方法是「滑动窗口哈希」。我简单解释一下：

• 把旧文件切成固定大小的块（比如每块64字节）
• 对每个块计算一个哈希值（类似指纹）
• 在新文件里滑动窗口，同样计算哈希值
• 哈希值匹配的，说明这块没变；不匹配的，就是变化的部分

我在项目中遇到过一个问题：如果块大小设置不合理，会导致差分效率极低。比如块太大，细微的改动会被忽略；块太小，哈希计算量暴增。我个人习惯用64-128字节的块大小，在大多数场景下表现都不错。

2. 差异编码

找到差异后，怎么高效地表示这些差异？常用的方式有两种：

• 复制指令：从旧文件的某个位置，复制一段数据到新文件
• 插入指令：直接插入一段新数据

举个例子，旧文件是「ABCDEFG」，新文件是「ABCDXFG」。差分包可以表示为：

复制 0, 4  // 从位置0复制4个字节：ABCD
插入 "X"   // 插入新字符X
复制 5, 2  // 从位置5复制2个字节：FG

你看，原本7个字节的内容，差分包只用了3条指令就搞定了。这就是差分算法的魔力。

差分 vs 全量升级：优劣对比

很多同学会问：既然差分这么好，为什么不全用差分？其实，每种方案都有它的适用场景。我整理了一个对比表格，方便大家理解：

对比维度	差分升级	全量升级
升级包大小	小（通常为全量的5%-30%）	大（整个固件）
传输时间	短	长
存储需求	低（车端需保留旧版本）	高（需足够空间存放全量包）
计算开销	高（需要差分/还原计算）	低（直接写入即可）
可靠性	依赖旧版本完整性	独立，不依赖旧版本
适用场景	小版本迭代、存储受限	大版本升级、首次刷写

从表格可以看出，差分升级最大的优势是「省空间、省流量」。但代价是什么呢？计算开销和可靠性风险。

我举个例子你就明白了。有一次，某个ECU的旧版本被意外损坏了，结果差分还原失败，车机直接变砖。后来我们加了一个校验机制：在还原之前，先检查旧版本的完整性。如果旧版本有问题，就自动切换到全量升级。

实际项目中的选择策略

说了这么多，到底该怎么选？我分享一个我在项目中常用的决策流程：

1. 先评估差异大小：用工具对比新旧版本，看差异占比
2. 再评估车端资源：flash剩余空间、RAM大小、CPU性能
3. 最后考虑可靠性：旧版本是否可恢复？有没有备份？

如果差异小于30%，且车端资源紧张，我倾向于用差分。如果差异大于40%，或者旧版本状态不确定，我会选择全量升级。

当然，还有一种折中方案：混合升级。把固件分成多个模块，变化大的模块用全量，变化小的用差分。这个我们后面章节会详细讲。

好，这一章就到这里。下一章我们会深入讲解bsdiff和hdiffpatch这两种主流差分算法的实现细节，到时候我会分享一些具体的代码优化技巧。