use crate::rope::*;
pub struct SlidingWindow {
arena: Arena,
d_max: u64,
pub m_max: u64,
w: u64,
h_prefix: u64,
l_prefix: u64,
r_window: Node,
pos: u64,
}
impl SlidingWindow {
pub fn new(d_max: u64, m_max: u64, prime: u64, base: u64) -> Self {
assert!(d_max >= 1, "d_max must be >= 1, got {}", d_max);
assert!(m_max >= 1, "m_max must be >= 1, got {}", m_max);
Self {
arena: Arena::with_hash(prime, base),
d_max,
m_max,
w: d_max + m_max,
h_prefix: 0,
l_prefix: 0,
r_window: None,
pos: 0,
}
}
pub fn default_window() -> Self {
Self::new(32768, 258, crate::polynomial_hash::MERSENNE_61, 131)
}
pub fn arena(&self) -> &Arena {
&self.arena
}
pub fn arena_mut(&mut self) -> &mut Arena {
&mut self.arena
}
#[inline]
pub fn window_len(&self) -> u64 {
self.arena.len(self.r_window)
}
#[inline]
pub fn pos(&self) -> u64 {
self.pos
}
pub fn current_hash(&mut self) -> u64 {
let wl = self.window_len();
let wh = self.arena.hash(self.r_window);
self.arena.hasher_mut().hash_concat(self.h_prefix, wl, wh)
}
pub fn final_hash(&mut self) -> u64 {
self.current_hash()
}
pub fn append_bytes(&mut self, data: &[u8]) {
if data.is_empty() {
return;
}
let leaf = self.arena.from_bytes(data);
self.r_window = self.arena.concat(self.r_window, leaf);
self.pos += data.len() as u64;
self.evict();
}
pub fn append_copy(&mut self, offset: u64, length: u64) {
let win_len = self.window_len();
assert!(
offset <= self.pos,
"Invalid copy: offset {} exceeds decoded length {}",
offset, self.pos
);
assert!(
offset <= win_len,
"Copy offset {} exceeds window size {}. Increase d_max (currently {}) to at least {}.",
offset, win_len, self.d_max, offset
);
let start = win_len - offset;
if offset >= length {
let (_, tmp) = self.arena.split(self.r_window, start);
let (source, _) = self.arena.split(tmp, length);
self.r_window = self.arena.concat(self.r_window, source);
} else {
let (_, tmp) = self.arena.split(self.r_window, start);
let (pattern, _) = self.arena.split(tmp, offset);
let q = length / offset;
let r = length % offset;
let mut rep = if q >= 1 {
self.arena.repeat(pattern, q)
} else {
None
};
if r > 0 {
let (partial, _) = self.arena.split(pattern, r);
rep = self.arena.concat(rep, partial);
}
self.r_window = self.arena.concat(self.r_window, rep);
}
self.pos += length;
self.evict();
}
fn evict(&mut self) {
let win_len = self.arena.len(self.r_window);
if win_len <= self.w {
return;
}
let excess = win_len - self.d_max;
let (r_old, r_keep) = self.arena.split(self.r_window, excess);
let old_len = self.arena.len(r_old);
let old_hash = self.arena.hash(r_old);
self.h_prefix = self.arena.hasher_mut().hash_concat(self.h_prefix, old_len, old_hash);
self.l_prefix += excess;
self.r_window = r_keep;
}
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::vec;
use alloc::vec::Vec;
use crate::polynomial_hash::MERSENNE_61;
#[test]
fn test_empty() {
let mut sw = SlidingWindow::default_window();
assert_eq!(sw.current_hash(), 0);
assert_eq!(sw.pos(), 0);
}
#[test]
fn test_append_bytes() {
let mut sw = SlidingWindow::default_window();
let expected = sw.arena().hash_bytes(b"hello");
sw.append_bytes(b"hello");
assert_eq!(sw.current_hash(), expected);
}
#[test]
fn test_append_incremental() {
let mut sw = SlidingWindow::default_window();
let expected = sw.arena().hash_bytes(b"hello world");
sw.append_bytes(b"hello ");
sw.append_bytes(b"world");
assert_eq!(sw.current_hash(), expected);
}
#[test]
fn test_non_overlapping_copy() {
let mut sw = SlidingWindow::default_window();
let expected = sw.arena().hash_bytes(b"hello worldworld");
sw.append_bytes(b"hello world");
sw.append_copy(5, 5);
assert_eq!(sw.current_hash(), expected);
}
#[test]
fn test_overlapping_copy() {
let mut sw = SlidingWindow::default_window();
let expected = sw.arena().hash_bytes(b"abababab");
sw.append_bytes(b"ab");
sw.append_copy(2, 6);
assert_eq!(sw.current_hash(), expected);
}
#[test]
fn test_eviction_preserves_hash() {
let mut sw = SlidingWindow::new(8, 4, MERSENNE_61, 131);
let data = b"the quick brown fox jumps over the lazy dog";
let expected = {
let mut a = Arena::with_hash(MERSENNE_61, 131);
a.hash_bytes(data)
};
for &byte in data.iter() {
sw.append_bytes(&[byte]);
}
assert_eq!(sw.current_hash(), expected);
}
#[test]
fn test_large_stream() {
let mut sw = SlidingWindow::new(32, 16, MERSENNE_61, 131);
let mut full_data = Vec::new();
for i in 0..50u8 {
let chunk = vec![i; 10];
sw.append_bytes(&chunk);
full_data.extend_from_slice(&chunk);
}
let expected = {
let mut a = Arena::with_hash(MERSENNE_61, 131);
a.hash_bytes(&full_data)
};
assert_eq!(sw.current_hash(), expected);
}
}