1//! An implementation of SipHash.
2
3#![allow(deprecated)] // the types in this module are deprecated
4
5use crate::cmp;
6use crate::marker::PhantomData;
7use crate::mem;
8use 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)]
20pub 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)]
30struct 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)]
49pub struct SipHasher(SipHasher24);
50
51#[derive(Debug)]
52struct 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)]
64struct 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
75macro_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.
101macro_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]
121unsafe 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
146impl 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
168impl 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
188impl<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")]
216impl 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")]
234impl 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
251impl<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
331impl<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
346impl<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)]
355trait Sip {
356 fn c_rounds(_: &mut State);
357 fn d_rounds(_: &mut State);
358}
359
360#[derive(Debug, Clone, Default)]
361struct Sip13Rounds;
362
363impl 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)]
378struct Sip24Rounds;
379
380impl 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