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.
18 use super::{Hasher, Writer};
20 /// An implementation of SipHash 2-4.
22 /// See: http://131002.net/siphash/
24 /// Consider this as a main "general-purpose" hash for all hashtables: it
25 /// runs at good speed (competitive with spooky and city) and permits
26 /// strong _keyed_ hashing. Key your hashtables from a strong RNG,
27 /// such as `rand::Rng`.
29 /// Although the SipHash algorithm is considered to be cryptographically
30 /// strong, this implementation has not been reviewed for such purposes.
31 /// As such, all cryptographic uses of this implementation are strongly
33 pub struct SipHasher {
36 length: uint, // how many bytes we've processed
37 v0: u64, // hash state
41 tail: u64, // unprocessed bytes le
42 ntail: uint, // how many bytes in tail are valid
45 // sadly, these macro definitions can't appear later,
46 // because they're needed in the following defs;
47 // this design could be improved.
49 macro_rules! u8to64_le {
50 ($buf:expr, $i:expr) =>
52 ($buf[1+$i] as u64) << 8 |
53 ($buf[2+$i] as u64) << 16 |
54 ($buf[3+$i] as u64) << 24 |
55 ($buf[4+$i] as u64) << 32 |
56 ($buf[5+$i] as u64) << 40 |
57 ($buf[6+$i] as u64) << 48 |
58 ($buf[7+$i] as u64) << 56);
59 ($buf:expr, $i:expr, $len:expr) =>
64 out |= ($buf[t+$i] as u64) << t*8;
73 (($x << $b) | ($x >> (64 - $b)))
76 macro_rules! compress {
77 ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
79 $v0 += $v1; $v1 = rotl!($v1, 13); $v1 ^= $v0;
81 $v2 += $v3; $v3 = rotl!($v3, 16); $v3 ^= $v2;
82 $v0 += $v3; $v3 = rotl!($v3, 21); $v3 ^= $v0;
83 $v2 += $v1; $v1 = rotl!($v1, 17); $v1 ^= $v2;
89 /// Creates a new `SipHasher` with the two initial keys set to 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 pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
98 let mut state = SipHasher {
113 /// Returns the computed hash.
114 #[unstable(feature = "hash")]
115 #[deprecated(since = "1.0.0", reason = "renamed to finish")]
116 pub fn result(&self) -> u64 { self.finish() }
119 impl Writer for SipHasher {
121 fn write(&mut self, msg: &[u8]) {
122 let length = msg.len();
123 self.length += length;
128 needed = 8 - self.ntail;
130 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
131 self.ntail += length;
135 let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
138 compress!(self.v0, self.v1, self.v2, self.v3);
139 compress!(self.v0, self.v1, self.v2, self.v3);
145 // Buffered tail is now flushed, process new input.
146 let len = length - needed;
147 let end = len & (!0x7);
148 let left = len & 0x7;
152 let mi = u8to64_le!(msg, i);
155 compress!(self.v0, self.v1, self.v2, self.v3);
156 compress!(self.v0, self.v1, self.v2, self.v3);
162 self.tail = u8to64_le!(msg, i, left);
167 impl Hasher for SipHasher {
170 fn reset(&mut self) {
172 self.v0 = self.k0 ^ 0x736f6d6570736575;
173 self.v1 = self.k1 ^ 0x646f72616e646f6d;
174 self.v2 = self.k0 ^ 0x6c7967656e657261;
175 self.v3 = self.k1 ^ 0x7465646279746573;
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 impl Clone for SipHasher {
204 fn clone(&self) -> SipHasher {
219 impl Default for SipHasher {
220 fn default() -> SipHasher {