fbz 0.1.15

Fast parallel compression and decompression for bzip2, gzip, LZ4, tar, and ZIP
Documentation
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) }
    }
}