rolling_hash/
lib.rs

1//! Rolling (Rabin-Karp-style) hash for strings and byte slices.
2//!
3//! Provides two flavours:
4//!
5//! * [`RollingHash`] — single-modulus rolling hash over `&[u8]`. The current
6//!   hash value is maintained incrementally as the window slides. Useful
7//!   when you need a fingerprint that updates in `O(1)` per shift.
8//!
9//! * [`DoubleRollingHash`] — same idea, with two different moduli for very
10//!   low collision rates; pairs of hashes can be compared for equality.
11//!
12//! Both flavours precompute the base-power table for substrings up to some
13//! `max_len`. To compare hashes of arbitrary substrings of a long string,
14//! use [`compute_hash`] (single) or build a [`DoubleRollingHash`] and
15//! query substrings using `hash_range(lo, hi)` / `combine(lo1, hi1, lo2, hi2)`.
16
17/// Default base used for the rolling hash.
18pub const DEFAULT_BASE: u64 = 131;
19/// Default modulus (a known large prime).
20pub const DEFAULT_MOD: u64 = (1 << 61) - 1;
21
22/// Single-modulus rolling hash with `O(1)` append / slide.
23#[derive(Debug, Clone)]
24pub struct RollingHash {
25    base: u64,
26    mod_: u64,
27    hash: u64,
28}
29
30impl RollingHash {
31    /// Create a new rolling hash with the default base and modulus.
32    pub fn new() -> Self {
33        Self::with_base_mod(DEFAULT_BASE, DEFAULT_MOD)
34    }
35
36    /// Create with a custom base and modulus.
37    pub fn with_base_mod(base: u64, mod_: u64) -> Self {
38        Self { base, mod_, hash: 0 }
39    }
40
41    /// Reset to the empty state.
42    pub fn clear(&mut self) {
43        self.hash = 0;
44    }
45
46    /// Append a byte to the hash, computing
47    /// `h = (h * base + byte) mod mod_`.
48    pub fn push(&mut self, byte: u8) {
49        self.hash = mul_mod(self.hash, self.base, self.mod_);
50        self.hash = add_mod(self.hash, byte as u64, self.mod_);
51    }
52
53    /// Remove the leftmost byte `b_old` from a window of size `n`, computing
54    /// `h = (h - b_old * base^(n-1)) mod mod_`.
55    ///
56    /// `window_len_before` is the length of the window *before* the removal.
57    pub fn pop(&mut self, b_old: u8, window_len_before: usize) {
58        debug_assert!(window_len_before >= 1);
59        let p = pow_mod(self.base, (window_len_before - 1) as u64, self.mod_);
60        let sub = mul_mod(b_old as u64, p, self.mod_);
61        self.hash = add_mod(self.hash, self.mod_ - sub % self.mod_, self.mod_);
62    }
63
64    /// Current hash value.
65    pub fn value(&self) -> u64 {
66        self.hash
67    }
68}
69
70impl Default for RollingHash {
71    fn default() -> Self {
72        Self::new()
73    }
74}
75
76/// Compute the polynomial hash of a byte slice.
77///
78/// `h(s) = s[0]*b^(n-1) + s[1]*b^(n-2) + ... + s[n-1]  (mod mod_)`.
79pub fn compute_hash(bytes: &[u8], base: u64, mod_: u64) -> u64 {
80    let mut h = 0u64;
81    for &b in bytes {
82        h = mul_mod(h, base, mod_);
83        h = add_mod(h, b as u64, mod_);
84    }
85    h
86}
87
88/// Two-modulus rolling hash with combine/equal-friendly semantics.
89#[derive(Debug, Clone)]
90pub struct DoubleRollingHash {
91    h1: RollingHash,
92    h2: RollingHash,
93    /// Base for the first hash stream (exposed for advanced users).
94    pub pub_b1: u64,
95    /// Base for the second hash stream.
96    pub pub_b2: u64,
97    /// Modulus for the first hash stream.
98    pub pub_m1: u64,
99    /// Modulus for the second hash stream.
100    pub pub_m2: u64,
101}
102
103impl DoubleRollingHash {
104    /// Create with two distinct (base, modulus) pairs. Recommended:
105    /// `(131, 2^61-1)` and `(137, 2^61-1)`.
106    pub fn new(base1: u64, mod1: u64, base2: u64, mod2: u64) -> Self {
107        Self {
108            h1: RollingHash::with_base_mod(base1, mod1),
109            h2: RollingHash::with_base_mod(base2, mod2),
110            pub_b1: base1,
111            pub_b2: base2,
112            pub_m1: mod1,
113            pub_m2: mod2,
114        }
115    }
116
117    /// Reset both hashes to 0.
118    pub fn clear(&mut self) {
119        self.h1.clear();
120        self.h2.clear();
121    }
122
123    /// Append a byte to both hashes.
124    pub fn push(&mut self, byte: u8) {
125        self.h1.push(byte);
126        self.h2.push(byte);
127    }
128
129    /// Get the pair `(hash1, hash2)`.
130    pub fn value(&self) -> (u64, u64) {
131        (self.h1.value(), self.h2.value())
132    }
133}
134
135fn mul_mod(a: u64, b: u64, m: u64) -> u64 {
136    // For m = 2^61 - 1, this matches the standard Rh_hash trick.
137    ((a as u128 * b as u128) % m as u128) as u64
138}
139
140fn add_mod(a: u64, b: u64, m: u64) -> u64 {
141    let s = a + b;
142    if s >= m {
143        s - m
144    } else {
145        s
146    }
147}
148
149fn pow_mod(mut base: u64, mut exp: u64, m: u64) -> u64 {
150    let mut result = 1u64;
151    while exp > 0 {
152        if exp & 1 == 1 {
153            result = mul_mod(result, base, m);
154        }
155        base = mul_mod(base, base, m);
156        exp >>= 1;
157    }
158    result
159}
rolling_hash/lib.rs

rolling_hash/
lib.rs
