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 2-4.
16 /// An implementation of SipHash 2-4.
18 /// See: http://131002.net/siphash/
20 /// Consider this as a main "general-purpose" hash for all hashtables: it
21 /// runs at good speed (competitive with spooky and city) and permits
22 /// strong _keyed_ hashing. Key your hashtables from a strong RNG,
23 /// such as `rand::Rng`.
25 /// Although the SipHash algorithm is considered to be cryptographically
26 /// strong, this implementation has not been reviewed for such purposes.
27 /// As such, all cryptographic uses of this implementation are strongly
29 #[stable(feature = "rust1", since = "1.0.0")]
30 pub struct SipHasher {
33 length: usize, // how many bytes we've processed
34 v0: u64, // hash state
38 tail: u64, // unprocessed bytes le
39 ntail: usize, // how many bytes in tail are valid
42 // sadly, these macro definitions can't appear later,
43 // because they're needed in the following defs;
44 // this design could be improved.
46 macro_rules! u8to64_le {
47 ($buf:expr, $i:expr) =>
49 ($buf[1+$i] as u64) << 8 |
50 ($buf[2+$i] as u64) << 16 |
51 ($buf[3+$i] as u64) << 24 |
52 ($buf[4+$i] as u64) << 32 |
53 ($buf[5+$i] as u64) << 40 |
54 ($buf[6+$i] as u64) << 48 |
55 ($buf[7+$i] as u64) << 56);
56 ($buf:expr, $i:expr, $len:expr) =>
61 out |= ($buf[t+$i] as u64) << t*8;
70 (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
73 macro_rules! compress {
74 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
76 $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
78 $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
79 $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
80 $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
86 /// Creates a new `SipHasher` with the two initial keys set to 0.
88 #[stable(feature = "rust1", since = "1.0.0")]
89 pub fn new() -> SipHasher {
90 SipHasher::new_with_keys(0, 0)
93 /// Creates a `SipHasher` that is keyed off the provided keys.
95 #[stable(feature = "rust1", since = "1.0.0")]
96 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
97 let mut state = SipHasher {
113 fn reset(&mut self) {
115 self.v0 = self.k0 ^ 0x736f6d6570736575;
116 self.v1 = self.k1 ^ 0x646f72616e646f6d;
117 self.v2 = self.k0 ^ 0x6c7967656e657261;
118 self.v3 = self.k1 ^ 0x7465646279746573;
123 fn write(&mut self, msg: &[u8]) {
124 let length = msg.len();
125 self.length += length;
130 needed = 8 - self.ntail;
132 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
133 self.ntail += length;
137 let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
140 compress!(self.v0, self.v1, self.v2, self.v3);
141 compress!(self.v0, self.v1, self.v2, self.v3);
147 // Buffered tail is now flushed, process new input.
148 let len = length - needed;
149 let end = len & (!0x7);
150 let left = len & 0x7;
154 let mi = u8to64_le!(msg, i);
157 compress!(self.v0, self.v1, self.v2, self.v3);
158 compress!(self.v0, self.v1, self.v2, self.v3);
164 self.tail = u8to64_le!(msg, i, left);
169 #[stable(feature = "rust1", since = "1.0.0")]
170 impl Hasher for SipHasher {
172 fn write(&mut self, msg: &[u8]) {
177 fn finish(&self) -> u64 {
178 let mut v0 = self.v0;
179 let mut v1 = self.v1;
180 let mut v2 = self.v2;
181 let mut v3 = self.v3;
183 let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
186 compress!(v0, v1, v2, v3);
187 compress!(v0, v1, v2, v3);
191 compress!(v0, v1, v2, v3);
192 compress!(v0, v1, v2, v3);
193 compress!(v0, v1, v2, v3);
194 compress!(v0, v1, v2, v3);
200 #[stable(feature = "rust1", since = "1.0.0")]
201 impl Clone for SipHasher {
203 fn clone(&self) -> SipHasher {
218 #[stable(feature = "rust1", since = "1.0.0")]
219 impl Default for SipHasher {
220 fn default() -> SipHasher {