xxHash 算法规范详解：从 XXH32/XXH64 原理到 RetroArch 中的工程实践

xxHash 算法规范详解：从 XXH32/XXH64 原理到 RetroArch 中的工程实践

【免费下载链接】RetroArchCross-platform, sophisticated frontend for the libretro API. Licensed GPLv3.项目地址: https://gitcode.com/GitHub_Trending/re/RetroArch

导读

本文以 RetroArch 仓库内附带的 xxHash 算法规范文档 为核心，系统拆解XXH32与XXH64两个经典变体的完整算法流程——从 16/32 字节 stripe 分块、4 路并行累加器、收敛合并到最终雪崩混合。同时结合仓库中 xxHash 参考实现（deps/xxHash/xxhash.h、deps/xxHash/xxhash.c）与 RetroArch 内部的真实调用场景（GLSL 着色器二进制缓存寻址、状态倒带索引哈希等），说明该算法"以速度为首要目标、跨平台确定性输出"的设计哲学。读完本文，你不仅能逐行复现这两套算法，还能理解为何一个面向模拟器的前端项目要内置这样一个非加密哈希库。

一、xxHash 是什么：定位与设计目标

xxHash 是一套非加密的极速摘要算法，由 Yann Collet 设计并维护。规范文档开篇即给出明确定位：

xxHash 以速度为主要设计目标，被标记为 non-cryptographic（非加密），不用于避免有意碰撞（两条不同消息产生相同摘要），也不用于阻止生成具有预定摘要的消息。

这意味着它不适合做密码签名、完整性防篡改等安全场景，而非常适合哈希表、去重、缓存寻址、校验和等"追求吞吐量"的场景。规范同时强调两个关键性质：

• 确定性（deterministic）：同一输入在任意 CPU / 操作系统上必须产出完全相同的摘要值，与字节序（endianness）、CPU 字宽无关；
• 两种变体输出不同：XXH32面向 32 位机器优化，XXH64面向 64 位机器优化，两者对同一输入的输出不相等。

仓库内的参考实现在 deps/xxHash/xxhash.h 中对算法家族做了更完整的概述，规范文档主要描述 XXH32/XXH64 这两个"经典"变体，而同一目录下的 deps/xxHash/xxh3.h 还提供基于 SIMD 的现代XXH3家族（64/128 位），可以看作是经典算法的演进版本。

1.1 符号约定（Operation notations）

规范使用以下符号描述算法，后续所有公式都遵循这套约定：

XXH32全部运算在模 2³² 下进行，XXH64全部运算在模 2⁶⁴ 下进行，算术溢出是被预期、被允许的正常行为——这正是一系列无分支旋转/乘法混合能跑出接近内存带宽速度的关键。

二、XXH32 算法逐步拆解

XXH32接收任意长度消息L（L可为 0）与可选seed（可为 0），输出 32 位无符号摘要。整体结构：按 16 字节 stripe 分块 → 4 路累加器并行处理 → 收敛合并 → 尾部消化 → 雪崩混合。

2.1 关键素数常量

算法大量使用 5 个 32 位素数常量（见规范 Step 0）：

static const u32 PRIME32_1 = 0x9E3779B1U; // 0b10011110001101110111100110110001 static const u32 PRIME32_2 = 0x85EBCA77U; // 0b10000101111010111100101001110111 static const u32 PRIME32_3 = 0xC2B2AE3DU; // 0b11000010101100101010111000111101 static const u32 PRIME32_4 = 0x27D4EB2FU; // 0b00100111110101001110101100101111 static const u32 PRIME32_5 = 0x165667B1U; // 0b00010110010101100110011110110001

规范对这些常数的选择理由给出了明确说明：它们都是素数，且 0/1 位分布"既不过于规则、也不过于不对称"，这种性质有助于提升散列的分散（dispersion）能力。版本记录显示 v0.1.1 版专门补充了这条关于常量选择动机的说明，可见其对算法质量的重要性。

2.2 Step 1：初始化内部累加器

算法维护 4 个 32 位累加器，初始值由seed派生：

u32 acc1 = seed + PRIME32_1 + PRIME32_2; u32 acc2 = seed + PRIME32_2; u32 acc3 = seed + 0; u32 acc4 = seed - PRIME32_1;

特殊情况：输入不足 16 字节。此时不处理任何 stripe、不使用并行累加器，改用单一累加器直接跳到 Step 4：

u32 acc = seed + PRIME32_5;

这一特判是"短输入路径"（short-input path），它保证了哪怕输入为 0 字节也能稳定产出摘要。

2.3 Step 2：处理 stripe（核心热路径）

• stripe：16 字节的连续输入段；
• lane：stripe 被均分为 4 条 4 字节车道，第 N 条车道负责更新第 N 个累加器；
• 每条 lane 按little-endian约定读取 32 位值（这也是跨平台确定性输出的关键约定之一）。

每个 {lane, accumulator} 的更新过程称为一个round：

accN = accN + (laneN * PRIME32_2); accN = accN <<< 13; accN = accN * PRIME32_1;

一次 round 的语义是：先乘后加把输入位"注入"累加器，再循环左移 13 位打散位序，再乘 PRIME32_1 完成扩散——使得输入 lane 的任意一个位都能影响输出累加器中的多个位。所有运算均为模 2³²。

Step 2 每次消费一个完整 stripe 并循环，直到剩余字节不足 16 字节时进入 Step 3。

2.4 Step 3：累加器收敛

4 路累加器合并为单个同宽（32 位）累加器，每路使用不同的旋转量（1、7、12、18），确保四路信息以不同相位混合：

acc = (acc1 <<< 1) + (acc2 <<< 7) + (acc3 <<< 12) + (acc4 <<< 18);

2.5 Step 4：加入输入长度

把输入总长度（低 32 位）加入累加器，使长度信息参与最终混合。规范特别注明：若输入长度超过 32 位表示范围，仅加入低 32 位：

acc = acc + (u32)inputLength;

2.6 Step 5：消费剩余输入

收敛后至多还剩 15 字节，按 4 字节一组、再按单字节逐字节消化：

while (remainingLength >= 4) { lane = read_32bit_little_endian(input_ptr); acc = acc + lane * PRIME32_3; acc = (acc <<< 17) * PRIME32_4; input_ptr += 4; remainingLength -= 4; } while (remainingLength >= 1) { lane = read_byte(input_ptr); acc = acc + lane * PRIME32_5; acc = (acc <<< 11) * PRIME32_1; input_ptr += 1; remainingLength -= 1; }

该过程确保所有输入字节都进入最终混合，不遗漏任何尾随数据。

2.7 Step 6：最终混合（雪崩效应）

最后一轮混合的目标是让输入任意位的翻转都能以近似均匀的概率影响输出的每一位，即雪崩效应（avalanche effect），从而让摘要分布无偏：

acc = acc xor (acc >> 15); acc = acc * PRIME32_2; acc = acc xor (acc >> 13); acc = acc * PRIME32_3; acc = acc xor (acc >> 16);

典型的"右移异或—乘—右移异或—乘—右移异或"三明治结构，右移量（15/13/16）与素数乘子配合完成充分扩散。

2.8 Step 7：输出与规范字节序

XXH32()返回 32 位无符号值。对于需要以二进制/十六进制存储或展示的系统，规范定义**规范格式（canonical format）**按big-endian（高位字节在前）排列，以保证十进制数值与十六进制展示一致。

三、XXH64 算法逐步拆解

XXH64与XXH32结构高度相似，核心差异是：使用 64 位算术，stripe 变为 32 字节，round 旋转量为 31，收敛过程更复杂（引入mergeAccumulator）。它在 64 位系统上能更高效地搬运内存，但对 CPU 的 64 位运算能力有依赖。

3.1 关键素数常量

static const u64 PRIME64_1 = 0x9E3779B185EBCA87ULL; // 0b1001111000110111011110011011000110000101111010111100101010000111 static const u64 PRIME64_2 = 0xC2B2AE3D27D4EB4FULL; // 0b1100001010110010101011100011110100100111110101001110101101001111 static const u64 PRIME64_3 = 0x165667B19E3779F9ULL; // 0b0001011001010110011001111011000110011110001101110111100111111001 static const u64 PRIME64_4 = 0x85EBCA77C2B2AE63ULL; // 0b1000010111101011110010100111011111000010101100101010111001100011 static const u64 PRIME64_5 = 0x27D4EB2F165667C5ULL; // 0b0010011111010100111010110010111100010110010101100110011111000101

与 XXH32 一样，这些常量是素数且位分布均衡，用于增强分散能力。可以注意到 PRIME64_1 的高 32 位与 PRIME32_1 相同、低 32 位与 PRIME32_2 相同，各常量之间也存在这种"拼接复用"关系，体现了两套常量集的同源设计。

3.2 Step 1：初始化内部累加器

u64 acc1 = seed + PRIME64_1 + PRIME64_2; u64 acc2 = seed + PRIME64_2; u64 acc3 = seed + 0; u64 acc4 = seed - PRIME64_1;

特殊情况：输入不足 32 字节，同样退化为单一累加器并直达 Step 4：

u64 acc = seed + PRIME64_5;

3.3 Step 2：处理 stripe

32 字节 stripe 均分为 4 条 8 字节 lane，little-endian 读取，round 公式：

round(accN,laneN): accN = accN + (laneN * PRIME64_2); accN = accN <<< 31; return accN * PRIME64_1;

与 XXH32 的 round 相比，旋转量从 13 变为 31，其余结构一致，运算在模 2⁶⁴ 下进行。循环消费完整 stripe 直至剩余不足 32 字节。

3.4 Step 3：累加器收敛（较 32 位更复杂）

规范明确指出 64 位的收敛比 32 位复杂，需要先定义辅助函数mergeAccumulator()：

mergeAccumulator(acc,accN): acc = acc xor round(0, accN); acc = acc * PRIME64_1; return acc + PRIME64_4;

再用于收敛公式——先做一次"旋转求和"的初步合并，再对 4 个累加器逐一调用 merge：

acc = (acc1 <<< 1) + (acc2 <<< 7) + (acc3 <<< 12) + (acc4 <<< 18); acc = mergeAccumulator(acc, acc1); acc = mergeAccumulator(acc, acc2); acc = mergeAccumulator(acc, acc3); acc = mergeAccumulator(acc, acc4);

3.5 Step 4：加入输入长度

acc = acc + inputLength;

inputLength为 64 位宽度，天然支持更大的输入规模。

3.6 Step 5：消费剩余输入

至多剩余 31 字节，分三档处理（8 字节组 → 4 字节组 → 单字节）：

while (remainingLength >= 8) { lane = read_64bit_little_endian(input_ptr); acc = acc xor round(0, lane); acc = (acc <<< 27) * PRIME64_1; acc = acc + PRIME64_4; input_ptr += 8; remainingLength -= 8; } if (remainingLength >= 4) { lane = read_32bit_little_endian(input_ptr); acc = acc xor (lane * PRIME64_1); acc = (acc <<< 23) * PRIME64_2; acc = acc + PRIME64_3; input_ptr += 4; remainingLength -= 4; } while (remainingLength >= 1) { lane = read_byte(input_ptr); acc = acc xor (lane * PRIME64_5); acc = (acc <<< 11) * PRIME64_1; input_ptr += 1; remainingLength -= 1; }

注意 64 位尾部处理普遍采用xor注入而非加法，且旋转量（27/23/11）与常量组合各不相同，进一步加大扩散。

3.7 Step 6：最终混合（雪崩）

acc = acc xor (acc >> 33); acc = acc * PRIME64_2; acc = acc xor (acc >> 29); acc = acc * PRIME64_3; acc = acc xor (acc >> 32);

右移量 33/29/32 与 32 位的 15/13/16 不同，但结构与目的完全一致。

3.8 Step 7：输出与规范字节序

XXH64()返回 64 位无符号值；规范字节序同样为 big-endian，与 XXH32 一致。

四、两种变体的对比与性能考量

规范在 Performance considerations 一节给出的工程指引，可以直接转化为选型决策：

• 算法简洁紧凑：实现简单，为任意长度消息提供系统无关的"指纹"；
• 支持流式处理：算法允许输入分多步流式送入（streaming），此时内部需要一个缓冲区，确保数据以完整 stripe 形式交给算法——这正是XXH32_state_t/XXH64_state_t结构体存在的意义；
• 64 位系统：XXH64一般更快，即使只需要 32 位摘要，官方也推荐优先使用 XXH64；
• 32 位系统：情况反转，XXH64因 64 位算术代价而性能下降，XXH32更快。

从参考实现的 API 设计（deps/xxHash/xxhash.h）也能印证上述两点：

• 单发（Single Shot）接口：XXH32(input, len, seed)、XXH64(input, len, seed)—— 无状态、对一块连续内存直接出摘要，通常最快；
• 流式（Streaming）接口：XXH*_createState / reset / update / digest / freeState—— 支持未知长度甚至超过size_t范围的分段输入；
• 内联模式：定义XXH_INLINE_ALL后包含头文件，可将实现内联进目标编译单元，对"长度是编译期常量"的小输入能显著提速，同时避免导出符号。

xxHash系列还提供了针对 XXH3 的向量化实现（deps/xxHash/xxh3.h）以及 x86 运行时分发层（deps/xxHash/xxh_x86dispatch.c），后者按 CPU 支持的指令集自动选择 SSE2/AVX2 等最优路径，属于性能工程的进阶形态。

五、RetroArch 仓库内的真实应用场景

xxHash 在 RetroArch 中并非装饰性依赖，而是被实际用于若干关键路径，这些调用点恰好完整覆盖了规范所述的三种 API 形态。

5.1 GLSL 着色器二进制缓存：流式 XXH64

gfx/drivers_shader/shader_glsl.c（ORBIS 平台分支）用XXH64的流式 API为多段 GLSL 源码拼接结果计算哈希，用于生成着色器二进制缓存的寻址键：

static const XXH64_hash_t gl_glsl_hash_shader( const char **source, const int source_length) { int n; XXH64_state_t* const state = XXH64_createState(); XXH64_reset(state, 0xAABBCCDDu); for(n = 0; n < source_length; n++) { XXH64_update(state, source[n], strlen(source[n])); } XXH64_hash_t const hash = XXH64_digest(state); XXH64_freeState(state); return hash; }

这是一个教科书式的流式调用序列：createState → reset(seed) → update ×N → digest → freeState，与规范"分多步流式送入、内部缓冲保证完整 stripe"的描述完全对应。这里使用固定种子0xAABBCCDD，哈希结果用于标识"某段着色器源码"是否已编译过，从而避免重复编译。

5.2 状态倒带索引：内联单发 XXH32

input/bsv/uint32s_index.c 中，RetroArch 通过XXH_INLINE_ALL内联模式引入 xxHash，并把XXH32封装为索引桶的哈希函数：

#define XXH_INLINE_ALL #include <xxHash/xxhash.h> #define HASHMAP_CAP 65536 #define uint32s_hash_bytes(bytes, len) XXH32(bytes,len,0)

这里采用XXH32的单发接口（seed 为 0），为模拟器状态倒带（rewind/statestream）机制中的uint32_t对象索引建立哈希映射，哈希表容量 65536。对"批量小对象哈希"这种场景，XXH32 的简洁与速度非常契合，也验证了规范"XXH32 面向 32 位机器、实现紧凑"的定位。

5.3 Zstandard 帧校验和：XXH64 作为格式约定

libretro-common/encodings/encoding_rzstd.c 及其头文件 libretro-common/include/encodings/rzstd.h 是 RetroArch 对 Zstandard（zstd）压缩格式的解码实现。Zstandard 帧格式本身就把XXH64 规定为内容校验和算法——源码注释中明确提到 "a frame's XXH64" 及 "frame content's XXH64"，并在实现中选择了跳过（skip）而非验证该校验和。这说明 xxHash 已经作为行业格式的组成部分（zstd 的默认 checksum 即 XXH64），其跨平台确定性在这里承担着格式兼容性的职责。

5.4 配套工具与测试资产

仓库内 xxHash 子目录还包含完整的工程配套：

• deps/xxHash/xxhsum.c：官方命令行工具，用法手册见 deps/xxHash/cli/xxhsum.1.md；
• deps/xxHash/tests/bench/benchHash.c：大/小数据吞吐基准；
• deps/xxHash/tests/collisions/main.c：碰撞强度测试；
• deps/xxHash/tests/multiInclude.c：验证头文件多次包含的健壮性。

这些测试与规范文档互为印证：规范描述算法"是什么"，测试则验证"跑得够快、撞得够少"。

六、结语：从规范到工程

回顾整个 xxHash 规范，其设计哲学清晰可见：在"充分扩散"与"极致速度"之间做工程权衡——用素数常量做乘加混合、用多路累加器榨取指令级并行、用统一的 little-endian 读取与规范 big-endian 输出保证跨平台确定性，同时明确声明自身非加密属性，把安全边界划得清清楚楚。

在 RetroArch 这样的跨平台模拟器前端中，xxHash 的价值体现在三个层面：着色器缓存寻址（流式 XXH64）省去重复编译开销、状态倒带索引（单发 XXH32）保证回放数据可快速检索、zstd 帧校验约定（XXH64）维持压缩格式兼容性。如果你需要在项目中引入"速度快、实现简单、跨平台确定"的摘要算法，deps/xxHash/doc/xxhash_spec.md 这份规范就是最权威的起点，而 deps/xxHash/xxhash.h 则提供了立即可用的参考实现。

【免费下载链接】RetroArchCross-platform, sophisticated frontend for the libretro API. Licensed GPLv3.项目地址: https://gitcode.com/GitHub_Trending/re/RetroArch