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.
22 /// An implementation of SipHash 2-4.
24 /// See: http://131002.net/siphash/
26 /// Consider this as a main "general-purpose" hash for all hashtables: it
27 /// runs at good speed (competitive with spooky and city) and permits
28 /// strong _keyed_ hashing. Key your hashtables from a strong RNG,
29 /// such as `rand::Rng`.
31 /// Although the SipHash algorithm is considered to be cryptographically
32 /// strong, this implementation has not been reviewed for such purposes.
33 /// As such, all cryptographic uses of this implementation are strongly
35 #[stable(feature = "rust1", since = "1.0.0")]
36 pub struct SipHasher {
39 length: uint, // how many bytes we've processed
40 v0: u64, // hash state
44 tail: u64, // unprocessed bytes le
45 ntail: uint, // how many bytes in tail are valid
48 // sadly, these macro definitions can't appear later,
49 // because they're needed in the following defs;
50 // this design could be improved.
52 macro_rules! u8to64_le {
53 ($buf:expr, $i:expr) =>
55 ($buf[1+$i] as u64) << 8 |
56 ($buf[2+$i] as u64) << 16 |
57 ($buf[3+$i] as u64) << 24 |
58 ($buf[4+$i] as u64) << 32 |
59 ($buf[5+$i] as u64) << 40 |
60 ($buf[6+$i] as u64) << 48 |
61 ($buf[7+$i] as u64) << 56);
62 ($buf:expr, $i:expr, $len:expr) =>
67 out |= ($buf[t+$i] as u64) << t*8;
76 (($x << $b) | ($x >> (64 - $b)))
79 macro_rules! compress {
80 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
82 $v0 += $v1; $v1 = rotl!($v1, 13); $v1 ^= $v0;
84 $v2 += $v3; $v3 = rotl!($v3, 16); $v3 ^= $v2;
85 $v0 += $v3; $v3 = rotl!($v3, 21); $v3 ^= $v0;
86 $v2 += $v1; $v1 = rotl!($v1, 17); $v1 ^= $v2;
92 /// Creates a new `SipHasher` with the two initial keys set to 0.
94 #[stable(feature = "rust1", since = "1.0.0")]
95 pub fn new() -> SipHasher {
96 SipHasher::new_with_keys(0, 0)
99 /// Creates a `SipHasher` that is keyed off the provided keys.
101 #[stable(feature = "rust1", since = "1.0.0")]
102 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
103 let mut state = SipHasher {
118 /// Returns the computed hash.
119 #[unstable(feature = "hash")]
120 #[deprecated(since = "1.0.0", reason = "renamed to finish")]
121 pub fn result(&self) -> u64 { self.finish() }
123 fn reset(&mut self) {
125 self.v0 = self.k0 ^ 0x736f6d6570736575;
126 self.v1 = self.k1 ^ 0x646f72616e646f6d;
127 self.v2 = self.k0 ^ 0x6c7967656e657261;
128 self.v3 = self.k1 ^ 0x7465646279746573;
132 fn write(&mut self, msg: &[u8]) {
133 let length = msg.len();
134 self.length += length;
139 needed = 8 - self.ntail;
141 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
142 self.ntail += length;
146 let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
149 compress!(self.v0, self.v1, self.v2, self.v3);
150 compress!(self.v0, self.v1, self.v2, self.v3);
156 // Buffered tail is now flushed, process new input.
157 let len = length - needed;
158 let end = len & (!0x7);
159 let left = len & 0x7;
163 let mi = u8to64_le!(msg, i);
166 compress!(self.v0, self.v1, self.v2, self.v3);
167 compress!(self.v0, self.v1, self.v2, self.v3);
173 self.tail = u8to64_le!(msg, i, left);
179 impl Writer for SipHasher {
181 fn write(&mut self, msg: &[u8]) {
186 #[stable(feature = "rust1", since = "1.0.0")]
187 impl Hasher for SipHasher {
192 fn reset(&mut self) {
198 fn write(&mut self, msg: &[u8]) {
202 fn finish(&self) -> u64 {
203 let mut v0 = self.v0;
204 let mut v1 = self.v1;
205 let mut v2 = self.v2;
206 let mut v3 = self.v3;
208 let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
211 compress!(v0, v1, v2, v3);
212 compress!(v0, v1, v2, v3);
216 compress!(v0, v1, v2, v3);
217 compress!(v0, v1, v2, v3);
218 compress!(v0, v1, v2, v3);
219 compress!(v0, v1, v2, v3);
225 #[stable(feature = "rust1", since = "1.0.0")]
226 impl Clone for SipHasher {
228 fn clone(&self) -> SipHasher {
243 #[stable(feature = "rust1", since = "1.0.0")]
244 impl Default for SipHasher {
245 fn default() -> SipHasher {