]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
1a4d82fc | 10 | |
3157f602 | 11 | //! An implementation of SipHash. |
1a4d82fc | 12 | |
9e0c209e | 13 | #![allow(deprecated)] |
e9174d1e | 14 | |
3157f602 | 15 | use marker::PhantomData; |
c1a9b12d | 16 | use ptr; |
c30ab7b3 SL |
17 | use cmp; |
18 | use mem; | |
3157f602 XL |
19 | |
20 | /// An implementation of SipHash 1-3. | |
21 | /// | |
c30ab7b3 SL |
22 | /// This is currently the default hashing function used by standard library |
23 | /// (eg. `collections::HashMap` uses it by default). | |
24 | /// | |
3157f602 | 25 | /// See: https://131002.net/siphash/ |
5bcae85e | 26 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
27 | #[rustc_deprecated(since = "1.13.0", |
28 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
29 | #[derive(Debug, Clone, Default)] |
30 | pub struct SipHasher13 { | |
31 | hasher: Hasher<Sip13Rounds>, | |
32 | } | |
33 | ||
34 | /// An implementation of SipHash 2-4. | |
35 | /// | |
36 | /// See: https://131002.net/siphash/ | |
5bcae85e | 37 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
38 | #[rustc_deprecated(since = "1.13.0", |
39 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
40 | #[derive(Debug, Clone, Default)] |
41 | pub struct SipHasher24 { | |
42 | hasher: Hasher<Sip24Rounds>, | |
43 | } | |
1a4d82fc JJ |
44 | |
45 | /// An implementation of SipHash 2-4. | |
46 | /// | |
54a0048b | 47 | /// See: https://131002.net/siphash/ |
1a4d82fc | 48 | /// |
54a0048b SL |
49 | /// SipHash is a general-purpose hashing function: it runs at a good |
50 | /// speed (competitive with Spooky and City) and permits strong _keyed_ | |
51 | /// hashing. This lets you key your hashtables from a strong RNG, such as | |
52 | /// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html). | |
53 | /// | |
54 | /// Although the SipHash algorithm is considered to be generally strong, | |
55 | /// it is not intended for cryptographic purposes. As such, all | |
56 | /// cryptographic uses of this implementation are _strongly discouraged_. | |
85aaf69f | 57 | #[stable(feature = "rust1", since = "1.0.0")] |
c30ab7b3 SL |
58 | #[rustc_deprecated(since = "1.13.0", |
59 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
60 | #[derive(Debug, Clone, Default)] |
61 | pub struct SipHasher(SipHasher24); | |
62 | ||
63 | #[derive(Debug)] | |
64 | struct Hasher<S: Sip> { | |
1a4d82fc JJ |
65 | k0: u64, |
66 | k1: u64, | |
c34b1796 | 67 | length: usize, // how many bytes we've processed |
3157f602 XL |
68 | state: State, // hash State |
69 | tail: u64, // unprocessed bytes le | |
70 | ntail: usize, // how many bytes in tail are valid | |
71 | _marker: PhantomData<S>, | |
72 | } | |
73 | ||
74 | #[derive(Debug, Clone, Copy)] | |
75 | struct State { | |
c1a9b12d SL |
76 | // v0, v2 and v1, v3 show up in pairs in the algorithm, |
77 | // and simd implementations of SipHash will use vectors | |
78 | // of v02 and v13. By placing them in this order in the struct, | |
79 | // the compiler can pick up on just a few simd optimizations by itself. | |
3157f602 | 80 | v0: u64, |
1a4d82fc | 81 | v2: u64, |
c1a9b12d | 82 | v1: u64, |
1a4d82fc | 83 | v3: u64, |
1a4d82fc JJ |
84 | } |
85 | ||
c30ab7b3 SL |
86 | macro_rules! compress { |
87 | ($state:expr) => ({ | |
88 | compress!($state.v0, $state.v1, $state.v2, $state.v3) | |
89 | }); | |
90 | ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => | |
1a4d82fc | 91 | ({ |
c30ab7b3 SL |
92 | $v0 = $v0.wrapping_add($v1); $v1 = $v1.rotate_left(13); $v1 ^= $v0; |
93 | $v0 = $v0.rotate_left(32); | |
94 | $v2 = $v2.wrapping_add($v3); $v3 = $v3.rotate_left(16); $v3 ^= $v2; | |
95 | $v0 = $v0.wrapping_add($v3); $v3 = $v3.rotate_left(21); $v3 ^= $v0; | |
96 | $v2 = $v2.wrapping_add($v1); $v1 = $v1.rotate_left(17); $v1 ^= $v2; | |
97 | $v2 = $v2.rotate_left(32); | |
1a4d82fc JJ |
98 | }); |
99 | } | |
100 | ||
c30ab7b3 | 101 | /// Load an integer of the desired type from a byte stream, in LE order. Uses |
c1a9b12d | 102 | /// `copy_nonoverlapping` to let the compiler generate the most efficient way |
c30ab7b3 | 103 | /// to load it from a possibly unaligned address. |
c1a9b12d | 104 | /// |
c30ab7b3 SL |
105 | /// Unsafe because: unchecked indexing at i..i+size_of(int_ty) |
106 | macro_rules! load_int_le { | |
107 | ($buf:expr, $i:expr, $int_ty:ident) => | |
1a4d82fc | 108 | ({ |
c30ab7b3 SL |
109 | debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len()); |
110 | let mut data = 0 as $int_ty; | |
111 | ptr::copy_nonoverlapping($buf.get_unchecked($i), | |
112 | &mut data as *mut _ as *mut u8, | |
113 | mem::size_of::<$int_ty>()); | |
114 | data.to_le() | |
3157f602 | 115 | }); |
1a4d82fc JJ |
116 | } |
117 | ||
c30ab7b3 SL |
118 | /// Load an u64 using up to 7 bytes of a byte slice. |
119 | /// | |
120 | /// Unsafe because: unchecked indexing at start..start+len | |
121 | #[inline] | |
122 | unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 { | |
123 | debug_assert!(len < 8); | |
124 | let mut i = 0; // current byte index (from LSB) in the output u64 | |
125 | let mut out = 0; | |
126 | if i + 3 < len { | |
127 | out = load_int_le!(buf, start + i, u32) as u64; | |
128 | i += 4; | |
129 | } | |
130 | if i + 1 < len { | |
131 | out |= (load_int_le!(buf, start + i, u16) as u64) << (i * 8); | |
132 | i += 2 | |
133 | } | |
134 | if i < len { | |
135 | out |= (*buf.get_unchecked(start + i) as u64) << (i * 8); | |
136 | i += 1; | |
137 | } | |
138 | debug_assert_eq!(i, len); | |
139 | out | |
140 | } | |
141 | ||
1a4d82fc JJ |
142 | impl SipHasher { |
143 | /// Creates a new `SipHasher` with the two initial keys set to 0. | |
144 | #[inline] | |
85aaf69f | 145 | #[stable(feature = "rust1", since = "1.0.0")] |
c30ab7b3 SL |
146 | #[rustc_deprecated(since = "1.13.0", |
147 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
1a4d82fc JJ |
148 | pub fn new() -> SipHasher { |
149 | SipHasher::new_with_keys(0, 0) | |
150 | } | |
151 | ||
152 | /// Creates a `SipHasher` that is keyed off the provided keys. | |
153 | #[inline] | |
85aaf69f | 154 | #[stable(feature = "rust1", since = "1.0.0")] |
c30ab7b3 SL |
155 | #[rustc_deprecated(since = "1.13.0", |
156 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
1a4d82fc | 157 | pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher { |
3157f602 XL |
158 | SipHasher(SipHasher24::new_with_keys(key0, key1)) |
159 | } | |
160 | } | |
161 | ||
3157f602 XL |
162 | impl SipHasher13 { |
163 | /// Creates a new `SipHasher13` with the two initial keys set to 0. | |
164 | #[inline] | |
5bcae85e | 165 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
166 | #[rustc_deprecated(since = "1.13.0", |
167 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
168 | pub fn new() -> SipHasher13 { |
169 | SipHasher13::new_with_keys(0, 0) | |
170 | } | |
171 | ||
172 | /// Creates a `SipHasher13` that is keyed off the provided keys. | |
173 | #[inline] | |
5bcae85e | 174 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
175 | #[rustc_deprecated(since = "1.13.0", |
176 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
177 | pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 { |
178 | SipHasher13 { | |
179 | hasher: Hasher::new_with_keys(key0, key1) | |
180 | } | |
181 | } | |
182 | } | |
183 | ||
184 | impl SipHasher24 { | |
185 | /// Creates a new `SipHasher24` with the two initial keys set to 0. | |
186 | #[inline] | |
5bcae85e | 187 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
188 | #[rustc_deprecated(since = "1.13.0", |
189 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
190 | pub fn new() -> SipHasher24 { |
191 | SipHasher24::new_with_keys(0, 0) | |
192 | } | |
193 | ||
194 | /// Creates a `SipHasher24` that is keyed off the provided keys. | |
195 | #[inline] | |
5bcae85e | 196 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
c30ab7b3 SL |
197 | #[rustc_deprecated(since = "1.13.0", |
198 | reason = "use `std::collections::hash_map::DefaultHasher` instead")] | |
3157f602 XL |
199 | pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 { |
200 | SipHasher24 { | |
201 | hasher: Hasher::new_with_keys(key0, key1) | |
202 | } | |
203 | } | |
204 | } | |
205 | ||
206 | impl<S: Sip> Hasher<S> { | |
207 | #[inline] | |
208 | fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> { | |
209 | let mut state = Hasher { | |
1a4d82fc JJ |
210 | k0: key0, |
211 | k1: key1, | |
212 | length: 0, | |
3157f602 XL |
213 | state: State { |
214 | v0: 0, | |
215 | v1: 0, | |
216 | v2: 0, | |
217 | v3: 0, | |
218 | }, | |
1a4d82fc JJ |
219 | tail: 0, |
220 | ntail: 0, | |
3157f602 | 221 | _marker: PhantomData, |
1a4d82fc JJ |
222 | }; |
223 | state.reset(); | |
224 | state | |
225 | } | |
226 | ||
d9579d0f | 227 | #[inline] |
85aaf69f SL |
228 | fn reset(&mut self) { |
229 | self.length = 0; | |
3157f602 XL |
230 | self.state.v0 = self.k0 ^ 0x736f6d6570736575; |
231 | self.state.v1 = self.k1 ^ 0x646f72616e646f6d; | |
232 | self.state.v2 = self.k0 ^ 0x6c7967656e657261; | |
233 | self.state.v3 = self.k1 ^ 0x7465646279746573; | |
85aaf69f SL |
234 | self.ntail = 0; |
235 | } | |
c30ab7b3 SL |
236 | |
237 | // Specialized write function that is only valid for buffers with len <= 8. | |
238 | // It's used to force inlining of write_u8 and write_usize, those would normally be inlined | |
239 | // except for composite types (that includes slices and str hashing because of delimiter). | |
240 | // Without this extra push the compiler is very reluctant to inline delimiter writes, | |
241 | // degrading performance substantially for the most common use cases. | |
242 | #[inline(always)] | |
243 | fn short_write(&mut self, msg: &[u8]) { | |
244 | debug_assert!(msg.len() <= 8); | |
245 | let length = msg.len(); | |
246 | self.length += length; | |
247 | ||
248 | let needed = 8 - self.ntail; | |
249 | let fill = cmp::min(length, needed); | |
250 | if fill == 8 { | |
251 | self.tail = unsafe { load_int_le!(msg, 0, u64) }; | |
252 | } else { | |
253 | self.tail |= unsafe { u8to64_le(msg, 0, fill) } << (8 * self.ntail); | |
254 | if length < needed { | |
255 | self.ntail += length; | |
256 | return; | |
257 | } | |
258 | } | |
259 | self.state.v3 ^= self.tail; | |
260 | S::c_rounds(&mut self.state); | |
261 | self.state.v0 ^= self.tail; | |
262 | ||
263 | // Buffered tail is now flushed, process new input. | |
264 | self.ntail = length - needed; | |
265 | self.tail = unsafe { u8to64_le(msg, needed, self.ntail) }; | |
266 | } | |
e9174d1e | 267 | } |
85aaf69f | 268 | |
e9174d1e | 269 | #[stable(feature = "rust1", since = "1.0.0")] |
3157f602 XL |
270 | impl super::Hasher for SipHasher { |
271 | #[inline] | |
272 | fn write(&mut self, msg: &[u8]) { | |
273 | self.0.write(msg) | |
274 | } | |
275 | ||
276 | #[inline] | |
277 | fn finish(&self) -> u64 { | |
278 | self.0.finish() | |
279 | } | |
280 | } | |
281 | ||
5bcae85e | 282 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
3157f602 XL |
283 | impl super::Hasher for SipHasher13 { |
284 | #[inline] | |
285 | fn write(&mut self, msg: &[u8]) { | |
286 | self.hasher.write(msg) | |
287 | } | |
288 | ||
289 | #[inline] | |
290 | fn finish(&self) -> u64 { | |
291 | self.hasher.finish() | |
292 | } | |
293 | } | |
294 | ||
5bcae85e | 295 | #[unstable(feature = "sip_hash_13", issue = "34767")] |
3157f602 XL |
296 | impl super::Hasher for SipHasher24 { |
297 | #[inline] | |
298 | fn write(&mut self, msg: &[u8]) { | |
299 | self.hasher.write(msg) | |
300 | } | |
301 | ||
302 | #[inline] | |
303 | fn finish(&self) -> u64 { | |
304 | self.hasher.finish() | |
305 | } | |
306 | } | |
307 | ||
308 | impl<S: Sip> super::Hasher for Hasher<S> { | |
c30ab7b3 SL |
309 | // see short_write comment for explanation |
310 | #[inline] | |
311 | fn write_usize(&mut self, i: usize) { | |
312 | let bytes = unsafe { | |
313 | ::slice::from_raw_parts(&i as *const usize as *const u8, mem::size_of::<usize>()) | |
314 | }; | |
315 | self.short_write(bytes); | |
316 | } | |
317 | ||
318 | // see short_write comment for explanation | |
319 | #[inline] | |
320 | fn write_u8(&mut self, i: u8) { | |
321 | self.short_write(&[i]); | |
322 | } | |
323 | ||
d9579d0f | 324 | #[inline] |
1a4d82fc JJ |
325 | fn write(&mut self, msg: &[u8]) { |
326 | let length = msg.len(); | |
327 | self.length += length; | |
328 | ||
85aaf69f | 329 | let mut needed = 0; |
1a4d82fc JJ |
330 | |
331 | if self.ntail != 0 { | |
332 | needed = 8 - self.ntail; | |
c30ab7b3 | 333 | self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << 8 * self.ntail; |
1a4d82fc | 334 | if length < needed { |
1a4d82fc JJ |
335 | self.ntail += length; |
336 | return | |
c30ab7b3 SL |
337 | } else { |
338 | self.state.v3 ^= self.tail; | |
339 | S::c_rounds(&mut self.state); | |
340 | self.state.v0 ^= self.tail; | |
341 | self.ntail = 0; | |
1a4d82fc | 342 | } |
1a4d82fc JJ |
343 | } |
344 | ||
345 | // Buffered tail is now flushed, process new input. | |
346 | let len = length - needed; | |
1a4d82fc JJ |
347 | let left = len & 0x7; |
348 | ||
349 | let mut i = needed; | |
c1a9b12d | 350 | while i < len - left { |
c30ab7b3 | 351 | let mi = unsafe { load_int_le!(msg, i, u64) }; |
1a4d82fc | 352 | |
3157f602 XL |
353 | self.state.v3 ^= mi; |
354 | S::c_rounds(&mut self.state); | |
355 | self.state.v0 ^= mi; | |
1a4d82fc JJ |
356 | |
357 | i += 8; | |
358 | } | |
359 | ||
c30ab7b3 | 360 | self.tail = unsafe { u8to64_le(msg, i, left) }; |
1a4d82fc JJ |
361 | self.ntail = left; |
362 | } | |
1a4d82fc | 363 | |
d9579d0f | 364 | #[inline] |
1a4d82fc | 365 | fn finish(&self) -> u64 { |
3157f602 | 366 | let mut state = self.state; |
1a4d82fc JJ |
367 | |
368 | let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail; | |
369 | ||
3157f602 XL |
370 | state.v3 ^= b; |
371 | S::c_rounds(&mut state); | |
372 | state.v0 ^= b; | |
1a4d82fc | 373 | |
3157f602 XL |
374 | state.v2 ^= 0xff; |
375 | S::d_rounds(&mut state); | |
1a4d82fc | 376 | |
3157f602 | 377 | state.v0 ^ state.v1 ^ state.v2 ^ state.v3 |
1a4d82fc JJ |
378 | } |
379 | } | |
380 | ||
3157f602 | 381 | impl<S: Sip> Clone for Hasher<S> { |
1a4d82fc | 382 | #[inline] |
3157f602 XL |
383 | fn clone(&self) -> Hasher<S> { |
384 | Hasher { | |
1a4d82fc JJ |
385 | k0: self.k0, |
386 | k1: self.k1, | |
387 | length: self.length, | |
3157f602 | 388 | state: self.state, |
1a4d82fc JJ |
389 | tail: self.tail, |
390 | ntail: self.ntail, | |
3157f602 | 391 | _marker: self._marker, |
1a4d82fc JJ |
392 | } |
393 | } | |
394 | } | |
395 | ||
3157f602 | 396 | impl<S: Sip> Default for Hasher<S> { |
9e0c209e | 397 | /// Creates a `Hasher<S>` with the two initial keys set to 0. |
3157f602 XL |
398 | #[inline] |
399 | fn default() -> Hasher<S> { | |
400 | Hasher::new_with_keys(0, 0) | |
401 | } | |
402 | } | |
403 | ||
404 | #[doc(hidden)] | |
405 | trait Sip { | |
406 | fn c_rounds(&mut State); | |
407 | fn d_rounds(&mut State); | |
408 | } | |
409 | ||
410 | #[derive(Debug, Clone, Default)] | |
411 | struct Sip13Rounds; | |
412 | ||
413 | impl Sip for Sip13Rounds { | |
414 | #[inline] | |
415 | fn c_rounds(state: &mut State) { | |
416 | compress!(state); | |
417 | } | |
418 | ||
419 | #[inline] | |
420 | fn d_rounds(state: &mut State) { | |
421 | compress!(state); | |
422 | compress!(state); | |
423 | compress!(state); | |
424 | } | |
425 | } | |
426 | ||
427 | #[derive(Debug, Clone, Default)] | |
428 | struct Sip24Rounds; | |
429 | ||
430 | impl Sip for Sip24Rounds { | |
431 | #[inline] | |
432 | fn c_rounds(state: &mut State) { | |
433 | compress!(state); | |
434 | compress!(state); | |
435 | } | |
436 | ||
437 | #[inline] | |
438 | fn d_rounds(state: &mut State) { | |
439 | compress!(state); | |
440 | compress!(state); | |
441 | compress!(state); | |
442 | compress!(state); | |
1a4d82fc JJ |
443 | } |
444 | } |