// rapidhash v1 (https://github.com/Nicoshev/rapidhash, BSD-2-Clause), as
// vendored by ninja v1.13.2 in src/third_party/rapidhash/rapidhash.h with
// RAPIDHASH_FAST and RAPIDHASH_UNROLLED. ninja's build log (format v7)
// stores this hash of each command, so moonja must match it bit for bit.
///|
let rapid_seed : UInt64 = 0xbdd89aa982704029
///|
let rapid_secret0 : UInt64 = 0x2d358dccaa6c78a5
///|
let rapid_secret1 : UInt64 = 0x8bb84b93962eacc9
///|
let rapid_secret2 : UInt64 = 0x4b33a62ed433d4a3
///|
/// The full 128-bit product of `a` and `b` as (low, high), computed from
/// 32-bit halves like rapidhash's portable fallback.
fn rapid_mum(a : UInt64, b : UInt64) -> (UInt64, UInt64) {
let mask : UInt64 = 0xffffffff
let ha = a >> 32
let hb = b >> 32
let la = a & mask
let lb = b & mask
let rh = ha * hb
let rm0 = ha * lb
let rm1 = hb * la
let rl = la * lb
let t = rl + (rm0 << 32)
let mut c : UInt64 = if t < rl { 1 } else { 0 }
let lo = t + (rm1 << 32)
c += if lo < t { 1 } else { 0 }
let hi = rh + (rm0 >> 32) + (rm1 >> 32) + c
(lo, hi)
}
///|
fn rapid_mix(a : UInt64, b : UInt64) -> UInt64 {
let (lo, hi) = rapid_mum(a, b)
lo ^ hi
}
///|
/// The little-endian 32-bit word at `i`. Assembled in 32-bit arithmetic:
/// on the JS backend UInt64 is a BigInt, and each BigInt operation costs.
fn rapid_word32(p : Bytes, i : Int32) -> UInt32 {
p[i].to_uint() |
(p[i + 1].to_uint() << 8) |
(p[i + 2].to_uint() << 16) |
(p[i + 3].to_uint() << 24)
}
///|
fn rapid_read64(p : Bytes, i : Int32) -> UInt64 {
rapid_word32(p, i).to_uint64() | (rapid_word32(p, i + 4).to_uint64() << 32)
}
///|
fn rapid_read32(p : Bytes, i : Int32) -> UInt64 {
rapid_word32(p, i).to_uint64()
}
///|
fn rapid_read_small(p : Bytes, k : Int32) -> UInt64 {
(p[0].to_uint64() << 56) |
(p[k >> 1].to_uint64() << 32) |
p[k - 1].to_uint64()
}
///|
/// rapidhash of `key` with ninja's default seed.
pub fn rapidhash(key : Bytes) -> UInt64 {
let len = key.length()
let len64 = len.to_uint64()
let mut seed = rapid_seed
seed = seed ^ rapid_mix(seed ^ rapid_secret0, rapid_secret1) ^ len64
let mut a : UInt64 = 0
let mut b : UInt64 = 0
if len <= 16 {
if len >= 4 {
let last = len - 4
a = (rapid_read32(key, 0) << 32) | rapid_read32(key, last)
let delta = (len & 24) >> (len >> 3)
b = (rapid_read32(key, delta) << 32) | rapid_read32(key, last - delta)
} else if len > 0 {
a = rapid_read_small(key, len)
b = 0
}
} else {
let mut p = 0
let mut i = len
if i > 48 {
let mut see1 = seed
let mut see2 = seed
while i >= 96 {
seed = rapid_mix(
rapid_read64(key, p) ^ rapid_secret0,
rapid_read64(key, p + 8) ^ seed,
)
see1 = rapid_mix(
rapid_read64(key, p + 16) ^ rapid_secret1,
rapid_read64(key, p + 24) ^ see1,
)
see2 = rapid_mix(
rapid_read64(key, p + 32) ^ rapid_secret2,
rapid_read64(key, p + 40) ^ see2,
)
seed = rapid_mix(
rapid_read64(key, p + 48) ^ rapid_secret0,
rapid_read64(key, p + 56) ^ seed,
)
see1 = rapid_mix(
rapid_read64(key, p + 64) ^ rapid_secret1,
rapid_read64(key, p + 72) ^ see1,
)
see2 = rapid_mix(
rapid_read64(key, p + 80) ^ rapid_secret2,
rapid_read64(key, p + 88) ^ see2,
)
p += 96
i -= 96
}
if i >= 48 {
seed = rapid_mix(
rapid_read64(key, p) ^ rapid_secret0,
rapid_read64(key, p + 8) ^ seed,
)
see1 = rapid_mix(
rapid_read64(key, p + 16) ^ rapid_secret1,
rapid_read64(key, p + 24) ^ see1,
)
see2 = rapid_mix(
rapid_read64(key, p + 32) ^ rapid_secret2,
rapid_read64(key, p + 40) ^ see2,
)
p += 48
i -= 48
}
seed = seed ^ see1 ^ see2
}
if i > 16 {
seed = rapid_mix(
rapid_read64(key, p) ^ rapid_secret2,
rapid_read64(key, p + 8) ^ seed ^ rapid_secret1,
)
if i > 32 {
seed = rapid_mix(
rapid_read64(key, p + 16) ^ rapid_secret2,
rapid_read64(key, p + 24) ^ seed,
)
}
}
a = rapid_read64(key, p + i - 16)
b = rapid_read64(key, p + i - 8)
}
a = a ^ rapid_secret1
b = b ^ seed
let (lo, hi) = rapid_mum(a, b)
rapid_mix(lo ^ rapid_secret0 ^ len64, hi ^ rapid_secret1)
}
///|
/// ninja's `BuildLog::LogEntry::HashCommand`: rapidhash of the command's
/// UTF-8 bytes.
pub fn hash_command(command : String) -> UInt64 {
rapidhash(@utf8.encode(command))
}