use super::window::roll;
use super::{Deflater, MAX_DIST, MIN_MATCH, W_MASK};
const EARLY_EXIT_LEVEL: u8 = 5;
#[inline]
fn word(window: &[u8], at: usize) -> u64 {
let bytes: [u8; 8] = window[at..at + 8]
.try_into()
.expect("eight bytes are eight bytes");
u64::from_le_bytes(bytes)
}
#[inline]
pub(super) fn compare256(window: &[u8], a: usize, b: usize) -> u32 {
let (a, b) = (&window[a..a + 256], &window[b..b + 256]);
let (a, b) = (a.as_chunks::<8>().0, b.as_chunks::<8>().0);
for (offset, (&x, &y)) in (0..).step_by(8).zip(a.iter().zip(b)) {
let difference = u64::from_le_bytes(x) ^ u64::from_le_bytes(y);
if difference != 0 {
return offset + difference.trailing_zeros() / 8;
}
}
256
}
#[inline]
pub(super) fn compare256_rle(window: &[u8], byte: usize, at: usize) -> u32 {
let run = u64::from_le_bytes([window[byte]; 8]);
for (offset, &chunk) in (0..)
.step_by(8)
.zip(window[at..at + 256].as_chunks::<8>().0)
{
let difference = run ^ u64::from_le_bytes(chunk);
if difference != 0 {
return offset + difference.trailing_zeros() / 8;
}
}
256
}
#[inline]
fn end_offset(best: u32) -> u32 {
match best {
0..4 => best - 1,
4..8 => best - 3,
_ => best - 7,
}
}
#[inline]
fn could_beat(window: &[u8], best: u32, scan: (u64, u64), candidate: usize, end: usize) -> bool {
let mask = match best {
0..4 => 0xFFFF,
4..8 => 0xFFFF_FFFF,
_ => u64::MAX,
};
(word(window, candidate + end) ^ scan.1) & mask == 0
&& (word(window, candidate) ^ scan.0) & mask == 0
}
impl Deflater {
fn search_limits(&self, best: u32) -> (u32, u32, u32) {
let mut chain = self.config.max_chain;
if best >= self.config.good_length {
chain >>= 2;
}
let limit = self.strstart.saturating_sub(MAX_DIST);
(chain, self.config.nice_length, limit)
}
pub(super) fn longest_match(&mut self, mut cur_match: u32) -> u32 {
let strstart = self.strstart;
let lookahead = self.lookahead;
let window = &self.win.bytes;
let prev = &self.win.prev;
let scan = strstart as usize;
let mut best = if self.prev_length != 0 {
self.prev_length
} else {
MIN_MATCH - 1
};
let mut offset = end_offset(best) as usize;
let mut scan_words = (word(window, scan), word(window, scan + offset));
let (mut chain, nice, limit) = self.search_limits(best);
let early_exit = self.level < EARLY_EXIT_LEVEL;
let next_in_chain = |chain: &mut u32, cur_match: &mut u32| {
*chain -= 1;
if *chain == 0 {
return false;
}
*cur_match = u32::from(prev[(*cur_match & W_MASK) as usize]);
*cur_match > limit
};
loop {
if cur_match >= strstart {
return best;
}
while !could_beat(window, best, scan_words, cur_match as usize, offset) {
if !next_in_chain(&mut chain, &mut cur_match) {
return best;
}
}
let len = compare256(window, scan + 2, cur_match as usize + 2) + 2;
if len > best {
self.match_start = cur_match;
if len >= lookahead {
return lookahead;
}
best = len;
if best >= nice {
return best;
}
offset = end_offset(best) as usize;
scan_words.1 = word(window, scan + offset);
} else if early_exit {
return best;
}
if !next_in_chain(&mut chain, &mut cur_match) {
return best;
}
}
}
pub(super) fn longest_match_slow(&mut self, mut cur_match: u32) -> u32 {
let strstart = self.strstart;
let lookahead = self.lookahead;
let window = &self.win.bytes;
let head = &self.win.head;
let prev = &self.win.prev;
let scan = strstart as usize;
let mut best = if self.prev_length != 0 {
self.prev_length
} else {
MIN_MATCH - 1
};
let mut offset = end_offset(best) as usize;
let mut scan_words = (word(window, scan), word(window, scan + offset));
let (mut chain, nice, limit_base) = self.search_limits(best);
let capped = |best: u32| best.min(lookahead);
let mut match_offset = 0;
if best >= MIN_MATCH {
let mut hash = roll(roll(0, window[scan + 1]), window[scan + 2]);
for i in MIN_MATCH..=best {
hash = roll(hash, window[scan + i as usize]);
let position = u32::from(head[hash as usize]);
if position < cur_match {
match_offset = i - 2;
cur_match = position;
}
}
if cur_match <= limit_base + match_offset {
return capped(best);
}
}
let mut limit = limit_base + match_offset;
let next_in_chain = |chain: &mut u32, cur_match: &mut u32, limit: u32| {
*chain -= 1;
if *chain == 0 {
return false;
}
*cur_match = u32::from(prev[(*cur_match & W_MASK) as usize]);
*cur_match > limit
};
loop {
if cur_match >= strstart {
return best;
}
while !could_beat(
window,
best,
scan_words,
(cur_match - match_offset) as usize,
offset,
) {
if !next_in_chain(&mut chain, &mut cur_match, limit) {
return best;
}
}
let match_start = cur_match - match_offset;
let len = compare256(window, scan + 2, match_start as usize + 2) + 2;
if len > best {
self.match_start = match_start;
if len >= lookahead {
return lookahead;
}
best = len;
if best >= nice {
return best;
}
offset = end_offset(best) as usize;
scan_words.1 = word(window, scan + offset);
if len > MIN_MATCH && match_start + len < strstart {
let mut next = match_start;
match_offset = 0;
for i in 0..=len - MIN_MATCH {
let position = u32::from(prev[((match_start + i) & W_MASK) as usize]);
if position < next {
if position <= limit_base + i {
return capped(best);
}
next = position;
match_offset = i;
}
}
cur_match = next;
let end = scan + (len - (MIN_MATCH + 1)) as usize;
let hash = roll(roll(roll(0, window[end]), window[end + 1]), window[end + 2]);
let position = u32::from(head[hash as usize]);
if position < cur_match {
match_offset = len - (MIN_MATCH + 1);
if position <= limit_base + match_offset {
return capped(best);
}
cur_match = position;
}
limit = limit_base + match_offset;
continue;
}
}
if !next_in_chain(&mut chain, &mut cur_match, limit) {
return best;
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn comparisons_count_equal_bytes() {
let mut window = vec![0_u8; 1024];
window[300..600].copy_from_slice(&[7; 300]);
window[12] = 1;
assert_eq!(compare256(&window, 0, 600), 12);
assert_eq!(compare256(&window, 13, 613), 256);
assert_eq!(compare256_rle(&window, 300, 301), 256);
assert_eq!(compare256_rle(&window, 300, 500), 100);
assert_eq!(compare256_rle(&window, 0, 1), 11);
}
#[test]
fn end_offsets_reach_the_byte_after_the_best() {
for best in 2..258 {
let width = match best {
0..4 => 2,
4..8 => 4,
_ => 8,
};
assert_eq!(end_offset(best) + width - 1, best, "best {best}");
}
}
}