在这里插入图片描述

FNV-1a 64-bit 在 MCU-32bit 上的实现与取舍：从原理、代码到适用边界

先看核心结论

FNV-1a 64-bit 的重点，不是“32 位 MCU 能不能跑 64 位整数”，而是下面三件事：

  1. 这个散列为什么能工作。
  2. 代码实现里每一步到底在做什么。
  3. 哪些场景适合用，哪些场景不适合用。

把这三件事讲清楚后，再讨论 32-bit 和 64-bit 的工程取舍，结构会更稳，也更接近实际选型过程。

FNV-1a 的标准更新过程可以概括成一条固定循环：

  • 状态从 offset_basis 开始
  • 每读取一个字节，先异或进状态
  • 再乘上固定的 FNV_Prime
  • 运算结果保留在固定比特宽度内

对 64-bit 版本，标准常量是：

1
2
#define FNV1A64_OFFSET_BASIS 0xCBF29CE484222325ULL
#define FNV1A64_PRIME        0x00000100000001B3ULL

这两个常量不是任意挑选出来的。offset_basis 决定初始状态，FNV_Prime 决定每次吸收新字节后如何扩散已有状态。

先把原理讲清楚

FNV-1a 只做两件事：吸收输入、扩散状态

FNV-1a 的每轮更新只有两步：

1
2
state = state XOR byte
state = state * FNV_Prime   (mod 2^N)

第一步的作用是把当前字节注入状态。
第二步的作用是把状态重新打散，让刚进入的低位变化尽快传播到更大的位范围中。

这两步合在一起，形成了 FNV-1a 的基本散列行为：

  • 输入顺序会影响结果
  • 每个新字节都会改变后续所有状态
  • 不需要缓存完整输入，天然支持流式更新

这也是 FNV-1a 很适合嵌入式系统的原因之一。串口、网络包、Flash 分块读取、日志流解析，本来就是“边到达边处理”的模式。

为什么是“先 XOR，再乘 prime”

FNV 家族里最容易混淆的是 FNV-1 和 FNV-1a。

  • FNV-1：先乘，再异或
  • FNV-1a：先异或，再乘

工程上更常用的是 FNV-1a。原因很直接：对短数据、小消息、短字符串，FNV-1a 的分布表现通常更好。因此，在大多数普通场景里，默认选 FNV-1a 更合理。

这件事在 MCU 场景尤其重要，因为很多实际输入本来就不长，例如：

  • 命令字
  • 配置项键名
  • 协议字段名
  • 文件路径片段
  • 资源标签
  • 小型二进制头部

如果输入大多只有几字节到几十字节，那么“小输入上的分布效果”通常比理论上的大块吞吐更关键。

FNV_Prime 为什么是这个值

32-bit 版本的 prime 是：

1
0x01000193 = 2^24 + 2^8 + 0x93

64-bit 版本的 prime 是：

1
0x00000100000001B3 = 2^40 + 2^8 + 0xB3

这类 prime 的结构有两个工程价值：

  1. 位分布经过专门选择，不是为了“好算”，而是为了散列质量。
  2. 由于高位项和低位项结构明确，乘法可以在某些平台上拆成“移位 + 小常数乘法 + 进位传播”。

因此，FNV-1a 的实现并不一定非要依赖一条完整的原生乘法指令。对资源有限的平台，prime 的结构本身就提供了可拆解空间。

offset_basis 的作用不是装饰，而是初始扰动

如果状态一开始就是 0，那么算法会更容易出现可预测的退化行为。FNV-1a 使用固定的非零 offset_basis 作为起点，目的就是让空状态带着初始扰动进入第一个字节的处理过程。

对 32-bit 版本，常量是：

1
0x811C9DC5

对 64-bit 版本，常量是：

1
0xCBF29CE484222325

这保证了相同输入在标准实现里有统一结果，也让跨平台实现保持互操作。

用 hash_32a.c 看清楚代码实现

为什么用 32-bit 源码讲 64-bit 算法

hash_32a.c 不是 64-bit 文件，但非常适合作为讲解入口。原因很简单：

  • 更新路径足够短
  • 关键动作没有被封装得太深
  • “直接乘法”和“移位加法展开”两种实现同时出现
  • 很适合拿来解释 FNV-1a 的单字节更新机制

换句话说，这份代码最有价值的地方不是“它是 32-bit”，而是“它把算法步骤写得很透明”。

先看一个等价化后的核心循环

下面这段示例代码不是原文件逐字复制，而是按 hash_32a.c 的结构整理后的等价写法，用来突出真正重要的部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdint.h>
#include <stddef.h>

#define FNV1A32_OFFSET_BASIS 0x811C9DC5u
#define FNV1A32_PRIME        0x01000193u

static uint32_t fnv1a32_step(uint32_t state, uint8_t byte)
{
    state ^= (uint32_t)byte;

    /* 等价于 state *= 0x01000193u */
    state += (state << 1)
          +  (state << 4)
          +  (state << 7)
          +  (state << 8)
          +  (state << 24);

    return state;
}

uint32_t fnv1a32_buf(const void *data, size_t len)
{
    const uint8_t *p = (const uint8_t *)data;
    uint32_t state = FNV1A32_OFFSET_BASIS;

    while (len--) {
        state = fnv1a32_step(state, *p++);
    }

    return state;
}

这段代码已经把 FNV-1a 的本质全部暴露出来了。

第一行真正做的事：把当前字节吸收进状态

1
state ^= (uint32_t)byte;

这一行只做注入，不做扩散。
当前字节进入状态后，还只是局部影响。如果这时直接返回，低位变化主要还停留在较低位。

所以 FNV-1a 的关键不在 XOR 本身，而在 XOR 后必须紧接着做一次固定乘法。

第二步真正做的事：把状态扩散开

32-bit prime 为 0x01000193。把它拆开：

1
0x01000193 = 2^24 + 2^8 + 2^7 + 2^4 + 2^1 + 1

于是：

1
2
3
4
5
6
7
state * 0x01000193
= state
+ (state << 1)
+ (state << 4)
+ (state << 7)
+ (state << 8)
+ (state << 24)

这就是源码里移位加法分支的数学来源。
也就是说，那串看起来像“位运算优化技巧”的表达式，本质上就是在实现固定常量乘法。

这个细节非常重要，因为它说明 FNV-1a 的实现从来不是“只能写成一条乘法”。只要乘数是固定常量，就可以按常量结构展开。

为什么源码同时保留直接乘法分支

hash_32a.c 里既有直接乘 FNV_32_PRIME 的分支，也有移位加法展开的分支。这种设计并不是重复，而是明确承认一个事实：

  • 算法逻辑固定
  • 最优实现路径取决于编译器和硬件

有的平台上，直接乘法更好。
有的平台上，移位加法更容易被优化，或者更容易审查执行代价。

这类写法很适合 MCU 工程，因为嵌入式实现往往不止关心“能不能跑”，还关心：

  • 指令序列是否稳定
  • 编译器是否会生成额外库调用
  • 是否引入不可控的长延迟
  • 是否方便做静态分析和性能估算

从 32-bit 代码平滑过渡到 64-bit 实现

64-bit 版本并没有改变算法

把 32-bit 换成 64-bit，更新步骤其实一模一样：

1
2
3
4
5
6
static uint64_t fnv1a64_step(uint64_t state, uint8_t byte)
{
    state ^= (uint64_t)byte;
    state *= 0x00000100000001B3ULL;
    return state;
}

变化只有两个：

  1. 状态宽度从 32 位扩展到 64 位。
  2. 常量从 32-bit offset_basis / prime 换成 64-bit offset_basis / prime。

因此，64-bit 的核心收益不是“算法更复杂”，而是状态空间更大，普通工程场景下的偶然碰撞概率更低。

最直接的 64-bit 参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdint.h>
#include <stddef.h>

#define FNV1A64_OFFSET_BASIS 0xCBF29CE484222325ULL
#define FNV1A64_PRIME        0x00000100000001B3ULL

uint64_t fnv1a64_buf(const void *data, size_t len)
{
    const uint8_t *p = (const uint8_t *)data;
    uint64_t state = FNV1A64_OFFSET_BASIS;

    while (len--) {
        state ^= (uint64_t)(*p++);
        state *= FNV1A64_PRIME;
    }

    return state;
}

如果目标平台的 uint64_t 加法和乘法成本可以接受，这已经是最清晰、最容易验证、最容易跨平台保持一致的写法。

更适合实际工程的形式：增量上下文接口

FNV-1a 天然适合写成“初始化、喂入分块、取结果”的接口，而不是只提供“一次性处理完整缓冲区”的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct {
    uint64_t state;
} fnv1a64_ctx_t;

static inline void fnv1a64_init(fnv1a64_ctx_t *ctx)
{
    ctx->state = FNV1A64_OFFSET_BASIS;
}

static inline void fnv1a64_update(fnv1a64_ctx_t *ctx, const void *data, size_t len)
{
    const uint8_t *p = (const uint8_t *)data;
    while (len--) {
        ctx->state ^= (uint64_t)(*p++);
        ctx->state *= FNV1A64_PRIME;
    }
}

static inline uint64_t fnv1a64_final(const fnv1a64_ctx_t *ctx)
{
    return ctx->state;
}

这种接口适合直接嵌进：

  • UART 接收状态机
  • 网络分片拼包流程
  • 文件系统分块读取
  • Flash 页扫描
  • 协议解析器
  • 日志聚合器

RFC 9923 也提供了上下文式的增量接口，说明这种写法本身就是 FNV 的标准使用方式之一。

使用场景应该怎么判断

适合的场景：快速查找、索引、映射

FNV 长期被用于多种非加密散列场景，包括数据库索引、DNS 服务器、文件指纹、缓存、符号表、哈希表、搜索/索引系统等。

映射到 MCU 和嵌入式软件里，最常见的落地方向是：

  • 命令字散列
  • 配置项键名散列
  • 资源路径与资源名映射
  • 协议字段名匹配
  • 哈希桶索引
  • 内部对象标识
  • 非安全用途的轻量文件或块标识

这类场景的共同特征是：

  • 追求速度和实现简单
  • 输入长度通常不大
  • 目标是快速区分与查找
  • 不要求抵抗主动攻击

适合流式处理场景

FNV-1a 对流式数据天然友好。只要保留当前状态，就可以持续吸收后续输入。RFC 9923 还明确说明，一个前缀的 FNV 结果可以直接作为后续拼接内容的 offset_basis，最终结果等价于一次性对完整拼接串做 FNV。

这意味着：

  • 前缀可复用
  • 共享头部可预计算
  • 分层协议可分段累计
  • 常量部分可以提前算好

对 MCU 来说，这种特性很有价值，因为它能减少重复计算，节省 CPU 时间。

不适合的场景：任何带安全对抗的用途

RFC 9923 讲得很明确：FNV 是非加密散列，不适合要求碰撞、原像或第二原像在计算上难以构造的场景。

因此，下面这些用途应该直接排除：

  • 安全认证
  • 防篡改摘要
  • 对抗性输入环境下的公开哈希表
  • 需要抗碰撞攻击的协议设计
  • 用散列值作为安全令牌

如果输入来自不可信外部实体，并且攻击者能主动构造输入，那么 FNV-1a 不该承担安全角色。

也不应该把它当作 CRC 的替代品

CRC 的目标是链路误码检测。
FNV-1a 的目标是散列分布和快速映射。

两者关注的问题不同，不能互相替代。
如果目标是检错，优先看 CRC。
如果目标是索引和散列分桶，再考虑 FNV。

优点和缺点需要分开看

优点

1. 实现极小

FNV-1a 的核心循环短，依赖少，移植成本低。
在 MCU 工程里，这意味着更容易放进启动阶段、Bootloader、小型库、协议栈底层，或者代码体积敏感的模块。

2. 易于审查和验证

算法步骤固定，状态更新非常直接。
相比结构更复杂的散列，FNV-1a 的实现更容易人工核查，也更容易写测试向量。

3. 天然支持流式输入

不需要一次性收齐完整数据。
这对串流、分块读取、协议解析非常友好。

4. 很适合短字符串和短键

对配置项、命令字、标识名、路径片段这类输入，FNV-1a 往往已经足够实用。

5. 64-bit 版本能明显扩大状态空间

当对象数量上升、哈希表变大、生命周期变长时，64-bit 版本比 32-bit 更不容易在普通工程场景下发生偶然碰撞。

缺点

1. 不是加密哈希

这是最重要的限制。
一旦需求涉及安全性，FNV-1a 就不该继续承担核心职责。

2. 碰撞抗性有限

对普通工程映射足够，不代表适合对抗性输入。
开放接口上的恶意构造输入，可能让哈希桶退化、查找性能恶化，甚至形成拒绝服务风险。

3. 64-bit 版本在 32 位 MCU 上未必总是划算

状态空间更大，不代表实现代价一定更低。
是否值得上 64-bit，要看对象规模、碰撞风险、工具链生成代码质量，以及对吞吐和代码尺寸的要求。

最后再看 32-bit 和 64-bit 的运用

先判断需求，再判断位宽

位宽选择不应该先看“平台是 32 位还是 64 位”，而应该先看：

  • 输入规模有多大
  • 哈希值要保存多久
  • 冲突代价有多高
  • 是否需要跨模块、跨文件、跨版本复用
  • 是否允许偶然碰撞导致退化

如果对象数量不大、哈希只做内部临时索引、生命周期很短，那么 32-bit 往往已经够用。
如果对象很多、哈希表更大、结果要长期保存，或者希望进一步降低碰撞风险，64-bit 更稳妥。

32-bit MCU 上并不等于不能用 64-bit FNV-1a

RFC 9923 在源码部分明确给出两套 64-bit 实现路径：

  • 一套面向具备 64-bit 算术支持的目标
  • 一套面向只有 32-bit 算术的目标

也就是说，“MCU-32bit 上能否使用 64-bit FNV-1a”并不是算法问题，而是实现代价问题。

当工具链支持较好时，直接使用 uint64_t

如果编译器能够稳定生成高质量 64-bit 运算代码，直接使用 uint64_t 版通常最值得优先考虑：

  • 代码短
  • 可读性最好
  • 最容易验证
  • 最容易与标准常量对齐

当 64-bit 乘法代价偏高时，按 prime 结构拆解

RFC 9923 在 64-bit FNV 的“仅有 32-bit 算术”版本中，把 64-bit prime 写成了可拆解形式：

1
2
3
/* 64-bit FNV_prime = 2^40 + 2^8 + 0xb3 */
#define FNV64primeX 0x01B3
#define FNV64shift  8

这背后的思路非常清晰：

  • 保留 64-bit 状态
  • 但不把实现强行写成一条完整的 64-bit 乘法
  • 而是利用 2^40 + 2^8 + 0xB3 的结构，把更新变成局部乘法、移位和进位传播

这与 hash_32a.c 的移位加法展开是同一类思路，只是状态从单个 32-bit 字扩展成多个更小分段。

更合理的工程建议

32-bit 版本优先的情况

  • 哈希仅做局部查找
  • 输入集合有限
  • 更在意速度和代码尺寸
  • 32-bit 的碰撞风险可接受

64-bit 版本优先的情况

  • 哈希值要长期保存或复用
  • 对象数量较多
  • 冲突代价较高
  • 希望在不引入复杂算法的前提下扩大状态空间

先做基准再定的情况

  • 平台没有原生高效 64-bit 乘法
  • 编译器版本不稳定
  • 代码尺寸和吞吐都很敏感
  • 同时在比较 32-bit FNV、64-bit FNV、CRC、或其他非加密散列

在这种情况下，最有效的办法不是争论，而是直接做三项测试：

  1. 每字节周期数
  2. 代码尺寸
  3. 目标输入集合上的冲突表现

小结

把 FNV-1a 64-bit 放到 MCU-32bit 场景里，最合理的理解顺序应该是：

  1. 先看原理：每个字节先 XOR，再乘固定 prime。
  2. 再看代码：hash_32a.c 已经把这个核心更新路径写得很透明。
  3. 再看用途：FNV-1a 适合快速索引、映射、流式散列，不适合安全用途。
  4. 最后再看位宽：32-bit 和 64-bit 的区别主要在状态空间与实现代价，而不是算法步骤。

这样梳理之后，讨论重点就不会跑偏到“32 位 MCU 能不能做 64 位乘法”这种局部问题上，而会回到真正影响选型的三个维度：散列原理、实现方式、适用边界。

参考资料

  • hash_32a.c
    https://github.com/lcn2/fnv/blob/master/hash_32a.c

  • RFC 9923 - The FNV Non-Cryptographic Hash Algorithm
    https://www.rfc-editor.org/rfc/rfc9923.html