summaryrefslogtreecommitdiffstats
path: root/vendor/ahash/src
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:19:03 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-17 12:19:03 +0000
commit64d98f8ee037282c35007b64c2649055c56af1db (patch)
tree5492bcf97fce41ee1c0b1cc2add283f3e66cdab0 /vendor/ahash/src
parentAdding debian version 1.67.1+dfsg1-1. (diff)
downloadrustc-64d98f8ee037282c35007b64c2649055c56af1db.tar.xz
rustc-64d98f8ee037282c35007b64c2649055c56af1db.zip
Merging upstream version 1.68.2+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/ahash/src')
-rw-r--r--vendor/ahash/src/aes_hash.rs30
-rw-r--r--vendor/ahash/src/convert.rs8
-rw-r--r--vendor/ahash/src/fallback_hash.rs40
-rw-r--r--vendor/ahash/src/hash_map.rs151
-rw-r--r--vendor/ahash/src/hash_quality_test.rs31
-rw-r--r--vendor/ahash/src/hash_set.rs66
-rw-r--r--vendor/ahash/src/lib.rs240
-rw-r--r--vendor/ahash/src/operations.rs67
-rw-r--r--vendor/ahash/src/random_state.rs510
-rw-r--r--vendor/ahash/src/specialize.rs23
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;
}