3. 差分算法原理：bsdiff/bspatch原理、增量包生成机制、差分算法在鸿蒙中的优化
好，咱们进入第三章。这一章我打算聊聊差分算法。说实话，这是OTA升级里最核心的技术之一。没有它，你每次升级都得下载整个系统镜像，那流量消耗可就大了去了。我自己在早期做嵌入式Linux OTA时，就吃过这个亏——一个200MB的固件，用户升级一次要等半小时，体验极差。
后来接触了bsdiff/bspatch，才算是打开了新世界的大门。说白了，差分算法就是找出新旧版本之间的差异，只传输差异部分。嗯，这里要注意，不是简单的文件对比，而是二进制级别的差异分析。
3.1 bsdiff/bspatch原理
bsdiff这个名字，我猜你也能猜出来——binary diff。它是由Colin Percival在2003年提出的算法。我当年第一次读他的论文时，说实话，被那个数学推导绕晕了。但实际用起来，效果是真的好。
它的核心思想是什么？我简单给你拆解一下：
- 后缀排序：对旧文件的所有后缀进行排序，构建一个后缀数组。这一步是为了快速找到最长公共子串。
- 匹配查找：在新文件中，用旧文件的后缀数组去匹配，找到最长的相同片段。
- 差异编码：把匹配到的部分标记为“复制”，没匹配到的部分标记为“插入”。
- 压缩输出：最后用bzip2或zlib把差异数据压缩一下。
你可能会问，为什么要搞这么复杂？直接按字节对比不行吗？我告诉你，不行。因为系统镜像里，很多数据只是发生了位移。比如你加了一个函数，后面的代码地址全变了。按字节对比，你会发现几乎全是差异。但bsdiff能识别出这种位移，只记录“从哪里复制多少字节”，效率高得多。
bspatch就是逆向操作。它读取差异文件，根据指令从旧文件中复制数据，或者插入新数据，最终拼出完整的新文件。我在项目中遇到过一个问题——bspatch在内存受限的设备上容易崩溃。后来发现是它默认把整个旧文件加载到内存里。嗯，这个坑我们后面再细说。
核心公式（简化版）：
增量包大小 ≈ 新文件大小 - 新旧文件公共部分大小 + 控制信息开销
实际压缩后，增量包通常只有新文件的5%-30%。
3.2 增量包生成机制
增量包是怎么生成的？我习惯把它分成三步：
- 差异计算：用bsdiff对比新旧版本，生成一个patch文件。
- 元数据打包：把patch文件、版本信息、校验和、签名等打包成一个增量包。
- 压缩与加密：对增量包进行压缩，必要时加密。
这里有个细节，很多人会忽略——分块差分。你想想看，一个系统镜像可能有几百个文件。如果整体做差分，一旦某个地方出错，整个升级就失败了。我建议的做法是：
- 把系统镜像按文件或分区拆成多个块
- 对每个块单独做差分
- 每个块生成独立的校验和
这样做的好处是，升级时可以并行处理，出错也能回滚到上一个块，而不是整个系统。
我曾经在一个项目中，因为没做分块差分，结果用户升级到一半断电了。重启后系统直接变砖。后来我们改成了分块差分+断点续传，才彻底解决了这个问题。
避坑指南：增量包生成时，一定要考虑旧版本的多样性。比如你有V1.0、V1.1、V1.2三个版本，用户可能从任何一个版本升级到V2.0。你需要为每个旧版本生成对应的增量包。我曾经见过一个团队只生成了V1.0到V2.0的增量包，结果V1.1的用户升级时直接下载了完整包，流量浪费了。
3.3 差分算法在鸿蒙中的优化
鸿蒙系统对差分算法做了不少优化。我参与过其中一部分工作，这里挑几个重点说说。
3.3.1 内存优化
bsdiff原版在计算差分时，需要把新旧两个文件都加载到内存里。对于几百MB的系统镜像，这简直是灾难。鸿蒙的做法是：
- 流式处理：把文件分成多个窗口，每次只处理一个窗口的数据。
- 内存池复用：后缀数组和匹配结果都放在预分配的内存池里，避免频繁malloc/free。
我记得当时测试，一个200MB的镜像，原版bsdiff需要1.2GB内存。优化后，鸿蒙只需要256MB。嗯，这个差距在嵌入式设备上是致命的。
3.3.2 算法加速
bsdiff最耗时的部分是后缀排序。鸿蒙引入了多线程并行排序，把一个大数组拆成多个小数组，分别排序后再合并。另外，还用了SIMD指令集来加速字符串比较。
我做过一个对比测试：
| 算法版本 | 差分时间（秒） | 内存占用（MB） | 增量包大小（MB） |
|---|---|---|---|
| 原版bsdiff | 45 | 1200 | 18 |
| 鸿蒙优化版 | 12 | 256 | 19 |
你看，时间缩短了将近4倍，内存降到了原来的五分之一，而增量包大小只增加了1MB。这个代价完全可以接受。
3.3.3 安全增强
差分算法本身不涉及安全，但鸿蒙在增量包生成时加入了签名和校验机制。具体来说：
- 每个差分块都带有独立的哈希值
- 增量包整体使用私钥签名
- 升级时，设备会逐块验证签名和哈希
为什么要逐块验证？你想想看，如果只验证整体签名，攻击者可以在某个块里植入恶意代码，只要整体哈希不变就行。但逐块验证就不一样了——每个块都被锁定，动一个字节都不行。
警告：差分算法不是万能的。如果新旧版本差异过大（比如超过50%），增量包的大小可能接近甚至超过完整包。这时候，我建议直接使用完整包升级。鸿蒙的OTA框架会自动判断这个阈值，当增量包大小超过完整包的80%时，自动切换为全量升级。
3.3.4 兼容性处理
鸿蒙还做了一件很聪明的事——版本兼容性矩阵。它记录了每个版本之间的差分效果。比如从V1.0到V2.0，差分效果很好，增量包只有15MB。但从V1.1到V2.0，因为中间有大量代码重构，增量包达到了80MB。系统会根据这个矩阵，自动选择最优的升级路径。
我个人觉得，这个设计非常实用。它避免了“一刀切”的升级策略，让每个用户都能获得最佳的升级体验。
好了，这一章的内容就到这里。差分算法看起来简单，但实际落地时坑很多。我建议你在自己的项目里，先从bsdiff/bspatch入手，跑通流程，再逐步优化。下一章，我们会聊聊升级包的签名与校验机制，那又是另一个有意思的话题。