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 // ignore-lexer-test FIXME #15883
13 //! An implementation of SipHash 2-4.
15 #![allow(deprecated)] // until the next snapshot for inherent wrapping ops
21 /// An implementation of SipHash 2-4.
23 /// See: http://131002.net/siphash/
25 /// Consider this as a main "general-purpose" hash for all hashtables: it
26 /// runs at good speed (competitive with spooky and city) and permits
27 /// strong _keyed_ hashing. Key your hashtables from a strong RNG,
28 /// such as `rand::Rng`.
30 /// Although the SipHash algorithm is considered to be cryptographically
31 /// strong, this implementation has not been reviewed for such purposes.
32 /// As such, all cryptographic uses of this implementation are strongly
34 #[stable(feature = "rust1", since = "1.0.0")]
35 pub struct SipHasher {
38 length: usize, // how many bytes we've processed
39 v0: u64, // hash state
43 tail: u64, // unprocessed bytes le
44 ntail: usize, // how many bytes in tail are valid
47 // sadly, these macro definitions can't appear later,
48 // because they're needed in the following defs;
49 // this design could be improved.
51 macro_rules! u8to64_le {
52 ($buf:expr, $i:expr) =>
54 ($buf[1+$i] as u64) << 8 |
55 ($buf[2+$i] as u64) << 16 |
56 ($buf[3+$i] as u64) << 24 |
57 ($buf[4+$i] as u64) << 32 |
58 ($buf[5+$i] as u64) << 40 |
59 ($buf[6+$i] as u64) << 48 |
60 ($buf[7+$i] as u64) << 56);
61 ($buf:expr, $i:expr, $len:expr) =>
66 out |= ($buf[t+$i] as u64) << t*8;
75 (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
78 macro_rules! compress {
79 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
81 $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
83 $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
84 $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
85 $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
91 /// Creates a new `SipHasher` with the two initial keys set to 0.
93 #[stable(feature = "rust1", since = "1.0.0")]
94 pub fn new() -> SipHasher {
95 SipHasher::new_with_keys(0, 0)
98 /// Creates a `SipHasher` that is keyed off the provided keys.
100 #[stable(feature = "rust1", since = "1.0.0")]
101 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
102 let mut state = SipHasher {
117 fn reset(&mut self) {
119 self.v0 = self.k0 ^ 0x736f6d6570736575;
120 self.v1 = self.k1 ^ 0x646f72616e646f6d;
121 self.v2 = self.k0 ^ 0x6c7967656e657261;
122 self.v3 = self.k1 ^ 0x7465646279746573;
126 fn write(&mut self, msg: &[u8]) {
127 let length = msg.len();
128 self.length += length;
133 needed = 8 - self.ntail;
135 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
136 self.ntail += length;
140 let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
143 compress!(self.v0, self.v1, self.v2, self.v3);
144 compress!(self.v0, self.v1, self.v2, self.v3);
150 // Buffered tail is now flushed, process new input.
151 let len = length - needed;
152 let end = len & (!0x7);
153 let left = len & 0x7;
157 let mi = u8to64_le!(msg, i);
160 compress!(self.v0, self.v1, self.v2, self.v3);
161 compress!(self.v0, self.v1, self.v2, self.v3);
167 self.tail = u8to64_le!(msg, i, left);
172 #[stable(feature = "rust1", since = "1.0.0")]
173 impl Hasher for SipHasher {
175 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 {