Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C++ (Circle)
CIRCT
Clean
CMake
CMakeScript
COBOL
C++ for OpenCL
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
D
Dart
Elixir
Erlang
Fortran
F#
Go
Haskell
HLSL
Hook
Hylo
ispc
Java
Julia
Kotlin
LLVM IR
LLVM MIR
Modula-2
Nim
Objective-C
Objective-C++
OCaml
OpenCL C
Pascal
Pony
Python
Racket
Ruby
Rust
Snowball
Scala
Solidity
Spice
Swift
LLVM TableGen
Toit
TypeScript Native
V
Vala
Visual Basic
WASM
Zig
Javascript
GIMPLE
rust source #1
Output
Compile to binary object
Link to binary
Execute the code
Intel asm syntax
Demangle identifiers
Verbose demangling
Filters
Unused labels
Library functions
Directives
Comments
Horizontal whitespace
Debug intrinsics
Compiler
mrustc (master)
rustc 1.0.0
rustc 1.1.0
rustc 1.10.0
rustc 1.11.0
rustc 1.12.0
rustc 1.13.0
rustc 1.14.0
rustc 1.15.1
rustc 1.16.0
rustc 1.17.0
rustc 1.18.0
rustc 1.19.0
rustc 1.2.0
rustc 1.20.0
rustc 1.21.0
rustc 1.22.0
rustc 1.23.0
rustc 1.24.0
rustc 1.25.0
rustc 1.26.0
rustc 1.27.0
rustc 1.27.1
rustc 1.28.0
rustc 1.29.0
rustc 1.3.0
rustc 1.30.0
rustc 1.31.0
rustc 1.32.0
rustc 1.33.0
rustc 1.34.0
rustc 1.35.0
rustc 1.36.0
rustc 1.37.0
rustc 1.38.0
rustc 1.39.0
rustc 1.4.0
rustc 1.40.0
rustc 1.41.0
rustc 1.42.0
rustc 1.43.0
rustc 1.44.0
rustc 1.45.0
rustc 1.45.2
rustc 1.46.0
rustc 1.47.0
rustc 1.48.0
rustc 1.49.0
rustc 1.5.0
rustc 1.50.0
rustc 1.51.0
rustc 1.52.0
rustc 1.53.0
rustc 1.54.0
rustc 1.55.0
rustc 1.56.0
rustc 1.57.0
rustc 1.58.0
rustc 1.59.0
rustc 1.6.0
rustc 1.60.0
rustc 1.61.0
rustc 1.62.0
rustc 1.63.0
rustc 1.64.0
rustc 1.65.0
rustc 1.66.0
rustc 1.67.0
rustc 1.68.0
rustc 1.69.0
rustc 1.7.0
rustc 1.70.0
rustc 1.71.0
rustc 1.72.0
rustc 1.73.0
rustc 1.74.0
rustc 1.75.0
rustc 1.76.0
rustc 1.77.0
rustc 1.78.0
rustc 1.79.0
rustc 1.8.0
rustc 1.80.0
rustc 1.81.0
rustc 1.9.0
rustc beta
rustc nightly
rustc-cg-gcc (master)
x86-64 GCCRS (GCC master)
x86-64 GCCRS (GCCRS master)
x86-64 GCCRS 14.1 (GCC)
x86-64 GCCRS 14.2 (GCC)
Options
Source code
use std::hash::BuildHasher; #[no_mangle] pub fn view_assembly(x: u64, h: &fast::RandomState) -> u64 { h.hash_one(x) } use core::hash::Hasher; // Arbitrary constants with high entropy. Hexadecimal digits of pi were used. const ARBITRARY1: u64 = 0x243f6a8885a308d3; const ARBITRARY2: u64 = 0x13198a2e03707344; const ARBITRARY3: u64 = 0xa4093822299f31d0; const ARBITRARY4: u64 = 0x082efa98ec4e6c89; const ARBITRARY5: u64 = 0x452821e638d01377; const ARBITRARY6: u64 = 0xbe5466cf34e90c6c; const ARBITRARY7: u64 = 0xc0ac29b7c97c50dd; const ARBITRARY8: u64 = 0x3f84d5b5b5470917; const ARBITRARY9: u64 = 0x9216d5d98979fb1b; #[inline(always)] const fn folded_multiply(x: u64, y: u64) -> u64 { #[cfg(target_pointer_width = "64")] { // We compute the full u64 x u64 -> u128 product, this is a single mul // instruction on x86-64, one mul plus one mulhi on ARM64. let full = (x as u128) * (y as u128); let lo = full as u64; let hi = (full >> 64) as u64; // The middle bits of the full product fluctuate the most with small // changes in the input. This is the top bits of lo and the bottom bits // of hi. We can thus make the entire output fluctuate with small // changes to the input by XOR'ing these two halves. lo ^ hi } #[cfg(target_pointer_width = "32")] { // u64 x u64 -> u128 product is prohibitively expensive on 32-bit. // Decompose into 32-bit parts. let lx = x as u32; let ly = y as u32; let hx = (x >> 32) as u32; let hy = (y >> 32) as u32; // u32 x u32 -> u64 the low bits of one with the high bits of the other. let afull = (lx as u64) * (hy as u64); let bfull = (hx as u64) * (ly as u64); // Combine, swapping low/high of one of them so the upper bits of the // product of one combine with the lower bits of the other. afull ^ bfull.rotate_right(32) } } /// The foldhash implementation optimized for speed. pub mod fast { use super::*; pub use seed::fast::{FixedState, RandomState}; /// A [`Hasher`] instance implementing foldhash, optimized for speed. /// /// It can't be created directly, see [`RandomState`] or [`FixedState`]. #[derive(Clone)] pub struct FoldHasher { accumulator: u64, sponge: u128, sponge_len: u8, global_seed: &'static [u64; 4], } impl FoldHasher { pub(crate) fn with_seed(per_hasher_seed: u64, global_seed: &'static [u64; 4]) -> FoldHasher { FoldHasher { accumulator: per_hasher_seed, sponge: 0, sponge_len: 0, global_seed } } #[inline(always)] fn write_num<T: Into<u128>>(&mut self, x: T) { let bits: usize = 8 * core::mem::size_of::<T>(); if self.sponge_len as usize + bits > 128 { let lo = self.sponge as u64; let hi = (self.sponge >> 64) as u64; self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.global_seed[0]); self.sponge = x.into(); self.sponge_len = 0; } else { self.sponge |= x.into() << self.sponge_len; self.sponge_len += bits as u8; } } } impl Hasher for FoldHasher { #[inline(always)] fn write(&mut self, bytes: &[u8]) { let mut s0 = self.accumulator; let mut s1 = self.global_seed[1]; let len = bytes.len(); if len <= 16 { // XOR the input into s0, s1, then multiply and fold. if len >= 8 { s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap()); s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap()); } else if len >= 4 { s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64; s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64; } else if len > 0 { let lo = bytes[0]; let mid = bytes[len / 2]; let hi = bytes[len - 1]; s0 ^= lo as u64; s1 ^= ((hi as u64) << 8) | mid as u64; } self.accumulator = folded_multiply(s0, s1); } else if len < 256 { self.accumulator = hash_bytes_medium(bytes, s0, s1, self.global_seed[0]); } else { self.accumulator = hash_bytes_long( bytes, s0, s1, self.global_seed[2], self.global_seed[3], self.global_seed[0], ); } } #[inline(always)] fn write_u8(&mut self, i: u8) { self.write_num(i); } #[inline(always)] fn write_u16(&mut self, i: u16) { self.write_num(i); } #[inline(always)] fn write_u32(&mut self, i: u32) { self.write_num(i); } #[inline(always)] fn write_u64(&mut self, i: u64) { self.write_num(i); } #[inline(always)] fn write_u128(&mut self, i: u128) { let lo = i as u64; let hi = (i >> 64) as u64; self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.global_seed[0]); } #[inline(always)] fn write_usize(&mut self, i: usize) { // u128 doesn't implement From<usize>. #[cfg(target_pointer_width = "32")] self.write_num(i as u32); #[cfg(target_pointer_width = "64")] self.write_num(i as u64); } #[inline(always)] fn finish(&self) -> u64 { if self.sponge_len > 0 { let lo = self.sponge as u64; let hi = (self.sponge >> 64) as u64; folded_multiply(lo ^ self.accumulator, hi ^ self.global_seed[0]) } else { self.accumulator } } } } /// The foldhash implementation optimized for quality. pub mod quality { use super::*; pub use seed::quality::{FixedState, RandomState}; /// A [`Hasher`] instance implementing foldhash, optimized for quality. /// /// It can't be created directly, see [`RandomState`] or [`FixedState`]. #[derive(Clone)] pub struct FoldHasher { pub(crate) inner: fast::FoldHasher, } impl Hasher for FoldHasher { #[inline(always)] fn write(&mut self, bytes: &[u8]) { self.inner.write(bytes); } #[inline(always)] fn write_u8(&mut self, i: u8) { self.inner.write_u8(i); } #[inline(always)] fn write_u16(&mut self, i: u16) { self.inner.write_u16(i); } #[inline(always)] fn write_u32(&mut self, i: u32) { self.inner.write_u32(i); } #[inline(always)] fn write_u64(&mut self, i: u64) { self.inner.write_u64(i); } #[inline(always)] fn write_u128(&mut self, i: u128) { self.inner.write_u128(i); } #[inline(always)] fn write_usize(&mut self, i: usize) { self.inner.write_usize(i); } #[inline(always)] fn finish(&self) -> u64 { folded_multiply(self.inner.finish(), ARBITRARY1) } } } /// Hashes strings >= 16 bytes, has unspecified behavior when bytes.len() < 16. fn hash_bytes_medium(bytes: &[u8], mut s0: u64, mut s1: u64, fold_seed: u64) -> u64 { // Process 32 bytes per iteration, 16 bytes from the start, 16 bytes from // the end. On the last iteration these two chunks can overlap, but that is // perfectly fine. let left_to_right = bytes.chunks_exact(16); let mut right_to_left = bytes.rchunks_exact(16); for lo in left_to_right { let hi = right_to_left.next().unwrap(); let unconsumed_start = lo.as_ptr(); let unconsumed_end = hi.as_ptr_range().end; if unconsumed_start >= unconsumed_end { break; } let a = u64::from_ne_bytes(lo[0..8].try_into().unwrap()); let b = u64::from_ne_bytes(lo[8..16].try_into().unwrap()); let c = u64::from_ne_bytes(hi[0..8].try_into().unwrap()); let d = u64::from_ne_bytes(hi[8..16].try_into().unwrap()); s0 = folded_multiply(a ^ s0, c ^ fold_seed); s1 = folded_multiply(b ^ s1, d ^ fold_seed); } s0 ^ s1 } /// Hashes strings >= 16 bytes, has unspecified behavior when bytes.len() < 16. #[cold] #[inline(never)] fn hash_bytes_long( bytes: &[u8], mut s0: u64, mut s1: u64, mut s2: u64, mut s3: u64, fold_seed: u64, ) -> u64 { let chunks = bytes.chunks_exact(64); let remainder = chunks.remainder().len(); for chunk in chunks { let a = u64::from_ne_bytes(chunk[0..8].try_into().unwrap()); let b = u64::from_ne_bytes(chunk[8..16].try_into().unwrap()); let c = u64::from_ne_bytes(chunk[16..24].try_into().unwrap()); let d = u64::from_ne_bytes(chunk[24..32].try_into().unwrap()); let e = u64::from_ne_bytes(chunk[32..40].try_into().unwrap()); let f = u64::from_ne_bytes(chunk[40..48].try_into().unwrap()); let g = u64::from_ne_bytes(chunk[48..56].try_into().unwrap()); let h = u64::from_ne_bytes(chunk[56..64].try_into().unwrap()); s0 = folded_multiply(a ^ s0, e ^ fold_seed); s1 = folded_multiply(b ^ s1, f ^ fold_seed); s2 = folded_multiply(c ^ s2, g ^ fold_seed); s3 = folded_multiply(d ^ s3, h ^ fold_seed); } s0 ^= s2; s1 ^= s3; if remainder > 0 { hash_bytes_medium(&bytes[bytes.len() - remainder.max(16)..], s0, s1, fold_seed) } else { s0 ^ s1 } } mod seed { use core::cell::UnsafeCell; use core::hash::BuildHasher; use core::sync::atomic::{AtomicU8, AtomicUsize, Ordering}; use super::{ folded_multiply, ARBITRARY2, ARBITRARY3, ARBITRARY4, ARBITRARY5, ARBITRARY6, ARBITRARY7, ARBITRARY8, ARBITRARY9, }; pub mod fast { use super::*; use crate::fast::FoldHasher; /// A [`BuildHasher`] for [`fast::FoldHasher`]s that are randomly initialized. #[derive(Copy, Clone, Debug)] pub struct RandomState { per_hasher_seed: u64, global_seed: &'static [u64; 4], } impl Default for RandomState { fn default() -> Self { // We use our current stack address in combination with // PER_HASHER_NONDETERMINISM to create a new value that is very likely // to have never been used as a random state before. // // PER_HASHER_NONDETERMINISM ensures that even if we create two // RandomStates with the same stack location it is still highly unlikely // you'll end up with the same random seed. // // PER_HASHER_NONDETERMINISM is loaded and updated in a racy manner, but // this doesn't matter in practice - it is impossible that two different // threads have the same stack location, so they'll almost surely // generate different seeds, and provide a different possible update for // PER_HASHER_NONDETERMINISM. If we would use a proper atomic update // then hash table creation would have a global contention point, which // users could not avoid. // // Finally, not all platforms have a 64-bit atomic, so we use usize. static PER_HASHER_NONDETERMINISM: AtomicUsize = AtomicUsize::new(0); let nondeterminism = PER_HASHER_NONDETERMINISM.load(Ordering::Relaxed) as u64; let stack_ptr = &nondeterminism as *const _ as u64; let per_hasher_seed = folded_multiply(nondeterminism ^ stack_ptr, ARBITRARY2); PER_HASHER_NONDETERMINISM.store(per_hasher_seed as usize, Ordering::Relaxed); Self { per_hasher_seed, global_seed: GlobalSeed::new().get(), } } } impl BuildHasher for RandomState { type Hasher = FoldHasher; fn build_hasher(&self) -> FoldHasher { FoldHasher::with_seed(self.per_hasher_seed, self.global_seed) } } /// A [`BuildHasher`] for [`fast::FoldHasher`]s that all have the same fixed seed. /// /// Not recommended unless you absolutely need determinism. #[derive(Copy, Clone, Debug)] pub struct FixedState { per_hasher_seed: u64, } impl FixedState { /// Creates a [`FixedState`] with the given seed. pub const fn with_seed(seed: u64) -> Self { // XOR with ARBITRARY3 such that with_seed(0) matches default. Self { per_hasher_seed: seed ^ ARBITRARY3, } } } impl Default for FixedState { fn default() -> Self { Self { per_hasher_seed: ARBITRARY3, } } } impl BuildHasher for FixedState { type Hasher = FoldHasher; fn build_hasher(&self) -> FoldHasher { FoldHasher::with_seed( self.per_hasher_seed, &[ARBITRARY4, ARBITRARY5, ARBITRARY6, ARBITRARY7], ) } } } pub mod quality { use super::*; use crate::quality::FoldHasher; /// A [`BuildHasher`] for [`quality::FoldHasher`]s that are randomly initialized. #[derive(Copy, Clone, Default, Debug)] pub struct RandomState { inner: fast::RandomState, } impl BuildHasher for RandomState { type Hasher = FoldHasher; fn build_hasher(&self) -> FoldHasher { FoldHasher { inner: self.inner.build_hasher(), } } } /// A [`BuildHasher`] for [`quality::FoldHasher`]s that all have the same fixed seed. /// /// Not recommended unless you absolutely need determinism. #[derive(Copy, Clone, Default, Debug)] pub struct FixedState { inner: fast::FixedState, } impl FixedState { /// Creates a [`FixedState`] with the given seed. pub const fn with_seed(seed: u64) -> Self { Self { // We do an additional folded multiply with the seed here for // the quality hash to ensure better independence between seed // and hash. If the seed is zero the folded multiply is zero, // preserving with_seed(0) == default(). inner: fast::FixedState::with_seed(folded_multiply(seed, ARBITRARY8)), } } } impl BuildHasher for FixedState { type Hasher = FoldHasher; fn build_hasher(&self) -> FoldHasher { FoldHasher { inner: self.inner.build_hasher(), } } } } fn generate_global_seed() -> [u64; 4] { let mix = |seed: u64, x: u64| folded_multiply(seed ^ x, ARBITRARY9); // Use address space layout randomization as our main randomness source. // This isn't great, but we don't advertise HashDoS resistance in the first // place. This is a whole lot better than nothing, at near zero cost with // no dependencies. let mut seed = 0; let stack_ptr = &seed as *const _; let func_ptr = generate_global_seed; let static_ptr = &GLOBAL_SEED_STORAGE as *const _; seed = mix(seed, stack_ptr as usize as u64); seed = mix(seed, func_ptr as usize as u64); seed = mix(seed, static_ptr as usize as u64); // If we have the standard library available, augment entropy with the // current time and an address from the allocator. #[cfg(feature = "std")] { let now = std::time::SystemTime::now(); if let Ok(duration) = now.duration_since(std::time::UNIX_EPOCH) { let ns = duration.as_nanos(); seed = mix(seed, ns as u64); seed = mix(seed, (ns >> 64) as u64); } let box_ptr = &*Box::new(0u8) as *const _; seed = mix(seed, box_ptr as usize as u64); } let seed_a = mix(seed, 0); let seed_b = mix(mix(mix(seed_a, 0), 0), 0); let seed_c = mix(mix(mix(seed_b, 0), 0), 0); let seed_d = mix(mix(mix(seed_c, 0), 0), 0); // Zeroes form a weak-point for the multiply-mix, and zeroes tend to be // a common input. So we want our global seeds that are XOR'ed with the // input to always be non-zero. To also ensure there is always a good spread // of bits, we give up 3 bits of entropy and simply force some bits on. const FORCED_ONES: u64 = (1 << 63) | (1 << 31) | 1; [ seed_a | FORCED_ONES, seed_b | FORCED_ONES, seed_c | FORCED_ONES, seed_d | FORCED_ONES, ] } // Now all the below code purely exists to cache the above seed as // efficiently as possible. Even if we weren't a no_std crate and had access to // OnceLock, we don't want to check whether the global is set each time we // hash an object, so we hand-roll a global storage where type safety allows us // to assume the storage is initialized after construction. struct GlobalSeedStorage { state: AtomicU8, seed: UnsafeCell<[u64; 4]>, } const UNINIT: u8 = 0; const LOCKED: u8 = 1; const INIT: u8 = 2; // SAFETY: we only mutate the UnsafeCells when state is in the thread-exclusive // LOCKED state, and only read the UnsafeCells when state is in the // once-achieved-eternally-preserved state INIT. unsafe impl Sync for GlobalSeedStorage {} static GLOBAL_SEED_STORAGE: GlobalSeedStorage = GlobalSeedStorage { state: AtomicU8::new(UNINIT), seed: UnsafeCell::new([0; 4]), }; /// An object representing an initialized global seed. /// /// Does not actually store the seed inside itself, it is a zero-sized type. /// This prevents inflating the RandomState size and in turn HashMap's size. #[derive(Copy, Clone, Debug)] pub struct GlobalSeed { // So we can't accidentally type GlobalSeed { } within this crate. _no_accidental_unsafe_init: (), } impl GlobalSeed { #[inline(always)] pub fn new() -> Self { if GLOBAL_SEED_STORAGE.state.load(Ordering::Acquire) != INIT { Self::init_slow() } Self { _no_accidental_unsafe_init: (), } } #[cold] #[inline(never)] fn init_slow() { // Generate seed outside of critical section. let seed = generate_global_seed(); loop { match GLOBAL_SEED_STORAGE.state.compare_exchange_weak( UNINIT, LOCKED, Ordering::Relaxed, Ordering::Acquire, ) { Ok(_) => unsafe { // SAFETY: we just acquired an exclusive lock. *GLOBAL_SEED_STORAGE.seed.get() = seed; GLOBAL_SEED_STORAGE.state.store(INIT, Ordering::Release); return; }, Err(INIT) => return, // Yes, it's a spin loop. We are a no_std crate (so no easy // access to proper locks), this is a one-time-per-program // initialization, and the critical section is only a few // store instructions, so it'll be fine. _ => core::hint::spin_loop(), } } } #[inline(always)] pub fn get(self) -> &'static [u64; 4] { // SAFETY: our constructor ensured we are in the INIT state and thus // this raw read does not race with any write. unsafe { &*GLOBAL_SEED_STORAGE.seed.get() } } } }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
About the author
Statistics
Changelog
Version tree