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.
15 use marker::PhantomData;
18 /// An implementation of SipHash 1-3.
20 /// See: https://131002.net/siphash/
21 #[unstable(feature = "sip_hash_13", issue = "29754")]
22 #[derive(Debug, Clone, Default)]
23 pub struct SipHasher13 {
24 hasher: Hasher<Sip13Rounds>,
27 /// An implementation of SipHash 2-4.
29 /// See: https://131002.net/siphash/
30 #[unstable(feature = "sip_hash_13", issue = "29754")]
31 #[derive(Debug, Clone, Default)]
32 pub struct SipHasher24 {
33 hasher: Hasher<Sip24Rounds>,
36 /// An implementation of SipHash 2-4.
38 /// See: https://131002.net/siphash/
40 /// This is currently the default hashing function used by standard library
41 /// (eg. `collections::HashMap` uses it by default).
43 /// SipHash is a general-purpose hashing function: it runs at a good
44 /// speed (competitive with Spooky and City) and permits strong _keyed_
45 /// hashing. This lets you key your hashtables from a strong RNG, such as
46 /// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html).
48 /// Although the SipHash algorithm is considered to be generally strong,
49 /// it is not intended for cryptographic purposes. As such, all
50 /// cryptographic uses of this implementation are _strongly discouraged_.
51 #[stable(feature = "rust1", since = "1.0.0")]
52 #[derive(Debug, Clone, Default)]
53 pub struct SipHasher(SipHasher24);
56 struct Hasher<S: Sip> {
59 length: usize, // how many bytes we've processed
60 state: State, // hash State
61 tail: u64, // unprocessed bytes le
62 ntail: usize, // how many bytes in tail are valid
63 _marker: PhantomData<S>,
66 #[derive(Debug, Clone, Copy)]
68 // v0, v2 and v1, v3 show up in pairs in the algorithm,
69 // and simd implementations of SipHash will use vectors
70 // of v02 and v13. By placing them in this order in the struct,
71 // the compiler can pick up on just a few simd optimizations by itself.
78 // sadly, these macro definitions can't appear later,
79 // because they're needed in the following defs;
80 // this design could be improved.
82 macro_rules! u8to64_le {
83 ($buf:expr, $i:expr) =>
85 ($buf[1+$i] as u64) << 8 |
86 ($buf[2+$i] as u64) << 16 |
87 ($buf[3+$i] as u64) << 24 |
88 ($buf[4+$i] as u64) << 32 |
89 ($buf[5+$i] as u64) << 40 |
90 ($buf[6+$i] as u64) << 48 |
91 ($buf[7+$i] as u64) << 56);
92 ($buf:expr, $i:expr, $len:expr) =>
97 out |= ($buf[t+$i] as u64) << t*8;
104 /// Load a full u64 word from a byte stream, in LE order. Use
105 /// `copy_nonoverlapping` to let the compiler generate the most efficient way
106 /// to load u64 from a possibly unaligned address.
108 /// Unsafe because: unchecked indexing at i..i+8
110 unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 {
111 debug_assert!(i + 8 <= buf.len());
113 ptr::copy_nonoverlapping(buf.get_unchecked(i), &mut data as *mut _ as *mut u8, 8);
118 ($x:expr, $b:expr) =>
119 (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
122 macro_rules! compress {
124 compress!($state.v0, $state.v1, $state.v2, $state.v3)
126 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
128 $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
129 $v0 = rotl!($v0, 32);
130 $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
131 $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
132 $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
133 $v2 = rotl!($v2, 32);
138 /// Creates a new `SipHasher` with the two initial keys set to 0.
140 #[stable(feature = "rust1", since = "1.0.0")]
141 pub fn new() -> SipHasher {
142 SipHasher::new_with_keys(0, 0)
145 /// Creates a `SipHasher` that is keyed off the provided keys.
147 #[stable(feature = "rust1", since = "1.0.0")]
148 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
149 SipHasher(SipHasher24::new_with_keys(key0, key1))
155 /// Creates a new `SipHasher13` with the two initial keys set to 0.
157 #[unstable(feature = "sip_hash_13", issue = "29754")]
158 pub fn new() -> SipHasher13 {
159 SipHasher13::new_with_keys(0, 0)
162 /// Creates a `SipHasher13` that is keyed off the provided keys.
164 #[unstable(feature = "sip_hash_13", issue = "29754")]
165 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 {
167 hasher: Hasher::new_with_keys(key0, key1)
173 /// Creates a new `SipHasher24` with the two initial keys set to 0.
175 #[unstable(feature = "sip_hash_13", issue = "29754")]
176 pub fn new() -> SipHasher24 {
177 SipHasher24::new_with_keys(0, 0)
180 /// Creates a `SipHasher24` that is keyed off the provided keys.
182 #[unstable(feature = "sip_hash_13", issue = "29754")]
183 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 {
185 hasher: Hasher::new_with_keys(key0, key1)
190 impl<S: Sip> Hasher<S> {
192 fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> {
193 let mut state = Hasher {
205 _marker: PhantomData,
212 fn reset(&mut self) {
214 self.state.v0 = self.k0 ^ 0x736f6d6570736575;
215 self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
216 self.state.v2 = self.k0 ^ 0x6c7967656e657261;
217 self.state.v3 = self.k1 ^ 0x7465646279746573;
222 #[stable(feature = "rust1", since = "1.0.0")]
223 impl super::Hasher for SipHasher {
225 fn write(&mut self, msg: &[u8]) {
230 fn finish(&self) -> u64 {
235 #[unstable(feature = "sip_hash_13", issue = "29754")]
236 impl super::Hasher for SipHasher13 {
238 fn write(&mut self, msg: &[u8]) {
239 self.hasher.write(msg)
243 fn finish(&self) -> u64 {
248 #[unstable(feature = "sip_hash_13", issue = "29754")]
249 impl super::Hasher for SipHasher24 {
251 fn write(&mut self, msg: &[u8]) {
252 self.hasher.write(msg)
256 fn finish(&self) -> u64 {
261 impl<S: Sip> super::Hasher for Hasher<S> {
263 fn write(&mut self, msg: &[u8]) {
264 let length = msg.len();
265 self.length += length;
270 needed = 8 - self.ntail;
272 self.tail |= u8to64_le!(msg, 0, length) << 8 * self.ntail;
273 self.ntail += length;
277 let m = self.tail | u8to64_le!(msg, 0, needed) << 8 * self.ntail;
280 S::c_rounds(&mut self.state);
286 // Buffered tail is now flushed, process new input.
287 let len = length - needed;
288 let left = len & 0x7;
291 while i < len - left {
292 let mi = unsafe { load_u64_le(msg, i) };
295 S::c_rounds(&mut self.state);
301 self.tail = u8to64_le!(msg, i, left);
306 fn finish(&self) -> u64 {
307 let mut state = self.state;
309 let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
312 S::c_rounds(&mut state);
316 S::d_rounds(&mut state);
318 state.v0 ^ state.v1 ^ state.v2 ^ state.v3
322 impl<S: Sip> Clone for Hasher<S> {
324 fn clone(&self) -> Hasher<S> {
332 _marker: self._marker,
337 impl<S: Sip> Default for Hasher<S> {
339 fn default() -> Hasher<S> {
340 Hasher::new_with_keys(0, 0)
346 fn c_rounds(&mut State);
347 fn d_rounds(&mut State);
350 #[derive(Debug, Clone, Default)]
353 impl Sip for Sip13Rounds {
355 fn c_rounds(state: &mut State) {
360 fn d_rounds(state: &mut State) {
367 #[derive(Debug, Clone, Default)]
370 impl Sip for Sip24Rounds {
372 fn c_rounds(state: &mut State) {
378 fn d_rounds(state: &mut State) {