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
   8 #[cfg(test)]
   9 mod tests;
  10
  11 #[derive(Debug, Clone)]
  12 pub struct SipHasher128 {
  13     k0: u64,
  14     k1: u64,
  15     length: usize, // how many bytes we've processed
  16     state: State,  // hash State
  17     tail: u64,     // unprocessed bytes le
  18     ntail: usize,  // how many bytes in tail are valid
  19 }
  20
  21 #[derive(Debug, Clone, Copy)]
  22 #[repr(C)]
  23 struct State {
  24     // v0, v2 and v1, v3 show up in pairs in the algorithm,
  25     // and simd implementations of SipHash will use vectors
  26     // of v02 and v13. By placing them in this order in the struct,
  27     // the compiler can pick up on just a few simd optimizations by itself.
  28     v0: u64,
  29     v2: u64,
  30     v1: u64,
  31     v3: u64,
  32 }
  33
  34 macro_rules! compress {
  35     ($state:expr) => {{ compress!($state.v0, $state.v1, $state.v2, $state.v3) }};
  36     ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
  37         $v0 = $v0.wrapping_add($v1);
  38         $v1 = $v1.rotate_left(13);
  39         $v1 ^= $v0;
  40         $v0 = $v0.rotate_left(32);
  41         $v2 = $v2.wrapping_add($v3);
  42         $v3 = $v3.rotate_left(16);
  43         $v3 ^= $v2;
  44         $v0 = $v0.wrapping_add($v3);
  45         $v3 = $v3.rotate_left(21);
  46         $v3 ^= $v0;
  47         $v2 = $v2.wrapping_add($v1);
  48         $v1 = $v1.rotate_left(17);
  49         $v1 ^= $v2;
  50         $v2 = $v2.rotate_left(32);
  51     }};
  52 }
  53
  54 /// Loads up to 8 bytes from a byte-slice into a little-endian u64.
  55 #[inline]
  56 fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
  57     assert!(len <= 8 && start + len <= buf.len());
  58
  59     let mut out = 0u64;
  60     unsafe {
  61         let out_ptr = &mut out as *mut _ as *mut u8;
  62         ptr::copy_nonoverlapping(buf.as_ptr().offset(start as isize), out_ptr, len);
  63     }
  64     out.to_le()
  65 }
  66
  67 impl SipHasher128 {
  68     #[inline]
  69     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher128 {
  70         let mut state = SipHasher128 {
  71             k0: key0,
  72             k1: key1,
  73             length: 0,
  74             state: State { v0: 0, v1: 0, v2: 0, v3: 0 },
  75             tail: 0,
  76             ntail: 0,
  77         };
  78         state.reset();
  79         state
  80     }
  81
  82     #[inline]
  83     fn reset(&mut self) {
  84         self.length = 0;
  85         self.state.v0 = self.k0 ^ 0x736f6d6570736575;
  86         self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
  87         self.state.v2 = self.k0 ^ 0x6c7967656e657261;
  88         self.state.v3 = self.k1 ^ 0x7465646279746573;
  89         self.ntail = 0;
  90
  91         // This is only done in the 128 bit version:
  92         self.state.v1 ^= 0xee;
  93     }
  94
  95     // A specialized write function for values with size <= 8.
  96     //
  97     // The hashing of multi-byte integers depends on endianness. E.g.:
  98     // - little-endian: `write_u32(0xDDCCBBAA)` == `write([0xAA, 0xBB, 0xCC, 0xDD])`
  99     // - big-endian:    `write_u32(0xDDCCBBAA)` == `write([0xDD, 0xCC, 0xBB, 0xAA])`
 100     //
 101     // This function does the right thing for little-endian hardware. On
 102     // big-endian hardware `x` must be byte-swapped first to give the right
 103     // behaviour. After any byte-swapping, the input must be zero-extended to
 104     // 64-bits. The caller is responsible for the byte-swapping and
 105     // zero-extension.
 106     #[inline]
 107     fn short_write<T>(&mut self, _x: T, x: u64) {
 108         let size = mem::size_of::<T>();
 109         self.length += size;
 110
 111         // The original number must be zero-extended, not sign-extended.
 112         debug_assert!(if size < 8 { x >> (8 * size) == 0 } else { true });
 113
 114         // The number of bytes needed to fill `self.tail`.
 115         let needed = 8 - self.ntail;
 116
 117         // SipHash parses the input stream as 8-byte little-endian integers.
 118         // Inputs are put into `self.tail` until 8 bytes of data have been
 119         // collected, and then that word is processed.
 120         //
 121         // For example, imagine that `self.tail` is 0x0000_00EE_DDCC_BBAA,
 122         // `self.ntail` is 5 (because 5 bytes have been put into `self.tail`),
 123         // and `needed` is therefore 3.
 124         //
 125         // - Scenario 1, `self.write_u8(0xFF)`: we have already zero-extended
 126         //   the input to 0x0000_0000_0000_00FF. We now left-shift it five
 127         //   bytes, giving 0x0000_FF00_0000_0000. We then bitwise-OR that value
 128         //   into `self.tail`, resulting in 0x0000_FFEE_DDCC_BBAA.
 129         //   (Zero-extension of the original input is critical in this scenario
 130         //   because we don't want the high two bytes of `self.tail` to be
 131         //   touched by the bitwise-OR.) `self.tail` is not yet full, so we
 132         //   return early, after updating `self.ntail` to 6.
 133         //
 134         // - Scenario 2, `self.write_u32(0xIIHH_GGFF)`: we have already
 135         //   zero-extended the input to 0x0000_0000_IIHH_GGFF. We now
 136         //   left-shift it five bytes, giving 0xHHGG_FF00_0000_0000. We then
 137         //   bitwise-OR that value into `self.tail`, resulting in
 138         //   0xHHGG_FFEE_DDCC_BBAA. `self.tail` is now full, and we can use it
 139         //   to update `self.state`. (As mentioned above, this assumes a
 140         //   little-endian machine; on a big-endian machine we would have
 141         //   byte-swapped 0xIIHH_GGFF in the caller, giving 0xFFGG_HHII, and we
 142         //   would then end up bitwise-ORing 0xGGHH_II00_0000_0000 into
 143         //   `self.tail`).
 144         //
 145         self.tail |= x << (8 * self.ntail);
 146         if size < needed {
 147             self.ntail += size;
 148             return;
 149         }
 150
 151         // `self.tail` is full, process it.
 152         self.state.v3 ^= self.tail;
 153         Sip24Rounds::c_rounds(&mut self.state);
 154         self.state.v0 ^= self.tail;
 155
 156         // Continuing scenario 2: we have one byte left over from the input. We
 157         // set `self.ntail` to 1 and `self.tail` to `0x0000_0000_IIHH_GGFF >>
 158         // 8*3`, which is 0x0000_0000_0000_00II. (Or on a big-endian machine
 159         // the prior byte-swapping would leave us with 0x0000_0000_0000_00FF.)
 160         //
 161         // The `if` is needed to avoid shifting by 64 bits, which Rust
 162         // complains about.
 163         self.ntail = size - needed;
 164         self.tail = if needed < 8 { x >> (8 * needed) } else { 0 };
 165     }
 166
 167     #[inline]
 168     pub fn finish128(mut self) -> (u64, u64) {
 169         let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
 170
 171         self.state.v3 ^= b;
 172         Sip24Rounds::c_rounds(&mut self.state);
 173         self.state.v0 ^= b;
 174
 175         self.state.v2 ^= 0xee;
 176         Sip24Rounds::d_rounds(&mut self.state);
 177         let _0 = self.state.v0 ^ self.state.v1 ^ self.state.v2 ^ self.state.v3;
 178
 179         self.state.v1 ^= 0xdd;
 180         Sip24Rounds::d_rounds(&mut self.state);
 181         let _1 = self.state.v0 ^ self.state.v1 ^ self.state.v2 ^ self.state.v3;
 182         (_0, _1)
 183     }
 184 }
 185
 186 impl Hasher for SipHasher128 {
 187     #[inline]
 188     fn write_u8(&mut self, i: u8) {
 189         self.short_write(i, i as u64);
 190     }
 191
 192     #[inline]
 193     fn write_u16(&mut self, i: u16) {
 194         self.short_write(i, i.to_le() as u64);
 195     }
 196
 197     #[inline]
 198     fn write_u32(&mut self, i: u32) {
 199         self.short_write(i, i.to_le() as u64);
 200     }
 201
 202     #[inline]
 203     fn write_u64(&mut self, i: u64) {
 204         self.short_write(i, i.to_le() as u64);
 205     }
 206
 207     #[inline]
 208     fn write_usize(&mut self, i: usize) {
 209         self.short_write(i, i.to_le() as u64);
 210     }
 211
 212     #[inline]
 213     fn write_i8(&mut self, i: i8) {
 214         self.short_write(i, i as u8 as u64);
 215     }
 216
 217     #[inline]
 218     fn write_i16(&mut self, i: i16) {
 219         self.short_write(i, (i as u16).to_le() as u64);
 220     }
 221
 222     #[inline]
 223     fn write_i32(&mut self, i: i32) {
 224         self.short_write(i, (i as u32).to_le() as u64);
 225     }
 226
 227     #[inline]
 228     fn write_i64(&mut self, i: i64) {
 229         self.short_write(i, (i as u64).to_le() as u64);
 230     }
 231
 232     #[inline]
 233     fn write_isize(&mut self, i: isize) {
 234         self.short_write(i, (i as usize).to_le() as u64);
 235     }
 236
 237     #[inline]
 238     fn write(&mut self, msg: &[u8]) {
 239         let length = msg.len();
 240         self.length += length;
 241
 242         let mut needed = 0;
 243
 244         if self.ntail != 0 {
 245             needed = 8 - self.ntail;
 246             self.tail |= u8to64_le(msg, 0, cmp::min(length, needed)) << (8 * self.ntail);
 247             if length < needed {
 248                 self.ntail += length;
 249                 return;
 250             } else {
 251                 self.state.v3 ^= self.tail;
 252                 Sip24Rounds::c_rounds(&mut self.state);
 253                 self.state.v0 ^= self.tail;
 254                 self.ntail = 0;
 255             }
 256         }
 257
 258         // Buffered tail is now flushed, process new input.
 259         let len = length - needed;
 260         let left = len & 0x7;
 261
 262         let mut i = needed;
 263         while i < len - left {
 264             let mi = u8to64_le(msg, i, 8);
 265
 266             self.state.v3 ^= mi;
 267             Sip24Rounds::c_rounds(&mut self.state);
 268             self.state.v0 ^= mi;
 269
 270             i += 8;
 271         }
 272
 273         self.tail = u8to64_le(msg, i, left);
 274         self.ntail = left;
 275     }
 276
 277     fn finish(&self) -> u64 {
 278         panic!("SipHasher128 cannot provide valid 64 bit hashes")
 279     }
 280 }
 281
 282 #[derive(Debug, Clone, Default)]
 283 struct Sip24Rounds;
 284
 285 impl Sip24Rounds {
 286     #[inline]
 287     fn c_rounds(state: &mut State) {
 288         compress!(state);
 289         compress!(state);
 290     }
 291
 292     #[inline]
 293     fn d_rounds(state: &mut State) {
 294         compress!(state);
 295         compress!(state);
 296         compress!(state);
 297         compress!(state);
 298     }
 299 }