2、差分算法基础：二进制差异、字节级比较、块级比较、哈希与校验和

各位同学，欢迎来到第二章。上一章我们聊了差分升级能省多少流量、怎么个省法。今天咱们把地基打牢——差分算法到底是怎么“找不同”的？

说白了，差分升级的核心就一句话：找出新旧版本之间的差异，只传输差异部分。但“找差异”这三个字，背后藏着不少门道。我做了这么多年嵌入式，见过太多团队在选差分策略上栽跟头——要么内存爆了，要么补丁包比全量还大。

这一章，我们就把二进制差异、字节级比较、块级比较、哈希与校验和这几个基础概念彻底讲透。

2.1 二进制差异：最朴素的思路

先问个问题：两个二进制文件摆在你面前，你怎么找不同？

最直接的办法——逐字节对比。从文件头开始，一个字节一个字节地比。遇到不一样的，记下位置和内容。这就是二进制差异的原始形态。

我在早期做Bootloader升级时，就试过这种原始方法。当时固件只有64KB，逐字节对比跑一遍也就几十毫秒。但后来固件涨到2MB，问题就来了——逐字节对比产生的差异记录，有时候比新文件本身还大。为什么？因为只要有一个字节偏移，后面所有字节都会“错位”，差异表会膨胀到不可接受。

所以，纯二进制差异只适合小文件或结构固定的场景。真正工业级的差分算法，不会这么蛮干。

2.2 字节级比较：细粒度但代价高

字节级比较，就是上面说的逐字节对比。它的优点是精度高——能精确到每个bit的变化。但缺点也很明显：

• 计算开销大：文件越大，对比次数线性增长
• 差异记录膨胀：微小偏移会导致大量“伪差异”
• 不适合大文件：嵌入式设备内存有限，扛不住

举个例子，新旧固件在中间插入了10个字节，后面所有字节都往后挪了10位。逐字节对比会认为从插入点开始，后面全是差异——实际上只有那10个字节是真正的变化。

2.3 块级比较：工业级差分的基础

既然逐字节不行，那换个思路——按块比较。把文件切成固定大小的块（比如每块512字节或1024字节），然后比较块与块之间的差异。

块级比较的核心优势：

• 降低计算量：比较次数从N字节降到N/块大小
• 容忍偏移：只要块边界对齐，插入/删除只影响局部
• 内存友好：可以流式处理，不用一次性加载整个文件

我记得有一次做OTA升级方案，设备只有64KB RAM，固件却有512KB。用块级比较，每次只加载两个块到内存，对比完就释放——完美解决内存瓶颈。

块大小怎么选？我一般遵循这个经验：

场景	推荐块大小	原因
小固件（<128KB）	256-512字节	差异粒度细，补丁包小
中等固件（128KB-1MB）	512-1024字节	平衡计算量与压缩率
大固件（>1MB）	1024-4096字节	减少对比次数，节省内存

2.4 哈希与校验和：快速判断“是否相同”

块级比较有个关键问题——怎么快速判断两个块是否相同？

你当然可以逐字节对比两个块，但那就回到字节级的老路上了。更聪明的做法是：给每个块算一个“指纹”，指纹相同就认为块相同，指纹不同再深入对比。

这个“指纹”就是哈希值或校验和。

2.4.1 校验和：轻量级但容易冲突

校验和是最简单的指纹算法。比如CRC32、Adler-32，计算速度快，占用资源少。但有个致命问题——冲突概率高。两个不同的块，可能算出相同的校验和。

我曾经在一个项目中用CRC32做块指纹，结果差分算法把两个不同的块当成相同的，导致生成的补丁包应用后固件跑飞了。排查了两天才发现是CRC32冲突。

2.4.2 哈希：更可靠的指纹

哈希算法（如MD5、SHA-1、SHA-256）冲突概率极低，适合做块指纹。代价是计算量比校验和大一些，但在现代MCU上完全可接受。

差分算法中常用的哈希策略：

• 滚动哈希（Rolling Hash）：rsync算法的核心，可以在滑动窗口中快速更新哈希值
• 强哈希 + 弱哈希：先用弱哈希（如Adler-32）快速筛选，再用强哈希（如MD5）确认

我个人习惯用“弱哈希+强哈希”的组合。先算一个32位的Adler-32，如果匹配，再算一个128位的MD5确认。这样既保证了速度，又避免了冲突。

2.5 知识体系总览

下面这张图，把本章的核心概念串起来了。你可以看到从原始二进制到工业级差分算法的演进路径。

2.6 实践中的选择建议

讲了这么多理论，最后给点实在的建议。你在实际项目中怎么选？

1. 资源极度受限（RAM < 32KB）：用块级比较 + CRC32校验和，接受一定的冲突风险，或者用滚动哈希做流式处理
2. 普通MCU（RAM 32-128KB）：块级比较 + Adler-32 + MD5组合，这是最稳妥的方案
3. 高性能MCU或Linux平台：直接用rsync算法或bsdiff，它们内部已经做了完善的哈希策略