nickbabcock/highway-rs

Native Rust port of Google's HighwayHash, which makes use of SIMD instructions for a fast and strong hash function

Highway-rs

This crate is a native Rust port of Google's HighwayHash, which is a fast, keyed, and strong hash function, whose output is hardware independent.

Features

• ✔ pure / stable rust
• ✔ zero dependencies
• ✔ generate consistent 64, 128, and 256bit hashes across all hardware
• ✔ > 10 GB/s with SIMD (SSE 4.1 AVX 2, NEON) aware instructions on x86 and aarch64 architectures
• ✔ > 3 GB/s on Wasm with the Wasm SIMD extension
• ✔ > 1 GB/s hardware agnostic implementation with zero unsafe code
• ✔ incremental / streaming hashes
• ✔ zero heap allocations
• ✔ no_std compatible
• ✔ fuzzed against reference implementation to ensure stability and compatibility

Caution

HighwayHash (the algorithm) has not undergone extensive cryptanalysis like SipHash (the default hashing algorithm in Rust), but according to the authors, HighwayHash output bits are uniformly distributed and should withstand differential and rotational attacks. Hence HighwayHash is referred to as a strong hash function, not a cryptographic hash function. I encourage anyone interested to peruse the paper to understand the risks.

Examples

The quickest way to get started:

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

A more complete tour of the API follows:

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);

Creating a 128bit and 256bit hash is just as simple.

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);

Use highway hash in standard rust collections

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));

Or if utilizing a key is not important, one can use the default

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));

Hashing a file, or anything implementing 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

Use Cases

HighwayHash can be used against untrusted user input where weak hashes can't be used due to exploitation, verified cryptographic hashes are too slow, and a strong hash function meets requirements. Some specific scenarios given by the authors of HighwayHash:

• Use 64bit hashes to for authenticating short lived messages
• Use 256bit hashes for checksums. Think file storage (S3) or any longer lived data where there is a need for strong guarantees against collisions.

HighwayHash may not be a good fit if the payloads trend small (< 100 bytes) and speed is up of the utmost importance, as HighwayHash hits its stride at larger payloads.

Wasm SIMD

When deploying HighwayHash to a Wasm environment, one can opt into using the Wasm SIMD instructions by adding a Rust flag:

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

Then HighwayHasher will automatically defer to the Wasm SIMD implementation via WasmHash.

Once opted in, the execution environment must support Wasm SIMD instructions, which Chrome, Firefox, and Node LTS have stabilized since mid-2021. The opt in is required as there is not a way for Wasm to detect SIMD capabilities at runtime. The mere presence of Wasm SIMD instructions will cause incompatible environments to fail to compile, so it is recommended to provide two Wasm payloads to downstream users: one with SIMD enabled and one without.

no_std crates

This crate has a feature, std, that is enabled by default. To use this crate in a no_std context, add the following to your Cargo.toml:

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

Be aware that the no_std version is unable to detect CPU features and so will always default to the portable implementation. If building for a known SSE 4.1 or AVX 2 machine (and the majority of machines in the last decade will support SSE 4.1), then explicitly enable the target feature:

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

Benchmarks

Benchmarks are ran with the following command:

(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

And can be analyzed with the R script found in the assets directory

Keep in mind, benchmarks will vary by machine. Newer machines typically handle AVX payloads better than older.

We'll first take a look at the throughput when calculating the 64bit hash of a varying payload with various implementations

Takeaways:

• The lower left corner of the graph illustrates HighwayHash's weakness: small payloads, as with a bit of squinting, one can see that HighwayHash ranks amongst the bottom.
• At larger payloads, HighwayHash can be competitive in performance as the CPU has room to stretch its proverbial SIMD legs on the input.
• AHash and t1ha perform fantastically and should be in one's toolkit for in memory data structures.

Now taking a look at calculating a 256bit hash value, we see a similar story.

Takeaways:

• HighwayHash is by far the fastest compared to the other functions, but if one needs a cryptographic hash, then BLAKE3 should be chosen

Even with the best eyesight, the differences are indistinguishable at smaller payloads, so let's look at the hash rate:

Takeaways:

• At smaller payloads HighwayHash maintains its performance lead

HighwayHash uses more rounds of permutation when finalizing the 256bit output compared to the 64bit and this is reflected in the following graphic:

Takeaways:

• At max, the 64bit hash can be computed 33% faster than the 256bit output
• After 64KiB there is no performance difference between 64bit and 256bit outputs

For those more into numbers and are curious about specifics or want more details about the hash functions at small payloads size, here is a table that breaks down throughput (in GB/s) at all payload sizes

Builder Benchmarks

Have fun running the builder benchmarks to see how performance differs with flags:

Default compilation

cargo bench -- highway-builder

Explicitly disable avx2

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

Explicitly disable avx2 when targeting native cpu

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

highway-rs's Issues

no_std support

Discussed a bit here:

I have another branch with no_std support for the PortableHash

Nice! One thing to note is that SIMD instructions should still be available on core, afaik. What's not available is is_x86_feature_detected so it seems possible that one can continue using AvxHash::force_new on no_std (and have AvxHash::new return None). But we can talk about this more on the PR when you have it situated.

cc @jRimbault

Just creating this issue to track the request so I don't forget about this.

example folder and question about 32bit

I'm still trying to understand how to host this from a browser. I will continue working towards this; just wondering if there are additional examples to include or suggestions.

Also, there's no discussion tab, so I'm adding it here. I'm interested in 32bit hashes. I understand the highway algorithm is 64bit minimum. It wouldn't need to be highway; something like crc32fast to provide the algorithm for a 32bit hash output? Do I fork and work a separate binding for crc32fast or extend highway or is it not a good idea for some reason?

Wasm SIMD implementation

https://doc.rust-lang.org/stable/core/arch/wasm32/index.html.

Exploratory work has already started at https://github.com/nickbabcock/highway-rs/tree/wasm

ARM NEON (AdvSIMD) support

The Google implementation now has code for NEON SIMD on aarch64 (and 32 but who cares):
google/highwayhash@ff5f27d

Porting to Rust would likely require adding new intrinsics to rust-simd..

Potential readability changes

I've been reviewing the code in portable.rs and I believe there's an opportunity for some refactoring to improve code readability and maintainability, specifically around the bitwise operations.

highway-rs/src/portable.rs

Line 235 in d407bd1

let size_mod4 = bytes.len() & 3;

1. Use Core Ops for Explicit Bitwise Operations: Leveraging core::ops::BitAnd can make the operations more explicit and easier to understand. For example:

use core::ops::BitAnd;

let size_mod4 = bytes.len().bitand(3);
let remainder_jump = bytes.len().bitand(!3);

2. change the operands to better reflect their bitwise nature

const TWO_LSB_MASK: usize = 0x0000_0000_0000_0003;
let size_mod4 = bytes.len().bitand(TWO_LSB_MASK);
let remainder_jump = bytes.len().bitand(!TWO_LSB_MASK);

There is precedent for 2. within this code, for instance

highway-rs/src/portable.rs

Line 136 in d407bd1

let a3 = a3_unmasked & 0x3FFF_FFFF_FFFF_FFFF;

(name could be LOW_TWO_BITS_MASK, BIT_MASK_3, !TWO_LSB_MASK could be TWO_LSB_MASK_NOT etc)

3. Standardize caps for hex representation
   line 136 is all caps, line 166 is no caps etc

If you agree atleast partially, let me know which of the above options seem most sensible to you.
If you leave it up to me, I would likely first introduce the core::ops and introduce consts for only those bitmasks used more than once. I'll prepare a PR upon that, and you could provide further critique on what seems the best readable code

Of course, one could be chosen without the other, or maybe the current code is as readable, understandable and maintainable in your view. Or, this implementation might look the way it does because the original looks that way and you'd like to keep parity. I haven't personally looked into the C/C++ version to have any strong feelings about that.

In anycase, if you'd like the style to stay the way it does, I will look into other avenues of improvement.

Excessive overhead in HighwayHasher for small payloads

The HighwayHasher facade will choose the best hashing implementation at runtime based on the underlying CPU capabilities.

I recently benchmarked the facade. At payloads under 1KB, the facade throughput can be twice as slow as the underlying AVX implementation. Of course, some overhead should be expected from the facade, but this is excessive. And such a large of a caveat shouldn't be present for the main entrypoint of the library.

Doing some profiling, most of the overhead comes from initialization where there is a memcpy of the implementation into HighwayHasher and since the internal implementations weigh ~192 bytes, this memcpy can be significant.

Not sure of the best way to solve this, but if I don't think of a good way, there's always the alternative of creating one-shot functions that can use a more traditional indirect function approach like what is used memchr

U64 input

Hi,

Thanks for this awesome crate.
I'm using HighwayHash but I'd like to input u64 instead of u8 without having to use Transmute.

Would it be possible for you to integrate the possibility in your crate? That would be so helpful!

Thank you

Release version 1.0

If I don't touch the public API in a year, the current version (0.8) will be re-released as 1.0.