/// The bloom library relied on the excellent murmur library
/// by Sébastien Paolacci. Unfortunately, it involved some heap
/// allocation. We want to avoid any heap allocation whatsoever
/// in the hashing process. To preserve backward compatibility, we roll
/// our own hashing functions. They are designed to be strictly equivalent
/// to Paolacci's implementation.
///|
let c1 : UInt64 = 0x87c37b91114253d5
///|
let c2 : UInt64 = 0x4cf5ad432745937f
///|
let block_size = 16
///|
/// Digest128 represents a partial evaluation of a 128 bits hash.
priv struct Digest128 {
mut h1 : UInt64 // Unfinalized running hash part 1.
mut h2 : UInt64 // Unfinalized running hash part 2.
}
///|
/// bmix will hash blocks (16 bytes)
fn Digest128::bmix(self : Digest128, bv : Bytes) -> Unit {
let n = bv.length() / block_size
for i in 0.. UInt64 {
let shift = shift % 64
if shift == 0 {
return num
}
(num << shift) | (num >> (64 - shift))
}
///|
/// bmix_words will hash two 64-bit words (16 bytes)
fn Digest128::bmix_words(
self : Digest128,
num1 : UInt64,
num2 : UInt64,
) -> Unit {
let mut h1 = self.h1
let mut h2 = self.h2
let mut k1 = num1 * c1
let mut k2 = num2 * c2
k1 = rotate_left(k1, 31)
k1 = k1 * c2
h1 = h1 ^ k1
h1 = rotate_left(h1, 27)
h1 = h1 + h2
h1 = h1 * 5 + 0x52dce729
k2 = rotate_left(k2, 33)
k2 = k2 * c1
h2 = h2 ^ k2
h2 = rotate_left(h2, 31)
h2 = h2 + h1
h2 = h2 * 5 + 0x38495ab5
self.h1 = h1
self.h2 = h2
}
///|
/// sum128 computers two 64-bit hash value. It is assumed that
/// bmix was first called on the data to process complete blocks
/// of 16 bytes. The 'tail' is a slice representing the 'tail' (leftover
/// elements, fewer than 16). If pad_tail is true, we make it seem like
/// there is an extra element with value 1 appended to the tail.
/// The length parameter represents the full length of the data (including
/// the blocks of 16 bytes, and, if pad_tail is true, an extra byte).
fn Digest128::sum128(
self : Digest128,
pad_tail : Bool,
length : UInt32,
tail : Bytes,
) -> (UInt64, UInt64) {
let mut h1 = self.h1
let mut h2 = self.h2
let mut k1 : UInt64 = 0
let mut k2 : UInt64 = 0
if pad_tail {
let remainder = (tail.length() + 1) & 15
match remainder {
15 => k2 = k2 ^ (1UL << 48)
14 => k2 = k2 ^ (1UL << 40)
13 => k2 = k2 ^ (1UL << 32)
12 => k2 = k2 ^ (1UL << 24)
11 => k2 = k2 ^ (1UL << 16)
10 => k2 = k2 ^ (1UL << 8)
9 => {
k2 = k2 ^ 1UL
k2 = k2 * c2
k2 = rotate_left(k2, 33)
k2 = k2 * c1
h2 = h2 ^ k2
}
8 => k1 = k1 ^ (1UL << 56)
7 => k1 = k1 ^ (1UL << 48)
6 => k1 = k1 ^ (1UL << 40)
5 => k1 = k1 ^ (1UL << 32)
4 => k1 = k1 ^ (1UL << 24)
3 => k1 = k1 ^ (1UL << 16)
2 => k1 = k1 ^ (1UL << 8)
1 => {
k1 = k1 ^ 1UL
k1 = k1 * c1
k1 = rotate_left(k1, 31)
k1 = k1 * c2
h1 = h1 ^ k1
}
_ => ()
}
}
let remainder = tail.length() & 15
if remainder >= 15 {
k2 = k2 ^ (tail[14].to_uint64() << 48)
}
if remainder >= 14 {
k2 = k2 ^ (tail[13].to_uint64() << 40)
}
if remainder >= 13 {
k2 = k2 ^ (tail[12].to_uint64() << 32)
}
if remainder >= 12 {
k2 = k2 ^ (tail[11].to_uint64() << 24)
}
if remainder >= 11 {
k2 = k2 ^ (tail[10].to_uint64() << 16)
}
if remainder >= 10 {
k2 = k2 ^ (tail[9].to_uint64() << 8)
}
if remainder >= 9 {
k2 = k2 ^ tail[8].to_uint64()
k2 = k2 * c2
k2 = rotate_left(k2, 33)
k2 = k2 * c1
h2 = h2 ^ k2
}
if remainder >= 8 {
k1 = k1 ^ (tail[7].to_uint64() << 56)
}
if remainder >= 7 {
k1 = k1 ^ (tail[6].to_uint64() << 48)
}
if remainder >= 6 {
k1 = k1 ^ (tail[5].to_uint64() << 40)
}
if remainder >= 5 {
k1 = k1 ^ (tail[4].to_uint64() << 32)
}
if remainder >= 4 {
k1 = k1 ^ (tail[3].to_uint64() << 24)
}
if remainder >= 3 {
k1 = k1 ^ (tail[2].to_uint64() << 16)
}
if remainder >= 2 {
k1 = k1 ^ (tail[1].to_uint64() << 8)
}
if remainder >= 1 {
k1 = k1 ^ tail[0].to_uint64()
k1 = k1 * c1
k1 = rotate_left(k1, 31)
k1 = k1 * c2
h1 = h1 ^ k1
}
h1 = h1 ^ length.to_uint64()
h2 = h2 ^ length.to_uint64()
h1 = h1 + h2
h2 = h2 + h1
h1 = fmix64(h1)
h2 = fmix64(h2)
h1 = h1 + h2
h2 = h2 + h1
return (h1, h2)
}
///|
fn fmix64(k : UInt64) -> UInt64 {
let mut k = k ^ (k >> 33)
k = k * 0xff51afd7ed558ccd
k = k ^ (k >> 33)
k = k * 0xc4ceb9fe1a85ec53
k = k ^ (k >> 33)
return k
}
///|
fn Digest128::new() -> Digest128 {
{ h1: 0, h2: 0, }
}
///|
/// sum256 will compute 4 64-bit hash values from the input.
/// It is designed to never allocate memory on the heap. So it
/// works without any byte buffer whatsoever.
fn Digest128::sum256(
self : Digest128,
data : Bytes,
) -> (UInt64, UInt64, UInt64, UInt64) {
// Process as many bytes as possible.
self.bmix(data)
// We have enough to compute the first two 64-bit numbers
let length = data.length()
let tail_length = length % block_size
let tail = data[length - tail_length:].to_owned()
let (hash1, hash2) = self.sum128(false, length.reinterpret_as_uint(), tail)
// Next we want to 'virtually' append 1 to the input, but,
// we do not want to append to an actual array!!!
if tail_length == block_size - 1 {
// We are left with no tail!!!
let word1 = read_uint64_le(tail[0:8])
let mut word2 = read_uint_le(tail[8:12]).to_uint64()
word2 = word2 |
(tail[12].to_uint64() << 32) |
(tail[13].to_uint64() << 40) |
(tail[14].to_uint64() << 48)
// We append 1.
word2 = word2 | (1UL << 56)
// We process the resulting 2 words.
self.bmix_words(word1, word2)
let (hash3, hash4) = self.sum128(
false,
(length + 1).reinterpret_as_uint(),
b"",
)
return (hash1, hash2, hash3, hash4)
} else {
// We still have a tail (fewer than 15 bytes) but we
// need to append '1' to it.
let (hash3, hash4) = self.sum128(
true,
(length + 1).reinterpret_as_uint(),
tail,
)
return (hash1, hash2, hash3, hash4)
}
}