src/librustc_data_structures/sip128.rs

   1 //! This is a copy of `core::hash::sip` adapted to providing 128 bit hashes.
   2
   3 use std::cmp;
   4 use std::hash::Hasher;
   5 use std::mem;
   6 use std::ptr;
   7 use std::slice;
   8
   9 #[cfg(test)]
  10 mod tests;
  11
  12 #[derive(Debug, Clone)]
  13 pub struct SipHasher128 {
  14     k0: u64,
  15     k1: u64,
  16     length: usize, // how many bytes we've processed
  17     state: State,  // hash State
  18     tail: u64,     // unprocessed bytes le
  19     ntail: usize,  // how many bytes in tail are valid
  20 }
  21
  22 #[derive(Debug, Clone, Copy)]
  23 #[repr(C)]
  24 struct State {
  25     // v0, v2 and v1, v3 show up in pairs in the algorithm,
  26     // and simd implementations of SipHash will use vectors
  27     // of v02 and v13. By placing them in this order in the struct,
  28     // the compiler can pick up on just a few simd optimizations by itself.
  29     v0: u64,
  30     v2: u64,
  31     v1: u64,
  32     v3: u64,
  33 }
  34
  35 macro_rules! compress {
  36     ($state:expr) => {{ compress!($state.v0, $state.v1, $state.v2, $state.v3) }};
  37     ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
  38         $v0 = $v0.wrapping_add($v1);
  39         $v1 = $v1.rotate_left(13);
  40         $v1 ^= $v0;
  41         $v0 = $v0.rotate_left(32);
  42         $v2 = $v2.wrapping_add($v3);
  43         $v3 = $v3.rotate_left(16);
  44         $v3 ^= $v2;
  45         $v0 = $v0.wrapping_add($v3);
  46         $v3 = $v3.rotate_left(21);
  47         $v3 ^= $v0;
  48         $v2 = $v2.wrapping_add($v1);
  49         $v1 = $v1.rotate_left(17);
  50         $v1 ^= $v2;
  51         $v2 = $v2.rotate_left(32);
  52     }};
  53 }
  54
  55 /// Loads an integer of the desired type from a byte stream, in LE order. Uses
  56 /// `copy_nonoverlapping` to let the compiler generate the most efficient way
  57 /// to load it from a possibly unaligned address.
  58 ///
  59 /// Unsafe because: unchecked indexing at i..i+size_of(int_ty)
  60 macro_rules! load_int_le {
  61     ($buf:expr, $i:expr, $int_ty:ident) => {{
  62         debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len());
  63         let mut data = 0 as $int_ty;
  64         ptr::copy_nonoverlapping(
  65             $buf.get_unchecked($i),
  66             &mut data as *mut _ as *mut u8,
  67             mem::size_of::<$int_ty>(),
  68         );
  69         data.to_le()
  70     }};
  71 }
  72
  73 /// Loads an u64 using up to 7 bytes of a byte slice.
  74 ///
  75 /// Unsafe because: unchecked indexing at start..start+len
  76 #[inline]
  77 unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
  78     debug_assert!(len < 8);
  79     let mut i = 0; // current byte index (from LSB) in the output u64
  80     let mut out = 0;
  81     if i + 3 < len {
  82         out = u64::from(load_int_le!(buf, start + i, u32));
  83         i += 4;
  84     }
  85     if i + 1 < len {
  86         out |= u64::from(load_int_le!(buf, start + i, u16)) << (i * 8);
  87         i += 2
  88     }
  89     if i < len {
  90         out |= u64::from(*buf.get_unchecked(start + i)) << (i * 8);
  91         i += 1;
  92     }
  93     debug_assert_eq!(i, len);
  94     out
  95 }
  96
  97 impl SipHasher128 {
  98     #[inline]
  99     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher128 {
 100         let mut state = SipHasher128 {
 101             k0: key0,
 102             k1: key1,
 103             length: 0,
 104             state: State { v0: 0, v1: 0, v2: 0, v3: 0 },
 105             tail: 0,
 106             ntail: 0,
 107         };
 108         state.reset();
 109         state
 110     }
 111
 112     #[inline]
 113     fn reset(&mut self) {
 114         self.length = 0;
 115         self.state.v0 = self.k0 ^ 0x736f6d6570736575;
 116         self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
 117         self.state.v2 = self.k0 ^ 0x6c7967656e657261;
 118         self.state.v3 = self.k1 ^ 0x7465646279746573;
 119         self.ntail = 0;
 120
 121         // This is only done in the 128 bit version:
 122         self.state.v1 ^= 0xee;
 123     }
 124
 125     // Specialized write function that is only valid for buffers with len <= 8.
 126     // It's used to force inlining of write_u8 and write_usize, those would normally be inlined
 127     // except for composite types (that includes slices and str hashing because of delimiter).
 128     // Without this extra push the compiler is very reluctant to inline delimiter writes,
 129     // degrading performance substantially for the most common use cases.
 130     #[inline]
 131     fn short_write(&mut self, msg: &[u8]) {
 132         debug_assert!(msg.len() <= 8);
 133         let length = msg.len();
 134         self.length += length;
 135
 136         let needed = 8 - self.ntail;
 137         let fill = cmp::min(length, needed);
 138         if fill == 8 {
 139             self.tail = unsafe { load_int_le!(msg, 0, u64) };
 140         } else {
 141             self.tail |= unsafe { u8to64_le(msg, 0, fill) } << (8 * self.ntail);
 142             if length < needed {
 143                 self.ntail += length;
 144                 return;
 145             }
 146         }
 147         self.state.v3 ^= self.tail;
 148         Sip24Rounds::c_rounds(&mut self.state);
 149         self.state.v0 ^= self.tail;
 150
 151         // Buffered tail is now flushed, process new input.
 152         self.ntail = length - needed;
 153         self.tail = unsafe { u8to64_le(msg, needed, self.ntail) };
 154     }
 155
 156     #[inline(always)]
 157     fn short_write_gen<T>(&mut self, x: T) {
 158         let bytes =
 159             unsafe { slice::from_raw_parts(&x as *const T as *const u8, mem::size_of::<T>()) };
 160         self.short_write(bytes);
 161     }
 162
 163     #[inline]
 164     pub fn finish128(mut self) -> (u64, u64) {
 165         let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
 166
 167         self.state.v3 ^= b;
 168         Sip24Rounds::c_rounds(&mut self.state);
 169         self.state.v0 ^= b;
 170
 171         self.state.v2 ^= 0xee;
 172         Sip24Rounds::d_rounds(&mut self.state);
 173         let _0 = self.state.v0 ^ self.state.v1 ^ self.state.v2 ^ self.state.v3;
 174
 175         self.state.v1 ^= 0xdd;
 176         Sip24Rounds::d_rounds(&mut self.state);
 177         let _1 = self.state.v0 ^ self.state.v1 ^ self.state.v2 ^ self.state.v3;
 178         (_0, _1)
 179     }
 180 }
 181
 182 impl Hasher for SipHasher128 {
 183     #[inline]
 184     fn write_u8(&mut self, i: u8) {
 185         self.short_write_gen(i);
 186     }
 187
 188     #[inline]
 189     fn write_u16(&mut self, i: u16) {
 190         self.short_write_gen(i);
 191     }
 192
 193     #[inline]
 194     fn write_u32(&mut self, i: u32) {
 195         self.short_write_gen(i);
 196     }
 197
 198     #[inline]
 199     fn write_u64(&mut self, i: u64) {
 200         self.short_write_gen(i);
 201     }
 202
 203     #[inline]
 204     fn write_usize(&mut self, i: usize) {
 205         self.short_write_gen(i);
 206     }
 207
 208     #[inline]
 209     fn write_i8(&mut self, i: i8) {
 210         self.short_write_gen(i);
 211     }
 212
 213     #[inline]
 214     fn write_i16(&mut self, i: i16) {
 215         self.short_write_gen(i);
 216     }
 217
 218     #[inline]
 219     fn write_i32(&mut self, i: i32) {
 220         self.short_write_gen(i);
 221     }
 222
 223     #[inline]
 224     fn write_i64(&mut self, i: i64) {
 225         self.short_write_gen(i);
 226     }
 227
 228     #[inline]
 229     fn write_isize(&mut self, i: isize) {
 230         self.short_write_gen(i);
 231     }
 232
 233     #[inline]
 234     fn write(&mut self, msg: &[u8]) {
 235         let length = msg.len();
 236         self.length += length;
 237
 238         let mut needed = 0;
 239
 240         if self.ntail != 0 {
 241             needed = 8 - self.ntail;
 242             self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << (8 * self.ntail);
 243             if length < needed {
 244                 self.ntail += length;
 245                 return;
 246             } else {
 247                 self.state.v3 ^= self.tail;
 248                 Sip24Rounds::c_rounds(&mut self.state);
 249                 self.state.v0 ^= self.tail;
 250                 self.ntail = 0;
 251             }
 252         }
 253
 254         // Buffered tail is now flushed, process new input.
 255         let len = length - needed;
 256         let left = len & 0x7;
 257
 258         let mut i = needed;
 259         while i < len - left {
 260             let mi = unsafe { load_int_le!(msg, i, u64) };
 261
 262             self.state.v3 ^= mi;
 263             Sip24Rounds::c_rounds(&mut self.state);
 264             self.state.v0 ^= mi;
 265
 266             i += 8;
 267         }
 268
 269         self.tail = unsafe { u8to64_le(msg, i, left) };
 270         self.ntail = left;
 271     }
 272
 273     fn finish(&self) -> u64 {
 274         panic!("SipHasher128 cannot provide valid 64 bit hashes")
 275     }
 276 }
 277
 278 #[derive(Debug, Clone, Default)]
 279 struct Sip24Rounds;
 280
 281 impl Sip24Rounds {
 282     #[inline]
 283     fn c_rounds(state: &mut State) {
 284         compress!(state);
 285         compress!(state);
 286     }
 287
 288     #[inline]
 289     fn d_rounds(state: &mut State) {
 290         compress!(state);
 291         compress!(state);
 292         compress!(state);
 293         compress!(state);
 294     }
 295 }