1 | //! An implementation of SipHash. |
2 | |
3 | #![allow (deprecated)] // the types in this module are deprecated |
4 | |
5 | use crate::cmp; |
6 | use crate::marker::PhantomData; |
7 | use crate::mem; |
8 | use crate::ptr; |
9 | |
10 | /// An implementation of SipHash 1-3. |
11 | /// |
12 | /// This is currently the default hashing function used by standard library |
13 | /// (e.g., `collections::HashMap` uses it by default). |
14 | /// |
15 | /// See: <https://131002.net/siphash> |
16 | #[unstable (feature = "hashmap_internals" , issue = "none" )] |
17 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
18 | #[derive (Debug, Clone, Default)] |
19 | #[doc (hidden)] |
20 | pub struct SipHasher13 { |
21 | hasher: Hasher<Sip13Rounds>, |
22 | } |
23 | |
24 | /// An implementation of SipHash 2-4. |
25 | /// |
26 | /// See: <https://131002.net/siphash/> |
27 | #[unstable (feature = "hashmap_internals" , issue = "none" )] |
28 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
29 | #[derive (Debug, Clone, Default)] |
30 | struct SipHasher24 { |
31 | hasher: Hasher<Sip24Rounds>, |
32 | } |
33 | |
34 | /// An implementation of SipHash 2-4. |
35 | /// |
36 | /// See: <https://131002.net/siphash/> |
37 | /// |
38 | /// SipHash is a general-purpose hashing function: it runs at a good |
39 | /// speed (competitive with Spooky and City) and permits strong _keyed_ |
40 | /// hashing. This lets you key your hash tables from a strong RNG, such as |
41 | /// [`rand::os::OsRng`](https://docs.rs/rand/latest/rand/rngs/struct.OsRng.html). |
42 | /// |
43 | /// Although the SipHash algorithm is considered to be generally strong, |
44 | /// it is not intended for cryptographic purposes. As such, all |
45 | /// cryptographic uses of this implementation are _strongly discouraged_. |
46 | #[stable (feature = "rust1" , since = "1.0.0" )] |
47 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
48 | #[derive (Debug, Clone, Default)] |
49 | pub struct SipHasher(SipHasher24); |
50 | |
51 | #[derive (Debug)] |
52 | struct Hasher<S: Sip> { |
53 | k0: u64, |
54 | k1: u64, |
55 | length: usize, // how many bytes we've processed |
56 | state: State, // hash State |
57 | tail: u64, // unprocessed bytes le |
58 | ntail: usize, // how many bytes in tail are valid |
59 | _marker: PhantomData<S>, |
60 | } |
61 | |
62 | #[derive (Debug, Clone, Copy)] |
63 | #[repr (C)] |
64 | struct State { |
65 | // v0, v2 and v1, v3 show up in pairs in the algorithm, |
66 | // and simd implementations of SipHash will use vectors |
67 | // of v02 and v13. By placing them in this order in the struct, |
68 | // the compiler can pick up on just a few simd optimizations by itself. |
69 | v0: u64, |
70 | v2: u64, |
71 | v1: u64, |
72 | v3: u64, |
73 | } |
74 | |
75 | macro_rules! compress { |
76 | ($state:expr) => {{ compress!($state.v0, $state.v1, $state.v2, $state.v3) }}; |
77 | ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{ |
78 | $v0 = $v0.wrapping_add($v1); |
79 | $v1 = $v1.rotate_left(13); |
80 | $v1 ^= $v0; |
81 | $v0 = $v0.rotate_left(32); |
82 | $v2 = $v2.wrapping_add($v3); |
83 | $v3 = $v3.rotate_left(16); |
84 | $v3 ^= $v2; |
85 | $v0 = $v0.wrapping_add($v3); |
86 | $v3 = $v3.rotate_left(21); |
87 | $v3 ^= $v0; |
88 | $v2 = $v2.wrapping_add($v1); |
89 | $v1 = $v1.rotate_left(17); |
90 | $v1 ^= $v2; |
91 | $v2 = $v2.rotate_left(32); |
92 | }}; |
93 | } |
94 | |
95 | /// Loads an integer of the desired type from a byte stream, in LE order. Uses |
96 | /// `copy_nonoverlapping` to let the compiler generate the most efficient way |
97 | /// to load it from a possibly unaligned address. |
98 | /// |
99 | /// Safety: this performs unchecked indexing of `$buf` at |
100 | /// `$i..$i+size_of::<$int_ty>()`, so that must be in-bounds. |
101 | macro_rules! load_int_le { |
102 | ($buf:expr, $i:expr, $int_ty:ident) => {{ |
103 | debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len()); |
104 | let mut data = 0 as $int_ty; |
105 | ptr::copy_nonoverlapping( |
106 | $buf.as_ptr().add($i), |
107 | &mut data as *mut _ as *mut u8, |
108 | mem::size_of::<$int_ty>(), |
109 | ); |
110 | data.to_le() |
111 | }}; |
112 | } |
113 | |
114 | /// Loads a u64 using up to 7 bytes of a byte slice. It looks clumsy but the |
115 | /// `copy_nonoverlapping` calls that occur (via `load_int_le!`) all have fixed |
116 | /// sizes and avoid calling `memcpy`, which is good for speed. |
117 | /// |
118 | /// Safety: this performs unchecked indexing of `buf` at `start..start+len`, so |
119 | /// that must be in-bounds. |
120 | #[inline ] |
121 | unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 { |
122 | debug_assert!(len < 8); |
123 | let mut i: usize = 0; // current byte index (from LSB) in the output u64 |
124 | let mut out: u64 = 0; |
125 | if i + 3 < len { |
126 | // SAFETY: `i` cannot be greater than `len`, and the caller must guarantee |
127 | // that the index start..start+len is in bounds. |
128 | out = unsafe { load_int_le!(buf, start + i, u32) } as u64; |
129 | i += 4; |
130 | } |
131 | if i + 1 < len { |
132 | // SAFETY: same as above. |
133 | out |= (unsafe { load_int_le!(buf, start + i, u16) } as u64) << (i * 8); |
134 | i += 2 |
135 | } |
136 | if i < len { |
137 | // SAFETY: same as above. |
138 | out |= (unsafe { *buf.get_unchecked(index:start + i) } as u64) << (i * 8); |
139 | i += 1; |
140 | } |
141 | //FIXME(fee1-dead): use debug_assert_eq |
142 | debug_assert!(i == len); |
143 | out |
144 | } |
145 | |
146 | impl SipHasher { |
147 | /// Creates a new `SipHasher` with the two initial keys set to 0. |
148 | #[inline ] |
149 | #[stable (feature = "rust1" , since = "1.0.0" )] |
150 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
151 | #[rustc_const_unstable (feature = "const_hash" , issue = "104061" )] |
152 | #[must_use ] |
153 | pub const fn new() -> SipHasher { |
154 | SipHasher::new_with_keys(key0:0, key1:0) |
155 | } |
156 | |
157 | /// Creates a `SipHasher` that is keyed off the provided keys. |
158 | #[inline ] |
159 | #[stable (feature = "rust1" , since = "1.0.0" )] |
160 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
161 | #[rustc_const_unstable (feature = "const_hash" , issue = "104061" )] |
162 | #[must_use ] |
163 | pub const fn new_with_keys(key0: u64, key1: u64) -> SipHasher { |
164 | SipHasher(SipHasher24 { hasher: Hasher::new_with_keys(key0, key1) }) |
165 | } |
166 | } |
167 | |
168 | impl SipHasher13 { |
169 | /// Creates a new `SipHasher13` with the two initial keys set to 0. |
170 | #[inline ] |
171 | #[unstable (feature = "hashmap_internals" , issue = "none" )] |
172 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
173 | #[rustc_const_unstable (feature = "const_hash" , issue = "104061" )] |
174 | pub const fn new() -> SipHasher13 { |
175 | SipHasher13::new_with_keys(key0:0, key1:0) |
176 | } |
177 | |
178 | /// Creates a `SipHasher13` that is keyed off the provided keys. |
179 | #[inline ] |
180 | #[unstable (feature = "hashmap_internals" , issue = "none" )] |
181 | #[deprecated (since = "1.13.0" , note = "use `std::hash::DefaultHasher` instead" )] |
182 | #[rustc_const_unstable (feature = "const_hash" , issue = "104061" )] |
183 | pub const fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 { |
184 | SipHasher13 { hasher: Hasher::new_with_keys(key0, key1) } |
185 | } |
186 | } |
187 | |
188 | impl<S: Sip> Hasher<S> { |
189 | #[inline ] |
190 | const fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> { |
191 | let mut state = Hasher { |
192 | k0: key0, |
193 | k1: key1, |
194 | length: 0, |
195 | state: State { v0: 0, v1: 0, v2: 0, v3: 0 }, |
196 | tail: 0, |
197 | ntail: 0, |
198 | _marker: PhantomData, |
199 | }; |
200 | state.reset(); |
201 | state |
202 | } |
203 | |
204 | #[inline ] |
205 | const fn reset(&mut self) { |
206 | self.length = 0; |
207 | self.state.v0 = self.k0 ^ 0x736f6d6570736575; |
208 | self.state.v1 = self.k1 ^ 0x646f72616e646f6d; |
209 | self.state.v2 = self.k0 ^ 0x6c7967656e657261; |
210 | self.state.v3 = self.k1 ^ 0x7465646279746573; |
211 | self.ntail = 0; |
212 | } |
213 | } |
214 | |
215 | #[stable (feature = "rust1" , since = "1.0.0" )] |
216 | impl super::Hasher for SipHasher { |
217 | #[inline ] |
218 | fn write(&mut self, msg: &[u8]) { |
219 | self.0.hasher.write(bytes:msg) |
220 | } |
221 | |
222 | #[inline ] |
223 | fn write_str(&mut self, s: &str) { |
224 | self.0.hasher.write_str(s); |
225 | } |
226 | |
227 | #[inline ] |
228 | fn finish(&self) -> u64 { |
229 | self.0.hasher.finish() |
230 | } |
231 | } |
232 | |
233 | #[unstable (feature = "hashmap_internals" , issue = "none" )] |
234 | impl super::Hasher for SipHasher13 { |
235 | #[inline ] |
236 | fn write(&mut self, msg: &[u8]) { |
237 | self.hasher.write(bytes:msg) |
238 | } |
239 | |
240 | #[inline ] |
241 | fn write_str(&mut self, s: &str) { |
242 | self.hasher.write_str(s); |
243 | } |
244 | |
245 | #[inline ] |
246 | fn finish(&self) -> u64 { |
247 | self.hasher.finish() |
248 | } |
249 | } |
250 | |
251 | impl<S: Sip> super::Hasher for Hasher<S> { |
252 | // Note: no integer hashing methods (`write_u*`, `write_i*`) are defined |
253 | // for this type. We could add them, copy the `short_write` implementation |
254 | // in librustc_data_structures/sip128.rs, and add `write_u*`/`write_i*` |
255 | // methods to `SipHasher`, `SipHasher13`, and `DefaultHasher`. This would |
256 | // greatly speed up integer hashing by those hashers, at the cost of |
257 | // slightly slowing down compile speeds on some benchmarks. See #69152 for |
258 | // details. |
259 | #[inline ] |
260 | fn write(&mut self, msg: &[u8]) { |
261 | let length = msg.len(); |
262 | self.length += length; |
263 | |
264 | let mut needed = 0; |
265 | |
266 | if self.ntail != 0 { |
267 | needed = 8 - self.ntail; |
268 | // SAFETY: `cmp::min(length, needed)` is guaranteed to not be over `length` |
269 | self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << (8 * self.ntail); |
270 | if length < needed { |
271 | self.ntail += length; |
272 | return; |
273 | } else { |
274 | self.state.v3 ^= self.tail; |
275 | S::c_rounds(&mut self.state); |
276 | self.state.v0 ^= self.tail; |
277 | self.ntail = 0; |
278 | } |
279 | } |
280 | |
281 | // Buffered tail is now flushed, process new input. |
282 | let len = length - needed; |
283 | let left = len & 0x7; // len % 8 |
284 | |
285 | let mut i = needed; |
286 | while i < len - left { |
287 | // SAFETY: because `len - left` is the biggest multiple of 8 under |
288 | // `len`, and because `i` starts at `needed` where `len` is `length - needed`, |
289 | // `i + 8` is guaranteed to be less than or equal to `length`. |
290 | let mi = unsafe { load_int_le!(msg, i, u64) }; |
291 | |
292 | self.state.v3 ^= mi; |
293 | S::c_rounds(&mut self.state); |
294 | self.state.v0 ^= mi; |
295 | |
296 | i += 8; |
297 | } |
298 | |
299 | // SAFETY: `i` is now `needed + len.div_euclid(8) * 8`, |
300 | // so `i + left` = `needed + len` = `length`, which is by |
301 | // definition equal to `msg.len()`. |
302 | self.tail = unsafe { u8to64_le(msg, i, left) }; |
303 | self.ntail = left; |
304 | } |
305 | |
306 | #[inline ] |
307 | fn write_str(&mut self, s: &str) { |
308 | // This hasher works byte-wise, and `0xFF` cannot show up in a `str`, |
309 | // so just hashing the one extra byte is enough to be prefix-free. |
310 | self.write(s.as_bytes()); |
311 | self.write_u8(0xFF); |
312 | } |
313 | |
314 | #[inline ] |
315 | fn finish(&self) -> u64 { |
316 | let mut state = self.state; |
317 | |
318 | let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail; |
319 | |
320 | state.v3 ^= b; |
321 | S::c_rounds(&mut state); |
322 | state.v0 ^= b; |
323 | |
324 | state.v2 ^= 0xff; |
325 | S::d_rounds(&mut state); |
326 | |
327 | state.v0 ^ state.v1 ^ state.v2 ^ state.v3 |
328 | } |
329 | } |
330 | |
331 | impl<S: Sip> Clone for Hasher<S> { |
332 | #[inline ] |
333 | fn clone(&self) -> Hasher<S> { |
334 | Hasher { |
335 | k0: self.k0, |
336 | k1: self.k1, |
337 | length: self.length, |
338 | state: self.state, |
339 | tail: self.tail, |
340 | ntail: self.ntail, |
341 | _marker: self._marker, |
342 | } |
343 | } |
344 | } |
345 | |
346 | impl<S: Sip> Default for Hasher<S> { |
347 | /// Creates a `Hasher<S>` with the two initial keys set to 0. |
348 | #[inline ] |
349 | fn default() -> Hasher<S> { |
350 | Hasher::new_with_keys(key0:0, key1:0) |
351 | } |
352 | } |
353 | |
354 | #[doc (hidden)] |
355 | trait Sip { |
356 | fn c_rounds(_: &mut State); |
357 | fn d_rounds(_: &mut State); |
358 | } |
359 | |
360 | #[derive (Debug, Clone, Default)] |
361 | struct Sip13Rounds; |
362 | |
363 | impl Sip for Sip13Rounds { |
364 | #[inline ] |
365 | fn c_rounds(state: &mut State) { |
366 | compress!(state); |
367 | } |
368 | |
369 | #[inline ] |
370 | fn d_rounds(state: &mut State) { |
371 | compress!(state); |
372 | compress!(state); |
373 | compress!(state); |
374 | } |
375 | } |
376 | |
377 | #[derive (Debug, Clone, Default)] |
378 | struct Sip24Rounds; |
379 | |
380 | impl Sip for Sip24Rounds { |
381 | #[inline ] |
382 | fn c_rounds(state: &mut State) { |
383 | compress!(state); |
384 | compress!(state); |
385 | } |
386 | |
387 | #[inline ] |
388 | fn d_rounds(state: &mut State) { |
389 | compress!(state); |
390 | compress!(state); |
391 | compress!(state); |
392 | compress!(state); |
393 | } |
394 | } |
395 | |