]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
4 | // | |
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. | |
1a4d82fc JJ |
10 | |
11 | //! An implementation of SipHash 2-4. | |
12 | ||
c1a9b12d | 13 | use ptr; |
1a4d82fc | 14 | use prelude::*; |
85aaf69f | 15 | use super::Hasher; |
1a4d82fc JJ |
16 | |
17 | /// An implementation of SipHash 2-4. | |
18 | /// | |
19 | /// See: http://131002.net/siphash/ | |
20 | /// | |
21 | /// Consider this as a main "general-purpose" hash for all hashtables: it | |
22 | /// runs at good speed (competitive with spooky and city) and permits | |
23 | /// strong _keyed_ hashing. Key your hashtables from a strong RNG, | |
24 | /// such as `rand::Rng`. | |
25 | /// | |
26 | /// Although the SipHash algorithm is considered to be cryptographically | |
27 | /// strong, this implementation has not been reviewed for such purposes. | |
28 | /// As such, all cryptographic uses of this implementation are strongly | |
29 | /// discouraged. | |
85aaf69f | 30 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
31 | pub struct SipHasher { |
32 | k0: u64, | |
33 | k1: u64, | |
c34b1796 | 34 | length: usize, // how many bytes we've processed |
c1a9b12d SL |
35 | // v0, v2 and v1, v3 show up in pairs in the algorithm, |
36 | // and simd implementations of SipHash will use vectors | |
37 | // of v02 and v13. By placing them in this order in the struct, | |
38 | // the compiler can pick up on just a few simd optimizations by itself. | |
1a4d82fc | 39 | v0: u64, // hash state |
1a4d82fc | 40 | v2: u64, |
c1a9b12d | 41 | v1: u64, |
1a4d82fc JJ |
42 | v3: u64, |
43 | tail: u64, // unprocessed bytes le | |
c34b1796 | 44 | ntail: usize, // how many bytes in tail are valid |
1a4d82fc JJ |
45 | } |
46 | ||
47 | // sadly, these macro definitions can't appear later, | |
48 | // because they're needed in the following defs; | |
49 | // this design could be improved. | |
50 | ||
51 | macro_rules! u8to64_le { | |
52 | ($buf:expr, $i:expr) => | |
53 | ($buf[0+$i] as u64 | | |
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) => | |
62 | ({ | |
63 | let mut t = 0; | |
c34b1796 | 64 | let mut out = 0; |
1a4d82fc JJ |
65 | while t < $len { |
66 | out |= ($buf[t+$i] as u64) << t*8; | |
67 | t += 1; | |
68 | } | |
69 | out | |
70 | }); | |
71 | } | |
72 | ||
c1a9b12d SL |
73 | /// Load a full u64 word from a byte stream, in LE order. Use |
74 | /// `copy_nonoverlapping` to let the compiler generate the most efficient way | |
75 | /// to load u64 from a possibly unaligned address. | |
76 | /// | |
77 | /// Unsafe because: unchecked indexing at i..i+8 | |
78 | #[inline] | |
79 | unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 { | |
80 | debug_assert!(i + 8 <= buf.len()); | |
81 | let mut data = 0u64; | |
82 | ptr::copy_nonoverlapping(buf.get_unchecked(i), | |
83 | &mut data as *mut _ as *mut u8, 8); | |
84 | data.to_le() | |
85 | } | |
86 | ||
1a4d82fc JJ |
87 | macro_rules! rotl { |
88 | ($x:expr, $b:expr) => | |
c34b1796 | 89 | (($x << $b) | ($x >> (64_i32.wrapping_sub($b)))) |
1a4d82fc JJ |
90 | } |
91 | ||
92 | macro_rules! compress { | |
93 | ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => | |
94 | ({ | |
c34b1796 | 95 | $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0; |
1a4d82fc | 96 | $v0 = rotl!($v0, 32); |
c34b1796 AL |
97 | $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2; |
98 | $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0; | |
99 | $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2; | |
1a4d82fc JJ |
100 | $v2 = rotl!($v2, 32); |
101 | }) | |
102 | } | |
103 | ||
104 | impl SipHasher { | |
105 | /// Creates a new `SipHasher` with the two initial keys set to 0. | |
106 | #[inline] | |
85aaf69f | 107 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
108 | pub fn new() -> SipHasher { |
109 | SipHasher::new_with_keys(0, 0) | |
110 | } | |
111 | ||
112 | /// Creates a `SipHasher` that is keyed off the provided keys. | |
113 | #[inline] | |
85aaf69f | 114 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
115 | pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher { |
116 | let mut state = SipHasher { | |
117 | k0: key0, | |
118 | k1: key1, | |
119 | length: 0, | |
120 | v0: 0, | |
121 | v1: 0, | |
122 | v2: 0, | |
123 | v3: 0, | |
124 | tail: 0, | |
125 | ntail: 0, | |
126 | }; | |
127 | state.reset(); | |
128 | state | |
129 | } | |
130 | ||
d9579d0f | 131 | #[inline] |
85aaf69f SL |
132 | fn reset(&mut self) { |
133 | self.length = 0; | |
134 | self.v0 = self.k0 ^ 0x736f6d6570736575; | |
135 | self.v1 = self.k1 ^ 0x646f72616e646f6d; | |
136 | self.v2 = self.k0 ^ 0x6c7967656e657261; | |
137 | self.v3 = self.k1 ^ 0x7465646279746573; | |
138 | self.ntail = 0; | |
139 | } | |
140 | ||
d9579d0f | 141 | #[inline] |
1a4d82fc JJ |
142 | fn write(&mut self, msg: &[u8]) { |
143 | let length = msg.len(); | |
144 | self.length += length; | |
145 | ||
85aaf69f | 146 | let mut needed = 0; |
1a4d82fc JJ |
147 | |
148 | if self.ntail != 0 { | |
149 | needed = 8 - self.ntail; | |
150 | if length < needed { | |
151 | self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail; | |
152 | self.ntail += length; | |
153 | return | |
154 | } | |
155 | ||
156 | let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail; | |
157 | ||
158 | self.v3 ^= m; | |
159 | compress!(self.v0, self.v1, self.v2, self.v3); | |
160 | compress!(self.v0, self.v1, self.v2, self.v3); | |
161 | self.v0 ^= m; | |
162 | ||
163 | self.ntail = 0; | |
164 | } | |
165 | ||
166 | // Buffered tail is now flushed, process new input. | |
167 | let len = length - needed; | |
1a4d82fc JJ |
168 | let left = len & 0x7; |
169 | ||
170 | let mut i = needed; | |
c1a9b12d SL |
171 | while i < len - left { |
172 | let mi = unsafe { load_u64_le(msg, i) }; | |
1a4d82fc JJ |
173 | |
174 | self.v3 ^= mi; | |
175 | compress!(self.v0, self.v1, self.v2, self.v3); | |
176 | compress!(self.v0, self.v1, self.v2, self.v3); | |
177 | self.v0 ^= mi; | |
178 | ||
179 | i += 8; | |
180 | } | |
181 | ||
182 | self.tail = u8to64_le!(msg, i, left); | |
183 | self.ntail = left; | |
184 | } | |
185 | } | |
186 | ||
85aaf69f | 187 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 188 | impl Hasher for SipHasher { |
85aaf69f | 189 | #[inline] |
85aaf69f SL |
190 | fn write(&mut self, msg: &[u8]) { |
191 | self.write(msg) | |
1a4d82fc JJ |
192 | } |
193 | ||
d9579d0f | 194 | #[inline] |
1a4d82fc JJ |
195 | fn finish(&self) -> u64 { |
196 | let mut v0 = self.v0; | |
197 | let mut v1 = self.v1; | |
198 | let mut v2 = self.v2; | |
199 | let mut v3 = self.v3; | |
200 | ||
201 | let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail; | |
202 | ||
203 | v3 ^= b; | |
204 | compress!(v0, v1, v2, v3); | |
205 | compress!(v0, v1, v2, v3); | |
206 | v0 ^= b; | |
207 | ||
208 | v2 ^= 0xff; | |
209 | compress!(v0, v1, v2, v3); | |
210 | compress!(v0, v1, v2, v3); | |
211 | compress!(v0, v1, v2, v3); | |
212 | compress!(v0, v1, v2, v3); | |
213 | ||
214 | v0 ^ v1 ^ v2 ^ v3 | |
215 | } | |
216 | } | |
217 | ||
85aaf69f | 218 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
219 | impl Clone for SipHasher { |
220 | #[inline] | |
221 | fn clone(&self) -> SipHasher { | |
222 | SipHasher { | |
223 | k0: self.k0, | |
224 | k1: self.k1, | |
225 | length: self.length, | |
226 | v0: self.v0, | |
227 | v1: self.v1, | |
228 | v2: self.v2, | |
229 | v3: self.v3, | |
230 | tail: self.tail, | |
231 | ntail: self.ntail, | |
232 | } | |
233 | } | |
234 | } | |
235 | ||
85aaf69f | 236 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
237 | impl Default for SipHasher { |
238 | fn default() -> SipHasher { | |
239 | SipHasher::new() | |
240 | } | |
241 | } |