use alloc::vec;
use alloc::vec::Vec;
pub(super) const MIN_MATCH: usize = 4;
pub(super) const MIN_SHORT_MATCH: usize = 3;
pub(super) const MIN_REPEAT_MATCH: usize = MIN_SHORT_MATCH;
pub(super) const MAX_MATCH: usize = 1 << 16;
const NONE: u32 = u32::MAX;
const SHORT_BITS_MAX: u32 = 17;
#[derive(Clone, Copy)]
pub(super) struct Match {
pub(super) literal_len: usize,
pub(super) match_len: usize,
pub(super) offset: usize,
}
pub(super) struct Params {
pub(super) hash_bits: u32,
pub(super) depth: u32,
pub(super) nice_len: usize,
}
impl Params {
pub(super) fn for_input(len: usize, window: usize) -> Self {
let searchable = len.min(window);
Self {
hash_bits: ceil_log2(searchable).clamp(10, 22),
depth: 64,
nice_len: 192,
}
}
}
fn ceil_log2(n: usize) -> u32 {
if n <= 1 {
0
} else {
usize::BITS - (n - 1).leading_zeros()
}
}
pub(super) struct HashChain {
head: Vec<u32>,
chain: Vec<u32>,
short: Vec<u32>,
hash_bits: u32,
short_bits: u32,
chain_mask: usize,
filled: usize,
}
impl HashChain {
pub(super) fn footprint(len: usize, window: usize, hash_bits: u32) -> usize {
let chain = window.min(len).max(1).next_power_of_two();
let short = 1usize << hash_bits.min(SHORT_BITS_MAX);
((1usize << hash_bits) + chain + short) * size_of::<u32>()
}
pub(super) fn new(len: usize, window: usize, hash_bits: u32) -> Self {
let chain_size = window.min(len).max(1).next_power_of_two();
let short_bits = hash_bits.min(SHORT_BITS_MAX);
Self {
head: vec![NONE; 1usize << hash_bits],
chain: vec![NONE; chain_size],
short: vec![NONE; 1usize << short_bits],
hash_bits,
short_bits,
chain_mask: chain_size - 1,
filled: 0,
}
}
fn hash(&self, input: &[u8], pos: usize) -> usize {
let word = u32::from_le_bytes([input[pos], input[pos + 1], input[pos + 2], input[pos + 3]]);
(word.wrapping_mul(2_654_435_761) >> (32 - self.hash_bits)) as usize
}
fn short_hash(&self, input: &[u8], pos: usize) -> usize {
let word = u32::from_le_bytes([input[pos], input[pos + 1], input[pos + 2], input[pos + 3]]);
((word & 0x00ff_ffff).wrapping_mul(2_654_435_761) >> (32 - self.short_bits)) as usize
}
pub(super) fn start_at(&mut self, from: usize) {
self.filled = from;
}
pub(super) fn fill_to(&mut self, input: &[u8], upto: usize) {
let end = upto.min((input.len() + 1).saturating_sub(MIN_MATCH));
while self.filled < end {
let slot = self.hash(input, self.filled);
self.chain[self.filled & self.chain_mask] = self.head[slot];
self.head[slot] = self.filled as u32;
let short = self.short_hash(input, self.filled);
self.short[short] = self.filled as u32;
self.filled += 1;
}
}
pub(super) fn candidates(
&self,
input: &[u8],
pos: usize,
floor: usize,
limit: usize,
params: &Params,
out: &mut Vec<(u32, u32)>,
) {
if limit < MIN_SHORT_MATCH || pos + MIN_MATCH > input.len() {
return;
}
let short = self.short[self.short_hash(input, pos)];
if short != NONE {
let at = short as usize;
if at >= floor && at < pos && common_prefix(input, at, pos, limit) >= MIN_SHORT_MATCH {
out.push((MIN_SHORT_MATCH as u32, (pos - at) as u32));
}
}
if limit < MIN_MATCH {
return;
}
let mut best_len = 0usize;
let mut candidate = self.head[self.hash(input, pos)];
for _ in 0..params.depth {
if candidate == NONE {
break;
}
let at = candidate as usize;
if at < floor {
break;
}
if best_len == 0 || input[at + best_len] == input[pos + best_len] {
let len = common_prefix(input, at, pos, limit);
if len > best_len && len >= MIN_MATCH {
best_len = len;
out.push((len as u32, (pos - at) as u32));
if len >= limit || len >= params.nice_len {
break;
}
}
}
candidate = self.chain[at & self.chain_mask];
}
}
}
pub(super) fn common_prefix(input: &[u8], a: usize, b: usize, limit: usize) -> usize {
let mut len = 0usize;
while len + 8 <= limit {
let x = u64::from_le_bytes(input[a + len..a + len + 8].try_into().unwrap_or_default());
let y = u64::from_le_bytes(input[b + len..b + len + 8].try_into().unwrap_or_default());
if x != y {
return len + ((x ^ y).trailing_zeros() / 8) as usize;
}
len += 8;
}
while len < limit && input[a + len] == input[b + len] {
len += 1;
}
len
}
pub(super) fn encode_offset(
repeats: [usize; 3],
offset: usize,
literal_len: usize,
) -> (u32, [usize; 3]) {
let value = if literal_len > 0 {
match offset {
o if o == repeats[0] => 1,
o if o == repeats[1] => 2,
o if o == repeats[2] => 3,
o => o + 3,
}
} else {
match offset {
o if o == repeats[1] => 1,
o if o == repeats[2] => 2,
o if repeats[0] > 1 && o == repeats[0] - 1 => 3,
o => o + 3,
}
};
let advanced = match (literal_len > 0, value) {
(true, 1) => repeats,
(true, 2) | (false, 1) => [repeats[1], repeats[0], repeats[2]],
_ => [offset, repeats[0], repeats[1]],
};
(value as u32, advanced)
}
#[derive(Clone, Copy)]
pub(super) struct History {
offsets: [usize; 3],
outright: u32,
}
impl History {
pub(super) fn fresh() -> Self {
Self {
offsets: [1, 4, 8],
outright: 3,
}
}
pub(super) fn offsets(&self) -> [usize; 3] {
self.offsets
}
pub(super) fn encode(&mut self, offset: usize, literal_len: usize) -> u32 {
if self.outright > 0 {
self.outright -= 1;
self.offsets = [offset, self.offsets[0], self.offsets[1]];
return (offset + 3) as u32;
}
let (value, advanced) = encode_offset(self.offsets, offset, literal_len);
self.offsets = advanced;
value
}
}
pub(super) fn repeat_candidates(repeats: [usize; 3], literal_len: usize) -> [usize; 3] {
if literal_len > 0 {
repeats
} else {
[repeats[1], repeats[2], repeats[0].saturating_sub(1)]
}
}