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.
13 #![allow(deprecated)] // until the next snapshot for inherent wrapping ops
18 /// An implementation of SipHash 2-4.
20 /// See: http://131002.net/siphash/
22 /// Consider this as a main "general-purpose" hash for all hashtables: it
23 /// runs at good speed (competitive with spooky and city) and permits
24 /// strong _keyed_ hashing. Key your hashtables from a strong RNG,
25 /// such as `rand::Rng`.
27 /// Although the SipHash algorithm is considered to be cryptographically
28 /// strong, this implementation has not been reviewed for such purposes.
29 /// As such, all cryptographic uses of this implementation are strongly
31 #[stable(feature = "rust1", since = "1.0.0")]
32 pub struct SipHasher {
35 length: usize, // how many bytes we've processed
36 v0: u64, // hash state
40 tail: u64, // unprocessed bytes le
41 ntail: usize, // how many bytes in tail are valid
44 // sadly, these macro definitions can't appear later,
45 // because they're needed in the following defs;
46 // this design could be improved.
48 macro_rules! u8to64_le {
49 ($buf:expr, $i:expr) =>
51 ($buf[1+$i] as u64) << 8 |
52 ($buf[2+$i] as u64) << 16 |
53 ($buf[3+$i] as u64) << 24 |
54 ($buf[4+$i] as u64) << 32 |
55 ($buf[5+$i] as u64) << 40 |
56 ($buf[6+$i] as u64) << 48 |
57 ($buf[7+$i] as u64) << 56);
58 ($buf:expr, $i:expr, $len:expr) =>
63 out |= ($buf[t+$i] as u64) << t*8;
72 (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
75 macro_rules! compress {
76 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
78 $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
80 $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
81 $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
82 $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
88 /// Creates a new `SipHasher` with the two initial keys set to 0.
90 #[stable(feature = "rust1", since = "1.0.0")]
91 pub fn new() -> SipHasher {
92 SipHasher::new_with_keys(0, 0)
95 /// Creates a `SipHasher` that is keyed off the provided keys.
97 #[stable(feature = "rust1", since = "1.0.0")]
98 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
99 let mut state = SipHasher {
115 fn reset(&mut self) {
117 self.v0 = self.k0 ^ 0x736f6d6570736575;
118 self.v1 = self.k1 ^ 0x646f72616e646f6d;
119 self.v2 = self.k0 ^ 0x6c7967656e657261;
120 self.v3 = self.k1 ^ 0x7465646279746573;
125 fn write(&mut self, msg: &[u8]) {
126 let length = msg.len();
127 self.length += length;
132 needed = 8 - self.ntail;
134 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
135 self.ntail += length;
139 let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
142 compress!(self.v0, self.v1, self.v2, self.v3);
143 compress!(self.v0, self.v1, self.v2, self.v3);
149 // Buffered tail is now flushed, process new input.
150 let len = length - needed;
151 let end = len & (!0x7);
152 let left = len & 0x7;
156 let mi = u8to64_le!(msg, i);
159 compress!(self.v0, self.v1, self.v2, self.v3);
160 compress!(self.v0, self.v1, self.v2, self.v3);
166 self.tail = u8to64_le!(msg, i, left);
171 #[stable(feature = "rust1", since = "1.0.0")]
172 impl Hasher for SipHasher {
174 fn write(&mut self, msg: &[u8]) {
179 fn finish(&self) -> u64 {
180 let mut v0 = self.v0;
181 let mut v1 = self.v1;
182 let mut v2 = self.v2;
183 let mut v3 = self.v3;
185 let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
188 compress!(v0, v1, v2, v3);
189 compress!(v0, v1, v2, v3);
193 compress!(v0, v1, v2, v3);
194 compress!(v0, v1, v2, v3);
195 compress!(v0, v1, v2, v3);
196 compress!(v0, v1, v2, v3);
202 #[stable(feature = "rust1", since = "1.0.0")]
203 impl Clone for SipHasher {
205 fn clone(&self) -> SipHasher {
220 #[stable(feature = "rust1", since = "1.0.0")]
221 impl Default for SipHasher {
222 fn default() -> SipHasher {