feoxdb/utils/
hash.rs

1use std::hash::Hasher;
2
3const C1: u32 = 0xcc9e2d51;
4const C2: u32 = 0x1b873593;
5const R1: u32 = 15;
6const R2: u32 = 13;
7const M: u32 = 5;
8const N: u32 = 0xe6546b64;
9
10#[inline(always)]
11pub fn murmur3_32(key: &[u8], seed: u32) -> u32 {
12    let mut h = seed;
13    let mut chunks = key.chunks_exact(4);
14
15    for chunk in chunks.by_ref() {
16        let mut k = u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
17        k = k.wrapping_mul(C1);
18        k = k.rotate_left(R1);
19        k = k.wrapping_mul(C2);
20
21        h ^= k;
22        h = h.rotate_left(R2);
23        h = h.wrapping_mul(M).wrapping_add(N);
24    }
25
26    let remainder = chunks.remainder();
27    if !remainder.is_empty() {
28        let mut k = 0u32;
29        for (i, &byte) in remainder.iter().enumerate() {
30            k |= (byte as u32) << (i * 8);
31        }
32
33        k = k.wrapping_mul(C1);
34        k = k.rotate_left(R1);
35        k = k.wrapping_mul(C2);
36        h ^= k;
37    }
38
39    h ^= key.len() as u32;
40    h ^= h >> 16;
41    h = h.wrapping_mul(0x85ebca6b);
42    h ^= h >> 13;
43    h = h.wrapping_mul(0xc2b2ae35);
44    h ^= h >> 16;
45
46    h
47}
48
49/// Compute hash of a key using the best available method.
50///
51/// On x86_64 CPUs with AES-NI support, uses hardware-accelerated hashing.
52/// Otherwise falls back to MurmurHash3.
53pub fn hash_key(key: &[u8]) -> u32 {
54    #[cfg(target_arch = "x86_64")]
55    {
56        if let Some(hash) = simd::hash_key_aes_safe(key) {
57            return hash;
58        }
59    }
60    murmur3_32(key, 0)
61}
62
63#[cfg(target_arch = "x86_64")]
64pub mod simd {
65    use std::arch::x86_64::*;
66
67    /// Compute hash using AES-NI instructions for better performance.
68    ///
69    /// Returns None if AES-NI is not supported on this CPU.
70    pub fn hash_key_aes_safe(key: &[u8]) -> Option<u32> {
71        if is_x86_feature_detected!("aes") {
72            unsafe { Some(hash_key_aes_unsafe(key)) }
73        } else {
74            None
75        }
76    }
77
78    /// Compute hash using AES-NI instructions for better performance.
79    ///
80    /// # Safety
81    ///
82    /// This function requires the CPU to support AES-NI instructions.
83    /// The caller must ensure that the CPU supports AES-NI before calling this function.
84    /// This is typically checked using `is_x86_feature_detected!("aes")`.
85    #[target_feature(enable = "aes")]
86    #[inline]
87    unsafe fn hash_key_aes_unsafe(key: &[u8]) -> u32 {
88        // Use a non-zero initial seed for better distribution
89        let seed = _mm_set_epi32(
90            0x9747b28c_u32 as i32,
91            0xc2b2ae35_u32 as i32,
92            0x85ebca6b_u32 as i32,
93            0xe6546b64_u32 as i32,
94        );
95        let mut hash = seed;
96
97        // Process full 16-byte chunks
98        let mut chunks = key.chunks_exact(16);
99        for chunk in chunks.by_ref() {
100            let data = _mm_loadu_si128(chunk.as_ptr() as *const __m128i);
101            // Mix the data with XOR before AES round
102            hash = _mm_xor_si128(hash, data);
103            // Apply AES round
104            hash = _mm_aesenc_si128(hash, seed);
105        }
106
107        // Handle remainder
108        let remainder = chunks.remainder();
109        if !remainder.is_empty() {
110            let mut buffer = [0u8; 16];
111            buffer[..remainder.len()].copy_from_slice(remainder);
112            // Mix in the length of remainder for better distribution
113            buffer[15] = remainder.len() as u8;
114
115            let data = _mm_loadu_si128(buffer.as_ptr() as *const __m128i);
116            hash = _mm_xor_si128(hash, data);
117            hash = _mm_aesenc_si128(hash, seed);
118        }
119
120        // Final mixing: incorporate key length
121        let len_vec = _mm_set1_epi32(key.len() as i32);
122        hash = _mm_xor_si128(hash, len_vec);
123        hash = _mm_aesenc_si128(hash, seed);
124
125        // Extract and mix all 4 32-bit parts for better distribution
126        let a = _mm_extract_epi32(hash, 0) as u32;
127        let b = _mm_extract_epi32(hash, 1) as u32;
128        let c = _mm_extract_epi32(hash, 2) as u32;
129        let d = _mm_extract_epi32(hash, 3) as u32;
130
131        // Final mixing similar to MurmurHash3 finalizer
132        let mut h = a ^ b ^ c ^ d;
133        h ^= h >> 16;
134        h = h.wrapping_mul(0x85ebca6b);
135        h ^= h >> 13;
136        h = h.wrapping_mul(0xc2b2ae35);
137        h ^= h >> 16;
138
139        h
140    }
141}
142
143pub struct MurmurHasher {
144    state: u32,
145}
146
147impl Default for MurmurHasher {
148    fn default() -> Self {
149        Self::new()
150    }
151}
152
153impl MurmurHasher {
154    pub fn new() -> Self {
155        Self { state: 0 }
156    }
157
158    pub fn with_seed(seed: u32) -> Self {
159        Self { state: seed }
160    }
161}
162
163impl Hasher for MurmurHasher {
164    fn write(&mut self, bytes: &[u8]) {
165        self.state = murmur3_32(bytes, self.state);
166    }
167
168    fn finish(&self) -> u64 {
169        self.state as u64
170    }
171}
feoxdb/utils/hash.rs

feoxdb/utils/
hash.rs
