Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Algol68
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C with Coccinelle
C++ with Coccinelle
C++ (Circle)
CIRCT
Clean
Clojure
CO2
Cargo
CMake
CMakeScript
COBOL
C++ for OpenCL
Makefile
Maven
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
CuTe DSL
D
Dart
Duckling
Elixir
Erlang
Fortran
F#
Gleam
GLSL
Go
Haskell
HLSL
Helion
Hook
Hylo
IL
ispc
Java
Julia
Kotlin
Lean
LLVM IR
LLVM MIR
Lua
Mach
Modula-2
Mojo
Nexium
Nim
Numba
Nix
Objective-C
Objective-C++
OCaml
Odin
OpenCL C
Pascal
Perl
Pony
PTX
Python
Racket
Raku
RazorForge
Ruby
Rust
Sail
Salam
SFPI C++
Snowball
Scala
Slang
Solidity
Spice
SPIR-V
Swift
LLVM TableGen
TileLang
Toit
Triton
TypeScript Native
V
Vala
Visual Basic
Vyper
WASM
Yul (Solidity IR)
Zig
Javascript
GIMPLE
Ygen
sway
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
BPF gcc (trunk)
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.82.0
rustc 1.83.0
rustc 1.84.0
rustc 1.85.0
rustc 1.86.0
rustc 1.87.0
rustc 1.88.0
rustc 1.89.0
rustc 1.9.0
rustc 1.90.0
rustc 1.91.0
rustc 1.92.0
rustc 1.93.0
rustc 1.94.0
rustc 1.95.0
rustc 1.96.0
rustc 1.97.0
rustc 1.98.0
rustc 1.99.0
rustc beta
rustc nightly
rustc-cg-cranelift (nightly)
rustc-cg-gcc (master)
x86-64 GCCRS (GCC master)
x86-64 GCCRS (GCCRS master)
x86-64 GCCRS 14.1 (GCC assertions)
x86-64 GCCRS 14.1 (GCC)
x86-64 GCCRS 14.2 (GCC assertions)
x86-64 GCCRS 14.2 (GCC)
x86-64 GCCRS 14.3 (GCC assertions)
x86-64 GCCRS 14.3 (GCC)
x86-64 GCCRS 15.1 (GCC assertions)
x86-64 GCCRS 15.1 (GCC)
x86-64 GCCRS 15.2 (GCC assertions)
x86-64 GCCRS 15.2 (GCC)
x86-64 GCCRS 16.1 (GCC assertions)
x86-64 GCCRS 16.1 (GCC)
x86-64 GCCRS 16.2 (GCC assertions)
x86-64 GCCRS 16.2 (GCC)
Options
Source code
use std::hint::black_box; /// This is a somewhat arbitrary cutoff for the long path. /// /// It's dependent on the cost of the function call, register clobbering, setup/teardown of the 7 /// independent lanes etc. The current value should be reached by testing against the /// hash/rapidhash-f/medium benchmarks, and may benefit from being tuned per target platform. const COLD_PATH_CUTOFF: usize = 400; /// Used only for generating random secrets. pub const DEFAULT_SECRETS: [u64; 7] = [ 0x2d358dccaa6c78a5, 0x8bb84b93962eacc9, 0x4b33a62ed433d4a3, 0x4d5a2da51de1aa47, 0xa0761d6478bd642f, 0xe7037ed1a0b428db, 0x90ed1765281c388c, ]; pub fn main() { let hash = black_box(rapidhash_example::<true>(black_box(b"hello"), black_box(0), black_box(&DEFAULT_SECRETS))); println!("{}", hash); } pub const fn rapidhash_example<const AVALANCHE: bool>(data: &[u8], seed: u64, secrets: &[u64; 7]) -> u64 { let hash = rapidhash_core::<AVALANCHE, false, false>(seed, secrets, data); if AVALANCHE { rapid_mix_np::<false>(hash, DEFAULT_SECRETS[1]) } else { hash } } #[inline(always)] #[must_use] pub const fn rapidhash_core<const AVALANCHE: bool, const COMPACT: bool, const PROTECTED: bool>(mut seed: u64, secrets: &[u64; 7], data: &[u8]) -> u64 { if likely(data.len() <= 16) { let mut a = 0; let mut b = 0; if likely(data.len() >= 8) { a = read_u64_np(data, 0); b = read_u64_np(data, data.len() - 8); } else if likely(data.len() >= 4) { a = read_u32_np(data, 0) as u64; b = read_u32_np(data, data.len() - 4) as u64; } else if !data.is_empty() { a = ((data[0] as u64) << 45) | data[data.len() - 1] as u64; b = data[data.len() >> 1] as u64; } seed = seed.wrapping_add(data.len() as u64); rapidhash_finish::<AVALANCHE, PROTECTED>(a, b , seed, secrets) } else { // SAFETY: we have just checked the length is >16 unsafe { rapidhash_core_17_288::<AVALANCHE, COMPACT, PROTECTED>(seed, secrets, data) } } } // Never inline this, keep the small string path as small as possible to improve the inlining // chances of the write_length_prefix and finish functions. If those two don't get inlined, the // overall performance can be 5x worse when hashing a single string under 100 bytes. <=288 inputs // pay the cost of one extra if, and >288 inputs pay one more function call, but this is nominal // in comparison to the overall hashing cost. #[cold] #[inline(never)] #[must_use] const unsafe fn rapidhash_core_17_288<const AVALANCHE: bool, const COMPACT: bool, const PROTECTED: bool>(mut seed: u64, secrets: &[u64; 7], data: &[u8]) -> u64 { // SAFETY: we promise to never call this with <=16 length data to omit some bounds checks. // This is really intended for codegen-units >1 and/or no LTO. assume(data.len() > 16); // This branch is a hack to move the function prologue/epilogue (stack spilling) into the >48 // path as it otherwise unnecessarily hurts the <48 path. // - It slows down aarch64 >48 inputs, where there is no stack spill. // - It speeds up x86_64 by removing the stack spill on the <48 path, but is // slightly slower on the >48 path... I cannot figure out how to move the spill into the >48 // path only but then re-use the already cached <48 path finish. Ideas welcome. // - It makes minimal difference on WASM. #[cfg(not(target_arch = "aarch64"))] if likely(data.len() <= 48) { // SAFETY: data.len() is guaranteed to be >16 return rapidhash_final_48::<AVALANCHE, PROTECTED>(seed, secrets, data, data); } let mut slice = data; if unlikely(data.len() > 48) { if unlikely(data.len() > COLD_PATH_CUTOFF) { // SAFETY: data.len() is guaranteed to be >COLD_PATH_CUTOFF return rapidhash_core_cold::<AVALANCHE, COMPACT, PROTECTED>(seed, secrets, data); } let mut see1 = seed; let mut see2 = seed; while slice.len() >= 48 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); let (_, split) = slice.split_at(48); slice = split; } seed ^= see1 ^ see2; } // SAFETY: data.len() is guaranteed to be >48, and therefore >16 rapidhash_final_48::<AVALANCHE, PROTECTED>(seed, secrets, slice, data) } /// The long path, intentionally kept cold because at this length of data the function call is /// minor, but the complexity of this function — if it were inlined — could prevent x.hash() from /// being inlined which would have a much higher penalty and prevent other optimisations. #[cold] #[inline(never)] #[must_use] const unsafe fn rapidhash_core_cold<const AVALANCHE: bool, const COMPACT: bool, const PROTECTED: bool>(mut seed: u64, secrets: &[u64; 7], data: &[u8]) -> u64 { // SAFETY: we promise to never call this with <=COLD_PATH_CUTOFF length data to omit some bounds checks assume(data.len() > COLD_PATH_CUTOFF); let mut slice = data; let mut see1 = seed; let mut see2 = seed; let mut see3 = seed; let mut see4 = seed; let mut see5 = seed; let mut see6 = seed; if !COMPACT { while slice.len() >= 224 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); see3 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 48) ^ secrets[3], read_u64_np(slice, 56) ^ see3); see4 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 64) ^ secrets[4], read_u64_np(slice, 72) ^ see4); see5 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 80) ^ secrets[5], read_u64_np(slice, 88) ^ see5); see6 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 96) ^ secrets[6], read_u64_np(slice, 104) ^ see6); seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 112) ^ secrets[0], read_u64_np(slice, 120) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 128) ^ secrets[1], read_u64_np(slice, 136) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 144) ^ secrets[2], read_u64_np(slice, 152) ^ see2); see3 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 160) ^ secrets[3], read_u64_np(slice, 168) ^ see3); see4 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 176) ^ secrets[4], read_u64_np(slice, 184) ^ see4); see5 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 192) ^ secrets[5], read_u64_np(slice, 200) ^ see5); see6 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 208) ^ secrets[6], read_u64_np(slice, 216) ^ see6); let (_, split) = slice.split_at(224); slice = split; } if likely(slice.len() >= 112) { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); see3 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 48) ^ secrets[3], read_u64_np(slice, 56) ^ see3); see4 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 64) ^ secrets[4], read_u64_np(slice, 72) ^ see4); see5 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 80) ^ secrets[5], read_u64_np(slice, 88) ^ see5); see6 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 96) ^ secrets[6], read_u64_np(slice, 104) ^ see6); let (_, split) = slice.split_at(112); slice = split; } } else { while slice.len() >= 112 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); see3 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 48) ^ secrets[3], read_u64_np(slice, 56) ^ see3); see4 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 64) ^ secrets[4], read_u64_np(slice, 72) ^ see4); see5 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 80) ^ secrets[5], read_u64_np(slice, 88) ^ see5); see6 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 96) ^ secrets[6], read_u64_np(slice, 104) ^ see6); let (_, split) = slice.split_at(112); slice = split; } } if !COMPACT { if slice.len() >= 48 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); let (_, split) = slice.split_at(48); slice = split; if slice.len() >= 48 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); let (_, split) = slice.split_at(48); slice = split; } } } else { while slice.len() >= 48 { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); see1 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[1], read_u64_np(slice, 24) ^ see1); see2 = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 32) ^ secrets[2], read_u64_np(slice, 40) ^ see2); let (_, split) = slice.split_at(48); slice = split; } } see3 ^= see4; see5 ^= see6; seed ^= see1; see3 ^= see2; seed ^= see5; seed ^= see3; rapidhash_final_48::<AVALANCHE, PROTECTED>(seed, secrets, slice, data) } #[inline(always)] #[must_use] const unsafe fn rapidhash_final_48<const AVALANCHE: bool, const PROTECTED: bool>(mut seed: u64, secrets: &[u64; 7], slice: &[u8], data: &[u8]) -> u64 { // SAFETY: the final 48 byte handling is only called with >16 length data assume(data.len() > 16); if likely(slice.len() > 16) { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 0) ^ secrets[0], read_u64_np(slice, 8) ^ seed); if likely(slice.len() > 32) { seed = rapid_mix_np::<PROTECTED>(read_u64_np(slice, 16) ^ secrets[0], read_u64_np(slice, 24) ^ seed); } } let a = read_u64_np(data, data.len() - 16); let b = read_u64_np(data, data.len() - 8); seed = seed.wrapping_add(data.len() as u64); rapidhash_finish::<AVALANCHE, PROTECTED>(a, b, seed, secrets) } #[inline(always)] #[must_use] const fn rapidhash_finish<const AVALANCHE: bool, const PROTECTED: bool>(mut a: u64, mut b: u64, seed: u64, secrets: &[u64; 7]) -> u64 { a ^= secrets[0]; b ^= seed; (a, b) = rapid_mum_np::<PROTECTED>(a, b); if AVALANCHE { // we keep RAPID_CONST constant as the XOR 0xaa can be done in a single instruction on some // platforms, whereas it would require an additional load for a random secret. rapid_mix_np::<PROTECTED>(a ^ 0xaaaaaaaaaaaaaaaa ^ seed, b ^ secrets[1]) } else { a ^ b } } // ALL OF THE BELOW ARE HINTS AND HELPER FUNCTIONS /// Wraps the `core::hint::likely` intrinsic if the `nightly` feature is enabled. #[inline(always)] pub const fn likely(x: bool) -> bool { #[cfg(feature = "nightly")] { core::hint::likely(x) } #[cfg(not(feature = "nightly"))] { if !x { cold_path(); } x } } /// Wraps the `core::hint::unlikely` intrinsic if the `nightly` feature is enabled. #[inline(always)] pub const fn unlikely(x: bool) -> bool { #[cfg(feature = "nightly")] { core::hint::unlikely(x) } #[cfg(not(feature = "nightly"))] { if x { cold_path(); } x } } #[allow(dead_code)] #[cold] #[inline(always)] const fn cold_path() {} /// Provides a stable `assume` function that uses `core::hint::assert_unchecked` when the stable /// rust compiler supports it. /// /// This is particularly relevant when LLVM isn't able to specialise the >16 input functions. This /// often happens with the default release profile, which uses a large number of codegen units and /// LTO off. #[inline(always)] pub const unsafe fn assume(cond: bool) { debug_assert!(cond); core::hint::assert_unchecked(cond); } /// A macro for assertions that can be disabled with the `unsafe` feature. These should all be /// elided at compile-time anyway. macro_rules! unsafe_assert { ($cond:expr) => { #[cfg(feature = "unsafe")] { debug_assert!($cond); } #[cfg(not(feature = "unsafe"))] { assert!($cond); } }; } /// Unsafe but const-friendly unaligned bytes to u64. The compiler can't seem to remove the bounds /// checks for small integers because we do some funky bit shifting in the indexing. /// /// SAFETY: `slice` must be at least `offset+8` bytes long, which we guarantee in this rapidhash /// implementation. #[inline(always)] pub const fn read_u64_np(slice: &[u8], offset: usize) -> u64 { unsafe_assert!(slice.len() >= 8 + offset); // SAFETY: read_u64_np must always be called in a manner that guarantees the above assertions unsafe { core::ptr::read_unaligned(slice.as_ptr().add(offset) as *const u64) } } /// Unsafe but const-friendly unaligned bytes to u32. The compiler can't seem to remove the bounds /// checks for small integers because we do some funky bit shifting in the indexing. /// /// SAFETY: `slice` must be at least `offset+8` bytes long, which we guarantee in this rapidhash /// implementation. #[inline(always)] pub const fn read_u32_np(slice: &[u8], offset: usize) -> u32 { unsafe_assert!(slice.len() >= 4 + offset); // SAFETY: read_u64_np must always be called in a manner that guarantees the above assertions unsafe { core::ptr::read_unaligned(slice.as_ptr().add(offset) as *const u32) } } /// NON-PORTABLE 64*64 to 128 bit multiply /// /// Returns the (low, high) 64 bits of the 128 bit result. /// /// # Non-portable version /// This version is not portable across all architectures and is intended for use only on the /// in-memory hash functions. /// /// # From the C code: /// Calculates 128-bit C = *A * *B. /// /// When RAPIDHASH_FAST is defined: /// Overwrites A contents with C's low 64 bits. /// Overwrites B contents with C's high 64 bits. /// /// When RAPIDHASH_PROTECTED is defined: /// Xors and overwrites A contents with C's low 64 bits. /// Xors and overwrites B contents with C's high 64 bits. #[inline(always)] #[must_use] pub const fn rapid_mum_np<const PROTECTED: bool>(a: u64, b: u64) -> (u64, u64) { #[cfg(any( all( target_pointer_width = "64", not(any(target_arch = "sparc64", target_arch = "wasm64")), ), target_arch = "aarch64", target_arch = "x86_64", all(target_family = "wasm", target_feature = "wide-arithmetic"), ))] { let r = (a as u128).wrapping_mul(b as u128); if !PROTECTED { (r as u64, (r >> 64) as u64) } else { (a ^ r as u64, b ^ (r >> 64) as u64) } } #[cfg(not(any( all( target_pointer_width = "64", not(any(target_arch = "sparc64", target_arch = "wasm64")), ), target_arch = "aarch64", target_arch = "x86_64", all(target_family = "wasm", target_feature = "wide-arithmetic"), )))] { // u64 x u64 -> u128 product is quite expensive on 32-bit. // We approximate it by expanding the multiplication and eliminating // carries by replacing additions with XORs: // (2^32 hx + lx)*(2^32 hy + ly) = // 2^64 hx*hy + 2^32 (hx*ly + lx*hy) + lx*ly ~= // 2^64 hx*hy ^ 2^32 (hx*ly ^ lx*hy) ^ lx*ly // Which when folded becomes: // (hx*hy ^ lx*ly) ^ (hx*ly ^ lx*hy).rotate_right(32) let lx = a as u32; let ly = b as u32; let hx = (a >> 32) as u32; let hy = (b >> 32) as u32; let ll = (lx as u64).wrapping_mul(ly as u64); let lh = (lx as u64).wrapping_mul(hy as u64); let hl = (hx as u64).wrapping_mul(ly as u64); let hh = (hx as u64).wrapping_mul(hy as u64); if !PROTECTED { ((hh ^ ll), (hl ^ lh).rotate_right(32)) } else { // If protected, we XOR the inputs with the results. // This is to ensure that the inputs are not recoverable from the output. ((a ^ hh ^ ll), (b ^ hl ^ lh).rotate_right(32)) } } } /// NON-PORTABLE Folded 64-bit multiply. [rapid_mum] then XOR the results together. /// /// # Non-portable version /// This version is not portable across all architectures and is intended for use only on the /// in-memory hash functions. #[inline(always)] #[must_use] pub const fn rapid_mix_np<const PROTECTED: bool>(a: u64, b: u64) -> u64 { #[cfg(any( all( target_pointer_width = "64", not(any(target_arch = "sparc64", target_arch = "wasm64")), ), target_arch = "aarch64", target_arch = "x86_64", all(target_family = "wasm", target_feature = "wide-arithmetic"), ))] { let r = (a as u128).wrapping_mul(b as u128); if !PROTECTED { (r as u64) ^ (r >> 64) as u64 } else { (a ^ r as u64) ^ (b ^ (r >> 64) as u64) } } #[cfg(not(any( all( target_pointer_width = "64", not(any(target_arch = "sparc64", target_arch = "wasm64")), ), target_arch = "aarch64", target_arch = "x86_64", all(target_family = "wasm", target_feature = "wide-arithmetic"), )))] { // u64 x u64 -> u128 product is quite expensive on 32-bit. // We approximate it by expanding the multiplication and eliminating // carries by replacing additions with XORs: // (2^32 hx + lx)*(2^32 hy + ly) = // 2^64 hx*hy + 2^32 (hx*ly + lx*hy) + lx*ly ~= // 2^64 hx*hy ^ 2^32 (hx*ly ^ lx*hy) ^ lx*ly // Which when folded becomes: // (hx*hy ^ lx*ly) ^ (hx*ly ^ lx*hy).rotate_right(32) let lx = a as u32; let ly = b as u32; let hx = (a >> 32) as u32; let hy = (b >> 32) as u32; let ll = (lx as u64).wrapping_mul(ly as u64); let lh = (lx as u64).wrapping_mul(hy as u64); let hl = (hx as u64).wrapping_mul(ly as u64); let hh = (hx as u64).wrapping_mul(hy as u64); if !PROTECTED { (hh ^ ll) ^ (hl ^ lh).rotate_right(32) } else { // If protected, we XOR the inputs with the results. // This is to ensure that the inputs are not recoverable from the output. (a ^ hh ^ ll) ^ (b ^ hl ^ lh).rotate_right(32) } } }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Compiler Explorer Shop
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
CE on Bluesky
Statistics
Changelog
Version tree