Skip to content

Instantly share code, notes, and snippets.

@zommiommy

zommiommy/sip.rs

Created July 28, 2023 10:51
Show Gist options
  • Save zommiommy/37ae8b30c38df51b11f5dcfb692feee6 to your computer and use it in GitHub Desktop.
Save zommiommy/37ae8b30c38df51b11f5dcfb692feee6 to your computer and use it in GitHub Desktop.
Download ZIP
Hashes impl
Raw
sip.rs
//! Implementation of SipHash from [Jean-Philippe Aumasson](https://www.aumasson.jp/) and Daniel J. Bernstein.
//!
//! SipHash is a general-purpose hashing function: it runs at a good
//! speed (competitive with Spooky and City) and permits strong _keyed_
//! hashing. This lets you key your hash tables from a strong RNG, such as
//! [`rand::os::OsRng`](https://docs.rs/rand/latest/rand/rngs/struct.OsRng.html).
//!
//! Although the SipHash algorithm is considered to be generally strong,
//! it is not intended for cryptographic purposes. As such, all
//! cryptographic uses of this implementation are _strongly discouraged
//!
//! # Reference
//! - <https://www.aumasson.jp/siphash/siphash.pdf>
//! - <https://131002.net/siphash/>
//! - <https://github.com/floodyberry/supercop/blob/master/crypto_auth/siphash24/sse41/siphash.c>
//! - <https://github.com/google/highwayhash/blob/master/highwayhash/sip_hash.h>
//! - <https://github.com/rust-lang/rust/blob/master/library/core/src/hash/sip.rs>
//!
//! # Reimplementation reasons
//! - The rust implementation is not const generic and is deprecated and has no simd optimzations
//! - The [most popular rust library](https://github.com/jedisct1/rust-siphash/tree/master)
//! is just a port of rust implementation and has the same problems minus the deprecation
pub type SipHash64<const C: usize, const D: usize> = Sip64Scalar<C, D>;
/// Loads an integer of the desired type from a byte stream, in LE order. Uses
/// `copy_nonoverlapping` to let the compiler generate the most efficient way
/// to load it from a possibly unaligned address.
///
/// Unsafe because: unchecked indexing at `i..i+size_of(int_ty)`
macro_rules! load_int_le {
($buf:expr, $i:expr, $int_ty:ident) => {{
debug_assert!($i + core::mem::size_of::<$int_ty>() <= $buf.len());
let mut data = 0 as $int_ty;
core::ptr::copy_nonoverlapping(
$buf.as_ptr().add($i),
&mut data as *mut _ as *mut u8,
core::mem::size_of::<$int_ty>(),
);
data.to_le()
}};
}
/// Loads a u64 using up to 7 bytes of a byte slice. It looks clumsy but the
/// `copy_nonoverlapping` calls that occur (via `load_int_le!`) all have fixed
/// sizes and avoid calling `memcpy`, which is good for speed.
///
/// Unsafe because: unchecked indexing at start..start+len
#[inline]
unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
debug_assert!(len < 8);
let mut i = 0; // current byte index (from LSB) in the output u64
let mut out = 0;
if i + 3 < len {
out = load_int_le!(buf, start + i, u32) as u64;
i += 4;
}
if i + 1 < len {
out |= (load_int_le!(buf, start + i, u16) as u64) << (i * 8);
i += 2
}
if i < len {
out |= (*buf.get_unchecked(start + i) as u64) << (i * 8);
i += 1;
}
debug_assert_eq!(i, len);
out
}
/// Porting of 64-bit SipHash from https://github.com/veorq/SipHash
#[derive(Debug, Clone, Copy)]
#[repr(align(16), C)] //alignement and C repr so the compiler can use simd instructions
pub struct Sip64Scalar<const C: usize, const D: usize> {
// interleave the v values so that the compiler can optimize with simd
v0: u64,
v2: u64,
v1: u64,
v3: u64,
k0: u64,
k1: u64,
/// precedent message
m: u64,
/// how many bytes we've processed
length: usize,
/// buffer of unprocessed bytes in little endian order
tail: u64,
/// how many bytes in tail are valid
ntail: usize,
}
impl<const C: usize, const D: usize> core::default::Default for Sip64Scalar<C, D> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<const C: usize, const D: usize> crate::hash::SeedableHasher for Sip64Scalar<C, D> {
type SeedType = [u8; 16];
/// Creates a new hasher with the given seed.
#[inline(always)]
fn new_with_seed(seed: Self::SeedType) -> Self {
Self::new_with_key(seed)
}
}
impl<const C: usize, const D: usize> Sip64Scalar<C, D> {
#[inline]
pub fn new() -> Self {
// same default key as rust implementation
Self::new_with_key([0; 16])
}
#[inline(always)]
pub fn new_with_key(key: [u8; 16]) -> Self {
Self::new_with_key_and_state(
key,
[
0x736f6d6570736575,
0x646f72616e646f6d,
0x6c7967656e657261,
0x7465646279746573,
],
)
}
#[inline(always)]
pub fn new_with_key_and_state(key: [u8; 16], state: [u64; 4]) -> Self {
let mut res = Self {
v0: state[0],
v1: state[1],
v2: state[2],
v3: state[3],
k0: u64::from_le_bytes(key[0..8].try_into().unwrap()),
k1: u64::from_le_bytes(key[8..16].try_into().unwrap()),
m: 0,
length: 0,
tail: 0,
ntail: 0,
};
res.v3 ^= res.k1;
res.v2 ^= res.k0;
res.v1 ^= res.k1;
res.v0 ^= res.k0;
res
}
#[inline(always)]
fn round(&mut self) {
self.v0 = self.v0.wrapping_add(self.v1);
self.v2 = self.v2.wrapping_add(self.v3);
self.v1 = self.v1.rotate_left(13);
self.v3 = self.v3.rotate_left(16);
self.v1 ^= self.v0;
self.v3 ^= self.v2;
self.v0 = self.v0.rotate_left(32);
self.v0 = self.v0.wrapping_add(self.v3);
self.v2 = self.v2.wrapping_add(self.v1);
self.v1 = self.v1.rotate_left(17);
self.v3 = self.v3.rotate_left(21);
self.v3 ^= self.v0;
self.v1 ^= self.v2;
self.v2 = self.v2.rotate_left(32);
}
// A specialized write function for values with size <= 8.
//
// The hashing of multi-byte integers depends on endianness. E.g.:
// - little-endian: `write_u32(0xDDCCBBAA)` == `write([0xAA, 0xBB, 0xCC, 0xDD])`
// - big-endian: `write_u32(0xDDCCBBAA)` == `write([0xDD, 0xCC, 0xBB, 0xAA])`
//
// This function does the right thing for little-endian hardware. On
// big-endian hardware `x` must be byte-swapped first to give the right
// behaviour. After any byte-swapping, the input must be zero-extended to
// 64-bits. The caller is responsible for the byte-swapping and
// zero-extension.
#[inline]
pub fn short_write<T>(&mut self, _x: T, x: u64) {
let size = core::mem::size_of::<T>();
self.length += size;
// The original number must be zero-extended, not sign-extended.
debug_assert!(if size < 8 { x >> (8 * size) == 0 } else { true });
// The number of bytes needed to fill `self.tail`.
let needed = 8 - self.ntail;
self.tail |= x << (8 * self.ntail);
if size < needed {
self.ntail += size;
return;
}
// `self.tail` is full, process it.
self.v3 ^= self.tail;
for _ in 0..C {
self.round();
}
self.v0 ^= self.tail;
self.ntail = size - needed;
self.tail = if needed < 8 { x >> (8 * needed) } else { 0 };
}
}
impl<const C: usize, const D: usize> core::hash::Hasher for Sip64Scalar<C, D> {
#[inline]
fn write(&mut self, msg: &[u8]) {
let length = msg.len();
self.length += length;
let mut needed = 0;
if self.ntail != 0 {
needed = 8 - self.ntail;
self.tail |=
unsafe { u8to64_le(msg, 0, core::cmp::min(length, needed)) } << (8 * self.ntail);
if length < needed {
self.ntail += length;
return;
} else {
self.v3 ^= self.tail;
for _ in 0..C {
self.round();
}
self.v0 ^= self.tail;
self.ntail = 0;
}
}
// Buffered tail is now flushed, process new input.
let len = length - needed;
let left = len & 0x7;
let mut i = needed;
while i < len - left {
let mi = unsafe { load_int_le!(msg, i, u64) };
self.v3 ^= mi;
for _ in 0..C {
self.round();
}
self.v0 ^= mi;
i += 8;
}
self.tail = unsafe { u8to64_le(msg, i, left) };
self.ntail = left;
}
#[inline]
fn finish(&self) -> u64 {
let mut state = *self;
let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;
state.v3 ^= b;
for _ in 0..C {
state.round();
}
state.v0 ^= b;
state.v2 ^= 0xff;
for _ in 0..D {
state.round();
}
state.v0 ^ state.v1 ^ state.v2 ^ state.v3
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.short_write(i, i.to_le() as u64);
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.short_write(i, i as u64);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.short_write(i, i.to_le() as u64);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.short_write(i, i.to_le());
}
}
/// Porting of 128-bit SipHash from https://github.com/veorq/SipHash
#[derive(Debug, Clone, Copy)]
#[repr(transparent)]
pub struct Sip128Scalar<const C: usize, const D: usize>(Sip64Scalar<C, D>);
impl<const C: usize, const D: usize> core::default::Default for Sip128Scalar<C, D> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<const C: usize, const D: usize> Sip128Scalar<C, D> {
#[inline]
pub fn new() -> Self {
Self(<Sip64Scalar<C, D>>::new())
}
#[inline(always)]
pub fn new_with_key(key: [u8; 16]) -> Self {
Self(<Sip64Scalar<C, D>>::new_with_key(key))
}
#[inline(always)]
pub fn new_with_key_and_state(key: [u8; 16], state: [u64; 4]) -> Self {
Self(<Sip64Scalar<C, D>>::new_with_key_and_state(key, state))
}
}
impl<const C: usize, const D: usize> crate::hash::SeedableHasher for Sip128Scalar<C, D> {
type SeedType = [u8; 16];
/// Creates a new hasher with the given seed.
#[inline(always)]
fn new_with_seed(seed: Self::SeedType) -> Self {
Self::new_with_key(seed)
}
}
impl<const C: usize, const D: usize> crate::hash::Hasher for Sip128Scalar<C, D> {
type HashType = u128;
#[inline(always)]
fn write(&mut self, msg: &[u8]) {
self.0.write(msg)
}
#[inline]
fn finish(&self) -> u128 {
let mut state = *self;
let b: u64 = ((self.0.length as u64 & 0xff) << 56) | self.0.tail;
state.0.v3 ^= b;
for _ in 0..C {
state.0.round();
}
state.0.v0 ^= b;
state.0.v2 ^= 0xff;
for _ in 0..D {
state.0.round();
}
let low = state.0.v0 ^ state.0.v1 ^ state.0.v2 ^ state.0.v3;
state.0.v1 ^= 0xdd;
for _ in 0..D {
state.0.round();
}
let high = state.0.v0 ^ state.0.v1 ^ state.0.v2 ^ state.0.v3;
((high as u128) << 64) | (low as u128)
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.0.write_usize(i);
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.0.write_u8(i);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.0.write_u32(i);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.0.write_u64(i);
}
}
#[cfg(test)]
mod test {
use crate::prelude::Hasher;
use super::*;
#[test]
fn test_siphasher() {
let data = (0..255_u8).collect::<Vec<_>>();
for i in 0..16 {
#[allow(deprecated)]
let mut sip =
core::hash::SipHasher::new_with_keys(0x0706050403020100, 0x0f0e0d0c0b0a0908);
sip.write(&data[..i]);
let truth = sip.finish();
let mut sip = <Sip64Scalar<2, 4>>::new_with_key([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
]);
sip.write(&data[..i]);
assert_eq!(sip.finish(), truth);
}
}
#[test]
fn test_default() {
let data = (0..255_u8).collect::<Vec<_>>();
for i in 0..16 {
#[allow(deprecated)]
let mut sip = std::collections::hash_map::DefaultHasher::new();
sip.write(&data[..i]);
let truth = sip.finish();
let mut sip = <Sip64Scalar<1, 3>>::new();
sip.write(&data[..i]);
assert_eq!(sip.finish(), truth);
}
}
}
Raw
siphalf.rs
pub struct SipHalf32<const C: usize, const D: usize> {}
pub struct SipHalf64<const C: usize, const D: usize> {}
Raw
sipsse.rs
#[cfg(target_feature = "sse")]
use core::arch::x86_64::*;
#[allow(non_snake_case)]
#[inline(always)]
const fn _MM_SHUFFLE(z: u32, y: u32, x: u32, w: u32) -> i32 {
((z << 6) | (y << 4) | (x << 2) | w) as i32
}
/// Porting of 64-bit SipHash from https://github.com/veorq/SipHash
/// based on the sse implementation of https://github.com/floodyberry/supercop/blob/master/crypto_auth/siphash24/sse41/siphash.c
#[derive(Debug, Clone, Copy)]
#[repr(align(16), C)] //alignement and C repr so we can use simd instructions
pub struct SipHash64SSE<const C: usize, const D: usize> {
v0v2: __m128i,
v1v3: __m128i,
k0k1: __m128i,
m: u64,
length: u64,
tail: __m128i,
ntail: usize,
}
impl<const C: usize, const D: usize> SipHash64SSE<C, D> {
#[inline(always)]
pub fn new() -> Self {
// same default key as rust implementation
Self::new_with_key([0; 16])
}
#[inline(always)]
pub fn new_with_key(key: [u8; 16]) -> Self {
unsafe {
let mut res = Self {
v0v2: _mm_set_epi64x(0x6c7967656e657261, 0x736f6d6570736575),
v1v3: _mm_set_epi64x(0x7465646279746573, 0x646f72616e646f6d),
k0k1: _mm_loadu_si128(key.as_ptr() as *const __m128i),
m: 0,
length: 0,
tail: _mm_setzero_si128(),
ntail: 0,
};
res.v1v3 = _mm_xor_si128(res.v1v3, res.k0k1);
res.v0v2 = _mm_xor_si128(res.v0v2, res.k0k1);
res
}
}
#[inline(always)]
fn round(&mut self) {
unsafe {
// v0 += v1, v2 += v3
self.v0v2 = _mm_add_epi64(self.v0v2, self.v1v3);
// rotl(v1v3, 13)
let b1 = _mm_xor_si128(
_mm_slli_epi64(self.v1v3, 13),
_mm_srli_epi64(self.v1v3, 64 - 13),
);
// rotl(v3, 16)
let b2 = _mm_shufflehi_epi16::<{ _MM_SHUFFLE(2, 1, 0, 3) }>(self.v1v3);
// select v1 from rotl(v1v3, 13) and v3 from rotl(v3, 16)
self.v1v3 = _mm_blend_epi16(b1, b2, 0b1111_0000);
// rotl 32 v2
self.v1v3 = _mm_shuffle_epi32::<{ _MM_SHUFFLE(0, 1, 3, 2) }>(self.v0v2);
// xor the two halves
self.v1v3 = _mm_xor_si128(self.v1v3, self.v0v2);
// rotl(v1v3, 17)
let b1 = _mm_xor_si128(
_mm_slli_epi64(self.v1v3, 17),
_mm_srli_epi64(self.v1v3, 64 - 17),
);
// rotl(v1v3, 21)
let b2 = _mm_xor_si128(
_mm_slli_epi64(self.v1v3, 21),
_mm_srli_epi64(self.v1v3, 64 - 21),
);
// select v1 from rotl(v1v3, 17) and v3 from rotl(v1v3, 17)
self.v1v3 = _mm_blend_epi16(b1, b2, 0b1111_0000);
// rotl 32 v2
self.v0v2 = _mm_shuffle_epi32::<{ _MM_SHUFFLE(0, 1, 3, 2) }>(self.v0v2);
// xor the two halves
self.v1v3 = _mm_xor_si128(self.v1v3, self.v0v2);
}
}
#[inline]
pub fn short_write<T>(&mut self, _x: T, x: u64) {
todo!();
}
}
impl<const C: usize, const D: usize> core::hash::Hasher for SipHash64SSE<C, D> {
#[inline]
fn write(&mut self, msg: &[u8]) {
let length = msg.len();
self.length += length as u64;
let mut needed = 0;
if self.ntail != 0 {
needed = 8 - self.ntail;
self.tail |=
unsafe { u8to64_le(msg, 0, core::cmp::min(length, needed)) } << (8 * self.ntail);
if length < needed {
self.ntail += length;
return;
} else {
self.v3 ^= self.tail;
for _ in 0..C {
self.round();
}
self.v0 ^= self.tail;
self.ntail = 0;
}
}
// Buffered tail is now flushed, process new input.
let len = length - needed;
let left = len & 0x7;
let mut i = needed;
while i < len - left {
let mi = unsafe { load_int_le!(msg, i, u64) };
self.v3 ^= mi;
for _ in 0..C {
self.round();
}
self.v0 ^= mi;
i += 8;
}
self.tail = unsafe { u8to64_le(msg, i, left) };
self.ntail = left;
}
#[inline]
fn finish(&self) -> u64 {
let mut state = *self;
unsafe {
//state.tail = _mm_xor_si128(state.tail, _mm_set_epi64x(self.length & 0xff), 0);
state.v1v3 = _mm_xor_si128(state.v1v3, state.tail);
for _ in 0..C {
state.round();
}
// v0 ^= b and v2 ^= 0xff
//state.v0v2 = _mm_xor_si128(state.v0v2, _mm_set_epi64x(b, 0xff));
for _ in 0..D {
state.round();
}
// v0 ^ v1 ^ v2 ^ v3
let tmp = _mm_xor_si128(state.v0v2, state.v1v3);
(_mm_extract_epi64(tmp, 0) ^ _mm_extract_epi64(tmp, 1)) as u64
}
}
#[inline]
fn write_usize(&mut self, i: usize) {
self.short_write(i, i.to_le() as u64);
}
#[inline]
fn write_u8(&mut self, i: u8) {
self.short_write(i, i as u64);
}
#[inline]
fn write_u32(&mut self, i: u32) {
self.short_write(i, i.to_le() as u64);
}
#[inline]
fn write_u64(&mut self, i: u64) {
self.short_write(i, i.to_le());
}
}
Raw
spookyv2.rs
//! SpookyHash is a public domain noncryptographic hash function producing
//! well-distributed 128-bit hash values for byte arrays of any length. It can
//! produce 64-bit and 32-bit hash values too, at the same speed, just use the
//! bottom n bits. The C++ reference implementation is specific to 64-bit x86
//! platforms, in particular it assumes the processor is little endian. Long
//! keys hash in 3 bytes per cycle, short keys take about 1 byte per cycle, and
//! there is a 30 cycle startup cost. Keys can be supplied in fragments. The
//! function allows a 128-bit seed. It's named SpookyHash because it was
//! released on Halloween.
//!
//! # Reference
//! - <http://burtleburtle.net/bob/hash/spooky.html>
use crate::hash;
use super::SeedableHasher;
///
/// sc_const: a constant which:
/// * is not zero
/// * is odd
/// * is a not-very-regular mix of 1's and 0's
/// * does not need any other special mathematical properties
///
pub const SC_CONST: u64 = 0xdeadbeefdeadbeef;
#[repr(align(8))] // so it's safe to read data as u64s
pub struct SpookyHashV2 {
data: [u8; 24], // unhashed data, for partial messages
state: State, // internal state of the hash
length: usize, // total length of the input so far
remainder: u8, // length of unhashed data stashed in m_data
}
impl SpookyHashV2 {
const ALLOW_UNALIGNED_READS: bool = false;
const NUM_VARS: usize = 12;
const BLOCK_SIZE: usize = Self::NUM_VARS * 8;
const BUF_SIZE: usize = Self::BLOCK_SIZE * 2;
}
impl core::default::Default for SpookyHashV2 {
#[inline(always)]
fn default() -> Self {
Self::new_with_seed(0)
}
}
impl SeedableHasher for SpookyHashV2 {
type SeedType = u128;
#[inline(always)]
fn new_with_seed(seed: Self::SeedType) -> Self {
let seed1 = seed as u64;
let seed2 = (seed >> 64) as u64;
Self {
data: [0; 24],
state: State {
s0: seed1,
s1: seed2,
s2: SC_CONST,
s3: seed1,
s4: seed2,
s5: SC_CONST,
s6: seed1,
s7: seed2,
s8: SC_CONST,
s9: seed1,
s10: seed2,
s11: SC_CONST,
},
length: 0,
remainder: 0,
}
}
}
impl super::Hasher for SpookyHashV2 {
type HashType = u128;
fn write(&mut self, mut msg: &[u8]) {
let new_length = self.remainder as usize + msg.len();
// Is this message fragment too short? If it is, stuff it away.
if new_length < Self::BUF_SIZE {
self.data[self.remainder as usize..new_length].copy_from_slice(msg);
self.remainder = new_length as u8;
return;
}
self.length += msg.len();
// if we've got anything stuffed away, use it now
if self.remainder != 0 {
let prefix = Self::BUF_SIZE - self.remainder as usize;
self.data[self.remainder as usize..Self::BUF_SIZE].copy_from_slice(&msg[..prefix]);
let low = unsafe { self.data[..Self::BLOCK_SIZE].align_to().1 };
let high = unsafe { self.data[Self::BLOCK_SIZE..].align_to().1 };
mix(low, &mut self.state);
mix(high, &mut self.state);
self.length -= prefix;
msg = &msg[prefix..];
}
// handle all whole blocks of sc_blockSize bytes
let blocks = self.length / Self::BLOCK_SIZE;
if Self::ALLOW_UNALIGNED_READS || (msg.as_ptr() as usize & 0x7) == 0 {
for _ in 0..blocks {
let block = unsafe { msg[..Self::BLOCK_SIZE].align_to().1 };
mix(block, &mut self.state);
msg = &msg[Self::BLOCK_SIZE..];
}
} else {
for _ in 0..blocks {
self.data.copy_from_slice(&msg[..Self::BLOCK_SIZE]);
let block = unsafe { self.data[..Self::BLOCK_SIZE].align_to().1 };
mix(block, &mut self.state);
msg = &msg[Self::BLOCK_SIZE..];
}
}
// stuff away the last few bytes
self.data.copy_from_slice(msg);
}
fn finish(&self) -> Self::HashType {
let hash1: u64;
let hash1: u64;
// init the variables
if self.length < Self::BUF_SIZE
{
let hash = ((self.state.s1 as u128) << 64) | (self.state.s0 as u128);
return short(self.data, hash);
}
const uint64 *data = (const uint64 *)m_data;
uint8 remainder = m_remainder;
if (remainder >= Self::BLOCK_SIZE)
{
// m_data can contain two blocks; handle any whole first block
mix(&data, &mut self.state);
data += Self::NUM_VARS;
remainder -= Self::BLOCK_SIZE;
}
// mix in the last partial block, and the length mod Self::BLOCK_SIZE
memset(&((uint8 *)data)[remainder], 0, (Self::BLOCK_SIZE-remainder));
((uint8 *)data)[Self::BLOCK_SIZE-1] = remainder;
// do some final mixing
End(data, &mut self.state);
*hash1 = h0;
*hash2 = h1;
}
}
/// This is not an array so the compiler can reorder the fields for simd operations
#[derive(Clone, Copy)]
struct State {
s0: u64,
s1: u64,
s2: u64,
s3: u64,
s4: u64,
s5: u64,
s6: u64,
s7: u64,
s8: u64,
s9: u64,
s10: u64,
s11: u64,
}
#[inline(always)]
/// This is used if the input is 96 bytes long or longer.
///
/// The internal state is fully overwritten every 96 bytes.
/// Every input bit appears to cause at least 128 bits of entropy
/// before 96 other bytes are combined, when run forward or backward
/// For every input bit,
/// Two inputs differing in just that input bit
/// Where "differ" means xor or subtraction
/// And the base value is random
/// When run forward or backwards one Mix
/// I tried 3 pairs of each; they all differed by at least 212 bits.
///
fn mix(data: &[u64], s: &mut State) {
debug_assert_eq!(data.len(), 12);
s.s0 = s.s0.wrapping_add(data[0]);
s.s2 ^= s.s10;
s.s11 ^= s.s0;
s.s0 = s.s0.rotate_left(11);
s.s11 = s.s11.wrapping_add(s.s1);
s.s1 = s.s1.wrapping_add(data[1]);
s.s3 ^= s.s11;
s.s0 ^= s.s1;
s.s1 = s.s1.rotate_left(32);
s.s0 = s.s0.wrapping_add(s.s2);
s.s2 = s.s2.wrapping_add(data[2]);
s.s4 ^= s.s0;
s.s1 ^= s.s2;
s.s2 = s.s2.rotate_left(43);
s.s1 = s.s1.wrapping_add(s.s3);
s.s3 = s.s3.wrapping_add(data[3]);
s.s5 ^= s.s1;
s.s2 ^= s.s3;
s.s3 = s.s3.rotate_left(31);
s.s2 = s.s2.wrapping_add(s.s4);
s.s4 = s.s4.wrapping_add(data[4]);
s.s6 ^= s.s2;
s.s3 ^= s.s4;
s.s4 = s.s4.rotate_left(17);
s.s3 = s.s3.wrapping_add(s.s5);
s.s5 = s.s5.wrapping_add(data[5]);
s.s7 ^= s.s3;
s.s4 ^= s.s5;
s.s5 = s.s5.rotate_left(28);
s.s4 = s.s4.wrapping_add(s.s6);
s.s6 = s.s6.wrapping_add(data[6]);
s.s8 ^= s.s4;
s.s5 ^= s.s6;
s.s6 = s.s6.rotate_left(39);
s.s5 = s.s5.wrapping_add(s.s7);
s.s7 = s.s7.wrapping_add(data[7]);
s.s9 ^= s.s5;
s.s6 ^= s.s7;
s.s7 = s.s7.rotate_left(57);
s.s6 = s.s6.wrapping_add(s.s8);
s.s8 = s.s8.wrapping_add(data[8]);
s.s10 ^= s.s6;
s.s7 ^= s.s8;
s.s8 = s.s8.rotate_left(55);
s.s7 = s.s7.wrapping_add(s.s9);
s.s9 = s.s9.wrapping_add(data[9]);
s.s11 ^= s.s7;
s.s8 ^= s.s9;
s.s9 = s.s9.rotate_left(54);
s.s8 = s.s8.wrapping_add(s.s10);
s.s10 = s.s10.wrapping_add(data[10]);
s.s0 ^= s.s8;
s.s9 ^= s.s10;
s.s10 = s.s10.rotate_left(22);
s.s9 = s.s9.wrapping_add(s.s11);
s.s11 = s.s11.wrapping_add(data[11]);
s.s1 ^= s.s9;
s.s10 ^= s.s11;
s.s11 = s.s11.rotate_left(46);
s.s10 = s.s10.wrapping_add(s.s0);
}
#[inline(always)]
/// Mix all 12 inputs together so that h0, h1 are a hash of them all.
///
/// For two inputs differing in just the input bits
/// Where "differ" means xor or subtraction
/// And the base value is random, or a counting value starting at that bit
/// The final result will have each bit of h0, h1 flip
/// For every input bit,
/// with probability 50 +- .3%
/// For every pair of input bits,
/// with probability 50 +- 3%
///
/// This does not rely on the last Mix() call having already mixed some.
/// Two iterations was almost good enough for a 64-bit result, but a
/// 128-bit result is reported, so End() does three iterations.
///
fn end_partial(h: &mut State) {
h.s11 = h.s11.wrapping_add(h.s1);
h.s2 ^= h.s11;
h.s1 = h.s1.rotate_left(44);
h.s0 = h.s0.wrapping_add(h.s2);
h.s3 ^= h.s0;
h.s2 = h.s2.rotate_left(15);
h.s1 = h.s1.wrapping_add(h.s3);
h.s4 ^= h.s1;
h.s3 = h.s3.rotate_left(34);
h.s2 = h.s2.wrapping_add(h.s4);
h.s5 ^= h.s2;
h.s4 = h.s4.rotate_left(21);
h.s3 = h.s3.wrapping_add(h.s5);
h.s6 ^= h.s3;
h.s5 = h.s5.rotate_left(38);
h.s4 = h.s4.wrapping_add(h.s6);
h.s7 ^= h.s4;
h.s6 = h.s6.rotate_left(33);
h.s5 = h.s5.wrapping_add(h.s7);
h.s8 ^= h.s5;
h.s7 = h.s7.rotate_left(10);
h.s6 = h.s6.wrapping_add(h.s8);
h.s9 ^= h.s6;
h.s8 = h.s8.rotate_left(13);
h.s7 = h.s7.wrapping_add(h.s9);
h.s10 ^= h.s7;
h.s9 = h.s9.rotate_left(38);
h.s8 = h.s8.wrapping_add(h.s10);
h.s11 ^= h.s8;
h.s10 = h.s10.rotate_left(53);
h.s9 = h.s9.wrapping_add(h.s11);
h.s0 ^= h.s9;
h.s11 = h.s11.rotate_left(42);
h.s10 = h.s10.wrapping_add(h.s0);
h.s1 ^= h.s10;
h.s0 = h.s0.rotate_left(54);
}
#[inline(always)]
fn end(data: &[u64], h: &mut State) {
debug_assert_eq!(data.len(), 12);
h.s0 += data[0];
h.s1 += data[1];
h.s2 += data[2];
h.s3 += data[3];
h.s4 += data[4];
h.s5 += data[5];
h.s6 += data[6];
h.s7 += data[7];
h.s8 += data[8];
h.s9 += data[9];
h.s10 += data[10];
h.s11 += data[11];
end_partial(h);
end_partial(h);
end_partial(h);
}
///
/// The goal is for each bit of the input to expand into 128 bits of
/// apparent entropy before it is fully overwritten.
/// n trials both set and cleared at least m bits of h0 h1 h2 h3
/// n: 2 m: 29
/// n: 3 m: 46
/// n: 4 m: 57
/// n: 5 m: 107
/// n: 6 m: 146
/// n: 7 m: 152
/// when run forwards or backwards
/// for all 1-bit and 2-bit diffs
/// with diffs defined by either xor or subtraction
/// with a base of all zeros plus a counter, or plus another bit, or random
///
#[inline(always)]
fn short_mix(h: &mut State) {
h.s2 = h.s2.rotate_left(50);
h.s2 = h.s2.wrapping_add(h.s3);
h.s0 ^= h.s2;
h.s3 = h.s3.rotate_left(52);
h.s3 = h.s3.wrapping_add(h.s0);
h.s1 ^= h.s3;
h.s0 = h.s0.rotate_left(30);
h.s0 = h.s0.wrapping_add(h.s1);
h.s2 ^= h.s0;
h.s1 = h.s1.rotate_left(41);
h.s1 = h.s1.wrapping_add(h.s2);
h.s3 ^= h.s1;
h.s2 = h.s2.rotate_left(54);
h.s2 = h.s2.wrapping_add(h.s3);
h.s0 ^= h.s2;
h.s3 = h.s3.rotate_left(48);
h.s3 = h.s3.wrapping_add(h.s0);
h.s1 ^= h.s3;
h.s0 = h.s0.rotate_left(38);
h.s0 = h.s0.wrapping_add(h.s1);
h.s2 ^= h.s0;
h.s1 = h.s1.rotate_left(37);
h.s1 = h.s1.wrapping_add(h.s2);
h.s3 ^= h.s1;
h.s2 = h.s2.rotate_left(62);
h.s2 = h.s2.wrapping_add(h.s3);
h.s0 ^= h.s2;
h.s3 = h.s3.rotate_left(34);
h.s3 = h.s3.wrapping_add(h.s0);
h.s1 ^= h.s3;
h.s0 = h.s0.rotate_left(5);
h.s0 = h.s0.wrapping_add(h.s1);
h.s2 ^= h.s0;
h.s1 = h.s1.rotate_left(36);
h.s1 = h.s1.wrapping_add(h.s2);
h.s3 ^= h.s1;
}
///
/// Mix all 4 inputs together so that h0, h1 are a hash of them all.
///
/// For two inputs differing in just the input bits
/// Where "differ" means xor or subtraction
/// And the base value is random, or a counting value starting at that bit
/// The final result will have each bit of h0, h1 flip
/// For every input bit,
/// with probability 50 +- .3% (it is probably better than that)
/// For every pair of input bits,
/// with probability 50 +- .75% (the worst case is approximately that)
///
#[inline(always)]
fn short_end(h: &mut State) {
h.s3 ^= h.s2;
h.s2 = h.s2.rotate_left(15);
h.s3 = h.s3.wrapping_add(h.s2);
h.s0 ^= h.s3;
h.s3 = h.s3.rotate_left(52);
h.s0 = h.s0.wrapping_add(h.s3);
h.s1 ^= h.s0;
h.s0 = h.s0.rotate_left(26);
h.s1 = h.s1.wrapping_add(h.s0);
h.s2 ^= h.s1;
h.s1 = h.s1.rotate_left(51);
h.s2 = h.s2.wrapping_add(h.s1);
h.s3 ^= h.s2;
h.s2 = h.s2.rotate_left(28);
h.s3 = h.s3.wrapping_add(h.s2);
h.s0 ^= h.s3;
h.s3 = h.s3.rotate_left(9);
h.s0 = h.s0.wrapping_add(h.s3);
h.s1 ^= h.s0;
h.s0 = h.s0.rotate_left(47);
h.s1 = h.s1.wrapping_add(h.s0);
h.s2 ^= h.s1;
h.s1 = h.s1.rotate_left(54);
h.s2 = h.s2.wrapping_add(h.s1);
h.s3 ^= h.s2;
h.s2 = h.s2.rotate_left(32);
h.s3 = h.s3.wrapping_add(h.s2);
h.s0 ^= h.s3;
h.s3 = h.s3.rotate_left(25);
h.s0 = h.s0.wrapping_add(h.s3);
h.s1 ^= h.s0;
h.s0 = h.s0.rotate_left(63);
h.s1 = h.s1.wrapping_add(h.s0);
}
#[inline(always)]
fn short(data: &[u8], hash: u128) -> u128 {
todo!();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment