Snap for 10453563 from 888d07dacb839cfe377aebb029c587195bb26052 to mainline-mediaprovider-release
Change-Id: I8b396f5516c1f1f132da0c955430395aba1786cb
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 832d476..5f20ebf 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,6 @@
{
"git": {
- "sha1": "e77cab8c1e15bfc9f54dfd28bd8820c2a7bb27c4"
- }
-}
+ "sha1": "f9acd508bd89e7c5b2877a9510098100f9018d64"
+ },
+ "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/.github/workflows/rust.yml b/.github/workflows/rust.yml
index ba596bf..c551724 100644
--- a/.github/workflows/rust.yml
+++ b/.github/workflows/rust.yml
@@ -32,6 +32,11 @@
with:
command: test
args: --no-default-features --features compile-time-rng
+ - name: check fixed-seed
+ uses: actions-rs/cargo@v1
+ with:
+ command: check
+ args: --no-default-features --features std
- name: check
uses: actions-rs/cargo@v1
with:
@@ -148,4 +153,4 @@
- uses: actions-rs/cargo@v1
with:
command: check
- args: --target wasm32-unknown-unknown
+ args: --target wasm32-unknown-unknown --no-default-features
diff --git a/Android.bp b/Android.bp
index 9e1253a..3e1997a 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,11 +39,10 @@
rust_library {
name: "libahash",
- // has rustc warnings
host_supported: true,
crate_name: "ahash",
cargo_env_compat: true,
- cargo_pkg_version: "0.7.6",
+ cargo_pkg_version: "0.8.3",
srcs: ["src/lib.rs"],
edition: "2018",
arch: {
@@ -56,11 +55,21 @@
},
features: [
"default",
+ "getrandom",
"runtime-rng",
+ "specialize",
"std",
+ "stdsimd",
],
rustlibs: [
+ "libcfg_if",
"libgetrandom",
"libonce_cell",
],
+ apex_available: [
+ "//apex_available:platform",
+ "//apex_available:anyapex",
+ ],
+ product_available: true,
+ vendor_available: true,
}
diff --git a/Cargo.toml b/Cargo.toml
index b412f79..a027c55 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,31 +3,51 @@
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
-# to registry (e.g., crates.io) dependencies
+# to registry (e.g., crates.io) dependencies.
#
-# If you believe there's an error in this file please file an
-# issue against the rust-lang/cargo repository. If you're
-# editing this file be aware that the upstream Cargo.toml
-# will likely look very different (and much more reasonable)
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
[package]
edition = "2018"
name = "ahash"
-version = "0.7.6"
+version = "0.8.3"
authors = ["Tom Kaitchuck <Tom.Kaitchuck@gmail.com>"]
build = "./build.rs"
-exclude = ["/smhasher", "/benchmark_tools"]
+exclude = [
+ "/smhasher",
+ "/benchmark_tools",
+]
description = "A non-cryptographic hash function using AES-NI for high performance"
documentation = "https://docs.rs/ahash"
readme = "README.md"
-keywords = ["hash", "hasher", "hashmap", "aes", "no-std"]
-categories = ["algorithms", "data-structures", "no-std"]
+keywords = [
+ "hash",
+ "hasher",
+ "hashmap",
+ "aes",
+ "no-std",
+]
+categories = [
+ "algorithms",
+ "data-structures",
+ "no-std",
+]
license = "MIT OR Apache-2.0"
repository = "https://github.com/tkaitchuck/ahash"
+
[package.metadata.docs.rs]
+rustc-args = [
+ "-C",
+ "target-feature=+aes",
+]
+rustdoc-args = [
+ "-C",
+ "target-feature=+aes",
+]
features = ["std"]
-rustc-args = ["-C", "target-feature=+aes"]
-rustdoc-args = ["-C", "target-feature=+aes"]
+
[profile.bench]
opt-level = 3
lto = "fat"
@@ -63,8 +83,29 @@
name = "map"
path = "tests/map_tests.rs"
harness = false
+
+[dependencies.atomic-polyfill]
+version = "1.0.1"
+optional = true
+
+[dependencies.cfg-if]
+version = "1.0"
+
+[dependencies.const-random]
+version = "0.1.12"
+optional = true
+
+[dependencies.getrandom]
+version = "0.2.7"
+optional = true
+
+[dependencies.serde]
+version = "1.0.117"
+optional = true
+
[dev-dependencies.criterion]
version = "0.3.2"
+features = ["html_reports"]
[dev-dependencies.fnv]
version = "1.0.5"
@@ -72,6 +113,9 @@
[dev-dependencies.fxhash]
version = "0.2.1"
+[dev-dependencies.hashbrown]
+version = "0.12.3"
+
[dev-dependencies.hex]
version = "0.4.2"
@@ -79,38 +123,35 @@
version = "0.1.10"
[dev-dependencies.rand]
-version = "0.7.3"
+version = "0.8.5"
[dev-dependencies.seahash]
version = "4.0"
[dev-dependencies.serde_json]
version = "1.0.59"
+
[build-dependencies.version_check]
-version = "0.9"
+version = "0.9.4"
[features]
+atomic-polyfill = [
+ "dep:atomic-polyfill",
+ "once_cell/atomic-polyfill",
+]
compile-time-rng = ["const-random"]
-default = ["std"]
+default = [
+ "std",
+ "runtime-rng",
+]
+no-rng = []
+runtime-rng = ["getrandom"]
std = []
-[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.const-random]
-version = "0.1.12"
-optional = true
-[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.getrandom]
-version = "0.2.3"
-
-[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.serde]
-version = "1.0.117"
-optional = true
[target."cfg(not(all(target_arch = \"arm\", target_os = \"none\")))".dependencies.once_cell]
-version = "1.8"
-features = ["alloc"]
+version = "1.13.1"
+features = [
+ "unstable",
+ "alloc",
+]
default-features = false
-[target."cfg(not(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\")))".dependencies.const-random]
-version = "0.1.12"
-optional = true
-
-[target."cfg(not(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\")))".dependencies.serde]
-version = "1.0.117"
-optional = true
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 4b56472..9b19105 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "ahash"
-version = "0.7.6"
+version = "0.8.3"
authors = ["Tom Kaitchuck <Tom.Kaitchuck@gmail.com>"]
license = "MIT OR Apache-2.0"
description = "A non-cryptographic hash function using AES-NI for high performance"
@@ -22,17 +22,27 @@
doc = true
[features]
-default = ["std"]
+default = ["std", "runtime-rng"]
# Enabling this will enable `AHashMap` and `AHashSet`.
std = []
-# This is an alternitive to runtime key generation which does compile time key generation if getrandom is not available.
-# (If getrandom is available this does nothing.)
-# If this is on (and getrandom is off) it implies the produced binary will not be identical.
-# If this is disabled and gerrandom is unavailable constant keys are used.
+# Runtime random key generation using getrandom.
+runtime-rng = ["getrandom"]
+
+# This is an alternative to runtime key generation which does compile time key generation if runtime-rng is not available.
+# (If runtime-rng is enabled this does nothing.)
+# If this is on (and runtime-rng is off) it implies the produced binary will not be identical.
+# If this is disabled and runtime-rng is unavailable constant keys are used.
compile-time-rng = ["const-random"]
+# Do not use any random number generator (either at compile time or runtime)
+# If either runtime-rng or compile-time-rng are enabled this does nothing.
+no-rng = []
+
+# in case this is being used on an architecture lacking core::sync::atomic::AtomicUsize and friends
+atomic-polyfill = [ "dep:atomic-polyfill", "once_cell/atomic-polyfill"]
+
[[bench]]
name = "ahash"
path = "tests/bench.rs"
@@ -62,29 +72,28 @@
codegen-units = 1
[build-dependencies]
-version_check = "0.9"
+version_check = "0.9.4"
-[target.'cfg(any(target_os = "linux", target_os = "android", target_os = "windows", target_os = "macos", target_os = "ios", target_os = "freebsd", target_os = "openbsd", target_os = "netbsd", target_os = "dragonfly", target_os = "solaris", target_os = "illumos", target_os = "fuchsia", target_os = "redox", target_os = "cloudabi", target_os = "haiku", target_os = "vxworks", target_os = "emscripten", target_os = "wasi"))'.dependencies]
-getrandom = { version = "0.2.3" }
+[dependencies]
const-random = { version = "0.1.12", optional = true }
serde = { version = "1.0.117", optional = true }
-
-[target.'cfg(not(any(target_os = "linux", target_os = "android", target_os = "windows", target_os = "macos", target_os = "ios", target_os = "freebsd", target_os = "openbsd", target_os = "netbsd", target_os = "dragonfly", target_os = "solaris", target_os = "illumos", target_os = "fuchsia", target_os = "redox", target_os = "cloudabi", target_os = "haiku", target_os = "vxworks", target_os = "emscripten", target_os = "wasi")))'.dependencies]
-const-random = { version = "0.1.12", optional = true }
-serde = { version = "1.0.117", optional = true }
+cfg-if = "1.0"
+atomic-polyfill = { version="1.0.1", optional=true}
+getrandom = { version = "0.2.7", optional = true }
[target.'cfg(not(all(target_arch = "arm", target_os = "none")))'.dependencies]
-once_cell = { version = "1.8", default-features = false, features = ["alloc"] }
+once_cell = { version = "1.13.1", default-features = false, features = ["unstable", "alloc"] }
[dev-dependencies]
no-panic = "0.1.10"
-criterion = {version = "0.3.2"}
+criterion = {version = "0.3.2", features = ["html_reports"] }
seahash = "4.0"
fnv = "1.0.5"
fxhash = "0.2.1"
hex = "0.4.2"
-rand = "0.7.3"
+rand = "0.8.5"
serde_json = "1.0.59"
+hashbrown = "0.12.3"
[package.metadata.docs.rs]
rustc-args = ["-C", "target-feature=+aes"]
diff --git a/LICENSE-MIT b/LICENSE-MIT
index 5afc2a7..cba2010 100644
--- a/LICENSE-MIT
+++ b/LICENSE-MIT
@@ -1,4 +1,4 @@
-Copyright (c) 2016 Amanieu d'Antras
+Copyright (c) 2018 Tom Kaitchuck
Permission is hereby granted, free of charge, to any
person obtaining a copy of this software and associated
diff --git a/METADATA b/METADATA
index 7ee2368..18aa68c 100644
--- a/METADATA
+++ b/METADATA
@@ -1,3 +1,7 @@
+# This project was upgraded with external_updater.
+# Usage: tools/external_updater/updater.sh update rust/crates/ahash
+# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md
+
name: "ahash"
description: "A non-cryptographic hash function using AES-NI for high performance"
third_party {
@@ -7,13 +11,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/ahash/ahash-0.7.6.crate"
+ value: "https://static.crates.io/crates/ahash/ahash-0.8.3.crate"
}
- version: "0.7.6"
+ version: "0.8.3"
license_type: NOTICE
last_upgrade_date {
- year: 2022
+ year: 2023
month: 2
- day: 28
+ day: 15
}
}
diff --git a/README.md b/README.md
index be365a7..18c421d 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,4 @@
-# aHash   
+# aHash   
AHash is the [fastest](https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md#Speed),
[DOS resistant hash](https://github.com/tkaitchuck/aHash/wiki/How-aHash-is-resists-DOS-attacks) currently available in Rust.
@@ -53,18 +53,16 @@
The aHash package has the following flags:
* `std`: This enables features which require the standard library. (On by default) This includes providing the utility classes `AHashMap` and `AHashSet`.
* `serde`: Enables `serde` support for the utility classes `AHashMap` and `AHashSet`.
-* `compile-time-rng`: Whenever possible aHash will seed hashers with random numbers using the [getrandom](https://github.com/rust-random/getrandom) crate.
-This is possible for OS targets which provide a source of randomness. (see the [full list](https://docs.rs/getrandom/0.2.0/getrandom/#supported-targets).)
-For OS targets without access to a random number generator, `compile-time-rng` provides an alternative.
+* `runtime-rng`: To obtain a seed for Hashers will obtain randomness from the operating system. (On by default)
+This is done using the [getrandom](https://github.com/rust-random/getrandom) crate.
+* `compile-time-rng`: For OS targets without access to a random number generator, `compile-time-rng` provides an alternative.
If `getrandom` is unavailable and `compile-time-rng` is enabled, aHash will generate random numbers at compile time and embed them in the binary.
This allows for DOS resistance even if there is no random number generator available at runtime (assuming the compiled binary is not public).
-This makes the binary non-deterministic, unless `getrandom` is available for the target in which case the flag does nothing.
-(If non-determinism is a problem see [constrandom's documentation](https://github.com/tkaitchuck/constrandom#deterministic-builds))
+This makes the binary non-deterministic. (If non-determinism is a problem see [constrandom's documentation](https://github.com/tkaitchuck/constrandom#deterministic-builds))
-**NOTE:** If `getrandom` is unavailable and `compile-time-rng` is disabled aHash will fall back on using the numeric
-value of memory addresses as a source of randomness. This is somewhat strong if ALSR is turned on (it is by default)
-but for embedded platforms this will result in weak keys. As a result, it is recommended to use `compile-time-rng` anytime
-random numbers will not be available at runtime.
+If both `runtime-rng` and `compile-time-rng` are enabled the `runtime-rng` will take precedence and `compile-time-rng` will do nothing.
+If neither flag is set, seeds can be supplied by the application. [Multiple apis](https://docs.rs/ahash/latest/ahash/random_state/struct.RandomState.html)
+are available to do this.
## Comparison with other hashers
diff --git a/TEST_MAPPING b/TEST_MAPPING
index 91f37bf..fe31e08 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -1,19 +1,17 @@
// Generated by update_crate_tests.py for tests that depend on this crate.
{
- "presubmit": [
+ "imports": [
{
- "name": "keystore2_test"
+ "path": "external/rust/crates/hashbrown"
},
{
- "name": "legacykeystore_test"
- }
- ],
- "presubmit-rust": [
- {
- "name": "keystore2_test"
+ "path": "external/rust/crates/hashlink"
},
{
- "name": "legacykeystore_test"
+ "path": "system/security/keystore2"
+ },
+ {
+ "path": "system/security/keystore2/legacykeystore"
}
]
}
diff --git a/build.rs b/build.rs
index 8be4964..0c5b769 100644
--- a/build.rs
+++ b/build.rs
@@ -4,32 +4,11 @@
fn main() {
println!("cargo:rerun-if-changed=build.rs");
- if let Some(channel) = version_check::Channel::read() {
- if channel.supports_features() {
- println!("cargo:rustc-cfg=feature=\"specialize\"");
- println!("cargo:rustc-cfg=feature=\"stdsimd\"");
- }
+ if let Some(true) = version_check::supports_feature("specialize") {
+ println!("cargo:rustc-cfg=feature=\"specialize\"");
}
- let os = env::var("CARGO_CFG_TARGET_OS").expect("CARGO_CFG_TARGET_OS was not set");
- if os.eq_ignore_ascii_case("linux")
- || os.eq_ignore_ascii_case("android")
- || os.eq_ignore_ascii_case("windows")
- || os.eq_ignore_ascii_case("macos")
- || os.eq_ignore_ascii_case("ios")
- || os.eq_ignore_ascii_case("freebsd")
- || os.eq_ignore_ascii_case("openbsd")
- || os.eq_ignore_ascii_case("dragonfly")
- || os.eq_ignore_ascii_case("solaris")
- || os.eq_ignore_ascii_case("illumos")
- || os.eq_ignore_ascii_case("fuchsia")
- || os.eq_ignore_ascii_case("redox")
- || os.eq_ignore_ascii_case("cloudabi")
- || os.eq_ignore_ascii_case("haiku")
- || os.eq_ignore_ascii_case("vxworks")
- || os.eq_ignore_ascii_case("emscripten")
- || os.eq_ignore_ascii_case("wasi")
- {
- println!("cargo:rustc-cfg=feature=\"runtime-rng\"");
+ if let Some(true) = version_check::supports_feature("stdsimd") {
+ println!("cargo:rustc-cfg=feature=\"stdsimd\"");
}
let arch = env::var("CARGO_CFG_TARGET_ARCH").expect("CARGO_CFG_TARGET_ARCH was not set");
if arch.eq_ignore_ascii_case("x86_64")
@@ -41,5 +20,4 @@
{
println!("cargo:rustc-cfg=feature=\"folded_multiply\"");
}
-
}
diff --git a/cargo2android.json b/cargo2android.json
index 0f12cfd..3db58a3 100644
--- a/cargo2android.json
+++ b/cargo2android.json
@@ -2,4 +2,4 @@
"device": true,
"patch": "patches/Android.bp.diff",
"run": true
-}
\ No newline at end of file
+}
diff --git a/patches/0001-Use-dev-urandom-instead-of-getrandom.patch b/patches/0001-Use-dev-urandom-instead-of-getrandom.patch
index c5f4df3..a46f1b7 100644
--- a/patches/0001-Use-dev-urandom-instead-of-getrandom.patch
+++ b/patches/0001-Use-dev-urandom-instead-of-getrandom.patch
@@ -1,6 +1,6 @@
-From 5bce943cdb8fc81525257413f174844d644d63c8 Mon Sep 17 00:00:00 2001
-From: Eric Biggers <ebiggers@google.com>
-Date: Tue, 20 Apr 2021 16:48:07 -0700
+From fff15380539c659ccdb03fcc192eb95578b1feb5 Mon Sep 17 00:00:00 2001
+From: Jeff Vander Stoep <jeffv@google.com>
+Date: Thu, 1 Dec 2022 11:29:41 +0100
Subject: [PATCH] Use /dev/urandom instead of getrandom()
To generate the ahash crate's default hash keys, use /dev/urandom
@@ -14,15 +14,18 @@
for the same reason. So this change just makes ahash work like HashMap.
Bug: 185934601
-Change-Id: Ie81a1f3a893d578348db11aee114d1a8f2d9fac5
+Change-Id: Ieaf4bcfde5664d0b5d845234d0c2139d89c4153c
---
+ src/random_state.rs | 13 ++++++++++++-
+ 1 file changed, 12 insertions(+), 1 deletion(-)
+
diff --git a/src/random_state.rs b/src/random_state.rs
-index c3628bf..835467c 100644
+index e885fa4..5b85726 100644
--- a/src/random_state.rs
+++ b/src/random_state.rs
-@@ -48,6 +48,15 @@ use crate::fallback_hash::*;
- #[cfg(not(all(target_arch = "arm", target_os = "none")))]
- static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new();
+@@ -48,6 +48,15 @@ pub(crate) const PI2: [u64; 4] = [
+ 0x3f84_d5b5_b547_0917,
+ ];
+#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
+fn read_urandom(dest: &mut [u8]) -> Result<(), std::io::Error> {
@@ -33,17 +36,20 @@
+ f.read_exact(dest)
+}
+
- /// A supplier of Randomness used for different hashers.
- /// See [RandomState.set_random_source].
- pub trait RandomSource {
-@@ -98,7 +107,9 @@ impl RandomSource for DefaultRandomSource {
+ cfg_if::cfg_if! {
+ if #[cfg(all(feature = "compile-time-rng", any(test, fuzzing)))] {
+ #[inline]
+@@ -78,7 +87,9 @@ cfg_if::cfg_if! {
- SEEDS.get_or_init(|| {
- let mut result: [u8; 64] = [0; 64];
-- getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
-+ if read_urandom(&mut result).is_err() {
-+ getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
-+ }
- Box::new(result.convert())
- })
- }
+ SEEDS.get_or_init(|| {
+ let mut result: [u8; 64] = [0; 64];
+- getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
++ if read_urandom(&mut result).is_err() {
++ getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
++ }
+ Box::new(result.convert())
+ })
+ }
+--
+2.38.1.584.g0f3c55d4c2-goog
+
diff --git a/patches/Android.bp.diff b/patches/Android.bp.diff
index 1c3d18b..574031d 100644
--- a/patches/Android.bp.diff
+++ b/patches/Android.bp.diff
@@ -1,9 +1,9 @@
diff --git a/Android.bp b/Android.bp
-index b6d9875..14124db 100644
+index f33ba7a..62b8b27 100644
--- a/Android.bp
+++ b/Android.bp
-@@ -44,9 +44,16 @@ rust_library {
- crate_name: "ahash",
+@@ -46,9 +46,16 @@ rust_library {
+ cargo_pkg_version: "0.8.2",
srcs: ["src/lib.rs"],
edition: "2018",
+ arch: {
@@ -17,6 +17,6 @@
features: [
"default",
- "folded_multiply",
+ "getrandom",
"runtime-rng",
"specialize",
- "std",
diff --git a/src/aes_hash.rs b/src/aes_hash.rs
index 1c98582..702044e 100644
--- a/src/aes_hash.rs
+++ b/src/aes_hash.rs
@@ -1,10 +1,8 @@
use crate::convert::*;
-#[cfg(feature = "specialize")]
-use crate::fallback_hash::MULTIPLE;
use crate::operations::*;
+use crate::random_state::PI;
use crate::RandomState;
use core::hash::Hasher;
-use crate::random_state::PI;
/// A `Hasher` for hashing an arbitrary stream of bytes.
///
@@ -50,7 +48,7 @@
/// println!("Hash is {:x}!", hasher.finish());
/// ```
#[inline]
- pub fn new_with_keys(key1: u128, key2: u128) -> Self {
+ pub(crate) fn new_with_keys(key1: u128, key2: u128) -> Self {
let pi: [u128; 2] = PI.convert();
let key1 = key1 ^ pi[0];
let key2 = key2 ^ pi[1];
@@ -70,7 +68,6 @@
}
}
-
#[inline]
pub(crate) fn from_random_state(rand_state: &RandomState) -> Self {
let key1 = [rand_state.k0, rand_state.k1].convert();
@@ -83,14 +80,6 @@
}
#[inline(always)]
- fn add_in_length(&mut self, length: u64) {
- //This will be scrambled by the next AES round.
- let mut enc: [u64; 2] = self.enc.convert();
- enc[0] = enc[0].wrapping_add(length);
- self.enc = enc.convert();
- }
-
- #[inline(always)]
fn hash_in(&mut self, new_value: u128) {
self.enc = aesenc(self.enc, new_value);
self.sum = shuffle_and_add(self.sum, new_value);
@@ -138,7 +127,11 @@
}
#[inline]
- #[cfg(any(target_pointer_width = "64", target_pointer_width = "32", target_pointer_width = "16"))]
+ #[cfg(any(
+ target_pointer_width = "64",
+ target_pointer_width = "32",
+ target_pointer_width = "16"
+ ))]
fn write_usize(&mut self, i: usize) {
self.write_u64(i as u64);
}
@@ -159,7 +152,8 @@
fn write(&mut self, input: &[u8]) {
let mut data = input;
let length = data.len();
- self.add_in_length(length as u64);
+ add_in_length(&mut self.enc, length as u64);
+
//A 'binary search' on sizes reduces the number of comparisons.
if data.len() <= 8 {
let value = read_small(data);
@@ -326,7 +320,7 @@
impl Hasher for AHasherStr {
#[inline]
fn finish(&self) -> u64 {
- let result : [u64; 2] = self.0.enc.convert();
+ let result: [u64; 2] = self.0.enc.convert();
result[0]
}
@@ -337,7 +331,8 @@
self.0.enc = aesdec(self.0.sum, self.0.enc);
self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc);
} else {
- self.0.add_in_length(bytes.len() as u64);
+ add_in_length(&mut self.0.enc, bytes.len() as u64);
+
let value = read_small(bytes).convert();
self.0.sum = shuffle_and_add(self.0.sum, value);
self.0.enc = aesdec(self.0.sum, self.0.enc);
@@ -436,4 +431,3 @@
assert_eq!(bytes, 0x6464646464646464);
}
}
-
diff --git a/src/convert.rs b/src/convert.rs
index 4c0a00e..fc47baa 100644
--- a/src/convert.rs
+++ b/src/convert.rs
@@ -7,17 +7,13 @@
impl Convert<$b> for $a {
#[inline(always)]
fn convert(self) -> $b {
- unsafe {
- core::mem::transmute::<$a, $b>(self)
- }
+ unsafe { core::mem::transmute::<$a, $b>(self) }
}
}
impl Convert<$a> for $b {
#[inline(always)]
fn convert(self) -> $a {
- unsafe {
- core::mem::transmute::<$b, $a>(self)
- }
+ unsafe { core::mem::transmute::<$b, $a>(self) }
}
}
};
diff --git a/src/fallback_hash.rs b/src/fallback_hash.rs
index aad9efc..f78074d 100644
--- a/src/fallback_hash.rs
+++ b/src/fallback_hash.rs
@@ -1,12 +1,11 @@
use crate::convert::*;
use crate::operations::folded_multiply;
use crate::operations::read_small;
+use crate::operations::MULTIPLE;
use crate::random_state::PI;
use crate::RandomState;
use core::hash::Hasher;
-///This constant come from Kunth's prng (Empirically it works better than those from splitmix32).
-pub(crate) const MULTIPLE: u64 = 6364136223846793005;
const ROT: u32 = 23; //17
/// A `Hasher` for hashing an arbitrary stream of bytes.
@@ -31,7 +30,7 @@
/// Creates a new hasher keyed to the provided key.
#[inline]
#[allow(dead_code)] // Is not called if non-fallback hash is used.
- pub fn new_with_keys(key1: u128, key2: u128) -> AHasher {
+ pub(crate) fn new_with_keys(key1: u128, key2: u128) -> AHasher {
let pi: [u128; 2] = PI.convert();
let key1: [u64; 2] = (key1 ^ pi[0]).convert();
let key2: [u64; 2] = (key2 ^ pi[1]).convert();
@@ -93,19 +92,10 @@
/// attacker somehow knew part of (but not all) the contents of the buffer before hand,
/// they would not be able to predict any of the bits in the buffer at the end.
#[inline(always)]
- #[cfg(feature = "folded_multiply")]
fn update(&mut self, new_data: u64) {
self.buffer = folded_multiply(new_data ^ self.buffer, MULTIPLE);
}
- #[inline(always)]
- #[cfg(not(feature = "folded_multiply"))]
- fn update(&mut self, new_data: u64) {
- let d1 = (new_data ^ self.buffer).wrapping_mul(MULTIPLE);
- self.pad = (self.pad ^ d1).rotate_left(8).wrapping_mul(MULTIPLE);
- self.buffer = (self.buffer ^ self.pad).rotate_left(24);
- }
-
/// Similar to the above this function performs an update using a "folded multiply".
/// However it takes in 128 bits of data instead of 64. Both halves must be masked.
///
@@ -118,21 +108,12 @@
/// can't be changed by the same set of input bits. To cancel this sequence with subsequent input would require
/// knowing the keys.
#[inline(always)]
- #[cfg(feature = "folded_multiply")]
fn large_update(&mut self, new_data: u128) {
let block: [u64; 2] = new_data.convert();
let combined = folded_multiply(block[0] ^ self.extra_keys[0], block[1] ^ self.extra_keys[1]);
self.buffer = (self.buffer.wrapping_add(self.pad) ^ combined).rotate_left(ROT);
}
- #[inline(always)]
- #[cfg(not(feature = "folded_multiply"))]
- fn large_update(&mut self, new_data: u128) {
- let block: [u64; 2] = new_data.convert();
- self.update(block[0] ^ self.extra_keys[0]);
- self.update(block[1] ^ self.extra_keys[1]);
- }
-
#[inline]
#[cfg(feature = "specialize")]
fn short_finish(&self) -> u64 {
@@ -170,7 +151,11 @@
}
#[inline]
- #[cfg(any(target_pointer_width = "64", target_pointer_width = "32", target_pointer_width = "16"))]
+ #[cfg(any(
+ target_pointer_width = "64",
+ target_pointer_width = "32",
+ target_pointer_width = "16"
+ ))]
fn write_usize(&mut self, i: usize) {
self.write_u64(i as u64);
}
@@ -208,18 +193,10 @@
}
#[inline]
- #[cfg(feature = "folded_multiply")]
fn finish(&self) -> u64 {
let rot = (self.buffer & 63) as u32;
folded_multiply(self.buffer, self.pad).rotate_left(rot)
}
-
- #[inline]
- #[cfg(not(feature = "folded_multiply"))]
- fn finish(&self) -> u64 {
- let rot = (self.buffer & 63) as u32;
- (self.buffer.wrapping_mul(MULTIPLE) ^ self.pad).rotate_left(rot)
- }
}
#[cfg(feature = "specialize")]
@@ -338,8 +315,7 @@
self.0.write(bytes)
} else {
let value = read_small(bytes);
- self.0.buffer = folded_multiply(value[0] ^ self.0.buffer,
- value[1] ^ self.0.extra_keys[1]);
+ self.0.buffer = folded_multiply(value[0] ^ self.0.buffer, value[1] ^ self.0.extra_keys[1]);
self.0.pad = self.0.pad.wrapping_add(bytes.len() as u64);
}
}
diff --git a/src/hash_map.rs b/src/hash_map.rs
index ec8fa43..2b6fbdc 100644
--- a/src/hash_map.rs
+++ b/src/hash_map.rs
@@ -1,4 +1,5 @@
use std::borrow::Borrow;
+use std::collections::hash_map::{IntoKeys, IntoValues};
use std::collections::{hash_map, HashMap};
use std::fmt::{self, Debug};
use std::hash::{BuildHasher, Hash};
@@ -25,6 +26,24 @@
}
}
+impl<K, V, const N: usize> From<[(K, V); N]> for AHashMap<K, V>
+where
+ K: Eq + Hash,
+{
+ /// # Examples
+ ///
+ /// ```
+ /// use ahash::AHashMap;
+ ///
+ /// let map1 = AHashMap::from([(1, 2), (3, 4)]);
+ /// let map2: AHashMap<_, _> = [(1, 2), (3, 4)].into();
+ /// assert_eq!(map1, map2);
+ /// ```
+ fn from(arr: [(K, V); N]) -> Self {
+ Self::from_iter(arr)
+ }
+}
+
impl<K, V> Into<HashMap<K, V, crate::RandomState>> for AHashMap<K, V> {
fn into(self) -> HashMap<K, V, crate::RandomState> {
self.0
@@ -32,12 +51,16 @@
}
impl<K, V> AHashMap<K, V, RandomState> {
+ /// This crates a hashmap using [RandomState::new] which obtains its keys from [RandomSource].
+ /// See the documentation in [RandomSource] for notes about key strength.
pub fn new() -> Self {
- AHashMap(HashMap::with_hasher(RandomState::default()))
+ AHashMap(HashMap::with_hasher(RandomState::new()))
}
+ /// This crates a hashmap with the specified capacity using [RandomState::new].
+ /// See the documentation in [RandomSource] for notes about key strength.
pub fn with_capacity(capacity: usize) -> Self {
- AHashMap(HashMap::with_capacity_and_hasher(capacity, RandomState::default()))
+ AHashMap(HashMap::with_capacity_and_hasher(capacity, RandomState::new()))
}
}
@@ -145,8 +168,6 @@
/// types that can be `==` without being identical. See the [module-level
/// documentation] for more.
///
- /// [module-level documentation]: crate::collections#insert-and-complex-keys
- ///
/// # Examples
///
/// ```
@@ -165,6 +186,68 @@
self.0.insert(k, v)
}
+ /// Creates a consuming iterator visiting all the keys in arbitrary order.
+ /// The map cannot be used after calling this.
+ /// The iterator element type is `K`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// let mut vec: Vec<&str> = map.into_keys().collect();
+ /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
+ /// // keys must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, ["a", "b", "c"]);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over keys takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ pub fn into_keys(self) -> IntoKeys<K, V> {
+ self.0.into_keys()
+ }
+
+ /// Creates a consuming iterator visiting all the values in arbitrary order.
+ /// The map cannot be used after calling this.
+ /// The iterator element type is `V`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use std::collections::HashMap;
+ ///
+ /// let map = HashMap::from([
+ /// ("a", 1),
+ /// ("b", 2),
+ /// ("c", 3),
+ /// ]);
+ ///
+ /// let mut vec: Vec<i32> = map.into_values().collect();
+ /// // The `IntoValues` iterator produces values in arbitrary order, so
+ /// // the values must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [1, 2, 3]);
+ /// ```
+ ///
+ /// # Performance
+ ///
+ /// In the current implementation, iterating over values takes O(capacity) time
+ /// instead of O(len) because it internally visits empty buckets too.
+ #[inline]
+ pub fn into_values(self) -> IntoValues<K, V> {
+ self.0.into_values()
+ }
+
/// Removes a key from the map, returning the value at the key if the key
/// was previously in the map.
///
@@ -261,13 +344,16 @@
}
}
-impl<K, V, S> FromIterator<(K, V)> for AHashMap<K, V, S>
+impl<K, V> FromIterator<(K, V)> for AHashMap<K, V, RandomState>
where
K: Eq + Hash,
- S: BuildHasher + Default,
{
+ /// This crates a hashmap from the provided iterator using [RandomState::new].
+ /// See the documentation in [RandomSource] for notes about key strength.
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
- AHashMap(HashMap::from_iter(iter))
+ let mut inner = HashMap::with_hasher(RandomState::new());
+ inner.extend(iter);
+ AHashMap(inner)
}
}
@@ -318,10 +404,14 @@
}
}
+/// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or
+/// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of
+/// constructors for [RandomState] must be used.
+#[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))]
impl<K, V> Default for AHashMap<K, V, RandomState> {
#[inline]
fn default() -> AHashMap<K, V, RandomState> {
- AHashMap::new()
+ AHashMap(HashMap::default())
}
}
@@ -346,6 +436,40 @@
let hash_map = HashMap::deserialize(deserializer);
hash_map.map(|hash_map| Self(hash_map))
}
+
+ fn deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error> {
+ use serde::de::{MapAccess, Visitor};
+
+ struct MapInPlaceVisitor<'a, K: 'a, V: 'a>(&'a mut AHashMap<K, V>);
+
+ impl<'a, 'de, K, V> Visitor<'de> for MapInPlaceVisitor<'a, K, V>
+ where
+ K: Deserialize<'de> + Eq + Hash,
+ V: Deserialize<'de>,
+ {
+ type Value = ();
+
+ fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+ formatter.write_str("a map")
+ }
+
+ fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
+ where
+ A: MapAccess<'de>,
+ {
+ self.0.clear();
+ self.0.reserve(map.size_hint().unwrap_or(0).min(4096));
+
+ while let Some((key, value)) = map.next_entry()? {
+ self.0.insert(key, value);
+ }
+
+ Ok(())
+ }
+ }
+
+ deserializer.deserialize_map(MapInPlaceVisitor(place))
+ }
}
#[cfg(test)]
@@ -364,8 +488,14 @@
let mut map = AHashMap::new();
map.insert("for".to_string(), 0);
map.insert("bar".to_string(), 1);
- let serialization = serde_json::to_string(&map).unwrap();
- let deserialization: AHashMap<String, u64> = serde_json::from_str(&serialization).unwrap();
+ let mut serialization = serde_json::to_string(&map).unwrap();
+ let mut deserialization: AHashMap<String, u64> = serde_json::from_str(&serialization).unwrap();
+ assert_eq!(deserialization, map);
+
+ map.insert("baz".to_string(), 2);
+ serialization = serde_json::to_string(&map).unwrap();
+ let mut deserializer = serde_json::Deserializer::from_str(&serialization);
+ AHashMap::deserialize_in_place(&mut deserializer, &mut deserialization).unwrap();
assert_eq!(deserialization, map);
}
}
diff --git a/src/hash_quality_test.rs b/src/hash_quality_test.rs
index 4cd3156..8f13d24 100644
--- a/src/hash_quality_test.rs
+++ b/src/hash_quality_test.rs
@@ -50,7 +50,7 @@
(same_byte_count, same_nibble_count)
}
-fn gen_combinations(options: &[u32; 8], depth: u32, so_far: Vec<u32>, combinations: &mut Vec<Vec<u32>>) {
+fn gen_combinations(options: &[u32; 11], depth: u32, so_far: Vec<u32>, combinations: &mut Vec<Vec<u32>>) {
if depth == 0 {
return;
}
@@ -63,8 +63,9 @@
}
fn test_no_full_collisions<T: Hasher>(gen_hash: impl Fn() -> T) {
- let options: [u32; 8] = [
- 0x00000000, 0x20000000, 0x40000000, 0x60000000, 0x80000000, 0xA0000000, 0xC0000000, 0xE0000000,
+ let options: [u32; 11] = [
+ 0x00000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000, 0xF0000000,
+ 1, 2, 4, 8, 15
];
let mut combinations = Vec::new();
gen_combinations(&options, 7, Vec::new(), &mut combinations);
@@ -89,7 +90,7 @@
map.insert(hash, array);
}
}
- assert_eq!(2396744, map.len());
+ assert_eq!(21435887, map.len()); //11^7 + 11^6 ...
}
fn test_keys_change_output<T: Hasher>(constructor: impl Fn(u128, u128) -> T) {
@@ -147,7 +148,14 @@
for alternitive in alternitives {
changed_bits |= base ^ alternitive
}
- assert_eq!(core::u64::MAX, changed_bits, "Bits changed: {:x} on num: {:?}", changed_bits, num);
+ assert_eq!(
+ core::u64::MAX,
+ changed_bits,
+ "Bits changed: {:x} on num: {:?}. base {:x}",
+ changed_bits,
+ num,
+ base
+ );
}
fn test_finish_is_consistent<T: Hasher>(constructor: impl Fn(u128, u128) -> T) {
@@ -273,11 +281,19 @@
let (same_bytes, same_nibbles) = count_same_bytes_and_nibbles(value, long.finish());
assert!(
same_bytes <= 3,
- "{} bytes of {} -> {:x} vs {:x}", num, c, value, long.finish()
+ "{} bytes of {} -> {:x} vs {:x}",
+ num,
+ c,
+ value,
+ long.finish()
);
assert!(
same_nibbles <= 8,
- "{} bytes of {} -> {:x} vs {:x}", num, c, value, long.finish()
+ "{} bytes of {} -> {:x} vs {:x}",
+ num,
+ c,
+ value,
+ long.finish()
);
let flipped_bits = (value ^ long.finish()).count_ones();
assert!(flipped_bits > 10);
@@ -370,7 +386,7 @@
fn fallback_keys_affect_every_byte() {
//For fallback second key is not used in every hash.
#[cfg(all(not(feature = "specialize"), feature = "folded_multiply"))]
- test_keys_affect_every_byte(0, |a, b| AHasher::new_with_keys(a ^ b, a));
+ test_keys_affect_every_byte(0, |a, b| AHasher::new_with_keys(a ^ b, a));
test_keys_affect_every_byte("", |a, b| AHasher::new_with_keys(a ^ b, a));
test_keys_affect_every_byte((0, 0), |a, b| AHasher::new_with_keys(a ^ b, a));
}
@@ -397,7 +413,12 @@
///Basic sanity tests of the cypto properties of aHash.
#[cfg(any(
all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
+ all(
+ any(target_arch = "arm", target_arch = "aarch64"),
+ any(target_feature = "aes", target_feature = "crypto"),
+ not(miri),
+ feature = "stdsimd"
+ )
))]
#[cfg(test)]
mod aes_tests {
@@ -460,7 +481,7 @@
#[test]
fn aes_keys_affect_every_byte() {
#[cfg(not(feature = "specialize"))]
- test_keys_affect_every_byte(0, AHasher::test_with_keys);
+ test_keys_affect_every_byte(0, AHasher::test_with_keys);
test_keys_affect_every_byte("", AHasher::test_with_keys);
test_keys_affect_every_byte((0, 0), AHasher::test_with_keys);
}
diff --git a/src/hash_set.rs b/src/hash_set.rs
index 9766b67..d03bef5 100644
--- a/src/hash_set.rs
+++ b/src/hash_set.rs
@@ -14,27 +14,49 @@
/// A [`HashSet`](std::collections::HashSet) using [`RandomState`](crate::RandomState) to hash the items.
/// (Requires the `std` feature to be enabled.)
#[derive(Clone)]
-pub struct AHashSet<T, S = crate::RandomState>(HashSet<T, S>);
+pub struct AHashSet<T, S = RandomState>(HashSet<T, S>);
-impl<T> From<HashSet<T, crate::RandomState>> for AHashSet<T> {
- fn from(item: HashSet<T, crate::RandomState>) -> Self {
+impl<T> From<HashSet<T, RandomState>> for AHashSet<T> {
+ fn from(item: HashSet<T, RandomState>) -> Self {
AHashSet(item)
}
}
-impl<T> Into<HashSet<T, crate::RandomState>> for AHashSet<T> {
- fn into(self) -> HashSet<T, crate::RandomState> {
+impl<T, const N: usize> From<[T; N]> for AHashSet<T>
+where
+ T: Eq + Hash,
+{
+ /// # Examples
+ ///
+ /// ```
+ /// use ahash::AHashSet;
+ ///
+ /// let set1 = AHashSet::from([1, 2, 3, 4]);
+ /// let set2: AHashSet<_> = [1, 2, 3, 4].into();
+ /// assert_eq!(set1, set2);
+ /// ```
+ fn from(arr: [T; N]) -> Self {
+ Self::from_iter(arr)
+ }
+}
+
+impl<T> Into<HashSet<T, RandomState>> for AHashSet<T> {
+ fn into(self) -> HashSet<T, RandomState> {
self.0
}
}
impl<T> AHashSet<T, RandomState> {
+ /// This crates a hashset using [RandomState::new].
+ /// See the documentation in [RandomSource] for notes about key strength.
pub fn new() -> Self {
- AHashSet(HashSet::with_hasher(RandomState::default()))
+ AHashSet(HashSet::with_hasher(RandomState::new()))
}
+ /// This crates a hashset with the specified capacity using [RandomState::new].
+ /// See the documentation in [RandomSource] for notes about key strength.
pub fn with_capacity(capacity: usize) -> Self {
- AHashSet(HashSet::with_capacity_and_hasher(capacity, RandomState::default()))
+ AHashSet(HashSet::with_capacity_and_hasher(capacity, RandomState::new()))
}
}
@@ -219,14 +241,17 @@
}
}
-impl<T, S> FromIterator<T> for AHashSet<T, S>
+impl<T> FromIterator<T> for AHashSet<T, RandomState>
where
T: Eq + Hash,
- S: BuildHasher + Default,
{
+ /// This crates a hashset from the provided iterator using [RandomState::new].
+ /// See the documentation in [RandomSource] for notes about key strength.
#[inline]
- fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T, S> {
- AHashSet(HashSet::from_iter(iter))
+ fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T> {
+ let mut inner = HashSet::with_hasher(RandomState::new());
+ inner.extend(iter);
+ AHashSet(inner)
}
}
@@ -268,6 +293,10 @@
}
}
+/// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or
+/// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of
+/// constructors for [RandomState] must be used.
+#[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))]
impl<T> Default for AHashSet<T, RandomState> {
/// Creates an empty `AHashSet<T, S>` with the `Default` value for the hasher.
#[inline]
@@ -295,6 +324,10 @@
let hash_set = HashSet::deserialize(deserializer);
hash_set.map(|hash_set| Self(hash_set))
}
+
+ fn deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error> {
+ HashSet::deserialize_in_place(deserializer, place)
+ }
}
#[cfg(all(test, feature = "serde"))]
@@ -306,8 +339,14 @@
let mut set = AHashSet::new();
set.insert("for".to_string());
set.insert("bar".to_string());
- let serialization = serde_json::to_string(&set).unwrap();
- let deserialization: AHashSet<String> = serde_json::from_str(&serialization).unwrap();
+ let mut serialization = serde_json::to_string(&set).unwrap();
+ let mut deserialization: AHashSet<String> = serde_json::from_str(&serialization).unwrap();
+ assert_eq!(deserialization, set);
+
+ set.insert("baz".to_string());
+ serialization = serde_json::to_string(&set).unwrap();
+ let mut deserializer = serde_json::Deserializer::from_str(&serialization);
+ AHashSet::deserialize_in_place(&mut deserializer, &mut deserialization).unwrap();
assert_eq!(deserialization, set);
}
}
diff --git a/src/lib.rs b/src/lib.rs
index 9964a7c..978f424 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,86 +1,208 @@
-//! AHash is a hashing algorithm is intended to be a high performance, (hardware specific), keyed hash function.
-//! This can be seen as a DOS resistant alternative to `FxHash`, or a fast equivalent to `SipHash`.
-//! It provides a high speed hash algorithm, but where the result is not predictable without knowing a Key.
-//! This allows it to be used in a `HashMap` without allowing for the possibility that an malicious user can
+//! AHash is a high performance keyed hash function.
+//!
+//! It quickly provides a high quality hash where the result is not predictable without knowing the Key.
+//! AHash works with `HashMap` to hash keys, but without allowing for the possibility that an malicious user can
//! induce a collision.
//!
//! # How aHash works
//!
-//! aHash uses the hardware AES instruction on x86 processors to provide a keyed hash function.
-//! aHash is not a cryptographically secure hash.
+//! When it is available aHash uses the hardware AES instructions to provide a keyed hash function.
+//! When it is not, aHash falls back on a slightly slower alternative algorithm.
//!
-//! # Example
-//! ```
-//! use ahash::{AHasher, RandomState};
-//! use std::collections::HashMap;
-//!
-//! let mut map: HashMap<i32, i32, RandomState> = HashMap::default();
-//! map.insert(12, 34);
-//! ```
-//! For convinence wrappers called `AHashMap` and `AHashSet` are also provided.
-//! These to the same thing with slightly less typing.
-//! ```ignore
-//! use ahash::AHashMap;
-//!
-//! let mut map: AHashMap<i32, i32> = AHashMap::with_capacity(4);
-//! map.insert(12, 34);
-//! map.insert(56, 78);
-//! ```
+//! Because aHash does not have a fixed standard for its output, it is able to improve over time.
+//! But this also means that different computers or computers using different versions of ahash may observe different
+//! hash values for the same input.
+#![cfg_attr(
+ all(feature = "std", any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng")),
+ doc = r##"
+# Basic Usage
+AHash provides an implementation of the [Hasher] trait.
+To construct a HashMap using aHash as its hasher do the following:
+```
+use ahash::{AHasher, RandomState};
+use std::collections::HashMap;
+
+let mut map: HashMap<i32, i32, RandomState> = HashMap::default();
+map.insert(12, 34);
+```
+
+### Randomness
+
+The above requires a source of randomness to generate keys for the hashmap. By default this obtained from the OS.
+It is also possible to have randomness supplied via the `compile-time-rng` flag, or manually.
+
+### If randomess is not available
+
+[AHasher::default()] can be used to hash using fixed keys. This works with
+[BuildHasherDefault](std::hash::BuildHasherDefault). For example:
+
+```
+use std::hash::BuildHasherDefault;
+use std::collections::HashMap;
+use ahash::AHasher;
+
+let mut m: HashMap<_, _, BuildHasherDefault<AHasher>> = HashMap::default();
+ # m.insert(12, 34);
+```
+It is also possible to instantiate [RandomState] directly:
+
+```
+use ahash::HashMap;
+use ahash::RandomState;
+
+let mut m = HashMap::with_hasher(RandomState::with_seed(42));
+ # m.insert(1, 2);
+```
+Or for uses besides a hashhmap:
+```
+use std::hash::BuildHasher;
+use ahash::RandomState;
+
+let hash_builder = RandomState::with_seed(42);
+let hash = hash_builder.hash_one("Some Data");
+```
+There are several constructors for [RandomState] with different ways to supply seeds.
+
+# Convenience wrappers
+
+For convenience, both new-type wrappers and type aliases are provided.
+
+The new type wrappers are called called `AHashMap` and `AHashSet`.
+```
+use ahash::AHashMap;
+
+let mut map: AHashMap<i32, i32> = AHashMap::new();
+map.insert(12, 34);
+```
+This avoids the need to type "RandomState". (For convience `From`, `Into`, and `Deref` are provided).
+
+# Aliases
+
+For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` ,
+the type aliases [HashMap], [HashSet] are provided.
+
+```
+use ahash::{HashMap, HashMapExt};
+
+let mut map: HashMap<i32, i32> = HashMap::new();
+map.insert(12, 34);
+```
+Note the import of [HashMapExt]. This is needed for the constructor.
+
+"##
+)]
#![deny(clippy::correctness, clippy::complexity, clippy::perf)]
#![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)]
#![cfg_attr(all(not(test), not(feature = "std")), no_std)]
#![cfg_attr(feature = "specialize", feature(min_specialization))]
+#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
#![cfg_attr(feature = "stdsimd", feature(stdsimd))]
#[macro_use]
mod convert;
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-mod aes_hash;
mod fallback_hash;
+
+cfg_if::cfg_if! {
+ if #[cfg(any(
+ all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
+ all(any(target_arch = "arm", target_arch = "aarch64"),
+ any(target_feature = "aes", target_feature = "crypto"),
+ not(miri),
+ feature = "stdsimd")
+ ))] {
+ mod aes_hash;
+ pub use crate::aes_hash::AHasher;
+ } else {
+ pub use crate::fallback_hash::AHasher;
+ }
+}
+
+cfg_if::cfg_if! {
+ if #[cfg(feature = "std")] {
+ mod hash_map;
+ mod hash_set;
+
+ pub use crate::hash_map::AHashMap;
+ pub use crate::hash_set::AHashSet;
+
+ /// [Hasher]: std::hash::Hasher
+ /// [HashMap]: std::collections::HashMap
+ /// Type alias for [HashMap]<K, V, ahash::RandomState>
+ pub type HashMap<K, V> = std::collections::HashMap<K, V, crate::RandomState>;
+
+ /// Type alias for [HashSet]<K, ahash::RandomState>
+ pub type HashSet<K> = std::collections::HashSet<K, crate::RandomState>;
+ }
+}
+
#[cfg(test)]
mod hash_quality_test;
-#[cfg(feature = "std")]
-mod hash_map;
-#[cfg(feature = "std")]
-mod hash_set;
mod operations;
-mod random_state;
+pub mod random_state;
mod specialize;
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-pub use crate::aes_hash::AHasher;
-
-#[cfg(not(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-pub use crate::fallback_hash::AHasher;
pub use crate::random_state::RandomState;
-pub use crate::specialize::CallHasher;
-
-#[cfg(feature = "std")]
-pub use crate::hash_map::AHashMap;
-#[cfg(feature = "std")]
-pub use crate::hash_set::AHashSet;
use core::hash::BuildHasher;
use core::hash::Hash;
use core::hash::Hasher;
+#[cfg(feature = "std")]
+/// A convenience trait that can be used together with the type aliases defined to
+/// get access to the `new()` and `with_capacity()` methods for the HashMap type alias.
+pub trait HashMapExt {
+ /// Constructs a new HashMap
+ fn new() -> Self;
+ /// Constructs a new HashMap with a given initial capacity
+ fn with_capacity(capacity: usize) -> Self;
+}
+
+#[cfg(feature = "std")]
+/// A convenience trait that can be used together with the type aliases defined to
+/// get access to the `new()` and `with_capacity()` methods for the HashSet type aliases.
+pub trait HashSetExt {
+ /// Constructs a new HashSet
+ fn new() -> Self;
+ /// Constructs a new HashSet with a given initial capacity
+ fn with_capacity(capacity: usize) -> Self;
+}
+
+#[cfg(feature = "std")]
+impl<K, V, S> HashMapExt for std::collections::HashMap<K, V, S>
+where
+ S: BuildHasher + Default,
+{
+ fn new() -> Self {
+ std::collections::HashMap::with_hasher(S::default())
+ }
+
+ fn with_capacity(capacity: usize) -> Self {
+ std::collections::HashMap::with_capacity_and_hasher(capacity, S::default())
+ }
+}
+
+#[cfg(feature = "std")]
+impl<K, S> HashSetExt for std::collections::HashSet<K, S>
+where
+ S: BuildHasher + Default,
+{
+ fn new() -> Self {
+ std::collections::HashSet::with_hasher(S::default())
+ }
+
+ fn with_capacity(capacity: usize) -> Self {
+ std::collections::HashSet::with_capacity_and_hasher(capacity, S::default())
+ }
+}
+
/// Provides a default [Hasher] with fixed keys.
/// This is typically used in conjunction with [BuildHasherDefault] to create
/// [AHasher]s in order to hash the keys of the map.
///
/// Generally it is preferable to use [RandomState] instead, so that different
-/// hashmaps will have different keys. However if fixed keys are desireable this
+/// hashmaps will have different keys. However if fixed keys are desirable this
/// may be used instead.
///
/// # Example
@@ -194,11 +316,24 @@
#[cfg(test)]
mod test {
use crate::convert::Convert;
+ use crate::specialize::CallHasher;
use crate::*;
use std::collections::HashMap;
use std::hash::Hash;
#[test]
+ fn test_ahash_alias_map_construction() {
+ let mut map = super::HashMap::with_capacity(1234);
+ map.insert(1, "test");
+ }
+
+ #[test]
+ fn test_ahash_alias_set_construction() {
+ let mut set = super::HashSet::with_capacity(1234);
+ set.insert(1);
+ }
+
+ #[test]
fn test_default_builder() {
use core::hash::BuildHasherDefault;
@@ -219,7 +354,6 @@
assert_eq!(bytes, 0x6464646464646464);
}
-
#[test]
fn test_non_zero() {
let mut hasher1 = AHasher::new_with_keys(0, 0);
@@ -241,7 +375,7 @@
#[test]
fn test_non_zero_specialized() {
- let hasher_build = RandomState::with_seeds(0,0,0,0);
+ let hasher_build = RandomState::with_seeds(0, 0, 0, 0);
let h1 = str::get_hash("foo", &hasher_build);
let h2 = str::get_hash("bar", &hasher_build);
diff --git a/src/operations.rs b/src/operations.rs
index b71fd5a..ffd3b1a 100644
--- a/src/operations.rs
+++ b/src/operations.rs
@@ -1,5 +1,8 @@
use crate::convert::*;
+///This constant comes from Kunth's prng (Empirically it works better than those from splitmix32).
+pub(crate) const MULTIPLE: u64 = 6364136223846793005;
+
/// This is a constant with a lot of special properties found by automated search.
/// See the unit tests below. (Below are alternative values)
#[cfg(all(target_feature = "ssse3", not(miri)))]
@@ -8,11 +11,19 @@
//const SHUFFLE_MASK: u128 = 0x040A0700_030E0106_0D050F08_020B0C09_u128;
#[inline(always)]
+#[cfg(feature = "folded_multiply")]
pub(crate) const fn folded_multiply(s: u64, by: u64) -> u64 {
let result = (s as u128).wrapping_mul(by as u128);
((result & 0xffff_ffff_ffff_ffff) as u64) ^ ((result >> 64) as u64)
}
+#[inline(always)]
+#[cfg(not(feature = "folded_multiply"))]
+pub(crate) const fn folded_multiply(s: u64, by: u64) -> u64 {
+ let b1 = s.wrapping_mul(by.swap_bytes());
+ let b2 = s.swap_bytes().wrapping_mul(!by);
+ b1 ^ b2.swap_bytes()
+}
/// Given a small (less than 8 byte slice) returns the same data stored in two u32s.
/// (order of and non-duplication of bytes is NOT guaranteed)
@@ -60,7 +71,7 @@
shuffle(sum.convert())
}
-#[allow(unused)] //not used by fallbac
+#[allow(unused)] //not used by fallback
#[inline(always)]
pub(crate) fn shuffle_and_add(base: u128, to_add: u128) -> u128 {
let shuffled: [u64; 2] = shuffle(base).convert();
@@ -101,14 +112,19 @@
}
}
-#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))]
+#[cfg(all(
+ any(target_arch = "arm", target_arch = "aarch64"),
+ any(target_feature = "aes", target_feature = "crypto"),
+ not(miri),
+ feature = "stdsimd"
+))]
#[allow(unused)]
#[inline(always)]
pub(crate) fn aesenc(value: u128, xor: u128) -> u128 {
- #[cfg(target_arch = "arm")]
- use core::arch::arm::*;
#[cfg(target_arch = "aarch64")]
use core::arch::aarch64::*;
+ #[cfg(target_arch = "arm")]
+ use core::arch::arm::*;
use core::mem::transmute;
unsafe {
let value = transmute(value);
@@ -131,14 +147,19 @@
}
}
-#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))]
+#[cfg(all(
+ any(target_arch = "arm", target_arch = "aarch64"),
+ any(target_feature = "aes", target_feature = "crypto"),
+ not(miri),
+ feature = "stdsimd"
+))]
#[allow(unused)]
#[inline(always)]
pub(crate) fn aesdec(value: u128, xor: u128) -> u128 {
- #[cfg(target_arch = "arm")]
- use core::arch::arm::*;
#[cfg(target_arch = "aarch64")]
use core::arch::aarch64::*;
+ #[cfg(target_arch = "arm")]
+ use core::arch::arm::*;
use core::mem::transmute;
unsafe {
let value = transmute(value);
@@ -146,6 +167,30 @@
}
}
+#[allow(unused)]
+#[inline(always)]
+pub(crate) fn add_in_length(enc: &mut u128, len: u64) {
+ #[cfg(all(target_arch = "x86_64", target_feature = "sse2", not(miri)))]
+ {
+ #[cfg(target_arch = "x86_64")]
+ use core::arch::x86_64::*;
+
+ unsafe {
+ let enc = enc as *mut u128;
+ let len = _mm_cvtsi64_si128(len as i64);
+ let data = _mm_loadu_si128(enc.cast());
+ let sum = _mm_add_epi64(data, len);
+ _mm_storeu_si128(enc.cast(), sum);
+ }
+ }
+ #[cfg(not(all(target_arch = "x86_64", target_feature = "sse2", not(miri))))]
+ {
+ let mut t: [u64; 2] = enc.convert();
+ t[0] = t[0].wrapping_add(len);
+ *enc = t.convert();
+ }
+}
+
#[cfg(test)]
mod test {
use super::*;
@@ -327,4 +372,12 @@
shuffled = shuffle(shuffled);
}
}
+
+ #[test]
+ fn test_add_length() {
+ let mut enc = (u64::MAX as u128) << 64 | 50;
+ add_in_length(&mut enc, u64::MAX);
+ assert_eq!(enc >> 64, u64::MAX as u128);
+ assert_eq!(enc as u64, 49);
+ }
}
diff --git a/src/random_state.rs b/src/random_state.rs
index 835467c..6bdd05f 100644
--- a/src/random_state.rs
+++ b/src/random_state.rs
@@ -1,72 +1,39 @@
-#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
-use crate::convert::Convert;
-#[cfg(feature = "specialize")]
-use crate::BuildHasherExt;
+use core::hash::Hash;
+cfg_if::cfg_if! {
+ if #[cfg(any(
+ all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
+ all(any(target_arch = "arm", target_arch = "aarch64"), any(target_feature = "aes", target_feature = "crypto"), not(miri), feature = "stdsimd")
+ ))] {
+ use crate::aes_hash::*;
+ } else {
+ use crate::fallback_hash::*;
+ }
+}
+cfg_if::cfg_if! {
+ if #[cfg(feature = "specialize")]{
+ use crate::BuildHasherExt;
+ }
+}
+cfg_if::cfg_if! {
+ if #[cfg(feature = "std")] {
+ extern crate std as alloc;
+ } else {
+ extern crate alloc;
+ }
+}
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-pub use crate::aes_hash::*;
+#[cfg(feature = "atomic-polyfill")]
+use atomic_polyfill as atomic;
+#[cfg(not(feature = "atomic-polyfill"))]
+use core::sync::atomic;
-#[cfg(not(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-pub use crate::fallback_hash::*;
-
-#[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
-use const_random::const_random;
+use alloc::boxed::Box;
+use atomic::{AtomicUsize, Ordering};
use core::any::{Any, TypeId};
use core::fmt;
use core::hash::BuildHasher;
-#[cfg(feature = "specialize")]
-use core::hash::Hash;
use core::hash::Hasher;
-#[cfg(not(feature = "std"))]
-extern crate alloc;
-#[cfg(feature = "std")]
-extern crate std as alloc;
-
-use alloc::boxed::Box;
-use core::sync::atomic::{AtomicUsize, Ordering};
-#[cfg(not(all(target_arch = "arm", target_os = "none")))]
-use once_cell::race::OnceBox;
-
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-use crate::aes_hash::*;
-#[cfg(not(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-use crate::fallback_hash::*;
-
-#[cfg(not(all(target_arch = "arm", target_os = "none")))]
-static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new();
-
-#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
-fn read_urandom(dest: &mut [u8]) -> Result<(), std::io::Error> {
- use std::fs::File;
- use std::io::Read;
-
- let mut f = File::open("/dev/urandom")?;
- f.read_exact(dest)
-}
-
-/// A supplier of Randomness used for different hashers.
-/// See [RandomState.set_random_source].
-pub trait RandomSource {
-
- fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2];
-
- fn gen_hasher_seed(&self) -> usize;
-
-}
-
pub(crate) const PI: [u64; 4] = [
0x243f_6a88_85a3_08d3,
0x1319_8a2e_0370_7344,
@@ -81,6 +48,101 @@
0x3f84_d5b5_b547_0917,
];
+#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
+fn read_urandom(dest: &mut [u8]) -> Result<(), std::io::Error> {
+ use std::fs::File;
+ use std::io::Read;
+
+ let mut f = File::open("/dev/urandom")?;
+ f.read_exact(dest)
+}
+
+cfg_if::cfg_if! {
+ if #[cfg(all(feature = "compile-time-rng", any(test, fuzzing)))] {
+ #[inline]
+ fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
+ use const_random::const_random;
+
+ const RAND: [[u64; 4]; 2] = [
+ [
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ ], [
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ ]
+ ];
+ &RAND
+ }
+ } else if #[cfg(all(feature = "runtime-rng", not(fuzzing)))] {
+ #[inline]
+ fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
+ use crate::convert::Convert;
+
+ static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new();
+
+ SEEDS.get_or_init(|| {
+ let mut result: [u8; 64] = [0; 64];
+ if read_urandom(&mut result).is_err() {
+ getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
+ }
+ Box::new(result.convert())
+ })
+ }
+ } else if #[cfg(feature = "compile-time-rng")] {
+ #[inline]
+ fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
+ use const_random::const_random;
+
+ const RAND: [[u64; 4]; 2] = [
+ [
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ ], [
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ const_random!(u64),
+ ]
+ ];
+ &RAND
+ }
+ } else {
+ #[inline]
+ fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
+ &[PI, PI2]
+ }
+ }
+}
+
+cfg_if::cfg_if! {
+ if #[cfg(not(all(target_arch = "arm", target_os = "none")))] {
+ use once_cell::race::OnceBox;
+
+ static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new();
+ }
+}
+/// A supplier of Randomness used for different hashers.
+/// See [set_random_source].
+///
+/// If [set_random_source] aHash will default to the best available source of randomness.
+/// In order this is:
+/// 1. OS provided random number generator (available if the `runtime-rng` flag is enabled which it is by default) - This should be very strong.
+/// 2. Strong compile time random numbers used to permute a static "counter". (available if `compile-time-rng` is enabled.
+/// __Enabling this is recommended if `runtime-rng` is not possible__)
+/// 3. A static counter that adds the memory address of each [RandomState] created permuted with fixed constants.
+/// (Similar to above but with fixed keys) - This is the weakest option. The strength of this heavily depends on whether or not ASLR is enabled.
+/// (Rust enables ASLR by default)
+pub trait RandomSource {
+ fn gen_hasher_seed(&self) -> usize;
+}
+
struct DefaultRandomSource {
counter: AtomicUsize,
}
@@ -92,6 +154,7 @@
}
}
+ #[cfg(all(target_arch = "arm", target_os = "none"))]
const fn default() -> DefaultRandomSource {
DefaultRandomSource {
counter: AtomicUsize::new(PI[3] as usize),
@@ -100,57 +163,50 @@
}
impl RandomSource for DefaultRandomSource {
-
- #[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
- fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
- static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new();
-
- SEEDS.get_or_init(|| {
- let mut result: [u8; 64] = [0; 64];
- if read_urandom(&mut result).is_err() {
- getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
+ cfg_if::cfg_if! {
+ if #[cfg(all(target_arch = "arm", target_os = "none"))] {
+ fn gen_hasher_seed(&self) -> usize {
+ let stack = self as *const _ as usize;
+ let previous = self.counter.load(Ordering::Relaxed);
+ let new = previous.wrapping_add(stack);
+ self.counter.store(new, Ordering::Relaxed);
+ new
}
- Box::new(result.convert())
- })
+ } else {
+ fn gen_hasher_seed(&self) -> usize {
+ let stack = self as *const _ as usize;
+ self.counter.fetch_add(stack, Ordering::Relaxed)
+ }
+ }
}
+}
- #[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
- fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
- const RAND: [[u64; 4]; 2] = [
- [
- const_random!(u64),
- const_random!(u64),
- const_random!(u64),
- const_random!(u64),
- ], [
- const_random!(u64),
- const_random!(u64),
- const_random!(u64),
- const_random!(u64),
- ]
- ];
- &RAND
- }
+cfg_if::cfg_if! {
+ if #[cfg(all(target_arch = "arm", target_os = "none"))] {
+ #[inline]
+ fn get_src() -> &'static dyn RandomSource {
+ static RAND_SOURCE: DefaultRandomSource = DefaultRandomSource::default();
+ &RAND_SOURCE
+ }
+ } else {
+ /// Provides an optional way to manually supply a source of randomness for Hasher keys.
+ ///
+ /// The provided [RandomSource] will be used to be used as a source of randomness by [RandomState] to generate new states.
+ /// If this method is not invoked the standard source of randomness is used as described in the Readme.
+ ///
+ /// The source of randomness can only be set once, and must be set before the first RandomState is created.
+ /// If the source has already been specified `Err` is returned with a `bool` indicating if the set failed because
+ /// method was previously invoked (true) or if the default source is already being used (false).
+ #[cfg(not(all(target_arch = "arm", target_os = "none")))]
+ pub fn set_random_source(source: impl RandomSource + Send + Sync + 'static) -> Result<(), bool> {
+ RAND_SOURCE.set(Box::new(Box::new(source))).map_err(|s| s.as_ref().type_id() != TypeId::of::<&DefaultRandomSource>())
+ }
- #[cfg(all(not(feature = "runtime-rng"), not(feature = "compile-time-rng")))]
- fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
- &[PI, PI2]
- }
-
- #[cfg(not(all(target_arch = "arm", target_os = "none")))]
- fn gen_hasher_seed(&self) -> usize {
- let stack = self as *const _ as usize;
- self.counter.fetch_add(stack, Ordering::Relaxed)
- }
-
- #[cfg(all(target_arch = "arm", target_os = "none"))]
- fn gen_hasher_seed(&self) -> usize {
- let stack = self as *const _ as usize;
- let previous = self.counter.load(Ordering::Relaxed);
- let new = previous.wrapping_add(stack);
- self.counter.store(new, Ordering::Relaxed);
- new
- }
+ #[inline]
+ fn get_src() -> &'static dyn RandomSource {
+ RAND_SOURCE.get_or_init(|| Box::new(Box::new(DefaultRandomSource::new()))).as_ref()
+ }
+ }
}
/// Provides a [Hasher] factory. This is typically used (e.g. by [HashMap]) to create
@@ -160,6 +216,16 @@
/// [Hasher]: std::hash::Hasher
/// [BuildHasher]: std::hash::BuildHasher
/// [HashMap]: std::collections::HashMap
+///
+/// There are multiple constructors each is documented in more detail below:
+///
+/// | Constructor | Dynamically random? | Seed |
+/// |---------------|---------------------|------|
+/// |`new` | Each instance unique|_[RandomSource]_|
+/// |`generate_with`| Each instance unique|`u64` x 4 + [RandomSource]|
+/// |`with_seed` | Fixed per process |`u64` + static random number|
+/// |`with_seeds` | Fixed |`u64` x 4|
+///
#[derive(Clone)]
pub struct RandomState {
pub(crate) k0: u64,
@@ -176,46 +242,30 @@
impl RandomState {
- /// Provides an optional way to manually supply a source of randomness for Hasher keys.
+ /// Create a new `RandomState` `BuildHasher` using random keys.
///
- /// The provided [RandomSource] will be used to be used as a source of randomness by [RandomState] to generate new states.
- /// If this method is not invoked the standard source of randomness is used as described in the Readme.
+ /// Each instance will have a unique set of keys derived from [RandomSource].
///
- /// The source of randomness can only be set once, and must be set before the first RandomState is created.
- /// If the source has already been specified `Err` is returned with a `bool` indicating if the set failed because
- /// method was previously invoked (true) or if the default source is already being used (false).
- #[cfg(not(all(target_arch = "arm", target_os = "none")))]
- pub fn set_random_source(source: impl RandomSource + Send + Sync + 'static) -> Result<(), bool> {
- RAND_SOURCE.set(Box::new(Box::new(source))).map_err(|s| s.as_ref().type_id() != TypeId::of::<&DefaultRandomSource>())
- }
-
- #[inline]
- #[cfg(not(all(target_arch = "arm", target_os = "none")))]
- fn get_src() -> &'static dyn RandomSource {
- RAND_SOURCE.get_or_init(|| Box::new(Box::new(DefaultRandomSource::new()))).as_ref()
- }
-
- #[inline]
- #[cfg(all(target_arch = "arm", target_os = "none"))]
- fn get_src() -> &'static dyn RandomSource {
- static RAND_SOURCE: DefaultRandomSource = DefaultRandomSource::default();
- &RAND_SOURCE
- }
-
- /// Use randomly generated keys
#[inline]
pub fn new() -> RandomState {
- let src = Self::get_src();
- let fixed = src.get_fixed_seeds();
+ let src = get_src();
+ let fixed = get_fixed_seeds();
Self::from_keys(&fixed[0], &fixed[1], src.gen_hasher_seed())
}
- /// Allows for supplying seeds, but each time it is called the resulting state will be different.
- /// This is done using a static counter, so it can safely be used with a fixed keys.
+ /// Create a new `RandomState` `BuildHasher` based on the provided seeds, but in such a way
+ /// that each time it is called the resulting state will be different and of high quality.
+ /// This allows fixed constant or poor quality seeds to be provided without the problem of different
+ /// `BuildHasher`s being identical or weak.
+ ///
+ /// This is done via permuting the provided values with the value of a static counter and memory address.
+ /// (This makes this method somewhat more expensive than `with_seeds` below which does not do this).
+ ///
+ /// The provided values (k0-k3) do not need to be of high quality but they should not all be the same value.
#[inline]
pub fn generate_with(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState {
- let src = Self::get_src();
- let fixed = src.get_fixed_seeds();
+ let src = get_src();
+ let fixed = get_fixed_seeds();
RandomState::from_keys(&fixed[0], &[k0, k1, k2, k3], src.gen_hasher_seed())
}
@@ -223,45 +273,117 @@
let &[k0, k1, k2, k3] = a;
let mut hasher = AHasher::from_random_state(&RandomState { k0, k1, k2, k3 });
hasher.write_usize(c);
- let mix = |k: u64| {
+ let mix = |l: u64, r: u64| {
let mut h = hasher.clone();
- h.write_u64(k);
+ h.write_u64(l);
+ h.write_u64(r);
h.finish()
};
RandomState {
- k0: mix(b[0]),
- k1: mix(b[1]),
- k2: mix(b[2]),
- k3: mix(b[3]),
+ k0: mix(b[0], b[2]),
+ k1: mix(b[1], b[3]),
+ k2: mix(b[2], b[1]),
+ k3: mix(b[3], b[0]),
}
}
/// Internal. Used by Default.
#[inline]
pub(crate) fn with_fixed_keys() -> RandomState {
- let [k0, k1, k2, k3] = Self::get_src().get_fixed_seeds()[0];
+ let [k0, k1, k2, k3] = get_fixed_seeds()[0];
RandomState { k0, k1, k2, k3 }
}
- /// Allows for explicitly setting a seed to used.
+ /// Build a `RandomState` from a single key. The provided key does not need to be of high quality,
+ /// but all `RandomState`s created from the same key will produce identical hashers.
+ /// (In contrast to `generate_with` above)
+ ///
+ /// This allows for explicitly setting the seed to be used.
///
/// Note: This method does not require the provided seed to be strong.
#[inline]
pub fn with_seed(key: usize) -> RandomState {
- let fixed = Self::get_src().get_fixed_seeds();
+ let fixed = get_fixed_seeds();
RandomState::from_keys(&fixed[0], &fixed[1], key)
}
/// Allows for explicitly setting the seeds to used.
+ /// All `RandomState`s created with the same set of keys key will produce identical hashers.
+ /// (In contrast to `generate_with` above)
///
- /// Note: This method is robust against 0s being passed for one or more of the parameters
- /// or the same value being passed for more than one parameter.
+ /// Note: If DOS resistance is desired one of these should be a decent quality random number.
+ /// If 4 high quality random number are not cheaply available this method is robust against 0s being passed for
+ /// one or more of the parameters or the same value being passed for more than one parameter.
+ /// It is recommended to pass numbers in order from highest to lowest quality (if there is any difference).
#[inline]
pub const fn with_seeds(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState {
- RandomState { k0: k0 ^ PI2[0], k1: k1 ^ PI2[1], k2: k2 ^ PI2[2], k3: k3 ^ PI2[3] }
+ RandomState {
+ k0: k0 ^ PI2[0],
+ k1: k1 ^ PI2[1],
+ k2: k2 ^ PI2[2],
+ k3: k3 ^ PI2[3],
+ }
+ }
+
+ /// Calculates the hash of a single value. This provides a more convenient (and faster) way to obtain a hash:
+ /// For example:
+ #[cfg_attr(
+ feature = "std",
+ doc = r##" # Examples
+```
+ use std::hash::BuildHasher;
+ use ahash::RandomState;
+
+ let hash_builder = RandomState::new();
+ let hash = hash_builder.hash_one("Some Data");
+```
+ "##
+ )]
+ /// This is similar to:
+ #[cfg_attr(
+ feature = "std",
+ doc = r##" # Examples
+```
+ use std::hash::{BuildHasher, Hash, Hasher};
+ use ahash::RandomState;
+
+ let hash_builder = RandomState::new();
+ let mut hasher = hash_builder.build_hasher();
+ "Some Data".hash(&mut hasher);
+ let hash = hasher.finish();
+```
+ "##
+ )]
+ /// (Note that these two ways to get a hash may not produce the same value for the same data)
+ ///
+ /// This is intended as a convenience for code which *consumes* hashes, such
+ /// as the implementation of a hash table or in unit tests that check
+ /// whether a custom [`Hash`] implementation behaves as expected.
+ ///
+ /// This must not be used in any code which *creates* hashes, such as in an
+ /// implementation of [`Hash`]. The way to create a combined hash of
+ /// multiple values is to call [`Hash::hash`] multiple times using the same
+ /// [`Hasher`], not to call this method repeatedly and combine the results.
+ #[inline]
+ pub fn hash_one<T: Hash>(&self, x: T) -> u64
+ where
+ Self: Sized,
+ {
+ use crate::specialize::CallHasher;
+ T::get_hash(&x, self)
}
}
+/// Creates an instance of RandomState using keys obtained from the random number generator.
+/// Each instance created in this way will have a unique set of keys. (But the resulting instance
+/// can be used to create many hashers each or which will have the same keys.)
+///
+/// This is the same as [RandomState::new()]
+///
+/// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or
+/// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of
+/// constructors for [RandomState] must be used.
+#[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))]
impl Default for RandomState {
#[inline]
fn default() -> Self {
@@ -277,26 +399,29 @@
/// [AHasher]s that will return different hashcodes, but [Hasher]s created from the same [BuildHasher]
/// will generate the same hashes for the same input data.
///
- /// # Examples
- ///
- /// ```
- /// use ahash::{AHasher, RandomState};
- /// use std::hash::{Hasher, BuildHasher};
- ///
- /// let build_hasher = RandomState::new();
- /// let mut hasher_1 = build_hasher.build_hasher();
- /// let mut hasher_2 = build_hasher.build_hasher();
- ///
- /// hasher_1.write_u32(1234);
- /// hasher_2.write_u32(1234);
- ///
- /// assert_eq!(hasher_1.finish(), hasher_2.finish());
- ///
- /// let other_build_hasher = RandomState::new();
- /// let mut different_hasher = other_build_hasher.build_hasher();
- /// different_hasher.write_u32(1234);
- /// assert_ne!(different_hasher.finish(), hasher_1.finish());
- /// ```
+ #[cfg_attr(
+ feature = "std",
+ doc = r##" # Examples
+```
+ use ahash::{AHasher, RandomState};
+ use std::hash::{Hasher, BuildHasher};
+
+ let build_hasher = RandomState::new();
+ let mut hasher_1 = build_hasher.build_hasher();
+ let mut hasher_2 = build_hasher.build_hasher();
+
+ hasher_1.write_u32(1234);
+ hasher_2.write_u32(1234);
+
+ assert_eq!(hasher_1.finish(), hasher_2.finish());
+
+ let other_build_hasher = RandomState::new();
+ let mut different_hasher = other_build_hasher.build_hasher();
+ different_hasher.write_u32(1234);
+ assert_ne!(different_hasher.finish(), hasher_1.finish());
+```
+ "##
+ )]
/// [Hasher]: std::hash::Hasher
/// [BuildHasher]: std::hash::BuildHasher
/// [HashMap]: std::collections::HashMap
@@ -304,6 +429,52 @@
fn build_hasher(&self) -> AHasher {
AHasher::from_random_state(self)
}
+
+
+ /// Calculates the hash of a single value. This provides a more convenient (and faster) way to obtain a hash:
+ /// For example:
+ #[cfg_attr(
+ feature = "std",
+ doc = r##" # Examples
+```
+ use std::hash::BuildHasher;
+ use ahash::RandomState;
+
+ let hash_builder = RandomState::new();
+ let hash = hash_builder.hash_one("Some Data");
+```
+ "##
+ )]
+ /// This is similar to:
+ #[cfg_attr(
+ feature = "std",
+ doc = r##" # Examples
+```
+ use std::hash::{BuildHasher, Hash, Hasher};
+ use ahash::RandomState;
+
+ let hash_builder = RandomState::new();
+ let mut hasher = hash_builder.build_hasher();
+ "Some Data".hash(&mut hasher);
+ let hash = hasher.finish();
+```
+ "##
+ )]
+ /// (Note that these two ways to get a hash may not produce the same value for the same data)
+ ///
+ /// This is intended as a convenience for code which *consumes* hashes, such
+ /// as the implementation of a hash table or in unit tests that check
+ /// whether a custom [`Hash`] implementation behaves as expected.
+ ///
+ /// This must not be used in any code which *creates* hashes, such as in an
+ /// implementation of [`Hash`]. The way to create a combined hash of
+ /// multiple values is to call [`Hash::hash`] multiple times using the same
+ /// [`Hasher`], not to call this method repeatedly and combine the results.
+ #[cfg(feature = "specialize")]
+ #[inline]
+ fn hash_one<T: Hash>(&self, x: T) -> u64 {
+ RandomState::hash_one(self, x)
+ }
}
#[cfg(feature = "specialize")]
@@ -339,27 +510,27 @@
#[test]
fn test_unique() {
- let a = RandomState::new();
- let b = RandomState::new();
+ let a = RandomState::generate_with(1, 2, 3, 4);
+ let b = RandomState::generate_with(1, 2, 3, 4);
assert_ne!(a.build_hasher().finish(), b.build_hasher().finish());
}
#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
#[test]
fn test_not_pi() {
- assert_ne!(PI, RandomState::get_src().get_fixed_seeds()[0]);
+ assert_ne!(PI, get_fixed_seeds()[0]);
}
#[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
#[test]
fn test_not_pi_const() {
- assert_ne!(PI, RandomState::get_src().get_fixed_seeds()[0]);
+ assert_ne!(PI, get_fixed_seeds()[0]);
}
#[cfg(all(not(feature = "runtime-rng"), not(feature = "compile-time-rng")))]
#[test]
fn test_pi() {
- assert_eq!(PI, RandomState::get_src().get_fixed_seeds()[0]);
+ assert_eq!(PI, get_fixed_seeds()[0]);
}
#[test]
diff --git a/src/specialize.rs b/src/specialize.rs
index d94a4ee..05d335b 100644
--- a/src/specialize.rs
+++ b/src/specialize.rs
@@ -17,28 +17,7 @@
/// Provides a way to get an optimized hasher for a given data type.
/// Rather than using a Hasher generically which can hash any value, this provides a way to get a specialized hash
/// for a specific type. So this may be faster for primitive types.
-/// # Example
-/// ```
-/// use std::hash::BuildHasher;
-/// use ahash::RandomState;
-/// use ahash::CallHasher;
-///
-/// let hash_builder = RandomState::new();
-/// //...
-/// let value: u32 = 17;
-/// let hash = u32::get_hash(&value, &hash_builder);
-/// ```
-/// Note that the type used to invoke `get_hash` must be the same a the type of value passed.
-/// For example get a hasher specialized on `[u8]` can invoke:
-/// ```
-/// /// use std::hash::BuildHasher;
-/// # use ahash::RandomState;
-/// # use ahash::CallHasher;
-/// # let hash_builder = RandomState::new();
-/// let bytes: [u8; 4] = [1, 2, 3, 4];
-/// let hash = <[u8]>::get_hash(&bytes, &hash_builder);
-/// ```
-pub trait CallHasher {
+pub(crate) trait CallHasher {
fn get_hash<H: Hash + ?Sized, B: BuildHasher>(value: &H, build_hasher: &B) -> u64;
}
diff --git a/tests/bench.rs b/tests/bench.rs
index 9e6dccc..5bc0fc9 100644
--- a/tests/bench.rs
+++ b/tests/bench.rs
@@ -1,39 +1,34 @@
-use ahash::{CallHasher, RandomState};
+#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
+
+use ahash::{AHasher, RandomState};
use criterion::*;
use fxhash::FxHasher;
+use rand::Rng;
use std::collections::hash_map::DefaultHasher;
-use std::hash::{Hash, Hasher};
+use std::hash::{BuildHasherDefault, Hash, Hasher};
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-fn aeshash<H: Hash>(b: &H) -> u64 {
- let build_hasher = RandomState::with_seeds(1, 2, 3, 4);
- H::get_hash(b, &build_hasher)
-}
-#[cfg(not(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-fn aeshash<H: Hash>(_b: &H) -> u64 {
- panic!("aes must be enabled")
-}
+// Needs to be in sync with `src/lib.rs`
+const AHASH_IMPL: &str = if cfg!(any(
+ all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "aes",
+ not(miri),
+ ),
+ all(
+ any(target_arch = "arm", target_arch = "aarch64"),
+ any(target_feature = "aes", target_feature = "crypto"),
+ not(miri),
+ feature = "stdsimd",
+ ),
+)) {
+ "aeshash"
+} else {
+ "fallbackhash"
+};
-#[cfg(not(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-)))]
-fn fallbackhash<H: Hash>(b: &H) -> u64 {
+fn ahash<H: Hash>(b: &H) -> u64 {
let build_hasher = RandomState::with_seeds(1, 2, 3, 4);
- H::get_hash(b, &build_hasher)
-}
-#[cfg(any(
- all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
- all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
-))]
-fn fallbackhash<H: Hash>(_b: &H) -> u64 {
- panic!("aes must be disabled")
+ build_hasher.hash_one(b)
}
fn fnvhash<H: Hash>(b: &H) -> u64 {
@@ -76,79 +71,128 @@
.collect()
}
-const U8_VALUE: u8 = 123;
-const U16_VALUE: u16 = 1234;
-const U32_VALUE: u32 = 12345678;
-const U64_VALUE: u64 = 1234567890123456;
-const U128_VALUE: u128 = 12345678901234567890123456789012;
+macro_rules! bench_inputs {
+ ($group:ident, $hash:ident) => {
+ // Number of iterations per batch should be high enough to hide timing overhead.
+ let size = BatchSize::NumIterations(2_000);
-fn bench_ahash(c: &mut Criterion) {
- let mut group = c.benchmark_group("aeshash");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(aeshash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(aeshash(s))));
+ let mut rng = rand::thread_rng();
+ $group.bench_function("u8", |b| b.iter_batched(|| rng.gen::<u8>(), |v| $hash(&v), size));
+ $group.bench_function("u16", |b| b.iter_batched(|| rng.gen::<u16>(), |v| $hash(&v), size));
+ $group.bench_function("u32", |b| b.iter_batched(|| rng.gen::<u32>(), |v| $hash(&v), size));
+ $group.bench_function("u64", |b| b.iter_batched(|| rng.gen::<u64>(), |v| $hash(&v), size));
+ $group.bench_function("u128", |b| b.iter_batched(|| rng.gen::<u128>(), |v| $hash(&v), size));
+ $group.bench_with_input("strings", &gen_strings(), |b, s| b.iter(|| $hash(black_box(s))));
+ };
}
-fn bench_fallback(c: &mut Criterion) {
- let mut group = c.benchmark_group("fallback");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fallbackhash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fallbackhash(s))));
+fn bench_ahash(c: &mut Criterion) {
+ let mut group = c.benchmark_group(AHASH_IMPL);
+ bench_inputs!(group, ahash);
}
fn bench_fx(c: &mut Criterion) {
let mut group = c.benchmark_group("fx");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fxhash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fxhash(s))));
+ bench_inputs!(group, fxhash);
}
fn bench_fnv(c: &mut Criterion) {
let mut group = c.benchmark_group("fnv");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(fnvhash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(fnvhash(s))));
+ bench_inputs!(group, fnvhash);
}
fn bench_sea(c: &mut Criterion) {
let mut group = c.benchmark_group("sea");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(seahash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(seahash(s))));
+ bench_inputs!(group, seahash);
}
fn bench_sip(c: &mut Criterion) {
let mut group = c.benchmark_group("sip");
- group.bench_with_input("u8", &U8_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
- group.bench_with_input("u16", &U16_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
- group.bench_with_input("u32", &U32_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
- group.bench_with_input("u64", &U64_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
- group.bench_with_input("u128", &U128_VALUE, |b, s| b.iter(|| black_box(siphash(s))));
- group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(siphash(s))));
+ bench_inputs!(group, siphash);
+}
+
+fn bench_map(c: &mut Criterion) {
+ #[cfg(feature = "std")]
+ {
+ let mut group = c.benchmark_group("map");
+ group.bench_function("aHash-alias", |b| {
+ b.iter(|| {
+ let hm: ahash::HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ group.bench_function("aHash-hashBrown", |b| {
+ b.iter(|| {
+ let hm: hashbrown::HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ group.bench_function("aHash-hashBrown-explicit", |b| {
+ b.iter(|| {
+ let hm: hashbrown::HashMap<i32, i32, RandomState> = (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ group.bench_function("aHash-wrapper", |b| {
+ b.iter(|| {
+ let hm: ahash::AHashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ group.bench_function("aHash-rand", |b| {
+ b.iter(|| {
+ let hm: std::collections::HashMap<i32, i32, RandomState> = (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ group.bench_function("aHash-default", |b| {
+ b.iter(|| {
+ let hm: std::collections::HashMap<i32, i32, BuildHasherDefault<AHasher>> =
+ (0..1_000_000).map(|i| (i, i)).collect();
+ let mut sum = 0;
+ for i in 0..1_000_000 {
+ if let Some(x) = hm.get(&i) {
+ sum += x;
+ }
+ }
+ })
+ });
+ }
}
criterion_main!(benches);
+
criterion_group!(
benches,
bench_ahash,
- bench_fallback,
bench_fx,
bench_fnv,
bench_sea,
- bench_sip
+ bench_sip,
+ bench_map
);
diff --git a/tests/map_tests.rs b/tests/map_tests.rs
index be617a2..8d798a0 100644
--- a/tests/map_tests.rs
+++ b/tests/map_tests.rs
@@ -1,10 +1,11 @@
+#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
+
use std::hash::{BuildHasher, Hash, Hasher};
+use ahash::RandomState;
use criterion::*;
use fxhash::FxHasher;
-use ahash::{AHasher, CallHasher, RandomState};
-
fn gen_word_pairs() -> Vec<String> {
let words: Vec<_> = r#"
a, ability, able, about, above, accept, according, account, across, act, action,
@@ -150,9 +151,18 @@
);
}
+#[cfg(feature = "specialize")]
#[allow(unused)] // False positive
fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
- H::get_hash(b, build_hasher)
+ build_hasher.hash_one(b)
+}
+
+#[cfg(not(feature = "specialize"))]
+#[allow(unused)] // False positive
+fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
+ let mut hasher = build_hasher.build_hasher();
+ b.hash(&mut hasher);
+ hasher.finish()
}
#[test]
@@ -169,10 +179,31 @@
check_for_collisions(&build_hasher, &sequence, 256);
}
+#[cfg(feature = "std")]
+#[test]
+fn test_ahash_alias_map_construction() {
+ let mut map = ahash::HashMap::default();
+ map.insert(1, "test");
+ use ahash::HashMapExt;
+ let mut map = ahash::HashMap::with_capacity(1234);
+ map.insert(1, "test");
+}
+
+#[cfg(feature = "std")]
+#[test]
+fn test_ahash_alias_set_construction() {
+ let mut set = ahash::HashSet::default();
+ set.insert(1);
+
+ use ahash::HashSetExt;
+ let mut set = ahash::HashSet::with_capacity(1235);
+ set.insert(1);
+}
+
fn ahash_vec<H: Hash>(b: &Vec<H>) -> u64 {
let mut total: u64 = 0;
for item in b {
- let mut hasher = AHasher::new_with_keys(1234, 5678);
+ let mut hasher = RandomState::with_seeds(12, 34, 56, 78).build_hasher();
item.hash(&mut hasher);
total = total.wrapping_add(hasher.finish());
}
diff --git a/tests/nopanic.rs b/tests/nopanic.rs
index d48ff55..56f754c 100644
--- a/tests/nopanic.rs
+++ b/tests/nopanic.rs
@@ -1,5 +1,5 @@
-use ahash::{AHasher, CallHasher, RandomState};
-use std::hash::BuildHasher;
+use ahash::{AHasher, RandomState};
+use std::hash::{BuildHasher, Hash, Hasher};
#[macro_use]
extern crate no_panic;
@@ -8,8 +8,8 @@
#[no_panic]
fn hash_test_final(num: i32, string: &str) -> (u64, u64) {
use core::hash::Hasher;
- let mut hasher1 = AHasher::new_with_keys(1, 2);
- let mut hasher2 = AHasher::new_with_keys(3, 4);
+ let mut hasher1 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
+ let mut hasher2 = RandomState::with_seeds(3, 4, 5, 6).build_hasher();
hasher1.write_i32(num);
hasher2.write(string.as_bytes());
(hasher1.finish(), hasher2.finish())
@@ -24,6 +24,17 @@
hasher: AHasher,
}
+impl SimpleBuildHasher {
+ fn hash_one<T: Hash>(&self, x: T) -> u64
+ where
+ Self: Sized,
+ {
+ let mut hasher = self.build_hasher();
+ x.hash(&mut hasher);
+ hasher.finish()
+ }
+}
+
impl BuildHasher for SimpleBuildHasher {
type Hasher = AHasher;
@@ -35,11 +46,11 @@
#[inline(never)]
#[no_panic]
fn hash_test_specialize(num: i32, string: &str) -> (u64, u64) {
- let hasher1 = AHasher::new_with_keys(1, 2);
- let hasher2 = AHasher::new_with_keys(1, 2);
+ let hasher1 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
+ let hasher2 = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
(
- i32::get_hash(&num, &SimpleBuildHasher { hasher: hasher1 }),
- <[u8]>::get_hash(string.as_bytes(), &SimpleBuildHasher { hasher: hasher2 }),
+ SimpleBuildHasher { hasher: hasher1 }.hash_one(num),
+ SimpleBuildHasher { hasher: hasher2 }.hash_one(string.as_bytes()),
)
}
@@ -53,10 +64,7 @@
fn hash_test_random(num: i32, string: &str) -> (u64, u64) {
let build_hasher1 = RandomState::with_seeds(1, 2, 3, 4);
let build_hasher2 = RandomState::with_seeds(1, 2, 3, 4);
- (
- i32::get_hash(&num, &build_hasher1),
- <[u8]>::get_hash(string.as_bytes(), &build_hasher2),
- )
+ (build_hasher1.hash_one(&num), build_hasher2.hash_one(string.as_bytes()))
}
#[inline(never)]
@@ -68,5 +76,6 @@
fn test_no_panic() {
hash_test_final_wrapper(2, "Foo");
hash_test_specialize_wrapper(2, "Bar");
- hash_test_random_wrapper(2, "Baz");
+ hash_test_random(2, "Baz");
+ hash_test_random_wrapper(2, "Bat");
}
