diff options
Diffstat (limited to 'vendor/ahash/src')
| -rw-r--r-- | vendor/ahash/src/aes_hash.rs | 30 | ||||
| -rw-r--r-- | vendor/ahash/src/convert.rs | 8 | ||||
| -rw-r--r-- | vendor/ahash/src/fallback_hash.rs | 40 | ||||
| -rw-r--r-- | vendor/ahash/src/hash_map.rs | 151 | ||||
| -rw-r--r-- | vendor/ahash/src/hash_quality_test.rs | 31 | ||||
| -rw-r--r-- | vendor/ahash/src/hash_set.rs | 66 | ||||
| -rw-r--r-- | vendor/ahash/src/lib.rs | 240 | ||||
| -rw-r--r-- | vendor/ahash/src/operations.rs | 67 | ||||
| -rw-r--r-- | vendor/ahash/src/random_state.rs | 510 | ||||
| -rw-r--r-- | vendor/ahash/src/specialize.rs | 23 |
10 files changed, 829 insertions, 337 deletions
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(); @@ -83,14 +80,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); self.sum = shuffle_and_add(self.sum, 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<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 +52,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 +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<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 +345,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 +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<K, V> Default for AHashMap<K, V, RandomState> { #[inline] fn default() -> AHashMap<K, V, RandomState> { - 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<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 +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<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/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<u64>) { 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<T: Hasher>(constructor: impl Fn(u128, u128) -> T) { @@ -273,11 +279,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); @@ -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<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 +242,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 +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<T> Default for AHashSet<T, RandomState> { /// Creates an empty `AHashSet<T, S>` 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<D: Deserializer<'de>>(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<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/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<i32, i32, RandomState> = HashMap::default(); -//! map.insert(12, 34); -//! ``` -//! For convinence wrappers called `AHashMap` and `AHashSet` are also provided. -//! These to the same thing with slightly less typing. -//! ```ignore -//! use ahash::AHashMap; -//! -//! let mut map: AHashMap<i32, i32> = AHashMap::with_capacity(4); -//! map.insert(12, 34); -//! map.insert(56, 78); -//! ``` +//! Because aHash does not have a fixed standard for its output, it is able to improve over time. +//! But this also means that different computers or computers using different versions of ahash may observe different +//! hash values for the same input. +#![cfg_attr( + all(feature = "std", any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng")), + doc = r##" +# Basic Usage +AHash provides an implementation of the [Hasher] trait. +To construct a HashMap using aHash as its hasher do the following: +``` +use ahash::{AHasher, RandomState}; +use std::collections::HashMap; + +let mut map: HashMap<i32, i32, RandomState> = HashMap::default(); +map.insert(12, 34); +``` + +### Randomness + +The above requires a source of randomness to generate keys for the hashmap. By default this obtained from the OS. +It is also possible to have randomness supplied via the `compile-time-rng` flag, or manually. + +### If randomess is not available + +[AHasher::default()] can be used to hash using fixed keys. This works with +[BuildHasherDefault](std::hash::BuildHasherDefault). For example: + +``` +use std::hash::BuildHasherDefault; +use std::collections::HashMap; +use ahash::AHasher; + +let mut m: HashMap<_, _, BuildHasherDefault<AHasher>> = HashMap::default(); + # m.insert(12, 34); +``` +It is also possible to instantiate [RandomState] directly: + +``` +use ahash::HashMap; +use ahash::RandomState; + +let mut m = HashMap::with_hasher(RandomState::with_seed(42)); + # m.insert(1, 2); +``` +Or for uses besides a hashhmap: +``` +use std::hash::BuildHasher; +use ahash::RandomState; + +let hash_builder = RandomState::with_seed(42); +let hash = hash_builder.hash_one("Some Data"); +``` +There are several constructors for [RandomState] with different ways to supply seeds. + +# Convenience wrappers + +For convenience, both new-type wrappers and type aliases are provided. + +The new type wrappers are called called `AHashMap` and `AHashSet`. +``` +use ahash::AHashMap; + +let mut map: AHashMap<i32, i32> = AHashMap::new(); +map.insert(12, 34); +``` +This avoids the need to type "RandomState". (For convience `From`, `Into`, and `Deref` are provided). + +# Aliases + +For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` , +the type aliases [HashMap], [HashSet] are provided. + +``` +use ahash::{HashMap, HashMapExt}; + +let mut map: HashMap<i32, i32> = HashMap::new(); +map.insert(12, 34); +``` +Note the import of [HashMapExt]. This is needed for the constructor. + +"## +)] #![deny(clippy::correctness, clippy::complexity, clippy::perf)] #![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)] #![cfg_attr(all(not(test), not(feature = "std")), no_std)] #![cfg_attr(feature = "specialize", feature(min_specialization))] +#![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))] #![cfg_attr(feature = "stdsimd", feature(stdsimd))] #[macro_use] mod convert; -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -mod aes_hash; mod fallback_hash; + +cfg_if::cfg_if! { + if #[cfg(any( + all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), + all(any(target_arch = "arm", target_arch = "aarch64"), + any(target_feature = "aes", target_feature = "crypto"), + not(miri), + feature = "stdsimd") + ))] { + mod aes_hash; + pub use crate::aes_hash::AHasher; + } else { + pub use crate::fallback_hash::AHasher; + } +} + +cfg_if::cfg_if! { + if #[cfg(feature = "std")] { + mod hash_map; + mod hash_set; + + pub use crate::hash_map::AHashMap; + pub use crate::hash_set::AHashSet; + + /// [Hasher]: std::hash::Hasher + /// [HashMap]: std::collections::HashMap + /// Type alias for [HashMap]<K, V, ahash::RandomState> + pub type HashMap<K, V> = std::collections::HashMap<K, V, crate::RandomState>; + + /// Type alias for [HashSet]<K, ahash::RandomState> + pub type HashSet<K> = std::collections::HashSet<K, crate::RandomState>; + } +} + #[cfg(test)] mod hash_quality_test; -#[cfg(feature = "std")] -mod hash_map; -#[cfg(feature = "std")] -mod hash_set; mod operations; -mod random_state; +pub mod random_state; mod specialize; -#[cfg(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -))] -pub use crate::aes_hash::AHasher; - -#[cfg(not(any( - all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), - all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") -)))] -pub use crate::fallback_hash::AHasher; pub use crate::random_state::RandomState; -pub use crate::specialize::CallHasher; - -#[cfg(feature = "std")] -pub use crate::hash_map::AHashMap; -#[cfg(feature = "std")] -pub use crate::hash_set::AHashSet; use core::hash::BuildHasher; use core::hash::Hash; use core::hash::Hasher; +#[cfg(feature = "std")] +/// A convenience trait that can be used together with the type aliases defined to +/// get access to the `new()` and `with_capacity()` methods for the HashMap type alias. +pub trait HashMapExt { + /// Constructs a new HashMap + fn new() -> Self; + /// Constructs a new HashMap with a given initial capacity + fn with_capacity(capacity: usize) -> Self; +} + +#[cfg(feature = "std")] +/// A convenience trait that can be used together with the type aliases defined to +/// get access to the `new()` and `with_capacity()` methods for the HashSet type aliases. +pub trait HashSetExt { + /// Constructs a new HashSet + fn new() -> Self; + /// Constructs a new HashSet with a given initial capacity + fn with_capacity(capacity: usize) -> Self; +} + +#[cfg(feature = "std")] +impl<K, V, S> HashMapExt for std::collections::HashMap<K, V, S> +where + S: BuildHasher + Default, +{ + fn new() -> Self { + std::collections::HashMap::with_hasher(S::default()) + } + + fn with_capacity(capacity: usize) -> Self { + std::collections::HashMap::with_capacity_and_hasher(capacity, S::default()) + } +} + +#[cfg(feature = "std")] +impl<K, S> HashSetExt for std::collections::HashSet<K, S> +where + S: BuildHasher + Default, +{ + fn new() -> Self { + std::collections::HashSet::with_hasher(S::default()) + } + + fn with_capacity(capacity: usize) -> Self { + std::collections::HashSet::with_capacity_and_hasher(capacity, S::default()) + } +} + /// Provides a default [Hasher] with fixed keys. /// This is typically used in conjunction with [BuildHasherDefault] to create /// [AHasher]s in order to hash the keys of the map. /// /// Generally it is preferable to use [RandomState] instead, so that different -/// hashmaps will have different keys. However if fixed keys are desireable this +/// hashmaps will have different keys. However if fixed keys are desirable this /// may be used instead. /// /// # Example @@ -194,11 +316,24 @@ 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() { 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<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 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<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, } @@ -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<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 { @@ -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<T: Hash>(&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<H: Hash + ?Sized, B: BuildHasher>(value: &H, build_hasher: &B) -> u64; } |