src/libstd/hash/sip.rs

   1 // Copyright 2012-2014 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 /*!
  12  * Implementation of SipHash 2-4
  13  *
  14  * See: http://131002.net/siphash/
  15  *
  16  * Consider this as a main "general-purpose" hash for all hashtables: it
  17  * runs at good speed (competitive with spooky and city) and permits
  18  * strong _keyed_ hashing. Key your hashtables from a strong RNG,
  19  * such as `rand::Rng`.
  20  *
  21  * Although the SipHash algorithm is considered to be cryptographically
  22  * strong, this implementation has not been reviewed for such purposes.
  23  * As such, all cryptographic uses of this implementation are strongly
  24  * discouraged.
  25  */
  26
  27 use clone::Clone;
  28 use container::Container;
  29 use default::Default;
  30 use int;
  31 use io::{IoResult, Writer};
  32 use iter::Iterator;
  33 use result::Ok;
  34 use slice::ImmutableVector;
  35 use uint;
  36
  37 use super::{Hash, Hasher};
  38
  39 /// `SipState` computes a SipHash 2-4 hash over a stream of bytes.
  40 pub struct SipState {
  41     k0: u64,
  42     k1: u64,
  43     length: uint, // how many bytes we've processed
  44     v0: u64,      // hash state
  45     v1: u64,
  46     v2: u64,
  47     v3: u64,
  48     tail: u64, // unprocessed bytes le
  49     ntail: uint,  // how many bytes in tail are valid
  50 }
  51
  52 // sadly, these macro definitions can't appear later,
  53 // because they're needed in the following defs;
  54 // this design could be improved.
  55
  56 macro_rules! u8to64_le (
  57     ($buf:expr, $i:expr) =>
  58     ($buf[0+$i] as u64 |
  59      $buf[1+$i] as u64 << 8 |
  60      $buf[2+$i] as u64 << 16 |
  61      $buf[3+$i] as u64 << 24 |
  62      $buf[4+$i] as u64 << 32 |
  63      $buf[5+$i] as u64 << 40 |
  64      $buf[6+$i] as u64 << 48 |
  65      $buf[7+$i] as u64 << 56);
  66     ($buf:expr, $i:expr, $len:expr) =>
  67     ({
  68         let mut t = 0;
  69         let mut out = 0u64;
  70         while t < $len {
  71             out |= $buf[t+$i] as u64 << t*8;
  72             t += 1;
  73         }
  74         out
  75     });
  76 )
  77
  78 macro_rules! rotl (
  79     ($x:expr, $b:expr) =>
  80     (($x << $b) | ($x >> (64 - $b)))
  81 )
  82
  83 macro_rules! compress (
  84     ($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
  85     ({
  86         $v0 += $v1; $v1 = rotl!($v1, 13); $v1 ^= $v0;
  87         $v0 = rotl!($v0, 32);
  88         $v2 += $v3; $v3 = rotl!($v3, 16); $v3 ^= $v2;
  89         $v0 += $v3; $v3 = rotl!($v3, 21); $v3 ^= $v0;
  90         $v2 += $v1; $v1 = rotl!($v1, 17); $v1 ^= $v2;
  91         $v2 = rotl!($v2, 32);
  92     })
  93 )
  94
  95 impl SipState {
  96     /// Create a `SipState` that is keyed off the provided keys.
  97     #[inline]
  98     pub fn new() -> SipState {
  99         SipState::new_with_keys(0, 0)
 100     }
 101
 102     /// Create a `SipState` that is keyed off the provided keys.
 103     #[inline]
 104     pub fn new_with_keys(key0: u64, key1: u64) -> SipState {
 105         let mut state = SipState {
 106             k0: key0,
 107             k1: key1,
 108             length: 0,
 109             v0: 0,
 110             v1: 0,
 111             v2: 0,
 112             v3: 0,
 113             tail: 0,
 114             ntail: 0,
 115         };
 116         state.reset();
 117         state
 118     }
 119
 120     /// Reset the state back to it's initial state.
 121     #[inline]
 122     pub fn reset(&mut self) {
 123         self.length = 0;
 124         self.v0 = self.k0 ^ 0x736f6d6570736575;
 125         self.v1 = self.k1 ^ 0x646f72616e646f6d;
 126         self.v2 = self.k0 ^ 0x6c7967656e657261;
 127         self.v3 = self.k1 ^ 0x7465646279746573;
 128         self.ntail = 0;
 129     }
 130
 131     /// Return the computed hash.
 132     #[inline]
 133     pub fn result(&self) -> u64 {
 134         let mut v0 = self.v0;
 135         let mut v1 = self.v1;
 136         let mut v2 = self.v2;
 137         let mut v3 = self.v3;
 138
 139         let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
 140
 141         v3 ^= b;
 142         compress!(v0, v1, v2, v3);
 143         compress!(v0, v1, v2, v3);
 144         v0 ^= b;
 145
 146         v2 ^= 0xff;
 147         compress!(v0, v1, v2, v3);
 148         compress!(v0, v1, v2, v3);
 149         compress!(v0, v1, v2, v3);
 150         compress!(v0, v1, v2, v3);
 151
 152         v0 ^ v1 ^ v2 ^ v3
 153     }
 154
 155     #[inline]
 156     fn write_le(&mut self, n: u64, size: uint) {
 157         self.tail |= n << 8*self.ntail;
 158         self.ntail += size;
 159
 160         if self.ntail >= 8 {
 161             let m = self.tail;
 162
 163             self.v3 ^= m;
 164             compress!(self.v0, self.v1, self.v2, self.v3);
 165             compress!(self.v0, self.v1, self.v2, self.v3);
 166             self.v0 ^= m;
 167
 168             self.ntail -= 8;
 169             if self.ntail == 0 {
 170                 self.tail = 0;
 171             } else {
 172                 self.tail = n >> 64 - 8*self.ntail;
 173             }
 174         }
 175     }
 176 }
 177
 178 macro_rules! make_write_le(
 179     ($this:expr, $n:expr, $size:expr) => ({
 180           $this.write_le($n as u64, $size);
 181           $this.length += $size;
 182           Ok(())
 183     })
 184 )
 185
 186 impl Writer for SipState {
 187     #[inline]
 188     fn write(&mut self, msg: &[u8]) -> IoResult<()> {
 189         let length = msg.len();
 190         self.length += length;
 191
 192         let mut needed = 0u;
 193
 194         if self.ntail != 0 {
 195             needed = 8 - self.ntail;
 196             if length < needed {
 197                 self.tail |= u8to64_le!(msg, 0, length) << 8*self.ntail;
 198                 self.ntail += length;
 199                 return Ok(());
 200             }
 201
 202             let m = self.tail | u8to64_le!(msg, 0, needed) << 8*self.ntail;
 203
 204             self.v3 ^= m;
 205             compress!(self.v0, self.v1, self.v2, self.v3);
 206             compress!(self.v0, self.v1, self.v2, self.v3);
 207             self.v0 ^= m;
 208
 209             self.ntail = 0;
 210         }
 211
 212         // Buffered tail is now flushed, process new input.
 213         let len = length - needed;
 214         let end = len & (!0x7);
 215         let left = len & 0x7;
 216
 217         let mut i = needed;
 218         while i < end {
 219             let mi = u8to64_le!(msg, i);
 220
 221             self.v3 ^= mi;
 222             compress!(self.v0, self.v1, self.v2, self.v3);
 223             compress!(self.v0, self.v1, self.v2, self.v3);
 224             self.v0 ^= mi;
 225
 226             i += 8;
 227         }
 228
 229         self.tail = u8to64_le!(msg, i, left);
 230         self.ntail = left;
 231
 232         Ok(())
 233     }
 234
 235     #[inline]
 236     fn write_u8(&mut self, n: u8) -> IoResult<()> {
 237         make_write_le!(self, n, 1)
 238     }
 239
 240     #[inline]
 241     fn write_le_u16(&mut self, n: u16) -> IoResult<()> {
 242         make_write_le!(self, n, 2)
 243     }
 244
 245     #[inline]
 246     fn write_le_u32(&mut self, n: u32) -> IoResult<()> {
 247         make_write_le!(self, n, 4)
 248     }
 249
 250     #[inline]
 251     fn write_le_u64(&mut self, n: u64) -> IoResult<()> {
 252         make_write_le!(self, n, 8)
 253     }
 254
 255     #[inline]
 256     fn write_le_uint(&mut self, n: uint) -> IoResult<()> {
 257         make_write_le!(self, n, uint::BYTES)
 258     }
 259
 260     #[inline]
 261     fn write_i8(&mut self, n: i8) -> IoResult<()> {
 262         make_write_le!(self, n, 1)
 263     }
 264
 265     #[inline]
 266     fn write_le_i16(&mut self, n: i16) -> IoResult<()> {
 267         make_write_le!(self, n, 2)
 268     }
 269
 270     #[inline]
 271     fn write_le_i32(&mut self, n: i32) -> IoResult<()> {
 272         make_write_le!(self, n, 4)
 273     }
 274
 275     #[inline]
 276     fn write_le_i64(&mut self, n: i64) -> IoResult<()> {
 277         make_write_le!(self, n, 8)
 278     }
 279
 280     #[inline]
 281     fn write_le_int(&mut self, n: int) -> IoResult<()> {
 282         make_write_le!(self, n, int::BYTES)
 283     }
 284
 285 }
 286
 287 impl Clone for SipState {
 288     #[inline]
 289     fn clone(&self) -> SipState {
 290         *self
 291     }
 292 }
 293
 294 impl Default for SipState {
 295     #[inline]
 296     fn default() -> SipState {
 297         SipState::new()
 298     }
 299 }
 300
 301 /// `SipHasher` computes the SipHash algorithm from a stream of bytes.
 302 #[deriving(Clone)]
 303 pub struct SipHasher {
 304     k0: u64,
 305     k1: u64,
 306 }
 307
 308 impl SipHasher {
 309     /// Create a `Sip`.
 310     #[inline]
 311     pub fn new() -> SipHasher {
 312         SipHasher::new_with_keys(0, 0)
 313     }
 314
 315     /// Create a `Sip` that is keyed off the provided keys.
 316     #[inline]
 317     pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
 318         SipHasher {
 319             k0: key0,
 320             k1: key1,
 321         }
 322     }
 323 }
 324
 325 impl Hasher<SipState> for SipHasher {
 326     #[inline]
 327     fn hash<T: Hash<SipState>>(&self, value: &T) -> u64 {
 328         let mut state = SipState::new_with_keys(self.k0, self.k1);
 329         value.hash(&mut state);
 330         state.result()
 331     }
 332 }
 333
 334 impl Default for SipHasher {
 335     #[inline]
 336     fn default() -> SipHasher {
 337         SipHasher::new()
 338     }
 339 }
 340
 341 /// Hash a value using the SipHash algorithm.
 342 #[inline]
 343 pub fn hash<T: Hash<SipState>>(value: &T) -> u64 {
 344     let mut state = SipState::new();
 345     value.hash(&mut state);
 346     state.result()
 347 }
 348
 349 /// Hash a value with the SipHash algorithm with the provided keys.
 350 #[inline]
 351 pub fn hash_with_keys<T: Hash<SipState>>(k0: u64, k1: u64, value: &T) -> u64 {
 352     let mut state = SipState::new_with_keys(k0, k1);
 353     value.hash(&mut state);
 354     state.result()
 355 }
 356
 357
 358
 359 #[cfg(test)]
 360 mod tests {
 361     extern crate test;
 362     use prelude::*;
 363     use num::ToStrRadix;
 364     use option::{Some, None};
 365     use str::{Str,StrSlice};
 366     use strbuf::StrBuf;
 367     use slice::{Vector, ImmutableVector};
 368     use self::test::Bencher;
 369
 370     use super::super::Hash;
 371     use super::{SipState, hash, hash_with_keys};
 372
 373     // Hash just the bytes of the slice, without length prefix
 374     struct Bytes<'a>(&'a [u8]);
 375
 376     impl<'a, S: Writer> Hash<S> for Bytes<'a> {
 377         #[allow(unused_must_use)]
 378         fn hash(&self, state: &mut S) {
 379             let Bytes(v) = *self;
 380             state.write(v);
 381         }
 382     }
 383
 384     #[test]
 385     #[allow(unused_must_use)]
 386     fn test_siphash() {
 387         let vecs : [[u8, ..8], ..64] = [
 388             [ 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72, ],
 389             [ 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74, ],
 390             [ 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d, ],
 391             [ 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85, ],
 392             [ 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf, ],
 393             [ 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18, ],
 394             [ 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb, ],
 395             [ 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab, ],
 396             [ 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93, ],
 397             [ 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e, ],
 398             [ 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a, ],
 399             [ 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4, ],
 400             [ 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75, ],
 401             [ 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14, ],
 402             [ 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7, ],
 403             [ 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1, ],
 404             [ 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f, ],
 405             [ 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69, ],
 406             [ 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b, ],
 407             [ 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb, ],
 408             [ 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe, ],
 409             [ 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0, ],
 410             [ 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93, ],
 411             [ 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8, ],
 412             [ 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8, ],
 413             [ 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc, ],
 414             [ 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17, ],
 415             [ 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f, ],
 416             [ 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde, ],
 417             [ 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6, ],
 418             [ 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad, ],
 419             [ 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32, ],
 420             [ 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71, ],
 421             [ 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7, ],
 422             [ 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12, ],
 423             [ 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15, ],
 424             [ 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31, ],
 425             [ 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02, ],
 426             [ 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca, ],
 427             [ 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a, ],
 428             [ 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e, ],
 429             [ 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad, ],
 430             [ 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18, ],
 431             [ 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4, ],
 432             [ 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9, ],
 433             [ 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9, ],
 434             [ 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb, ],
 435             [ 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0, ],
 436             [ 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6, ],
 437             [ 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7, ],
 438             [ 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee, ],
 439             [ 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1, ],
 440             [ 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a, ],
 441             [ 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81, ],
 442             [ 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f, ],
 443             [ 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24, ],
 444             [ 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7, ],
 445             [ 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea, ],
 446             [ 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60, ],
 447             [ 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66, ],
 448             [ 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c, ],
 449             [ 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f, ],
 450             [ 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5, ],
 451             [ 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95, ]
 452         ];
 453
 454         let k0 = 0x_07_06_05_04_03_02_01_00_u64;
 455         let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08_u64;
 456         let mut buf = Vec::new();
 457         let mut t = 0;
 458         let mut state_inc = SipState::new_with_keys(k0, k1);
 459         let mut state_full = SipState::new_with_keys(k0, k1);
 460
 461         fn to_hex_str(r: &[u8, ..8]) -> ~str {
 462             let mut s = StrBuf::new();
 463             for b in r.iter() {
 464                 s.push_str((*b as uint).to_str_radix(16u));
 465             }
 466             s.into_owned()
 467         }
 468
 469         fn result_bytes(h: u64) -> ~[u8] {
 470             ~[(h >> 0) as u8,
 471               (h >> 8) as u8,
 472               (h >> 16) as u8,
 473               (h >> 24) as u8,
 474               (h >> 32) as u8,
 475               (h >> 40) as u8,
 476               (h >> 48) as u8,
 477               (h >> 56) as u8,
 478             ]
 479         }
 480
 481         fn result_str(h: u64) -> ~str {
 482             let r = result_bytes(h);
 483             let mut s = StrBuf::new();
 484             for b in r.iter() {
 485                 s.push_str((*b as uint).to_str_radix(16u));
 486             }
 487             s.into_owned()
 488         }
 489
 490         while t < 64 {
 491             debug!("siphash test {}", t);
 492             let vec = u8to64_le!(vecs[t], 0);
 493             let out = hash_with_keys(k0, k1, &Bytes(buf.as_slice()));
 494             debug!("got {:?}, expected {:?}", out, vec);
 495             assert_eq!(vec, out);
 496
 497             state_full.reset();
 498             state_full.write(buf.as_slice());
 499             let f = result_str(state_full.result());
 500             let i = result_str(state_inc.result());
 501             let v = to_hex_str(&vecs[t]);
 502             debug!("{}: ({}) => inc={} full={}", t, v, i, f);
 503
 504             assert!(f == i && f == v);
 505
 506             buf.push(t as u8);
 507             state_inc.write_u8(t as u8);
 508
 509             t += 1;
 510         }
 511     }
 512
 513     #[test] #[cfg(target_arch = "arm")]
 514     fn test_hash_uint() {
 515         let val = 0xdeadbeef_deadbeef_u64;
 516         assert!(hash(&(val as u64)) != hash(&(val as uint)));
 517         assert_eq!(hash(&(val as u32)), hash(&(val as uint)));
 518     }
 519     #[test] #[cfg(target_arch = "x86_64")]
 520     fn test_hash_uint() {
 521         let val = 0xdeadbeef_deadbeef_u64;
 522         assert_eq!(hash(&(val as u64)), hash(&(val as uint)));
 523         assert!(hash(&(val as u32)) != hash(&(val as uint)));
 524     }
 525     #[test] #[cfg(target_arch = "x86")]
 526     fn test_hash_uint() {
 527         let val = 0xdeadbeef_deadbeef_u64;
 528         assert!(hash(&(val as u64)) != hash(&(val as uint)));
 529         assert_eq!(hash(&(val as u32)), hash(&(val as uint)));
 530     }
 531
 532     #[test]
 533     fn test_hash_idempotent() {
 534         let val64 = 0xdeadbeef_deadbeef_u64;
 535         assert_eq!(hash(&val64), hash(&val64));
 536         let val32 = 0xdeadbeef_u32;
 537         assert_eq!(hash(&val32), hash(&val32));
 538     }
 539
 540     #[test]
 541     fn test_hash_no_bytes_dropped_64() {
 542         let val = 0xdeadbeef_deadbeef_u64;
 543
 544         assert!(hash(&val) != hash(&zero_byte(val, 0)));
 545         assert!(hash(&val) != hash(&zero_byte(val, 1)));
 546         assert!(hash(&val) != hash(&zero_byte(val, 2)));
 547         assert!(hash(&val) != hash(&zero_byte(val, 3)));
 548         assert!(hash(&val) != hash(&zero_byte(val, 4)));
 549         assert!(hash(&val) != hash(&zero_byte(val, 5)));
 550         assert!(hash(&val) != hash(&zero_byte(val, 6)));
 551         assert!(hash(&val) != hash(&zero_byte(val, 7)));
 552
 553         fn zero_byte(val: u64, byte: uint) -> u64 {
 554             assert!(byte < 8);
 555             val & !(0xff << (byte * 8))
 556         }
 557     }
 558
 559     #[test]
 560     fn test_hash_no_bytes_dropped_32() {
 561         let val = 0xdeadbeef_u32;
 562
 563         assert!(hash(&val) != hash(&zero_byte(val, 0)));
 564         assert!(hash(&val) != hash(&zero_byte(val, 1)));
 565         assert!(hash(&val) != hash(&zero_byte(val, 2)));
 566         assert!(hash(&val) != hash(&zero_byte(val, 3)));
 567
 568         fn zero_byte(val: u32, byte: uint) -> u32 {
 569             assert!(byte < 4);
 570             val & !(0xff << (byte * 8))
 571         }
 572     }
 573
 574     #[test]
 575     fn test_hash_no_concat_alias() {
 576         let s = ("aa", "bb");
 577         let t = ("aabb", "");
 578         let u = ("a", "abb");
 579
 580         assert!(s != t && t != u);
 581         assert!(hash(&s) != hash(&t) && hash(&s) != hash(&u));
 582
 583         let v = (&[1u8], &[0u8, 0], &[0u8]);
 584         let w = (&[1u8, 0, 0, 0], &[], &[]);
 585
 586         assert!(v != w);
 587         assert!(hash(&v) != hash(&w));
 588     }
 589
 590     #[bench]
 591     fn bench_str_under_8_bytes(b: &mut Bencher) {
 592         let s = "foo";
 593         b.iter(|| {
 594             assert_eq!(hash(&s), 16262950014981195938);
 595         })
 596     }
 597
 598     #[bench]
 599     fn bench_str_of_8_bytes(b: &mut Bencher) {
 600         let s = "foobar78";
 601         b.iter(|| {
 602             assert_eq!(hash(&s), 4898293253460910787);
 603         })
 604     }
 605
 606     #[bench]
 607     fn bench_str_over_8_bytes(b: &mut Bencher) {
 608         let s = "foobarbaz0";
 609         b.iter(|| {
 610             assert_eq!(hash(&s), 10581415515220175264);
 611         })
 612     }
 613
 614     #[bench]
 615     fn bench_long_str(b: &mut Bencher) {
 616         let s = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor \
 617 incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud \
 618 exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute \
 619 irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla \
 620 pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui \
 621 officia deserunt mollit anim id est laborum.";
 622         b.iter(|| {
 623             assert_eq!(hash(&s), 17717065544121360093);
 624         })
 625     }
 626
 627     #[bench]
 628     fn bench_u64(b: &mut Bencher) {
 629         let u = 16262950014981195938u64;
 630         b.iter(|| {
 631             assert_eq!(hash(&u), 5254097107239593357);
 632         })
 633     }
 634
 635     #[deriving(Hash)]
 636     struct Compound {
 637         x: u8,
 638         y: u64,
 639         z: ~str,
 640     }
 641
 642     #[bench]
 643     fn bench_compound_1(b: &mut Bencher) {
 644         let compound = Compound {
 645             x: 1,
 646             y: 2,
 647             z: "foobarbaz".to_owned(),
 648         };
 649         b.iter(|| {
 650             assert_eq!(hash(&compound), 15783192367317361799);
 651         })
 652     }
 653 }