From 218caa410aa38c29984be31a5229b9fa717560ee Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:13 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- vendor/ahash/.cargo-checksum.json | 2 +- vendor/ahash/Cargo.toml | 105 ++++--- vendor/ahash/LICENSE-MIT | 2 +- vendor/ahash/README.md | 16 +- vendor/ahash/build.rs | 30 +- vendor/ahash/src/aes_hash.rs | 30 +- vendor/ahash/src/convert.rs | 8 +- vendor/ahash/src/fallback_hash.rs | 40 +-- vendor/ahash/src/hash_map.rs | 151 +++++++++- vendor/ahash/src/hash_quality_test.rs | 31 ++- vendor/ahash/src/hash_set.rs | 66 ++++- vendor/ahash/src/lib.rs | 240 ++++++++++++---- vendor/ahash/src/operations.rs | 67 ++++- vendor/ahash/src/random_state.rs | 510 ++++++++++++++++++++++------------ vendor/ahash/src/specialize.rs | 23 +- vendor/ahash/tests/bench.rs | 139 ++++++++- vendor/ahash/tests/map_tests.rs | 39 ++- vendor/ahash/tests/nopanic.rs | 35 ++- 18 files changed, 1101 insertions(+), 433 deletions(-) (limited to 'vendor/ahash') diff --git a/vendor/ahash/.cargo-checksum.json b/vendor/ahash/.cargo-checksum.json index 8c7a10105..f49de138d 100644 --- a/vendor/ahash/.cargo-checksum.json +++ b/vendor/ahash/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"31399b9babab52fabfe71f52ffe38fef0d3d894fdd5829f84a4e69b031f463c9","FAQ.md":"9eb41898523ee209a0a937f9bcb78afe45ad55ca0556f8a4d4063558098f6d1e","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ff8f68cb076caf8cefe7a6430d4ac086ce6af2ca8ce2c4e5a2004d4552ef52a2","README.md":"72185284f100e149998fe5301f70489e617cc4415b51cc77e967c63c6e970a67","build.rs":"123b322034273b5aa1b4934d84c277fef279afd533ecfb44831a3715e9887fcd","rustfmt.toml":"e090969e99df9360705680cc0097cfaddae10c22dc2e01470592cf3b9787fd36","src/aes_hash.rs":"04483498a0d86e3ab099e22f734ea6fcac384b92f349bd310456856bf6a9a5e2","src/convert.rs":"f0e78840046493d0679a9ec077c8164cf57cf30d5e852b11bfadfdd996d29bd1","src/fallback_hash.rs":"ec00691bd555c69f7446afe893b6631cb84207cb7b512260dec8ef488e1905f3","src/hash_map.rs":"ed0c79c41c2218ad9591a585670a2b9b983807c9725880b780138a44c126cbfd","src/hash_quality_test.rs":"6c1fea90a38dc7b2ac5b2fa6e44a565e0c3385c72df6e87231401f920912d053","src/hash_set.rs":"dc3d33e290aad62457ab1f5e64d3e33eb79e28c9468bfc8686339f0bbd8b19aa","src/lib.rs":"9fec7d1d412e414231c9b929081b1daa7c3b788a9f91eedd79a55efdf5d0d291","src/operations.rs":"10772e65b8b7106f195428c5eb8dbf6cbd49dd5a2165ac750e54af5995210f88","src/random_state.rs":"b7981967ec5ecbff04d166b5e05c59c386062b4de3b36816f3c98ef284372f63","src/specialize.rs":"38d3b56ef4f264d564f48dbcb8ac137928babf90635090c9771c1a62140d1f30","tests/bench.rs":"0851dffebaffd7a437f6f9946ed5e03a957e9a6eb0da7911451af58778c411ec","tests/map_tests.rs":"e0f155f964dd965740b072ee1da110a8c6ef34491c95219f7c89064112c7840f","tests/nopanic.rs":"3363675c4c1a197b86604a0aebbe958fb5ec7c01a414fbfd70e9eb8a29707400"},"package":"fcb51a0695d8f838b1ee009b3fbf66bda078cd64590202a864a8f3e8c4315c47"} \ No newline at end of file +{"files":{"Cargo.toml":"8eb7fc9d3e5ba10dbc6400f61c380b208502c7b1390fb683ed947765822c0cbb","FAQ.md":"9eb41898523ee209a0a937f9bcb78afe45ad55ca0556f8a4d4063558098f6d1e","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"0444c6991eead6822f7b9102e654448d51624431119546492e8b231db42c48bb","README.md":"c66723dab78f118b9f0aeb09923c03ed46cd4596757cac9a0ed6bd91a3aea6cc","build.rs":"21e62c29f64f294a6871b5f0831b789cadc5f8e4e02423ab9acccb30c4d401bd","rustfmt.toml":"e090969e99df9360705680cc0097cfaddae10c22dc2e01470592cf3b9787fd36","src/aes_hash.rs":"1392355b354446bd71d9bfcf654b8209210974268db658f8f30c10594b7e421f","src/convert.rs":"b47fc60fc47b3492235da337d4ba247bd80a3e0b5e468d34784db24f1f294244","src/fallback_hash.rs":"37cb76793cd11f0b582e89c91ffaeb7270ed31c90b3a3c082a87ccbe9b188fcc","src/hash_map.rs":"08e05937577ea797d9f8efcdbe45c3dcb1c6f6b71434d27284b139d16b5058bd","src/hash_quality_test.rs":"f603f13f5e7d67f0aa197066555bb8c990e2ce6a3ab5393b551a154920e6fcff","src/hash_set.rs":"f91aeb3d6c07d437a011a3cc88d74d50083e24c553b8dff227706543efa29803","src/lib.rs":"940ab09005f8e98b01ad40da35b69e0fb2de998d58960ed501d24568f3d9f363","src/operations.rs":"605b0bfadf8d4abb4416c33a056cfefc694f6de60591a8fd39bb5a12e91a3286","src/random_state.rs":"5e097a409381f2f46be7f9946d007d6fd3ae7dc5b9443a03b3714a7057826578","src/specialize.rs":"56354db8a0f7e6ee1340a08f2ab6f79a0ff439fd61badac5e7e59fe4f4a653ba","tests/bench.rs":"eae408c803fdf65ac27043dfb4c6d723496a9e5a45f69f8ee92bba9c719d455b","tests/map_tests.rs":"6161e7255fc22977ad871d8bcf948717a8b57b503033d9ddb565f3b145ccab34","tests/nopanic.rs":"0d28a46248d77283941db1d9fd154c68b965c81a0e3db1fe4a43e06fc448da8f"},"package":"bf6ccdb167abbf410dcb915cabd428929d7f6a04980b54a11f26a39f1c7f7107"} \ No newline at end of file diff --git a/vendor/ahash/Cargo.toml b/vendor/ahash/Cargo.toml index b412f7916..e251c700b 100644 --- a/vendor/ahash/Cargo.toml +++ b/vendor/ahash/Cargo.toml @@ -3,31 +3,51 @@ # When uploading crates to the registry Cargo will automatically # "normalize" Cargo.toml files for maximal compatibility # with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g., crates.io) dependencies +# to registry (e.g., crates.io) dependencies. # -# If you believe there's an error in this file please file an -# issue against the rust-lang/cargo repository. If you're -# editing this file be aware that the upstream Cargo.toml -# will likely look very different (and much more reasonable) +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. [package] edition = "2018" name = "ahash" -version = "0.7.6" +version = "0.8.2" authors = ["Tom Kaitchuck "] build = "./build.rs" -exclude = ["/smhasher", "/benchmark_tools"] +exclude = [ + "/smhasher", + "/benchmark_tools", +] description = "A non-cryptographic hash function using AES-NI for high performance" documentation = "https://docs.rs/ahash" readme = "README.md" -keywords = ["hash", "hasher", "hashmap", "aes", "no-std"] -categories = ["algorithms", "data-structures", "no-std"] +keywords = [ + "hash", + "hasher", + "hashmap", + "aes", + "no-std", +] +categories = [ + "algorithms", + "data-structures", + "no-std", +] license = "MIT OR Apache-2.0" repository = "https://github.com/tkaitchuck/ahash" + [package.metadata.docs.rs] +rustc-args = [ + "-C", + "target-feature=+aes", +] +rustdoc-args = [ + "-C", + "target-feature=+aes", +] features = ["std"] -rustc-args = ["-C", "target-feature=+aes"] -rustdoc-args = ["-C", "target-feature=+aes"] + [profile.bench] opt-level = 3 lto = "fat" @@ -63,8 +83,29 @@ harness = false name = "map" path = "tests/map_tests.rs" harness = false + +[dependencies.atomic-polyfill] +version = "1.0.1" +optional = true + +[dependencies.cfg-if] +version = "1.0" + +[dependencies.const-random] +version = "0.1.12" +optional = true + +[dependencies.getrandom] +version = "0.2.7" +optional = true + +[dependencies.serde] +version = "1.0.117" +optional = true + [dev-dependencies.criterion] version = "0.3.2" +features = ["html_reports"] [dev-dependencies.fnv] version = "1.0.5" @@ -72,6 +113,9 @@ version = "1.0.5" [dev-dependencies.fxhash] version = "0.2.1" +[dev-dependencies.hashbrown] +version = "0.12.3" + [dev-dependencies.hex] version = "0.4.2" @@ -79,38 +123,35 @@ version = "0.4.2" version = "0.1.10" [dev-dependencies.rand] -version = "0.7.3" +version = "0.8.5" [dev-dependencies.seahash] version = "4.0" [dev-dependencies.serde_json] version = "1.0.59" + [build-dependencies.version_check] -version = "0.9" +version = "0.9.4" [features] +atomic-polyfill = [ + "dep:atomic-polyfill", + "once_cell/atomic-polyfill", +] compile-time-rng = ["const-random"] -default = ["std"] +default = [ + "std", + "runtime-rng", +] +no-rng = [] +runtime-rng = ["getrandom"] std = [] -[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.const-random] -version = "0.1.12" -optional = true - -[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.getrandom] -version = "0.2.3" -[target."cfg(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\"))".dependencies.serde] -version = "1.0.117" -optional = true [target."cfg(not(all(target_arch = \"arm\", target_os = \"none\")))".dependencies.once_cell] -version = "1.8" -features = ["alloc"] +version = "1.13.1" +features = [ + "unstable", + "alloc", +] default-features = false -[target."cfg(not(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\")))".dependencies.const-random] -version = "0.1.12" -optional = true - -[target."cfg(not(any(target_os = \"linux\", target_os = \"android\", target_os = \"windows\", target_os = \"macos\", target_os = \"ios\", target_os = \"freebsd\", target_os = \"openbsd\", target_os = \"netbsd\", target_os = \"dragonfly\", target_os = \"solaris\", target_os = \"illumos\", target_os = \"fuchsia\", target_os = \"redox\", target_os = \"cloudabi\", target_os = \"haiku\", target_os = \"vxworks\", target_os = \"emscripten\", target_os = \"wasi\")))".dependencies.serde] -version = "1.0.117" -optional = true diff --git a/vendor/ahash/LICENSE-MIT b/vendor/ahash/LICENSE-MIT index 5afc2a7b0..cba20106d 100644 --- a/vendor/ahash/LICENSE-MIT +++ b/vendor/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/vendor/ahash/README.md b/vendor/ahash/README.md index be365a79f..efab7b270 100644 --- a/vendor/ahash/README.md +++ b/vendor/ahash/README.md @@ -53,18 +53,16 @@ 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. 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/vendor/ahash/build.rs b/vendor/ahash/build.rs index 8be4964e5..0c5b76929 100644 --- a/vendor/ahash/build.rs +++ b/vendor/ahash/build.rs @@ -4,32 +4,11 @@ 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\""); - println!("cargo:rustc-cfg=feature=\"stdsimd\""); - } + if let Some(true) = version_check::supports_feature("specialize") { + println!("cargo:rustc-cfg=feature=\"specialize\""); } - let os = env::var("CARGO_CFG_TARGET_OS").expect("CARGO_CFG_TARGET_OS was not set"); - if os.eq_ignore_ascii_case("linux") - || os.eq_ignore_ascii_case("android") - || os.eq_ignore_ascii_case("windows") - || os.eq_ignore_ascii_case("macos") - || os.eq_ignore_ascii_case("ios") - || os.eq_ignore_ascii_case("freebsd") - || os.eq_ignore_ascii_case("openbsd") - || os.eq_ignore_ascii_case("dragonfly") - || os.eq_ignore_ascii_case("solaris") - || os.eq_ignore_ascii_case("illumos") - || os.eq_ignore_ascii_case("fuchsia") - || os.eq_ignore_ascii_case("redox") - || os.eq_ignore_ascii_case("cloudabi") - || os.eq_ignore_ascii_case("haiku") - || os.eq_ignore_ascii_case("vxworks") - || os.eq_ignore_ascii_case("emscripten") - || os.eq_ignore_ascii_case("wasi") - { - println!("cargo:rustc-cfg=feature=\"runtime-rng\""); + if let Some(true) = version_check::supports_feature("stdsimd") { + println!("cargo:rustc-cfg=feature=\"stdsimd\""); } let arch = env::var("CARGO_CFG_TARGET_ARCH").expect("CARGO_CFG_TARGET_ARCH was not set"); if arch.eq_ignore_ascii_case("x86_64") @@ -41,5 +20,4 @@ fn main() { { println!("cargo:rustc-cfg=feature=\"folded_multiply\""); } - } diff --git a/vendor/ahash/src/aes_hash.rs b/vendor/ahash/src/aes_hash.rs index 1c98582ce..702044e5e 100644 --- a/vendor/ahash/src/aes_hash.rs +++ b/vendor/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(); @@ -82,14 +79,6 @@ 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); @@ -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); @@ -326,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] } @@ -337,7 +331,8 @@ impl Hasher for AHasherStr { self.0.enc = aesdec(self.0.sum, self.0.enc); self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc); } else { - self.0.add_in_length(bytes.len() as u64); + add_in_length(&mut self.0.enc, bytes.len() as u64); + let value = read_small(bytes).convert(); self.0.sum = shuffle_and_add(self.0.sum, value); self.0.enc = aesdec(self.0.sum, self.0.enc); @@ -436,4 +431,3 @@ mod tests { assert_eq!(bytes, 0x6464646464646464); } } - diff --git a/vendor/ahash/src/convert.rs b/vendor/ahash/src/convert.rs index 4c0a00eb7..fc47baabb 100644 --- a/vendor/ahash/src/convert.rs +++ b/vendor/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) - } + unsafe { core::mem::transmute::<$a, $b>(self) } } } impl Convert<$a> for $b { #[inline(always)] fn convert(self) -> $a { - unsafe { - core::mem::transmute::<$b, $a>(self) - } + unsafe { core::mem::transmute::<$b, $a>(self) } } } }; diff --git a/vendor/ahash/src/fallback_hash.rs b/vendor/ahash/src/fallback_hash.rs index aad9efc85..f78074d77 100644 --- a/vendor/ahash/src/fallback_hash.rs +++ b/vendor/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(); @@ -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,21 +108,12 @@ 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 { @@ -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")] @@ -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); } } diff --git a/vendor/ahash/src/hash_map.rs b/vendor/ahash/src/hash_map.rs index ec8fa433b..c1cb57d10 100644 --- a/vendor/ahash/src/hash_map.rs +++ b/vendor/ahash/src/hash_map.rs @@ -1,5 +1,6 @@ use std::borrow::Borrow; use std::collections::{hash_map, HashMap}; +use std::collections::hash_map::{IntoKeys, IntoValues}; use std::fmt::{self, Debug}; use std::hash::{BuildHasher, Hash}; use std::iter::FromIterator; @@ -13,6 +14,7 @@ use serde::{ }; use crate::RandomState; +use crate::random_state::RandomSource; /// A [`HashMap`](std::collections::HashMap) using [`RandomState`](crate::RandomState) to hash the items. /// (Requires the `std` feature to be enabled.) @@ -25,6 +27,24 @@ impl From> for AHashMap { } } +impl From<[(K, V); N]> for AHashMap +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 Into> for AHashMap { fn into(self) -> HashMap { self.0 @@ -32,12 +52,16 @@ impl Into> for AHashMap { } impl AHashMap { + /// 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 +169,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 +187,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 { + 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 = 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 { + 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 +345,16 @@ where } } -impl FromIterator<(K, V)> for AHashMap +impl FromIterator<(K, V)> for AHashMap 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>(iter: T) -> Self { - AHashMap(HashMap::from_iter(iter)) + let mut inner = HashMap::with_hasher(RandomState::new()); + inner.extend(iter); + AHashMap(inner) } } @@ -318,10 +405,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 Default for AHashMap { #[inline] fn default() -> AHashMap { - AHashMap::new() + AHashMap(HashMap::default()) } } @@ -346,6 +437,40 @@ where let hash_map = HashMap::deserialize(deserializer); hash_map.map(|hash_map| Self(hash_map)) } + + fn deserialize_in_place>(deserializer: D, place: &mut Self) -> Result<(), D::Error> { + use serde::de::{MapAccess, Visitor}; + + struct MapInPlaceVisitor<'a, K: 'a, V: 'a>(&'a mut AHashMap); + + 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(self, mut map: A) -> Result + 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 +489,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 = serde_json::from_str(&serialization).unwrap(); + let mut serialization = serde_json::to_string(&map).unwrap(); + let mut deserialization: AHashMap = 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/vendor/ahash/src/hash_quality_test.rs b/vendor/ahash/src/hash_quality_test.rs index 4cd3156af..bd85eddda 100644 --- a/vendor/ahash/src/hash_quality_test.rs +++ b/vendor/ahash/src/hash_quality_test.rs @@ -147,7 +147,13 @@ fn assert_each_byte_differs(num: u64, base: u64, alternitives: Vec) { for alternitive in alternitives { changed_bits |= base ^ alternitive } - assert_eq!(core::u64::MAX, changed_bits, "Bits changed: {:x} on num: {:?}", changed_bits, num); + assert_eq!( + core::u64::MAX, + changed_bits, + "Bits changed: {:x} on num: {:?}", + changed_bits, + num + ); } fn test_finish_is_consistent(constructor: impl Fn(u128, u128) -> T) { @@ -273,11 +279,19 @@ fn test_padding_doesnot_collide(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); @@ -370,7 +384,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)); } @@ -397,7 +411,12 @@ 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( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) ))] #[cfg(test)] mod aes_tests { @@ -460,7 +479,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/vendor/ahash/src/hash_set.rs b/vendor/ahash/src/hash_set.rs index 9766b676f..8d1341a14 100644 --- a/vendor/ahash/src/hash_set.rs +++ b/vendor/ahash/src/hash_set.rs @@ -1,4 +1,5 @@ use crate::RandomState; +use crate::random_state::RandomSource; use std::collections::{hash_set, HashSet}; use std::fmt::{self, Debug}; use std::hash::{BuildHasher, Hash}; @@ -14,27 +15,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(HashSet); +pub struct AHashSet(HashSet); -impl From> for AHashSet { - fn from(item: HashSet) -> Self { +impl From> for AHashSet { + fn from(item: HashSet) -> Self { AHashSet(item) } } -impl Into> for AHashSet { - fn into(self) -> HashSet { +impl From<[T; N]> for AHashSet +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 Into> for AHashSet { + fn into(self) -> HashSet { self.0 } } impl AHashSet { + /// 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 +242,17 @@ where } } -impl FromIterator for AHashSet +impl FromIterator for AHashSet 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>(iter: I) -> AHashSet { - AHashSet(HashSet::from_iter(iter)) + fn from_iter>(iter: I) -> AHashSet { + let mut inner = HashSet::with_hasher(RandomState::new()); + inner.extend(iter); + AHashSet(inner) } } @@ -268,6 +294,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 Default for AHashSet { /// Creates an empty `AHashSet` with the `Default` value for the hasher. #[inline] @@ -295,6 +325,10 @@ where let hash_set = HashSet::deserialize(deserializer); hash_set.map(|hash_set| Self(hash_set)) } + + fn deserialize_in_place>(deserializer: D, place: &mut Self) -> Result<(), D::Error> { + HashSet::deserialize_in_place(deserializer, place) + } } #[cfg(all(test, feature = "serde"))] @@ -306,8 +340,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 = serde_json::from_str(&serialization).unwrap(); + let mut serialization = serde_json::to_string(&set).unwrap(); + let mut deserialization: AHashSet = 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/vendor/ahash/src/lib.rs b/vendor/ahash/src/lib.rs index 9964a7c47..978f42413 100644 --- a/vendor/ahash/src/lib.rs +++ b/vendor/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 = 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 = 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 = 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> = 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 = AHashMap::new(); +map.insert(12, 34); +``` +This avoids the need to type "RandomState". (For convience `From`, `Into`, and `Deref` are provided). + +# Aliases + +For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` , +the type aliases [HashMap], [HashSet] are provided. + +``` +use ahash::{HashMap, HashMapExt}; + +let mut map: HashMap = HashMap::new(); +map.insert(12, 34); +``` +Note the import of [HashMapExt]. This is needed for the constructor. + +"## +)] #![deny(clippy::correctness, clippy::complexity, clippy::perf)] #![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)] #![cfg_attr(all(not(test), not(feature = "std")), no_std)] #![cfg_attr(feature = "specialize", feature(min_specialization))] +#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))] #![cfg_attr(feature = "stdsimd", feature(stdsimd))] #[macro_use] mod convert; -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -mod aes_hash; mod fallback_hash; + +cfg_if::cfg_if! { + if #[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all(any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd") + ))] { + mod aes_hash; + pub use crate::aes_hash::AHasher; + } else { + pub use crate::fallback_hash::AHasher; + } +} + +cfg_if::cfg_if! { + if #[cfg(feature = "std")] { + mod hash_map; + mod hash_set; + + pub use crate::hash_map::AHashMap; + pub use crate::hash_set::AHashSet; + + /// [Hasher]: std::hash::Hasher + /// [HashMap]: std::collections::HashMap + /// Type alias for [HashMap] + pub type HashMap = std::collections::HashMap; + + /// Type alias for [HashSet] + pub type HashSet = std::collections::HashSet; + } +} + #[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 HashMapExt for std::collections::HashMap +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 HashSetExt for std::collections::HashSet +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,10 +316,23 @@ impl 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() { use core::hash::BuildHasherDefault; @@ -219,7 +354,6 @@ mod test { assert_eq!(bytes, 0x6464646464646464); } - #[test] fn test_non_zero() { let mut hasher1 = AHasher::new_with_keys(0, 0); @@ -241,7 +375,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/vendor/ahash/src/operations.rs b/vendor/ahash/src/operations.rs index b71fd5a74..ffd3b1a1a 100644 --- a/vendor/ahash/src/operations.rs +++ b/vendor/ahash/src/operations.rs @@ -1,5 +1,8 @@ use crate::convert::*; +///This constant comes from Kunth's prng (Empirically it works better than those from splitmix32). +pub(crate) const MULTIPLE: u64 = 6364136223846793005; + /// This is a constant with a lot of special properties found by automated search. /// See the unit tests below. (Below are alternative values) #[cfg(all(target_feature = "ssse3", not(miri)))] @@ -8,11 +11,19 @@ const SHUFFLE_MASK: u128 = 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) @@ -60,7 +71,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(); @@ -101,14 +112,19 @@ pub(crate) fn aesenc(value: u128, xor: u128) -> u128 { } } -#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))] +#[cfg(all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" +))] #[allow(unused)] #[inline(always)] pub(crate) fn aesenc(value: u128, xor: u128) -> u128 { - #[cfg(target_arch = "arm")] - use core::arch::arm::*; #[cfg(target_arch = "aarch64")] use core::arch::aarch64::*; + #[cfg(target_arch = "arm")] + use core::arch::arm::*; use core::mem::transmute; unsafe { let value = transmute(value); @@ -131,14 +147,19 @@ pub(crate) fn aesdec(value: u128, xor: u128) -> u128 { } } -#[cfg(all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd"))] +#[cfg(all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" +))] #[allow(unused)] #[inline(always)] pub(crate) fn aesdec(value: u128, xor: u128) -> u128 { - #[cfg(target_arch = "arm")] - use core::arch::arm::*; #[cfg(target_arch = "aarch64")] use core::arch::aarch64::*; + #[cfg(target_arch = "arm")] + use core::arch::arm::*; use core::mem::transmute; unsafe { let value = transmute(value); @@ -146,6 +167,30 @@ pub(crate) fn aesdec(value: u128, xor: u128) -> u128 { } } +#[allow(unused)] +#[inline(always)] +pub(crate) fn add_in_length(enc: &mut u128, len: u64) { + #[cfg(all(target_arch = "x86_64", target_feature = "sse2", not(miri)))] + { + #[cfg(target_arch = "x86_64")] + use core::arch::x86_64::*; + + unsafe { + let enc = enc as *mut u128; + let len = _mm_cvtsi64_si128(len as i64); + let data = _mm_loadu_si128(enc.cast()); + let sum = _mm_add_epi64(data, len); + _mm_storeu_si128(enc.cast(), sum); + } + } + #[cfg(not(all(target_arch = "x86_64", target_feature = "sse2", not(miri))))] + { + let mut t: [u64; 2] = enc.convert(); + t[0] = t[0].wrapping_add(len); + *enc = t.convert(); + } +} + #[cfg(test)] mod test { use super::*; @@ -327,4 +372,12 @@ 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/vendor/ahash/src/random_state.rs b/vendor/ahash/src/random_state.rs index c3628bf14..e885fa44e 100644 --- a/vendor/ahash/src/random_state.rs +++ b/vendor/ahash/src/random_state.rs @@ -1,62 +1,38 @@ -#[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_if::cfg_if! { + if #[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all(any(target_arch = "arm", target_arch = "aarch64"), any(target_feature = "aes", target_feature = "crypto"), not(miri), feature = "stdsimd") + ))] { + use crate::aes_hash::*; + } else { + use crate::fallback_hash::*; + } +} +cfg_if::cfg_if! { + if #[cfg(feature = "specialize")]{ + use crate::BuildHasherExt; + } +} +cfg_if::cfg_if! { + if #[cfg(feature = "std")] { + extern crate std as alloc; + } else { + extern crate alloc; + } +} -#[cfg(not(feature = "std"))] -extern crate alloc; -#[cfg(feature = "std")] -extern crate std as alloc; +#[cfg(feature = "atomic-polyfill")] +use atomic_polyfill as atomic; +#[cfg(not(feature = "atomic-polyfill"))] +use core::sync::atomic; use alloc::boxed::Box; -use core::sync::atomic::{AtomicUsize, Ordering}; -#[cfg(not(all(target_arch = "arm", target_os = "none")))] -use once_cell::race::OnceBox; - -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -use crate::aes_hash::*; -#[cfg(not(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -)))] -use crate::fallback_hash::*; - -#[cfg(not(all(target_arch = "arm", target_os = "none")))] -static RAND_SOURCE: OnceBox> = 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 atomic::{AtomicUsize, Ordering}; +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, @@ -72,6 +48,89 @@ 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 { + 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> = 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, } @@ -83,6 +142,7 @@ impl DefaultRandomSource { } } + #[cfg(all(target_arch = "arm", target_os = "none"))] const fn default() -> DefaultRandomSource { DefaultRandomSource { counter: AtomicUsize::new(PI[3] as usize), @@ -91,55 +151,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 @@ -149,6 +204,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, @@ -165,46 +230,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()) } @@ -212,45 +261,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(&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 { @@ -266,26 +387,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 @@ -293,6 +417,52 @@ 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(&self, x: T) -> u64 { + RandomState::hash_one(self, x) + } } #[cfg(feature = "specialize")] @@ -328,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/vendor/ahash/src/specialize.rs b/vendor/ahash/src/specialize.rs index d94a4eed0..05d335b19 100644 --- a/vendor/ahash/src/specialize.rs +++ b/vendor/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(value: &H, build_hasher: &B) -> u64; } diff --git a/vendor/ahash/tests/bench.rs b/vendor/ahash/tests/bench.rs index 9e6dccc48..84a373959 100644 --- a/vendor/ahash/tests/bench.rs +++ b/vendor/ahash/tests/bench.rs @@ -1,20 +1,32 @@ -use ahash::{CallHasher, RandomState}; +#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))] + +use ahash::{AHasher, RandomState}; use criterion::*; use fxhash::FxHasher; use std::collections::hash_map::DefaultHasher; -use std::hash::{Hash, Hasher}; +use std::hash::{BuildHasherDefault, Hash, Hasher}; #[cfg(any( all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") + all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) ))] fn aeshash(b: &H) -> u64 { let build_hasher = RandomState::with_seeds(1, 2, 3, 4); - H::get_hash(b, &build_hasher) + build_hasher.hash_one(b) } #[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") + all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) )))] fn aeshash(_b: &H) -> u64 { panic!("aes must be enabled") @@ -22,15 +34,25 @@ fn aeshash(_b: &H) -> u64 { #[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") + all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) )))] fn fallbackhash(b: &H) -> u64 { let build_hasher = RandomState::with_seeds(1, 2, 3, 4); - H::get_hash(b, &build_hasher) + build_hasher.hash_one(b) } #[cfg(any( all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") + all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) ))] fn fallbackhash(_b: &H) -> u64 { panic!("aes must be disabled") @@ -82,6 +104,7 @@ const U32_VALUE: u32 = 12345678; const U64_VALUE: u64 = 1234567890123456; const U128_VALUE: u128 = 12345678901234567890123456789012; +#[cfg(target_feature = "aes")] 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)))); @@ -92,6 +115,7 @@ fn bench_ahash(c: &mut Criterion) { group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(aeshash(s)))); } +#[cfg(not(target_feature = "aes"))] 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)))); @@ -142,13 +166,108 @@ fn bench_sip(c: &mut Criterion) { group.bench_with_input("string", &gen_strings(), |b, s| b.iter(|| black_box(siphash(s)))); } +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 = (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 = (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 = (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 = (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 = (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> = + (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); + +#[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all( + any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) +))] +criterion_group!(benches, bench_ahash, bench_fx, bench_fnv, bench_sea, bench_sip); + +#[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"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd" + ) +)))] criterion_group!( benches, - bench_ahash, bench_fallback, bench_fx, bench_fnv, bench_sea, - bench_sip + bench_sip, + bench_map, ); diff --git a/vendor/ahash/tests/map_tests.rs b/vendor/ahash/tests/map_tests.rs index be617a2e7..8d798a046 100644 --- a/vendor/ahash/tests/map_tests.rs +++ b/vendor/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 { let words: Vec<_> = r#" a, ability, able, about, above, accept, according, account, across, act, action, @@ -150,9 +151,18 @@ fn check_for_collisions(build_hasher: &B, items: &[H], ); } +#[cfg(feature = "specialize")] #[allow(unused)] // False positive fn hash(b: &H, build_hasher: &B) -> u64 { - H::get_hash(b, build_hasher) + build_hasher.hash_one(b) +} + +#[cfg(not(feature = "specialize"))] +#[allow(unused)] // False positive +fn hash(b: &H, build_hasher: &B) -> u64 { + let mut hasher = build_hasher.build_hasher(); + b.hash(&mut hasher); + hasher.finish() } #[test] @@ -169,10 +179,31 @@ 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); +} + fn ahash_vec(b: &Vec) -> 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/vendor/ahash/tests/nopanic.rs b/vendor/ahash/tests/nopanic.rs index d48ff559d..56f754cbe 100644 --- a/vendor/ahash/tests/nopanic.rs +++ b/vendor/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(&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"); } -- cgit v1.2.3