src/libcore/hash/sip.rs

   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.
  10
  11 //! An implementation of SipHash.
  12
  13 use marker::PhantomData;
  14 use ptr;
  15
  16 /// An implementation of SipHash 1-3.
  17 ///
  18 /// See: https://131002.net/siphash/
  19 #[unstable(feature = "sip_hash_13", issue = "34767")]
  20 #[derive(Debug, Clone, Default)]
  21 pub struct SipHasher13 {
  22     hasher: Hasher<Sip13Rounds>,
  23 }
  24
  25 /// An implementation of SipHash 2-4.
  26 ///
  27 /// See: https://131002.net/siphash/
  28 #[unstable(feature = "sip_hash_13", issue = "34767")]
  29 #[derive(Debug, Clone, Default)]
  30 pub struct SipHasher24 {
  31     hasher: Hasher<Sip24Rounds>,
  32 }
  33
  34 /// An implementation of SipHash 2-4.
  35 ///
  36 /// See: https://131002.net/siphash/
  37 ///
  38 /// This is currently the default hashing function used by standard library
  39 /// (eg. `collections::HashMap` uses it by default).
  40 ///
  41 /// SipHash is a general-purpose hashing function: it runs at a good
  42 /// speed (competitive with Spooky and City) and permits strong _keyed_
  43 /// hashing. This lets you key your hashtables from a strong RNG, such as
  44 /// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html).
  45 ///
  46 /// Although the SipHash algorithm is considered to be generally strong,
  47 /// it is not intended for cryptographic purposes. As such, all
  48 /// cryptographic uses of this implementation are _strongly discouraged_.
  49 #[stable(feature = "rust1", since = "1.0.0")]
  50 #[derive(Debug, Clone, Default)]
  51 pub struct SipHasher(SipHasher24);
  52
  53 #[derive(Debug)]
  54 struct Hasher<S: Sip> {
  55     k0: u64,
  56     k1: u64,
  57     length: usize, // how many bytes we've processed
  58     state: State, // hash State
  59     tail: u64, // unprocessed bytes le
  60     ntail: usize, // how many bytes in tail are valid
  61     _marker: PhantomData<S>,
  62 }
  63
  64 #[derive(Debug, Clone, Copy)]
  65 struct State {
  66     // v0, v2 and v1, v3 show up in pairs in the algorithm,
  67     // and simd implementations of SipHash will use vectors
  68     // of v02 and v13. By placing them in this order in the struct,
  69     // the compiler can pick up on just a few simd optimizations by itself.
  70     v0: u64,
  71     v2: u64,
  72     v1: u64,
  73     v3: u64,
  74 }
  75
  76 // sadly, these macro definitions can't appear later,
  77 // because they're needed in the following defs;
  78 // this design could be improved.
  79
  80 macro_rules! u8to64_le {
  81     ($buf:expr, $i:expr) =>
  82     ($buf[0+$i] as u64 |
  83      ($buf[1+$i] as u64) << 8 |
  84      ($buf[2+$i] as u64) << 16 |
  85      ($buf[3+$i] as u64) << 24 |
  86      ($buf[4+$i] as u64) << 32 |
  87      ($buf[5+$i] as u64) << 40 |
  88      ($buf[6+$i] as u64) << 48 |
  89      ($buf[7+$i] as u64) << 56);
  90     ($buf:expr, $i:expr, $len:expr) =>
  91     ({
  92         let mut t = 0;
  93         let mut out = 0;
  94         while t < $len {
  95             out |= ($buf[t+$i] as u64) << t*8;
  96             t += 1;
  97         }
  98         out
  99     });
 100 }
 101
 102 /// Load a full u64 word from a byte stream, in LE order. Use
 103 /// `copy_nonoverlapping` to let the compiler generate the most efficient way
 104 /// to load u64 from a possibly unaligned address.
 105 ///
 106 /// Unsafe because: unchecked indexing at i..i+8
 107 #[inline]
 108 unsafe fn load_u64_le(buf: &[u8], i: usize) -> u64 {
 109     debug_assert!(i + 8 <= buf.len());
 110     let mut data = 0u64;
 111     ptr::copy_nonoverlapping(buf.get_unchecked(i), &mut data as *mut _ as *mut u8, 8);
 112     data.to_le()
 113 }
 114
 115 macro_rules! rotl {
 116     ($x:expr, $b:expr) =>
 117     (($x << $b) | ($x >> (64_i32.wrapping_sub($b))))
 118 }
 119
 120 macro_rules! compress {
 121     ($state:expr) => ({
 122         compress!($state.v0, $state.v1, $state.v2, $state.v3)
 123     });
 124     ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
 125     ({
 126         $v0 = $v0.wrapping_add($v1); $v1 = rotl!($v1, 13); $v1 ^= $v0;
 127         $v0 = rotl!($v0, 32);
 128         $v2 = $v2.wrapping_add($v3); $v3 = rotl!($v3, 16); $v3 ^= $v2;
 129         $v0 = $v0.wrapping_add($v3); $v3 = rotl!($v3, 21); $v3 ^= $v0;
 130         $v2 = $v2.wrapping_add($v1); $v1 = rotl!($v1, 17); $v1 ^= $v2;
 131         $v2 = rotl!($v2, 32);
 132     });
 133 }
 134
 135 impl SipHasher {
 136     /// Creates a new `SipHasher` with the two initial keys set to 0.
 137     #[inline]
 138     #[stable(feature = "rust1", since = "1.0.0")]
 139     pub fn new() -> SipHasher {
 140         SipHasher::new_with_keys(0, 0)
 141     }
 142
 143     /// Creates a `SipHasher` that is keyed off the provided keys.
 144     #[inline]
 145     #[stable(feature = "rust1", since = "1.0.0")]
 146     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
 147         SipHasher(SipHasher24::new_with_keys(key0, key1))
 148     }
 149 }
 150
 151
 152 impl SipHasher13 {
 153     /// Creates a new `SipHasher13` with the two initial keys set to 0.
 154     #[inline]
 155     #[unstable(feature = "sip_hash_13", issue = "34767")]
 156     pub fn new() -> SipHasher13 {
 157         SipHasher13::new_with_keys(0, 0)
 158     }
 159
 160     /// Creates a `SipHasher13` that is keyed off the provided keys.
 161     #[inline]
 162     #[unstable(feature = "sip_hash_13", issue = "34767")]
 163     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 {
 164         SipHasher13 {
 165             hasher: Hasher::new_with_keys(key0, key1)
 166         }
 167     }
 168 }
 169
 170 impl SipHasher24 {
 171     /// Creates a new `SipHasher24` with the two initial keys set to 0.
 172     #[inline]
 173     #[unstable(feature = "sip_hash_13", issue = "34767")]
 174     pub fn new() -> SipHasher24 {
 175         SipHasher24::new_with_keys(0, 0)
 176     }
 177
 178     /// Creates a `SipHasher24` that is keyed off the provided keys.
 179     #[inline]
 180     #[unstable(feature = "sip_hash_13", issue = "34767")]
 181     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 {
 182         SipHasher24 {
 183             hasher: Hasher::new_with_keys(key0, key1)
 184         }
 185     }
 186 }
 187
 188 impl<S: Sip> Hasher<S> {
 189     #[inline]
 190     fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> {
 191         let mut state = Hasher {
 192             k0: key0,
 193             k1: key1,
 194             length: 0,
 195             state: State {
 196                 v0: 0,
 197                 v1: 0,
 198                 v2: 0,
 199                 v3: 0,
 200             },
 201             tail: 0,
 202             ntail: 0,
 203             _marker: PhantomData,
 204         };
 205         state.reset();
 206         state
 207     }
 208
 209     #[inline]
 210     fn reset(&mut self) {
 211         self.length = 0;
 212         self.state.v0 = self.k0 ^ 0x736f6d6570736575;
 213         self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
 214         self.state.v2 = self.k0 ^ 0x6c7967656e657261;
 215         self.state.v3 = self.k1 ^ 0x7465646279746573;
 216         self.ntail = 0;
 217     }
 218 }
 219
 220 #[stable(feature = "rust1", since = "1.0.0")]
 221 impl super::Hasher for SipHasher {
 222     #[inline]
 223     fn write(&mut self, msg: &[u8]) {
 224         self.0.write(msg)
 225     }
 226
 227     #[inline]
 228     fn finish(&self) -> u64 {
 229         self.0.finish()
 230     }
 231 }
 232
 233 #[unstable(feature = "sip_hash_13", issue = "34767")]
 234 impl super::Hasher for SipHasher13 {
 235     #[inline]
 236     fn write(&mut self, msg: &[u8]) {
 237         self.hasher.write(msg)
 238     }
 239
 240     #[inline]
 241     fn finish(&self) -> u64 {
 242         self.hasher.finish()
 243     }
 244 }
 245
 246 #[unstable(feature = "sip_hash_13", issue = "34767")]
 247 impl super::Hasher for SipHasher24 {
 248     #[inline]
 249     fn write(&mut self, msg: &[u8]) {
 250         self.hasher.write(msg)
 251     }
 252
 253     #[inline]
 254     fn finish(&self) -> u64 {
 255         self.hasher.finish()
 256     }
 257 }
 258
 259 impl<S: Sip> super::Hasher for Hasher<S> {
 260     #[inline]
 261     fn write(&mut self, msg: &[u8]) {
 262         let length = msg.len();
 263         self.length += length;
 264
 265         let mut needed = 0;
 266
 267         if self.ntail != 0 {
 268             needed = 8 - self.ntail;
 269             if length < needed {
 270                 self.tail |= u8to64_le!(msg, 0, length) << 8 * self.ntail;
 271                 self.ntail += length;
 272                 return
 273             }
 274
 275             let m = self.tail | u8to64_le!(msg, 0, needed) << 8 * self.ntail;
 276
 277             self.state.v3 ^= m;
 278             S::c_rounds(&mut self.state);
 279             self.state.v0 ^= m;
 280
 281             self.ntail = 0;
 282         }
 283
 284         // Buffered tail is now flushed, process new input.
 285         let len = length - needed;
 286         let left = len & 0x7;
 287
 288         let mut i = needed;
 289         while i < len - left {
 290             let mi = unsafe { load_u64_le(msg, i) };
 291
 292             self.state.v3 ^= mi;
 293             S::c_rounds(&mut self.state);
 294             self.state.v0 ^= mi;
 295
 296             i += 8;
 297         }
 298
 299         self.tail = u8to64_le!(msg, i, left);
 300         self.ntail = left;
 301     }
 302
 303     #[inline]
 304     fn finish(&self) -> u64 {
 305         let mut state = self.state;
 306
 307         let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
 308
 309         state.v3 ^= b;
 310         S::c_rounds(&mut state);
 311         state.v0 ^= b;
 312
 313         state.v2 ^= 0xff;
 314         S::d_rounds(&mut state);
 315
 316         state.v0 ^ state.v1 ^ state.v2 ^ state.v3
 317     }
 318 }
 319
 320 impl<S: Sip> Clone for Hasher<S> {
 321     #[inline]
 322     fn clone(&self) -> Hasher<S> {
 323         Hasher {
 324             k0: self.k0,
 325             k1: self.k1,
 326             length: self.length,
 327             state: self.state,
 328             tail: self.tail,
 329             ntail: self.ntail,
 330             _marker: self._marker,
 331         }
 332     }
 333 }
 334
 335 impl<S: Sip> Default for Hasher<S> {
 336     #[inline]
 337     fn default() -> Hasher<S> {
 338         Hasher::new_with_keys(0, 0)
 339     }
 340 }
 341
 342 #[doc(hidden)]
 343 trait Sip {
 344     fn c_rounds(&mut State);
 345     fn d_rounds(&mut State);
 346 }
 347
 348 #[derive(Debug, Clone, Default)]
 349 struct Sip13Rounds;
 350
 351 impl Sip for Sip13Rounds {
 352     #[inline]
 353     fn c_rounds(state: &mut State) {
 354         compress!(state);
 355     }
 356
 357     #[inline]
 358     fn d_rounds(state: &mut State) {
 359         compress!(state);
 360         compress!(state);
 361         compress!(state);
 362     }
 363 }
 364
 365 #[derive(Debug, Clone, Default)]
 366 struct Sip24Rounds;
 367
 368 impl Sip for Sip24Rounds {
 369     #[inline]
 370     fn c_rounds(state: &mut State) {
 371         compress!(state);
 372         compress!(state);
 373     }
 374
 375     #[inline]
 376     fn d_rounds(state: &mut State) {
 377         compress!(state);
 378         compress!(state);
 379         compress!(state);
 380         compress!(state);
 381     }
 382 }