#simd #hash #hasher #avx #highway-hash

无需 std highway

Google's HighwayHash 的原生 Rust 端口,该算法利用 SIMD 指令实现快速且强大的哈希函数

20 个版本 (3 个稳定版)

1.2.0 2024年6月21日
1.1.0 2023年6月30日
1.0.0 2023年3月1日
0.8.1 2022年10月11日
0.1.4 2018年10月1日

算法 类别中排名 第24

Download history • Rust 包仓库 6336/week @ 2024-05-01 • Rust 包仓库 9345/week @ 2024-05-08 • Rust 包仓库 8790/week @ 2024-05-15 • Rust 包仓库 8178/week @ 2024-05-22 • Rust 包仓库 7339/week @ 2024-05-29 • Rust 包仓库 6362/week @ 2024-06-05 • Rust 包仓库 6650/week @ 2024-06-12 • Rust 包仓库 7986/week @ 2024-06-19 • Rust 包仓库 7142/week @ 2024-06-26 • Rust 包仓库 6913/week @ 2024-07-03 • Rust 包仓库 8303/week @ 2024-07-10 • Rust 包仓库 8334/week @ 2024-07-17 • Rust 包仓库 7349/week @ 2024-07-24 • Rust 包仓库 9045/week @ 2024-07-31 • Rust 包仓库 8789/week @ 2024-08-07 • Rust 包仓库 9362/week @ 2024-08-14 • Rust 包仓库

每月下载量 35,864
24 软件包使用(直接使用12个)

使用 MIT 许可协议

110KB
2.5K SLoC

ci Rust Version

Highway-rs

本软件包是 Google 的 HighwayHash 的原生 Rust 端口,这是一个快速、带键、且强大的哈希函数,其输出与硬件无关。

功能

  • ✔ 纯净 / 稳定的 Rust
  • ✔ 无依赖项
  • ✔ 在所有硬件上生成一致的 64、128 和 256 位哈希值
  • ✔ 在 x86 和 aarch64 架构上使用 SIMD(SSE 4.1 AVX 2、NEON)感知指令时,速度超过 10 GB/s
  • ✔ 在 Wasm 上使用 Wasm SIMD 扩展时,速度超过 3 GB/s
  • ✔ 使用零不安全代码的硬件无关实现,速度超过 1 GB/s
  • ✔ 增量 / 流式哈希
  • ✔ 零堆分配
  • ✔ 与 no_std 兼容
  • ✔ 与参考实现进行模糊测试,以确保稳定性和兼容性

注意

HighwayHash(该算法)没有像 SipHash(Rust 中的默认哈希算法)那样经过广泛的密码分析,但根据作者的说法,HighwayHash 的输出位均匀分布,应该能够抵抗差分和旋转攻击。因此,HighwayHash 被称为强哈希函数,而不是密码学哈希函数。我鼓励任何感兴趣的人阅读这篇论文以了解风险。

示例

开始的最快方式

use highway::{HighwayHasher, HighwayHash};
let res: u64 = HighwayHasher::default().hash64(&[]);
let res2: [u64; 2] = HighwayHasher::default().hash128(&[]);
let res3: [u64; 4] = HighwayHasher::default().hash256(&[]);

更全面的 API 导览

use highway::{HighwayHasher, HighwayHash, Key};

// HighwayHash requires a key that should be hidden from attackers
// to ensure outputs are unpredictable, so attackers can't mount
// DoS attacks.
let key = Key([1, 2, 3, 4]);

// A HighwayHasher is the recommended approach to hashing,
// as it will select the fastest algorithm available
let mut hasher = HighwayHasher::new(key);

// Append some data
hasher.append(&[255]);

// After all data has been appended, you ask for
// 64, 128, or 256bit output. The hasher is consumed
// after finalization.
let res: u64 = hasher.finalize64();

assert_eq!(0x07858f24d_2d79b2b2, res);

创建 128 位和 256 位的哈希值同样简单。

use highway::{HighwayHasher, HighwayHash, Key};

// Generate 128bit hash
let key = Key([1, 2, 3, 4]);
let mut hasher128 = HighwayHasher::new(key);
hasher128.append(&[255]);
let res128: [u64; 2] = hasher128.finalize128();
assert_eq!([0xbb007d2462e77f3c, 0x224508f916b3991f], res128);

// Generate 256bit hash
let key = Key([1, 2, 3, 4]);
let mut hasher256 = HighwayHasher::new(key);
hasher256.append(&[255]);
let res256: [u64; 4] = hasher256.finalize256();
let expected: [u64; 4] = [
    0x7161cadbf7cd70e1,
    0xaac4905de62b2f5e,
    0x7b02b936933faa7,
    0xc8efcfc45b239f8d,
];
assert_eq!(expected, res256);

在标准 Rust 集合中使用 highway 哈希

use std::collections::HashMap;
use highway::{HighwayBuildHasher, Key};
let mut map =
  HashMap::with_hasher(HighwayBuildHasher::new(Key([
    0xcbf29ce484222325,
    0xc3a5c85c97cb3127,
    0xb492b66fbe98f273,
    0x9ae16a3b2f90404f,
  ])));

map.insert(1, 2);
assert_eq!(map.get(&1), Some(&2));

如果使用密钥不重要,可以使用默认的

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use highway::HighwayHasher;
let mut map =
  HashMap::with_hasher(BuildHasherDefault::<HighwayHasher>::default());

map.insert(1, 2);
assert_eq!(map.get(&1), Some(&2));

哈希文件或任何实现了 Read 的内容

use std::hash::Hasher;
use highway::{PortableHash, HighwayHash};

let mut file = &b"hello world"[..];

// We're using the `PortableHash` to show importing a specific hashing
// implementation (all hash outputs are already portable / hardware agnostic).
// The main reason for directly using `PortableHash` would be if avoiding
// `unsafe` code blocks is a top priority.
let mut hasher = PortableHash::default();
std::io::copy(&mut file, &mut hasher)?;
let hash64 = hasher.finish(); // core Hasher API
let hash256 = hasher.finalize256(); // HighwayHash API

使用场景

HighwayHash 可用于针对不可信的用户输入,由于利用、验证的密码学哈希太慢或需要强大的哈希函数,因此不能使用弱哈希。以下是一些 HighwayHash 作者给出的具体场景:

  • 使用 64 位哈希值验证短期消息
  • 使用 256 位哈希值进行校验和。例如,文件存储(S3)或任何需要强大碰撞保证的长期数据。

HighwayHash 如果数据包大小趋势较小(<100 字节)并且速度非常重要,可能不是最佳选择,因为 HighwayHash 在较大数据包时才能发挥最佳性能。

Wasm SIMD

当将 HighwayHash 部署到 Wasm 环境时,可以通过添加 Rust 标志来选择使用 Wasm SIMD 指令。

RUSTFLAGS="-C target-feature=+simd128" wasm-pack build

然后 HighwayHasher 将自动通过 WasmHash 转到 Wasm SIMD 实现。

一旦选择加入,执行环境必须支持 Wasm SIMD 指令,Chrome、Firefox 和 Node LTS 自 2021 年中以来已稳定支持。由于 Wasm 无法在运行时检测 SIMD 功能,因此需要选择加入。仅仅存在 Wasm SIMD 指令就可能导致不兼容的环境无法编译,因此建议为下游用户提供两个 Wasm 数据包:一个启用 SIMD,另一个未启用。

no_std

此包有一个默认启用的功能,即 std。要在 no_std 环境中使用此包,请将以下内容添加到您的 Cargo.toml

[dependencies]
highway = { version = "x", default-features = false }

请注意,no_std 版本无法检测 CPU 功能,因此始终默认使用可移植实现。如果为已知支持 SSE 4.1 或 AVX 2 的机器(在过去十年中的大多数机器都将支持 SSE 4.1)构建,则可显式启用目标功能。

RUSTFLAGS="-C target-feature=+sse4.1" cargo test
RUSTFLAGS="-C target-feature=+avx2" cargo test

基准测试

基准测试使用以下命令运行

(cd compare && cargo clean && RUSTFLAGS="-C target-cpu=native" cargo bench)
find ./compare/target -wholename "*/new/raw.csv" -print0 | xargs -0 xsv cat rows > assets/highway.csv

可以使用位于资产目录中的 R 脚本进行分析

请注意,基准测试会因机器而异。较新的机器通常比较旧的机器更好地处理 AVX 数据包。

我们将首先查看使用各种实现计算不同大小数据包的 64 位哈希值的吞吐量。

64bit-highwayhash.png

要点

  • 图表的左下角说明了 HighwayHash 的弱点:小型数据包,略微眯眼即可看到 HighwayHash 在底部。
  • 在较大数据包的情况下,HighwayHash 在性能上可以具有竞争力,因为 CPU 有足够的空间在其输入上施展 SIMD 的优势。
  • AHash 和 t1ha 表现出色,应将其作为内存数据结构的工具包之一。

现在我们来看计算 256 位哈希值的情况,故事大致相同。

256bit-highwayhash.png

要点

  • 与其它函数相比,HighwayHash 的速度是最快的,但如果需要加密哈希,则应选择 BLAKE3。

即使在最佳视力下,在较小数据包的情况下,差异也是无法分辨的,因此让我们看看哈希率。

256bit-highwayhash-rate.png

要点

  • 在较小数据包的情况下,HighwayHash 保持其性能优势。

与 64 位相比,HighwayHash 在最终确定 256 位输出时使用更多的置换轮次,这在以下图形中有所反映。

64bit-vs-256bit-highwayhash.png

要点

  • 64 位哈希可以比 256 位输出快 33%。
  • 在 64KiB 之后,64 位和 256 位输出之间没有性能差异。

对于那些更关注数字、对具体细节感兴趣或想了解关于小数据包大小哈希函数的更多详细信息的人,以下是一个表格,列出了所有数据包大小的吞吐量(以 GB/s 计)。

highwayhash-table.png

构建器基准测试

运行构建器基准测试以查看性能如何随标志而变化。

默认编译

cargo bench -- highway-builder

显式禁用 avx2

RUSTFLAGS="-C target-feature=-avx2" cargo bench -- highway-builder

针对本地 CPU 时显式禁用 avx2

RUSTFLAGS="-C target-cpu=native -C target-feature=+sse4.1,-avx2" \
  cargo bench -- highway-builder

无运行时依赖