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.
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.
11 //! An implementation of SipHash.
13 use marker::PhantomData;
16 /// An implementation of SipHash 1-3.
18 /// See: https://131002.net/siphash/
19 #[unstable(feature = "sip_hash_13", issue = "34767")]
20 #[derive(Debug, Clone, Default)]
21 pub struct SipHasher13 {
22 hasher: Hasher<Sip13Rounds>,
25 /// An implementation of SipHash 2-4.
27 /// See: https://131002.net/siphash/
28 #[unstable(feature = "sip_hash_13", issue = "34767")]
29 #[derive(Debug, Clone, Default)]
30 pub struct SipHasher24 {
31 hasher: Hasher<Sip24Rounds>,
34 /// An implementation of SipHash 2-4.
36 /// See: https://131002.net/siphash/
38 /// This is currently the default hashing function used by standard library
39 /// (eg. `collections::HashMap` uses it by default).
41 /// SipHash is a general-purpose hashing function: it runs at a good
42 /// speed (competitive with Spooky and City) and permits strong _keyed_
43 /// hashing. This lets you key your hashtables from a strong RNG, such as
44 /// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html).
46 /// Although the SipHash algorithm is considered to be generally strong,
47 /// it is not intended for cryptographic purposes. As such, all
48 /// cryptographic uses of this implementation are _strongly discouraged_.
49 #[stable(feature = "rust1", since = "1.0.0")]
50 #[derive(Debug, Clone, Default)]
51 pub struct SipHasher(SipHasher24);
54 struct Hasher<S: Sip> {
57 length: usize, // how many bytes we've processed
58 state: State, // hash State
59 tail: u64, // unprocessed bytes le
60 ntail: usize, // how many bytes in tail are valid
61 _marker: PhantomData<S>,
64 #[derive(Debug, Clone, Copy)]
66 // v0, v2 and v1, v3 show up in pairs in the algorithm,
67 // and simd implementations of SipHash will use vectors
68 // of v02 and v13. By placing them in this order in the struct,
69 // the compiler can pick up on just a few simd optimizations by itself.
76 // sadly, these macro definitions can't appear later,
77 // because they're needed in the following defs;
78 // this design could be improved.
80 macro_rules! u8to64_le {
81 ($buf:expr, $i:expr) =>
83 ($buf[1+$i] as u64) << 8 |
84 ($buf[2+$i] as u64) << 16 |
85 ($buf[3+$i] as u64) << 24 |
86 ($buf[4+$i] as u64) << 32 |
87 ($buf[5+$i] as u64) << 40 |
88 ($buf[6+$i] as u64) << 48 |
89 ($buf[7+$i] as u64) << 56);
90 ($buf:expr, $i:expr, $len:expr) =>
95 out |= ($buf[t+$i] as u64) << t*8;
102 /// Load a full u64 word from a byte stream, in LE order. Use
103 /// `copy_nonoverlapping` to let the compiler generate the most efficient way
104 /// to load u64 from a possibly unaligned address.
106 /// Unsafe because: unchecked indexing at i..i+8
108 unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 {
109 debug_assert!(i + 8 <= buf.len());
111 ptr::copy_nonoverlapping(buf.get_unchecked(i), &mut data as *mut _ as *mut u8, 8);
116 ($x:expr, $b:expr) =>
117 (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
120 macro_rules! compress {
122 compress!($state.v0, $state.v1, $state.v2, $state.v3)
124 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
126 $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
127 $v0 = rotl!($v0, 32);
128 $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
129 $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
130 $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
131 $v2 = rotl!($v2, 32);
136 /// Creates a new `SipHasher` with the two initial keys set to 0.
138 #[stable(feature = "rust1", since = "1.0.0")]
139 pub fn new() -> SipHasher {
140 SipHasher::new_with_keys(0, 0)
143 /// Creates a `SipHasher` that is keyed off the provided keys.
145 #[stable(feature = "rust1", since = "1.0.0")]
146 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
147 SipHasher(SipHasher24::new_with_keys(key0, key1))
153 /// Creates a new `SipHasher13` with the two initial keys set to 0.
155 #[unstable(feature = "sip_hash_13", issue = "34767")]
156 pub fn new() -> SipHasher13 {
157 SipHasher13::new_with_keys(0, 0)
160 /// Creates a `SipHasher13` that is keyed off the provided keys.
162 #[unstable(feature = "sip_hash_13", issue = "34767")]
163 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 {
165 hasher: Hasher::new_with_keys(key0, key1)
171 /// Creates a new `SipHasher24` with the two initial keys set to 0.
173 #[unstable(feature = "sip_hash_13", issue = "34767")]
174 pub fn new() -> SipHasher24 {
175 SipHasher24::new_with_keys(0, 0)
178 /// Creates a `SipHasher24` that is keyed off the provided keys.
180 #[unstable(feature = "sip_hash_13", issue = "34767")]
181 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 {
183 hasher: Hasher::new_with_keys(key0, key1)
188 impl<S: Sip> Hasher<S> {
190 fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> {
191 let mut state = Hasher {
203 _marker: PhantomData,
210 fn reset(&mut self) {
212 self.state.v0 = self.k0 ^ 0x736f6d6570736575;
213 self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
214 self.state.v2 = self.k0 ^ 0x6c7967656e657261;
215 self.state.v3 = self.k1 ^ 0x7465646279746573;
220 #[stable(feature = "rust1", since = "1.0.0")]
221 impl super::Hasher for SipHasher {
223 fn write(&mut self, msg: &[u8]) {
228 fn finish(&self) -> u64 {
233 #[unstable(feature = "sip_hash_13", issue = "34767")]
234 impl super::Hasher for SipHasher13 {
236 fn write(&mut self, msg: &[u8]) {
237 self.hasher.write(msg)
241 fn finish(&self) -> u64 {
246 #[unstable(feature = "sip_hash_13", issue = "34767")]
247 impl super::Hasher for SipHasher24 {
249 fn write(&mut self, msg: &[u8]) {
250 self.hasher.write(msg)
254 fn finish(&self) -> u64 {
259 impl<S: Sip> super::Hasher for Hasher<S> {
261 fn write(&mut self, msg: &[u8]) {
262 let length = msg.len();
263 self.length += length;
268 needed = 8 - self.ntail;
270 self.tail |= u8to64_le!(msg, 0, length) << 8 * self.ntail;
271 self.ntail += length;
275 let m = self.tail | u8to64_le!(msg, 0, needed) << 8 * self.ntail;
278 S::c_rounds(&mut self.state);
284 // Buffered tail is now flushed, process new input.
285 let len = length - needed;
286 let left = len & 0x7;
289 while i < len - left {
290 let mi = unsafe { load_u64_le(msg, i) };
293 S::c_rounds(&mut self.state);
299 self.tail = u8to64_le!(msg, i, left);
304 fn finish(&self) -> u64 {
305 let mut state = self.state;
307 let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
310 S::c_rounds(&mut state);
314 S::d_rounds(&mut state);
316 state.v0 ^ state.v1 ^ state.v2 ^ state.v3
320 impl<S: Sip> Clone for Hasher<S> {
322 fn clone(&self) -> Hasher<S> {
330 _marker: self._marker,
335 impl<S: Sip> Default for Hasher<S> {
337 fn default() -> Hasher<S> {
338 Hasher::new_with_keys(0, 0)
344 fn c_rounds(&mut State);
345 fn d_rounds(&mut State);
348 #[derive(Debug, Clone, Default)]
351 impl Sip for Sip13Rounds {
353 fn c_rounds(state: &mut State) {
358 fn d_rounds(state: &mut State) {
365 #[derive(Debug, Clone, Default)]
368 impl Sip for Sip24Rounds {
370 fn c_rounds(state: &mut State) {
376 fn d_rounds(state: &mut State) {