LV010-差分算法对比与嵌入式移植

一、 差分算法对比

1. 三个主流算法的差异

维度	bsdiff / bspatch	xdelta3	HDiffPatch
核心思路	后缀数组找近似匹配 + 差异块	滑动窗口 + 指令编码	覆盖匹配 + 优化编码
补丁体积	小	中	通常最小
设备端 RAM	中（需载入旧镜像索引）	低（窗口化）	可调，有嵌入式优化模式
设备端复杂度	中	低	低（hpatch 为嵌入式优化）
流式应用	支持但实现复杂	原生流式	原生流式，支持只读旧数据
嵌入式移植	需裁剪	容易	最易，作者提供 MCU 示例

工程结论：服务器端算力充足时用 bsdiff 或 HDiffPatch 生成补丁；设备端 RAM 紧张时优先 HDiffPatch 的流式 hpatch，它能把 RAM 占用压到几 KB。

2. 算法选择与约束的对应关系

约束	倾向
设备 RAM < 16 KB	HDiffPatch 流式 / xdelta 小窗口
追求最小补丁体积	HDiffPatch
已有 bsdiff 工具链	保留 bsdiff，谨慎评估设备端 RAM
需要边下边打补丁	选流式实现，避免临时文件

二、 嵌入式差分移植要点

1. RAM 占用是首要瓶颈

差分应用（patch）需要同时读旧镜像、写新镜像、处理控制流，RAM 开销容易失控。优化手段：

（1）流式应用：不整载旧镜像，按控制块按需从 Flash 读取（XIP 场景天然满足，因为旧镜像本来就可直接寻址）

（2）缓冲分级：控制块解析用小缓冲（几十字节），数据段复制用中缓冲（256 B~4 KB），避免一次性申请大块连续 RAM

（3）只读旧镜像：旧镜像只在当前运行槽，绝不能被修改——这恰好满足 A/B 方案"旧槽不动"的不变量

2. seek 与 Flash 读取优化

bspatch 的控制块里包含大量 seek 操作，每次 seek 都对应一次 Flash 读取。两个优化点：

• 预读合并：连续的小段 seek 合并成一次大块读取，减少 Flash 访问次数
• 写缓冲对齐：新镜像写入按 Flash 页对齐（LV022-MCU无BankSwap落地方案 的写缓冲原则），避免"读改写"

开源差分库只解决"如何应用补丁"，产品化还需要补上校验与降级——这部分与 A/B 双槽是同一个决策流程，统一放在本篇第四节。

三、 压缩与打包

1. 压缩算法的选择

算法	压缩率	解压 RAM	适用
bzip2	高	~8 MB	服务器端生成可以，设备端不可用
zlib / gzip	中	~32 KB	通用，SWUpdate 默认
zstd	接近 bzip2	可调（几十 KB~几 MB）	设备端首选，支持流式
lzma	高	~1 MB 起步	中等资源设备

实践结论：设备端用 zstd 是目前的最优解——压缩率接近 bzip2，解压内存可调，流式接口友好。bsdiff 原始的 bzip2 输出在嵌入式设备上不可行，需要把差分包改为 zstd 封装。

2. 包格式的扩展

LV007-升级包格式与传输机制 的包头需要扩展两个字段才能支持差分：

package_type   = 2 (delta)
src_version    = 本补丁要求的源版本
payload_format = 负载封装格式（raw / zstd / bzip2）

设备端解析时按 payload_format 选择解压器，对上层透明。

四、 差分与 A/B 的组合

1. 从库到产品：必须补齐的三层校验

差分升级与 A/B 双槽并不矛盾，反而是绝配：差分包负责"省流量"，A/B 双槽负责"保可靠"。但开源差分库只提供"应用补丁"这一步，产品化必须自己补齐补丁前后的校验，并给每一层失败准备好降级路径。

三层"守门"缺一不可，每层拦住的是不同的故障：

层	校验什么	拦住什么	失败后怎么办
打补丁前	设备当前版本 == 补丁声明的源版本	补丁发给了不该收它的设备	直接换整包，连旧镜像都不必读
打补丁前	旧镜像 CRC == 补丁生成时的源镜像 CRC	本地固件被意外改写过（运行期日志越界、上次升级不干净），打补丁只会错上加错	换整包，并上报"旧镜像不一致"
打补丁后	重建镜像 SHA-256 == 预期值，且验签通过	补丁应用过程出错、目标槽写入出错	换整包；重打同一补丁没有意义

第三层的验签不可省：差分重建出的新镜像与整包下载得到的镜像享有完全相同的信任要求，见 LV019-升级安全机制。

2. 决策与降级的参考实现

// delta_apply.c —— 差分升级决策与降级（伪代码骨架，可移植）
#include <stdint.h>
#include <stdbool.h>
#include <string.h>

typedef enum {
    DELTA_OK,
    DELTA_SRC_MISMATCH,
    DELTA_OLD_IMAGE_BAD,
    DELTA_PATCH_FAIL,
} delta_result_t;

/* 升级入口：先尝试差分，失败自动降级整包 */
int ota_apply_delta_or_full(const ota_header_t *hdr,
                            const uint8_t *delta_pkg,
                            uint32_t delta_size,
                            const char *full_url)
{
    delta_result_t r = try_apply_delta(hdr, delta_pkg, delta_size);
    if (r == DELTA_OK) {
        return 0;
    }
    /* 降级为整包：复用整包下载与写入流程 */
    log_warn("delta failed(%d), fallback to full", r);
    return ota_apply_full(full_url);
}

static delta_result_t try_apply_delta(const ota_header_t *hdr,
                                      const uint8_t *delta_pkg,
                                      uint32_t delta_size)
{
    /* 1. 源版本匹配 */
    if (hdr->package_type != OTA_PKG_DELTA ||
        hdr->src_version != current_version()) {
        return DELTA_SRC_MISMATCH;
    }

    /* 2. 本地旧镜像与补丁声明的源版本逐字节一致 */
    if (image_crc32(active_slot_addr(), active_slot_size())
            != hdr->src_image_crc32) {
        return DELTA_OLD_IMAGE_BAD;
    }

    /* 3. 应用补丁重建新镜像到目标槽 */
    if (hpatch_apply(active_slot_addr(), delta_pkg, delta_size,
                     target_slot_addr()) != 0) {
        return DELTA_PATCH_FAIL;
    }

    /* 4. 重建结果与预期哈希一致 */
    uint8_t digest[32];
    sha256(target_slot_addr(), active_slot_size(), digest);
    if (memcmp(digest, hdr->payload_sha256, 32) != 0) {
        return DELTA_PATCH_FAIL;
    }

    return DELTA_OK;
}

【注意】

降级为整包时不要擦除目标槽里已写入的半成品新镜像——直接按整包流程从头下载并覆盖即可，避免多一次无谓的 Flash 擦写。

五、 服务器端补丁生成

1. 版本矩阵与流水线

发布新版本时，需要为"仍在网的所有历史版本"生成补丁。版本碎片化是主要成本：

• 只对最近 N 个版本（如 N = 3）生成补丁，更老的设备走整包
• 补丁生成是 CI 的独立阶段，与整包构建并行，产物一起入库
• 版本描述文件里要区分"差分包（含源版本）"与"整包（兜底）"两个条目（见 LV031-发布与量产运维 的 fallback_package）

2. 补丁质量评估

评估差分方案是否划算，需要跟踪三个指标：

指标	含义	健康阈值
补丁 / 整包体积比	差分带来的流量节省	< 30%
差分升级成功率	差分路径的可靠性	≥ 整包成功率 − 1%
降级率	差分失败改走整包的比例	< 5%

若降级率长期偏高，说明版本碎片化或旧镜像一致性问题严重，应缩短差分支持窗口（减小 N），而不是硬撑差分。

六、 常见问题

（1）差分包比整包还大：说明两个版本差异过大（如大版本重构），应直接发整包

（2）重建出的镜像哈希不对：最常见原因是旧镜像被写入过（如运行期日志、参数区写到了代码区附近），需检查分区隔离

（3）设备 RAM 不够跑差分：换流式 hpatch，或放弃差分走整包

（4）差分成功后验签失败：补丁生成时对新镜像的摘要算错了（例如对压缩后数据而非原始镜像计算），需统一摘要计算口径

（5）服务器补丁生成太慢：只保留最近 N 个版本的补丁；或把补丁生成挪到夜间批处理任务

---

本文档由 markdowncli 技能辅助生成