diff options
Diffstat (limited to 'third_party/rust/ahash')
| -rw-r--r-- | third_party/rust/ahash/.cargo-checksum.json | 2 | ||||
| -rw-r--r-- | third_party/rust/ahash/Cargo.toml | 74 | ||||
| -rw-r--r-- | third_party/rust/ahash/LICENSE-MIT | 2 | ||||
| -rw-r--r-- | third_party/rust/ahash/README.md | 19 | ||||
| -rw-r--r-- | third_party/rust/ahash/build.rs | 31 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/aes_hash.rs | 65 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/convert.rs | 11 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/fallback_hash.rs | 51 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/hash_map.rs | 150 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/hash_quality_test.rs | 95 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/hash_set.rs | 65 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/lib.rs | 243 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/operations.rs | 98 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/random_state.rs | 511 | ||||
| -rw-r--r-- | third_party/rust/ahash/src/specialize.rs | 23 | ||||
| -rw-r--r-- | third_party/rust/ahash/tests/bench.rs | 205 | ||||
| -rw-r--r-- | third_party/rust/ahash/tests/map_tests.rs | 115 | ||||
| -rw-r--r-- | third_party/rust/ahash/tests/nopanic.rs | 35 |
18 files changed, 1207 insertions, 588 deletions
diff --git a/third_party/rust/ahash/.cargo-checksum.json b/third_party/rust/ahash/.cargo-checksum.json index d2fa45cb86..f72f808ffc 100644 --- a/third_party/rust/ahash/.cargo-checksum.json +++ b/third_party/rust/ahash/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"a519809f46c9aad28d6c48748f330fe31e05029d234b6d1743522ec403441744","FAQ.md":"9eb41898523ee209a0a937f9bcb78afe45ad55ca0556f8a4d4063558098f6d1e","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ff8f68cb076caf8cefe7a6430d4ac086ce6af2ca8ce2c4e5a2004d4552ef52a2","README.md":"72185284f100e149998fe5301f70489e617cc4415b51cc77e967c63c6e970a67","build.rs":"f80cb1cdb731a63d16513f1f0b0871d9c077d2c6bf2312af40a202f9c0fefe49","rustfmt.toml":"e090969e99df9360705680cc0097cfaddae10c22dc2e01470592cf3b9787fd36","src/aes_hash.rs":"0b11ce066931396222d2bed7eff678fdd7c8351819485efb721f62a30551866b","src/convert.rs":"f0e78840046493d0679a9ec077c8164cf57cf30d5e852b11bfadfdd996d29bd1","src/fallback_hash.rs":"ec00691bd555c69f7446afe893b6631cb84207cb7b512260dec8ef488e1905f3","src/hash_map.rs":"ed0c79c41c2218ad9591a585670a2b9b983807c9725880b780138a44c126cbfd","src/hash_quality_test.rs":"61695e5cac46ea25021a9d04199fb00c513e0c0c9c0f67aca0c647b9d2f7dd5a","src/hash_set.rs":"dc3d33e290aad62457ab1f5e64d3e33eb79e28c9468bfc8686339f0bbd8b19aa","src/lib.rs":"9fec7d1d412e414231c9b929081b1daa7c3b788a9f91eedd79a55efdf5d0d291","src/operations.rs":"10772e65b8b7106f195428c5eb8dbf6cbd49dd5a2165ac750e54af5995210f88","src/random_state.rs":"ce9689147659efa975887debe1481daddca09386ea8e1d5b4ee90ebeda6c8745","src/specialize.rs":"38d3b56ef4f264d564f48dbcb8ac137928babf90635090c9771c1a62140d1f30","tests/bench.rs":"0851dffebaffd7a437f6f9946ed5e03a957e9a6eb0da7911451af58778c411ec","tests/map_tests.rs":"e0f155f964dd965740b072ee1da110a8c6ef34491c95219f7c89064112c7840f","tests/nopanic.rs":"3363675c4c1a197b86604a0aebbe958fb5ec7c01a414fbfd70e9eb8a29707400"},"package":"891477e0c6a8957309ee5c45a6368af3ae14bb510732d2684ffa19af310920f9"}
\ No newline at end of file +{"files":{"Cargo.toml":"ddcbd9309cebf3ffd26f87e09bb8f971793535955ebfd9a7196eba31a53471f8","FAQ.md":"9eb41898523ee209a0a937f9bcb78afe45ad55ca0556f8a4d4063558098f6d1e","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"0444c6991eead6822f7b9102e654448d51624431119546492e8b231db42c48bb","README.md":"d7f74d616a751bcca23d5d3b58a6daf556356a526c5f0b6aa0504715d176549a","build.rs":"23cbf4cf1b742e2c4da8bc58d06d1d021479dec80cec6a0bc3704c7172e2864a","rustfmt.toml":"e090969e99df9360705680cc0097cfaddae10c22dc2e01470592cf3b9787fd36","src/aes_hash.rs":"013602aec42150e59ba9ed6135525a624a4b42c1b1328b9857ec238aa12c3178","src/convert.rs":"54e49f93d51665366923d4d815cfd67790d3c769e84ab4386ba97f928d17d1bd","src/fallback_hash.rs":"a82451f6458a6e7a7e7da82a3c982e9bb825a2092ab79c41459d8011775fb0b1","src/hash_map.rs":"5ee97baa64fa528ba9c01bd018332c4974846c4813c6f8c30cee9f3546598f1c","src/hash_quality_test.rs":"1a560a181a804791bc6ad797df5352cdd87123fed7f19f659de0c2d883248bed","src/hash_set.rs":"360e55d066b44624f06e49efa140c03fda635fb17a59622cc29a83830bd1f263","src/lib.rs":"e2f4e7bfcf2807c73e3b8d3b1bd83c6789313b6b55edd59e15e04146e55e01b6","src/operations.rs":"38ed2b48a13d826c48ede5f304c9c2572c0c8f64ac8ac5a1ed4e112e536f3a97","src/random_state.rs":"03f40a654cfca2e00a2dabd21c85368ee50b8b6289efe98ea1745b25c721b9c6","src/specialize.rs":"56354db8a0f7e6ee1340a08f2ab6f79a0ff439fd61badac5e7e59fe4f4a653ba","tests/bench.rs":"7a425f564201560f9a8fb6c77f91f29bb88ec815b10bd27d15740c922a4f928e","tests/map_tests.rs":"e56b6f700e3b1176210e4b266d7a42b3263e966e5e565d53b1bc27af7a87168e","tests/nopanic.rs":"0d28a46248d77283941db1d9fd154c68b965c81a0e3db1fe4a43e06fc448da8f"},"package":"e89da841a80418a9b391ebaea17f5c112ffaaa96f621d2c285b5174da76b9011"}
\ No newline at end of file diff --git a/third_party/rust/ahash/Cargo.toml b/third_party/rust/ahash/Cargo.toml index 5830a500d9..279954f9a7 100644 --- a/third_party/rust/ahash/Cargo.toml +++ b/third_party/rust/ahash/Cargo.toml @@ -11,8 +11,9 @@ [package] edition = "2018" +rust-version = "1.60.0" name = "ahash" -version = "0.7.8" +version = "0.8.11" authors = ["Tom Kaitchuck <Tom.Kaitchuck@gmail.com>"] build = "./build.rs" exclude = [ @@ -84,8 +85,33 @@ 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.17" +optional = true + +[dependencies.getrandom] +version = "0.2.7" +optional = true + +[dependencies.serde] +version = "1.0.117" +optional = true + +[dependencies.zerocopy] +version = "0.7.31" +features = ["simd"] +default-features = false + [dev-dependencies.criterion] version = "0.3.2" +features = ["html_reports"] [dev-dependencies.fnv] version = "1.0.5" @@ -93,14 +119,20 @@ version = "1.0.5" [dev-dependencies.fxhash] version = "0.2.1" +[dev-dependencies.hashbrown] +version = "0.14.3" + [dev-dependencies.hex] version = "0.4.2" [dev-dependencies.no-panic] version = "0.1.10" +[dev-dependencies.pcg-mwc] +version = "0.2.1" + [dev-dependencies.rand] -version = "0.7.3" +version = "0.8.5" [dev-dependencies.seahash] version = "4.0" @@ -108,8 +140,11 @@ version = "4.0" [dev-dependencies.serde_json] version = "1.0.59" +[dev-dependencies.smallvec] +version = "1.13.1" + [build-dependencies.version_check] -version = "0.9" +version = "0.9.4" [features] atomic-polyfill = [ @@ -117,33 +152,16 @@ atomic-polyfill = [ "once_cell/atomic-polyfill", ] compile-time-rng = ["const-random"] -default = ["std"] +default = [ + "std", + "runtime-rng", +] +nightly-arm-aes = [] +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.13.1" +version = "1.18.0" features = ["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.atomic-polyfill] -version = "1.0.1" -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 - -[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/third_party/rust/ahash/LICENSE-MIT b/third_party/rust/ahash/LICENSE-MIT index 5afc2a7b0a..cba20106dd 100644 --- a/third_party/rust/ahash/LICENSE-MIT +++ b/third_party/rust/ahash/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/third_party/rust/ahash/README.md b/third_party/rust/ahash/README.md index be365a79f1..aa071cf51d 100644 --- a/third_party/rust/ahash/README.md +++ b/third_party/rust/ahash/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,17 @@ map.insert(56, 78); 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. +* `nightly-arm-aes`: To use AES instructions on 32-bit ARM, which requires nightly. This is not needed on AArch64. 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/third_party/rust/ahash/build.rs b/third_party/rust/ahash/build.rs index 6aba02526b..a136b3666c 100644 --- a/third_party/rust/ahash/build.rs +++ b/third_party/rust/ahash/build.rs @@ -4,34 +4,8 @@ use std::env; 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\""); - if version_check::Version::read().map_or(false, |v| v.at_most("1.77.9")) { - println!("cargo:rustc-cfg=feature=\"stdsimd\""); - } - } - } - 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("specialize") { + println!("cargo:rustc-cfg=feature=\"specialize\""); } let arch = env::var("CARGO_CFG_TARGET_ARCH").expect("CARGO_CFG_TARGET_ARCH was not set"); if arch.eq_ignore_ascii_case("x86_64") @@ -43,5 +17,4 @@ fn main() { { println!("cargo:rustc-cfg=feature=\"folded_multiply\""); } - } diff --git a/third_party/rust/ahash/src/aes_hash.rs b/third_party/rust/ahash/src/aes_hash.rs index 7e619b520b..daf3ae4fad 100644 --- a/third_party/rust/ahash/src/aes_hash.rs +++ b/third_party/rust/ahash/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 @@ impl AHasher { /// 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 @@ impl AHasher { } } - #[inline] pub(crate) fn from_random_state(rand_state: &RandomState) -> Self { let key1 = [rand_state.k0, rand_state.k1].convert(); @@ -83,32 +80,24 @@ impl AHasher { } #[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.enc = aesdec(self.enc, new_value); self.sum = shuffle_and_add(self.sum, new_value); } #[inline(always)] fn hash_in_2(&mut self, v1: u128, v2: u128) { - self.enc = aesenc(self.enc, v1); + self.enc = aesdec(self.enc, v1); self.sum = shuffle_and_add(self.sum, v1); - self.enc = aesenc(self.enc, v2); + self.enc = aesdec(self.enc, v2); self.sum = shuffle_and_add(self.sum, v2); } #[inline] #[cfg(feature = "specialize")] fn short_finish(&self) -> u64 { - let combined = aesdec(self.sum, self.enc); - let result: [u64; 2] = aesenc(combined, combined).convert(); + let combined = aesenc(self.sum, self.enc); + let result: [u64; 2] = aesdec(combined, combined).convert(); result[0] } } @@ -138,7 +127,11 @@ impl Hasher for AHasher { } #[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 @@ impl Hasher for AHasher { 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); @@ -180,10 +174,10 @@ impl Hasher for AHasher { sum[1] = shuffle_and_add(sum[1], tail[3]); while data.len() > 64 { let (blocks, rest) = data.read_u128x4(); - current[0] = aesenc(current[0], blocks[0]); - current[1] = aesenc(current[1], blocks[1]); - current[2] = aesenc(current[2], blocks[2]); - current[3] = aesenc(current[3], blocks[3]); + current[0] = aesdec(current[0], blocks[0]); + current[1] = aesdec(current[1], blocks[1]); + current[2] = aesdec(current[2], blocks[2]); + current[3] = aesdec(current[3], blocks[3]); sum[0] = shuffle_and_add(sum[0], blocks[0]); sum[1] = shuffle_and_add(sum[1], blocks[1]); sum[0] = shuffle_and_add(sum[0], blocks[2]); @@ -214,9 +208,9 @@ impl Hasher for AHasher { } #[inline] fn finish(&self) -> u64 { - let combined = aesdec(self.sum, self.enc); - let result: [u64; 2] = aesenc(aesenc(combined, self.key), combined).convert(); - result[1] + let combined = aesenc(self.sum, self.enc); + let result: [u64; 2] = aesdec(aesdec(combined, self.key), combined).convert(); + result[0] } } @@ -231,8 +225,7 @@ pub(crate) struct AHasherU64 { impl Hasher for AHasherU64 { #[inline] fn finish(&self) -> u64 { - let rot = (self.pad & 63) as u32; - self.buffer.rotate_left(rot) + folded_multiply(self.buffer, self.pad) } #[inline] @@ -327,7 +320,7 @@ pub(crate) struct AHasherStr(pub AHasher); 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] } @@ -335,14 +328,15 @@ impl Hasher for AHasherStr { fn write(&mut self, bytes: &[u8]) { if bytes.len() > 8 { self.0.write(bytes); - self.0.enc = aesdec(self.0.sum, self.0.enc); - self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc); + self.0.enc = aesenc(self.0.sum, self.0.enc); + self.0.enc = aesdec(aesdec(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); - self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc); + self.0.enc = aesenc(self.0.sum, self.0.enc); + self.0.enc = aesdec(aesdec(self.0.enc, self.0.key), self.0.enc); } } @@ -437,4 +431,3 @@ mod tests { assert_eq!(bytes, 0x6464646464646464); } } - diff --git a/third_party/rust/ahash/src/convert.rs b/third_party/rust/ahash/src/convert.rs index 4c0a00eb7c..712eae163b 100644 --- a/third_party/rust/ahash/src/convert.rs +++ b/third_party/rust/ahash/src/convert.rs @@ -7,17 +7,13 @@ macro_rules! convert { impl Convert<$b> for $a { #[inline(always)] fn convert(self) -> $b { - unsafe { - core::mem::transmute::<$a, $b>(self) - } + zerocopy::transmute!(self) } } impl Convert<$a> for $b { #[inline(always)] fn convert(self) -> $a { - unsafe { - core::mem::transmute::<$b, $a>(self) - } + zerocopy::transmute!(self) } } }; @@ -69,8 +65,7 @@ macro_rules! as_array { { #[inline(always)] fn as_array<T>(slice: &[T]) -> &[T; $len] { - assert_eq!(slice.len(), $len); - unsafe { &*(slice.as_ptr() as *const [_; $len]) } + core::convert::TryFrom::try_from(slice).unwrap() } as_array($input) } diff --git a/third_party/rust/ahash/src/fallback_hash.rs b/third_party/rust/ahash/src/fallback_hash.rs index aad9efc859..bc5cbfeeec 100644 --- a/third_party/rust/ahash/src/fallback_hash.rs +++ b/third_party/rust/ahash/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 @@ impl AHasher { /// 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(); @@ -57,8 +56,8 @@ impl AHasher { #[allow(dead_code)] // Is not called if non-fallback hash is used. pub(crate) fn from_random_state(rand_state: &RandomState) -> AHasher { AHasher { - buffer: rand_state.k0, - pad: rand_state.k1, + buffer: rand_state.k1, + pad: rand_state.k0, extra_keys: [rand_state.k2, rand_state.k3], } } @@ -93,19 +92,10 @@ impl AHasher { /// 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,25 +108,16 @@ impl AHasher { /// 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 { - self.buffer.wrapping_add(self.pad) + folded_multiply(self.buffer, self.pad) } } @@ -170,7 +151,11 @@ impl Hasher for AHasher { } #[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 @@ impl Hasher for AHasher { } #[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")] @@ -233,8 +210,8 @@ pub(crate) struct AHasherU64 { impl Hasher for AHasherU64 { #[inline] fn finish(&self) -> u64 { - let rot = (self.pad & 63) as u32; - self.buffer.rotate_left(rot) + folded_multiply(self.buffer, self.pad) + //self.buffer } #[inline] @@ -338,8 +315,7 @@ impl Hasher for AHasherStr { 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); } } @@ -365,7 +341,6 @@ impl Hasher for AHasherStr { #[cfg(test)] mod tests { - use crate::convert::Convert; use crate::fallback_hash::*; #[test] diff --git a/third_party/rust/ahash/src/hash_map.rs b/third_party/rust/ahash/src/hash_map.rs index ec8fa433bb..2b6fbdc89f 100644 --- a/third_party/rust/ahash/src/hash_map.rs +++ b/third_party/rust/ahash/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> From<HashMap<K, V, crate::RandomState>> for AHashMap<K, V> { } } +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> Into<HashMap<K, V, crate::RandomState>> for AHashMap<K, V> { } 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 @@ where /// 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 @@ where 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 @@ where } } -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 @@ where } } +/// 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 @@ where 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 @@ mod test { 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/third_party/rust/ahash/src/hash_quality_test.rs b/third_party/rust/ahash/src/hash_quality_test.rs index 17228d4716..f2fab16013 100644 --- a/third_party/rust/ahash/src/hash_quality_test.rs +++ b/third_party/rust/ahash/src/hash_quality_test.rs @@ -1,5 +1,5 @@ use core::hash::{Hash, Hasher}; -use std::collections::{HashMap}; +use std::collections::HashMap; fn assert_sufficiently_different(a: u64, b: u64, tolerance: i32) { let (same_byte_count, same_nibble_count) = count_same_bytes_and_nibbles(a, b); @@ -50,7 +50,7 @@ fn count_same_bytes_and_nibbles(a: u64, b: u64) -> (i32, i32) { (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,19 +63,15 @@ fn gen_combinations(options: &[u32; 8], depth: u32, so_far: Vec<u32>, combinatio } 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); let mut map: HashMap<u64, Vec<u8>> = HashMap::new(); for combination in combinations { - let array = unsafe { - let (begin, middle, end) = combination.align_to::<u8>(); - assert_eq!(0, begin.len()); - assert_eq!(0, end.len()); - middle.to_vec() - }; + use zerocopy::AsBytes; + let array = combination.as_slice().as_bytes().to_vec(); let mut hasher = gen_hash(); hasher.write(&array); let hash = hasher.finish(); @@ -89,7 +85,7 @@ fn test_no_full_collisions<T: Hasher>(gen_hash: impl Fn() -> T) { 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) { @@ -112,13 +108,13 @@ fn test_keys_change_output<T: Hasher>(constructor: impl Fn(u128, u128) -> T) { fn test_input_affect_every_byte<T: Hasher>(constructor: impl Fn(u128, u128) -> T) { let base = hash_with(&0, constructor(0, 0)); for shift in 0..16 { - let mut alternitives = vec![]; + let mut alternatives = vec![]; for v in 0..256 { let input = (v as u128) << (shift * 8); let hasher = constructor(0, 0); - alternitives.push(hash_with(&input, hasher)); + alternatives.push(hash_with(&input, hasher)); } - assert_each_byte_differs(shift, base, alternitives); + assert_each_byte_differs(shift, base, alternatives); } } @@ -126,28 +122,35 @@ fn test_input_affect_every_byte<T: Hasher>(constructor: impl Fn(u128, u128) -> T fn test_keys_affect_every_byte<H: Hash, T: Hasher>(item: H, constructor: impl Fn(u128, u128) -> T) { let base = hash_with(&item, constructor(0, 0)); for shift in 0..16 { - let mut alternitives1 = vec![]; - let mut alternitives2 = vec![]; + let mut alternatives1 = vec![]; + let mut alternatives2 = vec![]; for v in 0..256 { let input = (v as u128) << (shift * 8); let hasher1 = constructor(input, 0); let hasher2 = constructor(0, input); let h1 = hash_with(&item, hasher1); let h2 = hash_with(&item, hasher2); - alternitives1.push(h1); - alternitives2.push(h2); + alternatives1.push(h1); + alternatives2.push(h2); } - assert_each_byte_differs(shift, base, alternitives1); - assert_each_byte_differs(shift, base, alternitives2); + assert_each_byte_differs(shift, base, alternatives1); + assert_each_byte_differs(shift, base, alternatives2); } } -fn assert_each_byte_differs(num: u64, base: u64, alternitives: Vec<u64>) { +fn assert_each_byte_differs(num: u64, base: u64, alternatives: Vec<u64>) { let mut changed_bits = 0_u64; - for alternitive in alternitives { - changed_bits |= base ^ alternitive - } - assert_eq!(core::u64::MAX, changed_bits, "Bits changed: {:x} on num: {:?}", changed_bits, num); + for alternative in alternatives { + changed_bits |= base ^ alternative + } + 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 +276,19 @@ fn test_padding_doesnot_collide<T: Hasher>(hasher: impl Fn() -> T) { 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); @@ -327,19 +338,24 @@ fn test_length_extension<T: Hasher>(hasher: impl Fn(u128, u128) -> T) { } fn test_sparse<T: Hasher>(hasher: impl Fn() -> T) { + use smallvec::SmallVec; + let mut buf = [0u8; 256]; let mut hashes = HashMap::new(); - for idx_1 in 0..256 { - for idx_2 in idx_1+1..256 { + for idx_1 in 0..255_u8 { + for idx_2 in idx_1 + 1..=255_u8 { for value_1 in [1, 2, 4, 8, 16, 32, 64, 128] { - for value_2 in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 20, 24, 31, 32, 33, 48, 64, 96, 127, 128, 129, 192, 254, 255] { - buf[idx_1] = value_1; - buf[idx_2] = value_2; + for value_2 in [ + 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 17, 18, 20, 24, 31, 32, 33, 48, 64, 96, 127, 128, 129, + 192, 254, 255, + ] { + buf[idx_1 as usize] = value_1; + buf[idx_2 as usize] = value_2; let hash_value = hash_with(&buf, &mut hasher()); - let keys = hashes.entry(hash_value).or_insert(Vec::new()); - keys.push((idx_1, value_1, idx_2, value_2)); - buf[idx_1] = 0; - buf[idx_2] = 0; + let keys = hashes.entry(hash_value).or_insert(SmallVec::<[[u8; 4]; 1]>::new()); + keys.push([idx_1, value_1, idx_2, value_2]); + buf[idx_1 as usize] = 0; + buf[idx_2 as usize] = 0; } } } @@ -392,7 +408,7 @@ mod fallback_tests { 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)); } @@ -425,7 +441,8 @@ mod fallback_tests { ///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(target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), ))] #[cfg(test)] mod aes_tests { @@ -488,7 +505,7 @@ mod aes_tests { #[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/third_party/rust/ahash/src/hash_set.rs b/third_party/rust/ahash/src/hash_set.rs index 9766b676ff..d03bef580f 100644 --- a/third_party/rust/ahash/src/hash_set.rs +++ b/third_party/rust/ahash/src/hash_set.rs @@ -14,27 +14,49 @@ use serde::{ /// 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 @@ where } } -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 @@ where } } +/// 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 @@ where 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 @@ mod test { 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/third_party/rust/ahash/src/lib.rs b/third_party/rust/ahash/src/lib.rs index 9964a7c47b..69fb2ca237 100644 --- a/third_party/rust/ahash/src/lib.rs +++ b/third_party/rust/ahash/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. -//! -//! # Example -//! ``` -//! use ahash::{AHasher, RandomState}; -//! use std::collections::HashMap; +//! 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. //! -//! 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 convenience `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 = "stdsimd", feature(stdsimd))] +#![cfg_attr(feature = "nightly-arm-aes", feature(stdarch_arm_neon_intrinsics))] #[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(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), + ))] { + 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,9 +316,21 @@ impl<B: BuildHasher> BuildHasherExt for B { #[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() { @@ -219,7 +353,6 @@ mod test { assert_eq!(bytes, 0x6464646464646464); } - #[test] fn test_non_zero() { let mut hasher1 = AHasher::new_with_keys(0, 0); @@ -241,7 +374,7 @@ mod test { #[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/third_party/rust/ahash/src/operations.rs b/third_party/rust/ahash/src/operations.rs index b71fd5a743..8395007535 100644 --- a/third_party/rust/ahash/src/operations.rs +++ b/third_party/rust/ahash/src/operations.rs @@ -1,4 +1,9 @@ use crate::convert::*; +#[allow(unused)] +use zerocopy::transmute; + +///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) @@ -8,11 +13,19 @@ const SHUFFLE_MASK: u128 = 0x020a0700_0c01030e_050f0d08_06090b04_u128; //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) @@ -44,8 +57,7 @@ pub(crate) fn shuffle(a: u128) -> u128 { use core::arch::x86::*; #[cfg(target_arch = "x86_64")] use core::arch::x86_64::*; - use core::mem::transmute; - unsafe { transmute(_mm_shuffle_epi8(transmute(a), transmute(SHUFFLE_MASK))) } + unsafe { transmute!(_mm_shuffle_epi8(transmute!(a), transmute!(SHUFFLE_MASK))) } } #[cfg(not(all(target_feature = "ssse3", not(miri))))] { @@ -60,7 +72,7 @@ pub(crate) fn add_and_shuffle(a: u128, b: u128) -> u128 { 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(); @@ -70,13 +82,12 @@ pub(crate) fn shuffle_and_add(base: u128, to_add: u128) -> u128 { #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "sse2", not(miri)))] #[inline(always)] pub(crate) fn add_by_64s(a: [u64; 2], b: [u64; 2]) -> [u64; 2] { - use core::mem::transmute; unsafe { #[cfg(target_arch = "x86")] use core::arch::x86::*; #[cfg(target_arch = "x86_64")] use core::arch::x86_64::*; - transmute(_mm_add_epi64(transmute(a), transmute(b))) + transmute!(_mm_add_epi64(transmute!(a), transmute!(b))) } } @@ -94,26 +105,26 @@ pub(crate) fn aesenc(value: u128, xor: u128) -> u128 { use core::arch::x86::*; #[cfg(target_arch = "x86_64")] use core::arch::x86_64::*; - use core::mem::transmute; unsafe { - let value = transmute(value); - transmute(_mm_aesenc_si128(value, transmute(xor))) + let value = transmute!(value); + transmute!(_mm_aesenc_si128(value, transmute!(xor))) } } -#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))] +#[cfg(any( + all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), +))] #[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::*; - use core::mem::transmute; - unsafe { - let value = transmute(value); - transmute(vaesmcq_u8(vaeseq_u8(value, transmute(xor)))) - } + #[cfg(target_arch = "arm")] + use core::arch::arm::*; + let res = unsafe { vaesmcq_u8(vaeseq_u8(transmute!(value), transmute!(0u128))) }; + let value: u128 = transmute!(res); + xor ^ value } #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)))] @@ -124,32 +135,55 @@ pub(crate) fn aesdec(value: u128, xor: u128) -> u128 { use core::arch::x86::*; #[cfg(target_arch = "x86_64")] use core::arch::x86_64::*; - use core::mem::transmute; unsafe { - let value = transmute(value); - transmute(_mm_aesdec_si128(value, transmute(xor))) + let value = transmute!(value); + transmute!(_mm_aesdec_si128(value, transmute!(xor))) } } -#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))] +#[cfg(any( + all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), +))] #[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::*; - use core::mem::transmute; - unsafe { - let value = transmute(value); - transmute(vaesimcq_u8(vaesdq_u8(value, transmute(xor)))) + #[cfg(target_arch = "arm")] + use core::arch::arm::*; + let res = unsafe { vaesimcq_u8(vaesdq_u8(transmute!(value), transmute!(0u128))) }; + let value: u128 = transmute!(res); + xor ^ value +} + +#[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::*; - use crate::convert::Convert; // This is code to search for the shuffle constant // @@ -162,7 +196,7 @@ mod test { // #[cfg(target_arch = "x86_64")] // use core::arch::x86_64::*; // MASK.with(|mask| { - // unsafe { transmute(_mm_shuffle_epi8(transmute(a), transmute(mask.get()))) } + // unsafe { transmute!(_mm_shuffle_epi8(transmute!(a), transmute!(mask.get()))) } // }) // } // @@ -327,4 +361,12 @@ mod test { 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/third_party/rust/ahash/src/random_state.rs b/third_party/rust/ahash/src/random_state.rs index 9ac2f3ec43..46a39ab068 100644 --- a/third_party/rust/ahash/src/random_state.rs +++ b/third_party/rust/ahash/src/random_state.rs @@ -1,33 +1,27 @@ -#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))] -use crate::convert::Convert; -#[cfg(feature = "specialize")] -use crate::BuildHasherExt; - -#[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(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 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; +cfg_if::cfg_if! { + if #[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)), + ))] { + 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(feature = "atomic-polyfill")] use atomic_polyfill as atomic; @@ -36,32 +30,10 @@ use core::sync::atomic; use alloc::boxed::Box; use 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(); - -/// 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; - -} +use core::any::{Any, TypeId}; +use core::fmt; +use core::hash::BuildHasher; +use core::hash::Hasher; pub(crate) const PI: [u64; 4] = [ 0x243f_6a88_85a3_08d3, @@ -77,6 +49,90 @@ pub(crate) const PI2: [u64; 4] = [ 0x3f84_d5b5_b547_0917, ]; +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]; + 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, } @@ -88,6 +144,7 @@ impl DefaultRandomSource { } } + #[cfg(all(target_arch = "arm", target_os = "none"))] const fn default() -> DefaultRandomSource { DefaultRandomSource { counter: AtomicUsize::new(PI[3] as usize), @@ -96,55 +153,50 @@ impl DefaultRandomSource { } 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]; - getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed."); - Box::new(result.convert()) - }) - } - - #[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(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_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 + } + } else { + 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 - } +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>()) + } + + #[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 @@ -154,6 +206,16 @@ impl RandomSource for DefaultRandomSource { /// [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, @@ -169,47 +231,30 @@ impl fmt::Debug for RandomState { } 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()) } @@ -217,45 +262,117 @@ impl RandomState { 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 { @@ -271,26 +388,29 @@ impl BuildHasher for RandomState { /// [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 @@ -298,6 +418,51 @@ impl BuildHasher for RandomState { 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")] @@ -305,8 +470,8 @@ impl BuildHasherExt for RandomState { #[inline] fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { let mut hasher = AHasherU64 { - buffer: self.k0, - pad: self.k1, + buffer: self.k1, + pad: self.k0, }; value.hash(&mut hasher); hasher.finish() @@ -333,27 +498,27 @@ mod test { #[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/third_party/rust/ahash/src/specialize.rs b/third_party/rust/ahash/src/specialize.rs index d94a4eed0d..05d335b191 100644 --- a/third_party/rust/ahash/src/specialize.rs +++ b/third_party/rust/ahash/src/specialize.rs @@ -17,28 +17,7 @@ use alloc::vec::Vec; /// 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/third_party/rust/ahash/tests/bench.rs b/third_party/rust/ahash/tests/bench.rs index 9e6dccc481..2d000c0a6a 100644 --- a/third_party/rust/ahash/tests/bench.rs +++ b/third_party/rust/ahash/tests/bench.rs @@ -1,39 +1,35 @@ -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}; - -#[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 { +use std::hash::{BuildHasherDefault, Hash, Hasher}; + +// 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(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)), + all( + feature = "nightly-arm-aes", + target_arch = "arm", + target_feature = "aes", + not(miri) + ), +)) { + "aeshash" +} else { + "fallbackhash" +}; + +fn ahash<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") -} - -#[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 { - 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 +72,128 @@ fn gen_strings() -> Vec<String> { .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; - -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)))); +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(50_000); + + 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/third_party/rust/ahash/tests/map_tests.rs b/third_party/rust/ahash/tests/map_tests.rs index be617a2e72..97fdbee0f9 100644 --- a/third_party/rust/ahash/tests/map_tests.rs +++ b/third_party/rust/ahash/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 @@ fn check_for_collisions<H: Hash, B: BuildHasher>(build_hasher: &B, items: &[H], ); } +#[cfg(feature = "specialize")] +#[allow(unused)] // False positive +fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 { + 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 { - H::get_hash(b, build_hasher) + let mut hasher = build_hasher.build_hasher(); + b.hash(&mut hasher); + hasher.finish() } #[test] @@ -169,10 +179,107 @@ fn test_bucket_distribution() { 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); +} + + +#[cfg(feature = "std")] +#[test] +fn test_key_ref() { + let mut map = ahash::HashMap::default(); + map.insert(1, "test"); + assert_eq!(Some((1, "test")), map.remove_entry(&1)); + + let mut map = ahash::HashMap::default(); + map.insert(&1, "test"); + assert_eq!(Some((&1, "test")), map.remove_entry(&&1)); + + let mut m = ahash::HashSet::<Box<String>>::default(); + m.insert(Box::from("hello".to_string())); + assert!(m.contains(&"hello".to_string())); + + let mut m = ahash::HashSet::<String>::default(); + m.insert("hello".to_string()); + assert!(m.contains("hello")); + + let mut m = ahash::HashSet::<Box<[u8]>>::default(); + m.insert(Box::from(&b"hello"[..])); + assert!(m.contains(&b"hello"[..])); +} + +#[cfg(feature = "std")] +#[test] +fn test_byte_dist() { + use rand::{SeedableRng, Rng, RngCore}; + use pcg_mwc::Mwc256XXA64; + + let mut r = Mwc256XXA64::seed_from_u64(0xe786_c22b_119c_1479); + let mut lowest = 2.541; + let mut highest = 2.541; + for _round in 0..100 { + let mut table: [bool; 256 * 8] = [false; 256 * 8]; + let hasher = RandomState::with_seeds(r.gen(), r.gen(), r.gen(), r.gen()); + for i in 0..128 { + let mut keys: [u8; 8] = hasher.hash_one((i as u64) << 30).to_ne_bytes(); + //let mut keys = r.next_u64().to_ne_bytes(); //This is a control to test assert sensitivity. + for idx in 0..8 { + while table[idx * 256 + keys[idx] as usize] { + keys[idx] = keys[idx].wrapping_add(1); + } + table[idx * 256 + keys[idx] as usize] = true; + } + } + + for idx in 0..8 { + let mut len = 0; + let mut total_len = 0; + let mut num_seq = 0; + for i in 0..256 { + if table[idx * 256 + i] { + len += 1; + } else if len != 0 { + num_seq += 1; + total_len += len; + len = 0; + } + } + let mean = total_len as f32 / num_seq as f32; + println!("Mean sequence length = {}", mean); + if mean > highest { + highest = mean; + } + if mean < lowest { + lowest = mean; + } + } + } + assert!(lowest > 1.9, "Lowest = {}", lowest); + assert!(highest < 3.9, "Highest = {}", highest); +} + + 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/third_party/rust/ahash/tests/nopanic.rs b/third_party/rust/ahash/tests/nopanic.rs index d48ff559d2..56f754cbee 100644 --- a/third_party/rust/ahash/tests/nopanic.rs +++ b/third_party/rust/ahash/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 @@ extern crate no_panic; #[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 @@ struct SimpleBuildHasher { 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 @@ impl BuildHasher for SimpleBuildHasher { #[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_wrapper(num: i32, string: &str) { 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 hash_test_specialize_wrapper(num: i32, string: &str) { 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"); } |