deflate/

matching.rs

use std::cmp;

use crate::chained_hash_table::{ChainedHashTable, WINDOW_SIZE};

const MAX_MATCH: usize = crate::huffman_table::MAX_MATCH as usize;
#[cfg(test)]
const MIN_MATCH: usize = crate::huffman_table::MIN_MATCH as usize;

/// Get the length of the checked match
/// The function returns number of bytes at and including `current_pos` that are the same as the
/// ones at `pos_to_check`
#[inline]
pub fn get_match_length(data: &[u8], current_pos: usize, pos_to_check: usize) -> usize {
    // Unsafe version using unaligned loads for comparison.
    // Faster when benching the matching function alone,
    // but not as significant when running the full thing.
    /*
        type Comp = u64;

        use std::mem::size_of;

        let max = cmp::min(data.len() - current_pos, MAX_MATCH);
        let mut left = max;
        let s = size_of::<Comp>();

        unsafe {
            let mut cur = data.as_ptr().offset(current_pos as isize);
            let mut tc = data.as_ptr().offset(pos_to_check as isize);
            while left >= s &&
                  (*(cur as *const Comp) == *(tc as *const Comp)) {
                      left -= s;
                      cur = cur.offset(s as isize);
                      tc = tc.offset(s as isize);
                  }
            while left > 0 && *cur == *tc {
                left -= 1;
                cur = cur.offset(1);
                tc = tc.offset(1);
            }
        }

        max - left
    */

    // Slightly faster than naive in single bench.
    // Does not use unaligned loads.
    // let l = cmp::min(MAX_MATCH, data.len() - current_pos);

    // let a = unsafe{&data.get_unchecked(current_pos..current_pos + l)};
    // let b = unsafe{&data.get_unchecked(pos_to_check..)};

    // let mut len = 0;

    // for (l, r) in a
    //     .iter()
    //     .zip(b.iter()) {
    //         if *l == *r {
    //             len += 1;
    //             continue;
    //         } else {
    //             break;
    //         }
    //     }
    // len as usize

    // Naive version
    data[current_pos..]
        .iter()
        .zip(data[pos_to_check..].iter())
        .take(MAX_MATCH)
        .take_while(|&(&a, &b)| a == b)
        .count()
}

/// Try finding the position and length of the longest match in the input data.
/// # Returns
/// (length, distance from position)
/// If no match is found that was better than `prev_length` or at all, or we are at the start,
/// the length value returned will be 2.
///
/// # Arguments:
/// `data`: The data to search in.
/// `hash_table`: Hash table to use for searching.
/// `position`: The position in the data to match against.
/// `prev_length`: The length of the previous `longest_match` check to compare against.
/// `max_hash_checks`: The maximum number of matching hash chain positions to check.
pub fn longest_match(
    data: &[u8],
    hash_table: &ChainedHashTable,
    position: usize,
    prev_length: usize,
    max_hash_checks: u16,
) -> (usize, usize) {
    // debug_assert_eq!(position, hash_table.current_head() as usize);

    // If we already have a match at the maximum length,
    // or we can't grow further, we stop here.
    if prev_length >= MAX_MATCH || position + prev_length >= data.len() {
        return (0, 0);
    }

    let limit = if position > WINDOW_SIZE {
        position - WINDOW_SIZE
    } else {
        0
    };

    // Make sure the length is at least one to simplify the matching code, as
    // otherwise the matching code might underflow.
    let prev_length = cmp::max(prev_length, 1);

    let max_length = cmp::min(data.len() - position, MAX_MATCH);

    // The position in the hash chain we are currently checking.
    let mut current_head = position;

    // The best match length we've found so far, and it's distance.
    let mut best_length = prev_length;
    let mut best_distance = 0;

    // The position of the previous value in the hash chain.
    let mut prev_head;

    for _ in 0..max_hash_checks {
        prev_head = current_head;
        current_head = hash_table.get_prev(current_head) as usize;
        if current_head >= prev_head || current_head < limit {
            // If the current hash chain value refers to itself, or is referring to
            // a value that's higher (we only move backwars through the chain),
            // we are at the end and can stop.
            break;
        }

        // We only check further if the match length can actually increase
        // Checking if the end byte and the potential next byte matches is generally
        // more likely to give a quick answer rather than checking from the start first, given
        // that the hashes match.
        // If there is no previous match, best_length will be 1 and the two first bytes will
        // be checked instead.
        // Since we've made sure best_length is always at least 1, this shouldn't underflow.
        if data[position + best_length - 1..=position + best_length]
            == data[current_head + best_length - 1..=current_head + best_length]
        {
            // Actually check how many bytes match.
            // At the moment this will check the two bytes we just checked again,
            // though adding code for skipping these bytes may not result in any speed
            // gain due to the added complexity.
            let length = get_match_length(data, position, current_head);
            if length > best_length {
                best_length = length;
                best_distance = position - current_head;
                if length == max_length {
                    // We are at the max length, so there is no point
                    // searching any longer
                    break;
                }
            }
        }
    }

    if best_length > prev_length {
        (best_length, best_distance)
    } else {
        (0, 0)
    }
}

/// Try finding the position and length of the longest match in the input data using fast zlib
/// hash skipping algorithm.
/// # Returns
/// (length, distance from position)
/// If no match is found that was better than `prev_length` or at all, or we are at the start,
/// the length value returned will be 2.
///
/// # Arguments:
/// `data`: The data to search in.
/// `hash_table`: Hash table to use for searching.
/// `position`: The position in the data to match against.
/// `prev_length`: The length of the previous `longest_match` check to compare against.
/// `max_hash_checks`: The maximum number of matching hash chain positions to check.
#[cfg(test)]
pub fn longest_match_fast(
    data: &[u8],
    hash_table: &ChainedHashTable,
    position: usize,
    prev_length: usize,
    max_hash_checks: u16,
) -> (usize, usize) {
    // debug_assert_eq!(position, hash_table.current_head() as usize);

    // If we already have a match at the maximum length,
    // or we can't grow further, we stop here.
    if prev_length >= MAX_MATCH || position + prev_length >= data.len() {
        return (0, 0);
    }

    let limit = if position > WINDOW_SIZE {
        position - WINDOW_SIZE
    } else {
        0
    };

    // Make sure the length is at least one to simplify the matching code, as
    // otherwise the matching code might underflow.
    let prev_length = cmp::max(prev_length, 1);

    let max_length = cmp::min(data.len() - position, MAX_MATCH);

    // The position in the hash chain we are currently checking.
    let mut current_head = position;

    // The best match length we've found so far, and it's distance.
    let mut best_length = prev_length;
    let mut best_distance = 0;
    // The offset from the start of the match of the hash chain we are traversing.
    let mut offset = 0;

    // The position of the previous value in the hash chain.
    let mut prev_head;

    for _ in 0..max_hash_checks {
        prev_head = current_head;
        current_head = hash_table.get_prev(current_head) as usize;
        if current_head >= prev_head || current_head < limit + offset {
            // If the current hash chain value refers to itself, or is referring to
            // a value that's higher (we only move backwars through the chain),
            // we are at the end and can stop.
            break;
        }

        let offset_head = current_head - offset;

        // We only check further if the match length can actually increase
        // Checking if the end byte and the potential next byte matches is generally
        // more likely to give a quick answer rather than checking from the start first, given
        // that the hashes match.
        // If there is no previous match, best_length will be 1 and the two first bytes will
        // be checked instead.
        // Since we've made sure best_length is always at least 1, this shouldn't underflow.
        if data[position + best_length - 1..position + best_length + 1]
            == data[offset_head + best_length - 1..offset_head + best_length + 1]
        {
            // Actually check how many bytes match.
            // At the moment this will check the two bytes we just checked again,
            // though adding code for skipping these bytes may not result in any speed
            // gain due to the added complexity.
            let length = get_match_length(data, position, offset_head);
            if length > best_length {
                best_length = length;
                best_distance = position - offset_head;
                if length == max_length {
                    // We are at the max length, so there is no point
                    // searching any longer
                    break;
                }

                // Find the position in the match where the next has position is the furthest away.
                // By moving to a different hash chain we can potentially skip a lot of checks,
                // saving time.
                // We avoid doing this for matches that extend past the starting position, as
                // those will contain positions that are not in the hash table yet.
                if best_distance > best_length {
                    offset = hash_table.farthest_next(offset_head, length);
                    current_head = offset_head + offset;
                }
            }
        }
    }

    if best_length > prev_length {
        (best_length, best_distance)
    } else {
        (0, 0)
    }
}

// Get the longest match from the current position of the hash table.
#[inline]
#[cfg(test)]
pub fn longest_match_current(data: &[u8], hash_table: &ChainedHashTable) -> (usize, usize) {
    use crate::compression_options::MAX_HASH_CHECKS;
    longest_match(
        data,
        hash_table,
        hash_table.current_head() as usize,
        MIN_MATCH as usize - 1,
        MAX_HASH_CHECKS,
    )
}

#[cfg(test)]
mod test {
    use super::{get_match_length, longest_match, longest_match_fast};
    use crate::chained_hash_table::{filled_hash_table, ChainedHashTable, HASH_BYTES};

    /// Test that match lengths are calculated correctly
    #[test]
    fn match_length() {
        let test_arr = [5u8, 5, 5, 5, 5, 9, 9, 2, 3, 5, 5, 5, 5, 5];
        let l = get_match_length(&test_arr, 9, 0);
        assert_eq!(l, 5);
        let l2 = get_match_length(&test_arr, 9, 7);
        assert_eq!(l2, 0);
        let l3 = get_match_length(&test_arr, 10, 0);
        assert_eq!(l3, 4);
    }

    /// Test that we get the longest of the matches
    #[test]
    fn get_longest_match() {
        let test_data = b"xTest data, Test_data,zTest data";
        let hash_table = filled_hash_table(&test_data[..23 + 1 + HASH_BYTES - 1]);

        let (length, distance) = super::longest_match_current(test_data, &hash_table);

        // We check that we get the longest match, rather than the shorter, but closer one.
        assert_eq!(distance, 22);
        assert_eq!(length, 9);
        let test_arr2 = [
            10u8, 10, 10, 10, 10, 10, 10, 10, 2, 3, 5, 10, 10, 10, 10, 10,
        ];
        let hash_table = filled_hash_table(&test_arr2[..HASH_BYTES + 1 + 1 + 2]);
        let (length, distance) = super::longest_match_current(&test_arr2, &hash_table);

        assert_eq!(distance, 1);
        assert_eq!(length, 4);
    }

    /// Make sure we can get a match at index zero
    #[test]
    fn match_index_zero() {
        let test_data = b"AAAAAAA";

        let mut hash_table = ChainedHashTable::from_starting_values(test_data[0], test_data[1]);
        for (n, &b) in test_data[2..5].iter().enumerate() {
            hash_table.add_hash_value(n, b);
        }

        let (match_length, match_dist) = longest_match(test_data, &hash_table, 1, 0, 4096);

        assert_eq!(match_dist, 1);
        assert!(match_length == 6);
    }

    /// Test for fast_zlib algorithm.
    /// Check that it doesn't give worse matches than the default one.
    /// ignored by default as it's slow, and best ran in release mode.
    #[ignore]
    #[test]
    fn fast_match_at_least_equal() {
        use crate::test_utils::get_test_data;
        for start_pos in 10000..50000 {
            const NUM_CHECKS: u16 = 400;
            let data = get_test_data();
            let hash_table = filled_hash_table(&data[..start_pos + 1]);
            let pos = hash_table.current_head() as usize;

            let naive_match = longest_match(&data[..], &hash_table, pos, 0, NUM_CHECKS);
            let fast_match = longest_match_fast(&data[..], &hash_table, pos, 0, NUM_CHECKS);

            if fast_match.0 > naive_match.0 {
                println!("Fast match found better match!");
            }

            assert!(
                fast_match.0 >= naive_match.0,
                "naive match had better length! start_pos: {}, naive: {:?}, fast {:?}",
                start_pos,
                naive_match,
                fast_match
            );
            assert!(
                fast_match.1 >= naive_match.1,
                "naive match had better dist! start_pos: {} naive {:?}, fast {:?}",
                start_pos,
                naive_match,
                fast_match
            );
        }
    }
}

#[cfg(all(test, feature = "benchmarks"))]
mod bench {
    use super::{longest_match, longest_match_fast};
    use chained_hash_table::filled_hash_table;
    use test_std::Bencher;
    use test_utils::get_test_data;
    #[bench]
    fn matching(b: &mut Bencher) {
        const POS: usize = 29000;
        let data = get_test_data();
        let hash_table = filled_hash_table(&data[..POS + 1]);
        let pos = hash_table.current_head() as usize;
        println!(
            "M: {:?}",
            longest_match(&data[..], &hash_table, pos, 0, 4096)
        );
        b.iter(|| longest_match(&data[..], &hash_table, pos, 0, 4096));
    }

    #[bench]
    fn fast_matching(b: &mut Bencher) {
        const POS: usize = 29000;
        let data = get_test_data();
        let hash_table = filled_hash_table(&data[..POS + 1]);
        let pos = hash_table.current_head() as usize;
        println!(
            "M: {:?}",
            longest_match_fast(&data[..], &hash_table, pos, 0, 4096)
        );
        b.iter(|| longest_match_fast(&data[..], &hash_table, pos, 0, 4096));
    }
}