use pltrs_core::alloc::{self, OutOfMemory};
use super::{Deflater, MAX_DIST, MAX_MATCH, MIN_LOOKAHEAD, MIN_MATCH, W_MASK, W_SIZE, WINDOW_SIZE};
const HASH_SIZE: usize = 1 << 16;
const ROLL_MASK: u32 = (1 << 15) - 1;
const WIN_INIT: u32 = MAX_MATCH;
const PADDING: usize = 8;
#[derive(Debug)]
pub(super) struct Window {
pub(super) bytes: Vec<u8>,
pub(super) head: Vec<u16>,
pub(super) prev: Vec<u16>,
high_water: u32,
}
impl Window {
pub(super) fn new() -> Result<Self, OutOfMemory> {
Ok(Self {
bytes: zeros(WINDOW_SIZE as usize + PADDING)?,
head: zeros(HASH_SIZE)?,
prev: zeros(W_SIZE as usize)?,
high_water: 0,
})
}
pub(super) fn restart(&mut self, len: usize) {
self.head.fill(0);
let reached = len.min(self.prev.len());
self.prev[..reached].fill(0);
self.high_water = 0;
}
#[inline]
pub(super) fn word(&self, position: u32) -> u32 {
let p = position as usize;
u32::from_le_bytes([
self.bytes[p],
self.bytes[p + 1],
self.bytes[p + 2],
self.bytes[p + 3],
])
}
fn slide_hash(&mut self) {
let slide = |table: &mut [u16]| {
for entry in table {
*entry = entry.saturating_sub(W_SIZE as u16);
}
};
slide(&mut self.head);
slide(&mut self.prev);
}
}
fn zeros<T: Clone + Default>(len: usize) -> Result<Vec<T>, OutOfMemory> {
let mut values = alloc::try_with_capacity(len)?;
values.resize(len, T::default());
Ok(values)
}
#[inline]
fn hash(word: u32) -> usize {
(word.wrapping_mul(2_654_435_761) >> 16) as usize
}
#[inline]
pub(super) fn roll(hash: u32, byte: u8) -> u32 {
(hash << 5 ^ u32::from(byte)) & ROLL_MASK
}
impl Deflater {
#[inline]
pub(super) fn quick_insert_string(&mut self, position: u32) -> u16 {
let key = if self.config.rolls() {
self.ins_h = roll(self.ins_h, self.win.bytes[position as usize + 2]);
self.ins_h as usize
} else {
hash(self.win.word(position))
};
self.link(key, position)
}
#[inline]
pub(super) fn insert_string(&mut self, position: u32, count: u32) {
for position in position..position + count {
self.quick_insert_string(position);
}
}
#[inline]
fn link(&mut self, key: usize, position: u32) -> u16 {
let head = self.win.head[key];
if u32::from(head) != position {
self.win.prev[(position & W_MASK) as usize] = head;
self.win.head[key] = position as u16;
}
head
}
pub(super) fn fill_window(&mut self, input: &mut &[u8]) {
loop {
let mut more = WINDOW_SIZE - self.lookahead - self.strstart;
if self.strstart >= W_SIZE + MAX_DIST {
let (low, high) = self.win.bytes.split_at_mut(W_SIZE as usize);
low.copy_from_slice(&high[..W_SIZE as usize]);
if self.match_start >= W_SIZE {
self.match_start -= W_SIZE;
} else {
self.match_start = 0;
self.prev_length = 0;
}
self.strstart -= W_SIZE;
self.block_start -= i64::from(W_SIZE);
self.win.slide_hash();
more += W_SIZE;
}
if input.is_empty() {
break;
}
let read = self.read_buf(input, self.strstart + self.lookahead, more);
self.lookahead += read;
if self.lookahead >= MIN_MATCH {
let start = self.strstart as usize;
if self.config.rolls() {
self.ins_h = roll(u32::from(self.win.bytes[start]), self.win.bytes[start + 1]);
} else if self.strstart >= 1 {
self.quick_insert_string(self.strstart + 2 - MIN_MATCH);
}
}
if self.lookahead >= MIN_LOOKAHEAD || input.is_empty() {
break;
}
}
self.zero_past_data();
}
fn zero_past_data(&mut self) {
let high_water = self.win.high_water;
if high_water >= WINDOW_SIZE {
return;
}
let end = self.strstart + self.lookahead;
let zeroed = if high_water < end {
end..end + (WINDOW_SIZE - end).min(WIN_INIT)
} else if high_water < end + WIN_INIT {
high_water..high_water + (end + WIN_INIT - high_water).min(WINDOW_SIZE - high_water)
} else {
return;
};
self.win.bytes[zeroed.start as usize..zeroed.end as usize].fill(0);
self.win.high_water = zeroed.end;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn hashes_follow_zlib_ng() {
assert_eq!(hash(0), 0);
assert_eq!(hash(u32::from_le_bytes(*b"abcd")), 0x630D);
assert_eq!(
roll(roll(roll(0, b'a'), b'b'), b'c'),
(0x61 << 10 ^ 0x62 << 5 ^ 0x63) & ROLL_MASK
);
}
#[test]
fn sliding_forgets_old_positions() {
let mut window = Window::new().unwrap();
window.head[1] = 40_000;
window.head[2] = 100;
window.prev[3] = W_SIZE as u16;
window.slide_hash();
assert_eq!(
(window.head[1], window.head[2], window.prev[3]),
(40_000 - W_SIZE as u16, 0, 0)
);
}
}