use alloc::collections::BTreeMap;
pub const MERSENNE_61: u64 = (1u64 << 61) - 1;
const INLINE_CACHE_SIZE: usize = 256;
#[inline]
pub fn mersenne_mod(a: u128, p: u64) -> u64 {
assert!(p != 0, "Modulus must be nonzero");
let k = 64 - p.leading_zeros(); let mask = p as u128;
let mut v = a;
while v > mask {
v = (v >> k) + (v & mask);
}
let r = v as u64;
if r >= p {
r - p
} else {
r
}
}
#[inline]
pub fn mersenne_mul(a: u64, b: u64, p: u64) -> u64 {
mersenne_mod(a as u128 * b as u128, p)
}
pub fn phi(q: u64, alpha: u64, p: u64) -> u64 {
if q == 0 {
return 0;
}
if q == 1 {
return 1;
}
let bits = 64 - q.leading_zeros();
let mut phi_val: u64 = 1;
let mut alpha_power: u64 = alpha;
for i in (0..bits - 1).rev() {
let sum = mersenne_mod(1u128 + alpha_power as u128, p);
phi_val = mersenne_mul(phi_val, sum, p);
alpha_power = mersenne_mul(alpha_power, alpha_power, p);
if (q >> i) & 1 == 1 {
phi_val = mersenne_mod(mersenne_mul(phi_val, alpha, p) as u128 + 1, p);
alpha_power = mersenne_mul(alpha_power, alpha, p);
}
}
phi_val
}
pub struct PolynomialHash {
p: u64,
x: u64,
inline_cache: [u64; INLINE_CACHE_SIZE],
overflow_cache: BTreeMap<u64, u64>,
}
impl PolynomialHash {
pub fn new(prime: u64, base: u64) -> Self {
assert!(base >= 2 && base < prime, "Base must be in [2, p-1]");
let mut inline_cache = [0u64; INLINE_CACHE_SIZE];
inline_cache[0] = 1;
for i in 1..INLINE_CACHE_SIZE {
inline_cache[i] = mersenne_mul(inline_cache[i - 1], base, prime);
}
Self {
p: prime,
x: base,
inline_cache,
overflow_cache: BTreeMap::new(),
}
}
pub fn default_hash() -> Self {
Self::new(MERSENNE_61, 131)
}
#[inline]
pub fn prime(&self) -> u64 {
self.p
}
#[inline]
pub fn base(&self) -> u64 {
self.x
}
#[inline]
pub fn power(&mut self, n: u64) -> u64 {
if n < INLINE_CACHE_SIZE as u64 {
return self.inline_cache[n as usize];
}
if let Some(&v) = self.overflow_cache.get(&n) {
return v;
}
let mut result = 1u64;
let mut base = self.x;
let mut exp = n;
let p = self.p;
while exp > 0 {
if exp & 1 == 1 {
result = mersenne_mul(result, base, p);
}
base = mersenne_mul(base, base, p);
exp >>= 1;
}
self.overflow_cache.insert(n, result);
result
}
pub fn hash(&self, data: &[u8]) -> u64 {
if data.is_empty() {
return 0;
}
if self.p == MERSENNE_61 && self.x == 131 {
return hash_default_profile(data);
}
let mut h: u64 = 0;
for &byte in data {
h = mersenne_mod(h as u128 * self.x as u128 + byte as u128 + 1, self.p);
}
h
}
pub fn hash_concat(&mut self, h_a: u64, len_b: u64, h_b: u64) -> u64 {
let x_pow = self.power(len_b);
mersenne_mod(h_a as u128 * x_pow as u128 + h_b as u128, self.p)
}
pub fn hash_repeat(&mut self, h_s: u64, d: u64, q: u64) -> u64 {
let x_d = self.power(d);
let phi_val = phi(q, x_d, self.p);
mersenne_mul(h_s, phi_val, self.p)
}
pub fn hash_overlap(&mut self, h_p: u64, d: u64, l: u64, h_prefix: u64) -> u64 {
let q = l / d;
let r = l % d;
let x_d = self.power(d);
let x_r = self.power(r);
let phi_val = phi(q, x_d, self.p);
let h_repeated = mersenne_mul(h_p, phi_val, self.p);
mersenne_mod(h_repeated as u128 * x_r as u128 + h_prefix as u128, self.p)
}
}
fn hash_default_profile(data: &[u8]) -> u64 {
const BASE8: u64 = 131u64.pow(8);
let mut h = 0u64;
let mut chunks = data.chunks_exact(8);
for chunk in &mut chunks {
let mut block = 0u64;
for &byte in chunk {
block = block * 131 + byte as u64 + 1;
}
h = mersenne_mod(h as u128 * BASE8 as u128 + block as u128, MERSENNE_61);
}
for &byte in chunks.remainder() {
h = mersenne_mod(h as u128 * 131 + byte as u128 + 1, MERSENNE_61);
}
h
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::vec::Vec;
#[test]
fn test_mersenne_mod_basic() {
assert_eq!(mersenne_mod(0, MERSENNE_61), 0);
assert_eq!(mersenne_mod(1, MERSENNE_61), 1);
assert_eq!(mersenne_mod(MERSENNE_61 as u128, MERSENNE_61), 0);
assert_eq!(mersenne_mod(MERSENNE_61 as u128 + 1, MERSENNE_61), 1);
}
#[test]
fn test_mersenne_mod_large() {
let val = MERSENNE_61 as u128 * 1000 + 42;
assert_eq!(mersenne_mod(val, MERSENNE_61), 42);
}
#[test]
fn test_mersenne_mod_full_width_inputs_and_small_moduli() {
assert_eq!(mersenne_mod(256, 3), 1);
for bits in 1..=64 {
let p = ((1u128 << bits) - 1) as u64;
for a in [0, 1, 256, u64::MAX as u128, 1u128 << 127, u128::MAX] {
assert_eq!(mersenne_mod(a, p), (a % p as u128) as u64);
}
}
}
#[test]
#[should_panic(expected = "Modulus must be nonzero")]
fn test_mersenne_mod_rejects_zero_modulus() {
mersenne_mod(1, 0);
}
#[test]
fn test_small_mersenne_hash_matches_modular_reference() {
let h = PolynomialHash::new(3, 2);
let data = [0, 1, 255, 254, 255];
let expected = data
.iter()
.fold(0u64, |acc, &byte| (acc * 2 + byte as u64 + 1) % 3);
assert_eq!(h.hash(&data), expected);
}
#[test]
fn test_mersenne_mul_commutative() {
let a = 12345u64;
let b = 67890u64;
assert_eq!(
mersenne_mul(a, b, MERSENNE_61),
mersenne_mul(b, a, MERSENNE_61)
);
}
#[test]
fn test_phi_base_cases() {
assert_eq!(phi(0, 131, MERSENNE_61), 0);
assert_eq!(phi(1, 131, MERSENNE_61), 1);
}
#[test]
fn test_phi_two() {
let alpha = 131u64;
let expected = mersenne_mod(1 + alpha as u128, MERSENNE_61);
assert_eq!(phi(2, alpha, MERSENNE_61), expected);
}
#[test]
fn test_phi_degenerate_alpha_one() {
assert_eq!(phi(100, 1, MERSENNE_61), 100);
assert_eq!(phi(1000, 1, MERSENNE_61), 1000);
}
#[test]
fn test_phi_large_q() {
let alpha = 5u64;
let q = 20u64;
let mut expected = 0u64;
let mut power = 1u64;
for _ in 0..q {
expected = mersenne_mod(expected as u128 + power as u128, MERSENNE_61);
power = mersenne_mul(power, alpha, MERSENNE_61);
}
assert_eq!(phi(q, alpha, MERSENNE_61), expected);
}
#[test]
fn test_hash_empty() {
let h = PolynomialHash::default_hash();
assert_eq!(h.hash(b""), 0);
}
#[test]
fn test_hash_deterministic() {
let h = PolynomialHash::default_hash();
assert_eq!(h.hash(b"hello world"), h.hash(b"hello world"));
}
#[test]
fn test_hash_different_data() {
let h = PolynomialHash::default_hash();
assert_ne!(h.hash(b"hello"), h.hash(b"world"));
}
#[test]
fn test_hash_concat_theorem1() {
let mut h = PolynomialHash::default_hash();
let a = b"hello ";
let b_ = b"world";
let h_a = h.hash(a);
let h_b = h.hash(b_);
let h_ab = h.hash(b"hello world");
assert_eq!(h.hash_concat(h_a, b_.len() as u64, h_b), h_ab);
}
#[test]
fn test_hash_repeat_theorem2() {
let mut h = PolynomialHash::default_hash();
let s = b"abc";
for q in [1, 2, 5, 10, 100] {
let repeated: Vec<u8> = s.iter().copied().cycle().take(s.len() * q).collect();
let expected = h.hash(&repeated);
let computed = h.hash_repeat(h.hash(s), s.len() as u64, q as u64);
assert_eq!(computed, expected, "Failed for q={}", q);
}
}
#[test]
fn test_hash_overlap_theorem5() {
let mut h = PolynomialHash::default_hash();
let pattern = b"ab";
let d = pattern.len() as u64;
let l = 7u64;
let r = l % d;
let expected = h.hash(b"abababa");
let h_prefix = h.hash(&pattern[..r as usize]);
let computed = h.hash_overlap(h.hash(pattern), d, l, h_prefix);
assert_eq!(computed, expected);
}
#[test]
fn test_python_cross_validation() {
let h = PolynomialHash::default_hash();
assert_eq!(h.hash(b"hello world"), 430229793999670395);
let ab100: Vec<u8> = b"ab".iter().copied().cycle().take(200).collect();
assert_eq!(h.hash(&ab100), 463276214322025987);
assert_eq!(h.hash(b"\x00"), 1);
}
#[test]
fn test_inline_cache_correctness() {
let mut h = PolynomialHash::default_hash();
for n in 0..256u64 {
let cached = h.power(n);
let computed = {
let mut r = 1u64;
let mut b = h.base();
let mut e = n;
let p = h.prime();
while e > 0 {
if e & 1 == 1 {
r = mersenne_mul(r, b, p);
}
b = mersenne_mul(b, b, p);
e >>= 1;
}
r
};
assert_eq!(cached, computed, "Mismatch at n={}", n);
}
}
#[test]
fn test_overflow_cache() {
let mut h = PolynomialHash::default_hash();
let p1 = h.power(1000);
let p2 = h.power(1000);
assert_eq!(p1, p2);
assert_ne!(p1, 0);
}
#[test]
fn test_power_exponents_do_not_truncate_to_pointer_width() {
let mut h = PolynomialHash::default_hash();
for (n, expected) in [
(1u64 << 32, 98_942_608_713_749_192),
((1u64 << 32) + 255, 1_154_367_712_108_772_148),
(u64::MAX, 523_719_968_513_806_577),
] {
assert_eq!(h.power(n), expected);
assert_eq!(h.power(n), expected);
}
}
}