const HASH_SIZE: usize = 1 << 16;
const NONE: u32 = u32::MAX;
#[inline]
pub(crate) fn match_length(bytes: &[u8], left: usize, right: usize, limit: usize) -> usize {
let mut length = 0;
while length + 8 <= limit {
let a = u64::from_le_bytes(bytes[left + length..left + length + 8].try_into().unwrap());
let b = u64::from_le_bytes(bytes[right + length..right + length + 8].try_into().unwrap());
let different = a ^ b;
if different != 0 {
return length + (different.trailing_zeros() as usize / 8);
}
length += 8;
}
while length < limit && bytes[left + length] == bytes[right + length] {
length += 1;
}
length
}
pub(crate) struct LatestMatch {
head: Vec<u32>,
window: usize,
}
impl LatestMatch {
pub fn new(window: usize) -> Self {
Self { head: vec![NONE; HASH_SIZE], window }
}
#[inline]
fn hash(bytes: &[u8], position: usize) -> usize {
let value = u32::from_le_bytes(bytes[position..position + 4].try_into().unwrap());
((value.wrapping_mul(0x9e37_79b1)) >> 16) as usize
}
#[inline]
pub fn insert_and_find(&mut self, bytes: &[u8], position: usize) -> Option<usize> {
if position + 4 > bytes.len() {
return None;
}
let slot = Self::hash(bytes, position);
let candidate = self.head[slot];
self.head[slot] = position as u32;
let candidate = (candidate != NONE).then_some(candidate as usize)?;
(position - candidate <= self.window && bytes[candidate..candidate + 4] == bytes[position..position + 4]).then_some(candidate)
}
#[inline]
pub fn insert(&mut self, bytes: &[u8], position: usize) {
if position + 4 <= bytes.len() {
self.head[Self::hash(bytes, position)] = position as u32;
}
}
}
pub(crate) struct HashChain {
head: Vec<u32>,
previous: Option<Vec<u32>>,
window: usize,
}
impl HashChain {
pub fn new(input_len: usize, window: usize, max_chain: usize) -> Self {
assert!(input_len < u32::MAX as usize);
Self { head: vec![NONE; HASH_SIZE], previous: (max_chain > 1).then(|| vec![NONE; input_len]), window }
}
fn hash(bytes: &[u8], position: usize) -> usize {
let value = u32::from(bytes[position]) << 16 | u32::from(bytes[position + 1]) << 8 | u32::from(bytes[position + 2]);
((value.wrapping_mul(0x1e35_a7bd)) >> 16) as usize
}
pub fn insert(&mut self, bytes: &[u8], position: usize) {
if position + 2 >= bytes.len() {
return;
}
let slot = Self::hash(bytes, position);
if let Some(previous) = &mut self.previous {
previous[position] = self.head[slot];
}
self.head[slot] = position as u32;
}
pub fn best_match(&self, bytes: &[u8], position: usize, max_length: usize, min_length: usize, max_chain: usize) -> (usize, usize) {
if position + min_length > bytes.len() || min_length < 3 {
return (0, 0);
}
let mut candidate = self.head[Self::hash(bytes, position)];
let minimum = position.saturating_sub(self.window);
let limit = (bytes.len() - position).min(max_length);
let mut best_length = min_length - 1;
let mut best_distance = 0;
let mut searched = 0;
while candidate != NONE && candidate as usize >= minimum && searched < max_chain {
let candidate_position = candidate as usize;
let distance = position - candidate_position;
if bytes[candidate_position] == bytes[position] && bytes.get(candidate_position + best_length) == bytes.get(position + best_length) {
let length = match_length(bytes, candidate_position, position, limit);
if length > best_length {
best_length = length;
best_distance = distance;
if length == limit {
break;
}
}
}
searched += 1;
if searched >= max_chain {
break;
}
candidate = self.previous.as_ref().map_or(NONE, |previous| previous[candidate_position]);
}
if best_length >= min_length { (best_length, best_distance) } else { (0, 0) }
}
}