deflate/
matching.rs

1use std::cmp;
2
3use crate::chained_hash_table::{ChainedHashTable, WINDOW_SIZE};
4
5const MAX_MATCH: usize = crate::huffman_table::MAX_MATCH as usize;
6#[cfg(test)]
7const MIN_MATCH: usize = crate::huffman_table::MIN_MATCH as usize;
8
9/// Get the length of the checked match
10/// The function returns number of bytes at and including `current_pos` that are the same as the
11/// ones at `pos_to_check`
12#[inline]
13pub fn get_match_length(data: &[u8], current_pos: usize, pos_to_check: usize) -> usize {
14    // Unsafe version using unaligned loads for comparison.
15    // Faster when benching the matching function alone,
16    // but not as significant when running the full thing.
17    /*
18        type Comp = u64;
19
20        use std::mem::size_of;
21
22        let max = cmp::min(data.len() - current_pos, MAX_MATCH);
23        let mut left = max;
24        let s = size_of::<Comp>();
25
26        unsafe {
27            let mut cur = data.as_ptr().offset(current_pos as isize);
28            let mut tc = data.as_ptr().offset(pos_to_check as isize);
29            while left >= s &&
30                  (*(cur as *const Comp) == *(tc as *const Comp)) {
31                      left -= s;
32                      cur = cur.offset(s as isize);
33                      tc = tc.offset(s as isize);
34                  }
35            while left > 0 && *cur == *tc {
36                left -= 1;
37                cur = cur.offset(1);
38                tc = tc.offset(1);
39            }
40        }
41
42        max - left
43    */
44
45    // Slightly faster than naive in single bench.
46    // Does not use unaligned loads.
47    // let l = cmp::min(MAX_MATCH, data.len() - current_pos);
48
49    // let a = unsafe{&data.get_unchecked(current_pos..current_pos + l)};
50    // let b = unsafe{&data.get_unchecked(pos_to_check..)};
51
52    // let mut len = 0;
53
54    // for (l, r) in a
55    //     .iter()
56    //     .zip(b.iter()) {
57    //         if *l == *r {
58    //             len += 1;
59    //             continue;
60    //         } else {
61    //             break;
62    //         }
63    //     }
64    // len as usize
65
66    // Naive version
67    data[current_pos..]
68        .iter()
69        .zip(data[pos_to_check..].iter())
70        .take(MAX_MATCH)
71        .take_while(|&(&a, &b)| a == b)
72        .count()
73}
74
75/// Try finding the position and length of the longest match in the input data.
76/// # Returns
77/// (length, distance from position)
78/// If no match is found that was better than `prev_length` or at all, or we are at the start,
79/// the length value returned will be 2.
80///
81/// # Arguments:
82/// `data`: The data to search in.
83/// `hash_table`: Hash table to use for searching.
84/// `position`: The position in the data to match against.
85/// `prev_length`: The length of the previous `longest_match` check to compare against.
86/// `max_hash_checks`: The maximum number of matching hash chain positions to check.
87pub fn longest_match(
88    data: &[u8],
89    hash_table: &ChainedHashTable,
90    position: usize,
91    prev_length: usize,
92    max_hash_checks: u16,
93) -> (usize, usize) {
94    // debug_assert_eq!(position, hash_table.current_head() as usize);
95
96    // If we already have a match at the maximum length,
97    // or we can't grow further, we stop here.
98    if prev_length >= MAX_MATCH || position + prev_length >= data.len() {
99        return (0, 0);
100    }
101
102    let limit = if position > WINDOW_SIZE {
103        position - WINDOW_SIZE
104    } else {
105        0
106    };
107
108    // Make sure the length is at least one to simplify the matching code, as
109    // otherwise the matching code might underflow.
110    let prev_length = cmp::max(prev_length, 1);
111
112    let max_length = cmp::min(data.len() - position, MAX_MATCH);
113
114    // The position in the hash chain we are currently checking.
115    let mut current_head = position;
116
117    // The best match length we've found so far, and it's distance.
118    let mut best_length = prev_length;
119    let mut best_distance = 0;
120
121    // The position of the previous value in the hash chain.
122    let mut prev_head;
123
124    for _ in 0..max_hash_checks {
125        prev_head = current_head;
126        current_head = hash_table.get_prev(current_head) as usize;
127        if current_head >= prev_head || current_head < limit {
128            // If the current hash chain value refers to itself, or is referring to
129            // a value that's higher (we only move backwars through the chain),
130            // we are at the end and can stop.
131            break;
132        }
133
134        // We only check further if the match length can actually increase
135        // Checking if the end byte and the potential next byte matches is generally
136        // more likely to give a quick answer rather than checking from the start first, given
137        // that the hashes match.
138        // If there is no previous match, best_length will be 1 and the two first bytes will
139        // be checked instead.
140        // Since we've made sure best_length is always at least 1, this shouldn't underflow.
141        if data[position + best_length - 1..=position + best_length]
142            == data[current_head + best_length - 1..=current_head + best_length]
143        {
144            // Actually check how many bytes match.
145            // At the moment this will check the two bytes we just checked again,
146            // though adding code for skipping these bytes may not result in any speed
147            // gain due to the added complexity.
148            let length = get_match_length(data, position, current_head);
149            if length > best_length {
150                best_length = length;
151                best_distance = position - current_head;
152                if length == max_length {
153                    // We are at the max length, so there is no point
154                    // searching any longer
155                    break;
156                }
157            }
158        }
159    }
160
161    if best_length > prev_length {
162        (best_length, best_distance)
163    } else {
164        (0, 0)
165    }
166}
167
168/// Try finding the position and length of the longest match in the input data using fast zlib
169/// hash skipping algorithm.
170/// # Returns
171/// (length, distance from position)
172/// If no match is found that was better than `prev_length` or at all, or we are at the start,
173/// the length value returned will be 2.
174///
175/// # Arguments:
176/// `data`: The data to search in.
177/// `hash_table`: Hash table to use for searching.
178/// `position`: The position in the data to match against.
179/// `prev_length`: The length of the previous `longest_match` check to compare against.
180/// `max_hash_checks`: The maximum number of matching hash chain positions to check.
181#[cfg(test)]
182pub fn longest_match_fast(
183    data: &[u8],
184    hash_table: &ChainedHashTable,
185    position: usize,
186    prev_length: usize,
187    max_hash_checks: u16,
188) -> (usize, usize) {
189    // debug_assert_eq!(position, hash_table.current_head() as usize);
190
191    // If we already have a match at the maximum length,
192    // or we can't grow further, we stop here.
193    if prev_length >= MAX_MATCH || position + prev_length >= data.len() {
194        return (0, 0);
195    }
196
197    let limit = if position > WINDOW_SIZE {
198        position - WINDOW_SIZE
199    } else {
200        0
201    };
202
203    // Make sure the length is at least one to simplify the matching code, as
204    // otherwise the matching code might underflow.
205    let prev_length = cmp::max(prev_length, 1);
206
207    let max_length = cmp::min(data.len() - position, MAX_MATCH);
208
209    // The position in the hash chain we are currently checking.
210    let mut current_head = position;
211
212    // The best match length we've found so far, and it's distance.
213    let mut best_length = prev_length;
214    let mut best_distance = 0;
215    // The offset from the start of the match of the hash chain we are traversing.
216    let mut offset = 0;
217
218    // The position of the previous value in the hash chain.
219    let mut prev_head;
220
221    for _ in 0..max_hash_checks {
222        prev_head = current_head;
223        current_head = hash_table.get_prev(current_head) as usize;
224        if current_head >= prev_head || current_head < limit + offset {
225            // If the current hash chain value refers to itself, or is referring to
226            // a value that's higher (we only move backwars through the chain),
227            // we are at the end and can stop.
228            break;
229        }
230
231        let offset_head = current_head - offset;
232
233        // We only check further if the match length can actually increase
234        // Checking if the end byte and the potential next byte matches is generally
235        // more likely to give a quick answer rather than checking from the start first, given
236        // that the hashes match.
237        // If there is no previous match, best_length will be 1 and the two first bytes will
238        // be checked instead.
239        // Since we've made sure best_length is always at least 1, this shouldn't underflow.
240        if data[position + best_length - 1..position + best_length + 1]
241            == data[offset_head + best_length - 1..offset_head + best_length + 1]
242        {
243            // Actually check how many bytes match.
244            // At the moment this will check the two bytes we just checked again,
245            // though adding code for skipping these bytes may not result in any speed
246            // gain due to the added complexity.
247            let length = get_match_length(data, position, offset_head);
248            if length > best_length {
249                best_length = length;
250                best_distance = position - offset_head;
251                if length == max_length {
252                    // We are at the max length, so there is no point
253                    // searching any longer
254                    break;
255                }
256
257                // Find the position in the match where the next has position is the furthest away.
258                // By moving to a different hash chain we can potentially skip a lot of checks,
259                // saving time.
260                // We avoid doing this for matches that extend past the starting position, as
261                // those will contain positions that are not in the hash table yet.
262                if best_distance > best_length {
263                    offset = hash_table.farthest_next(offset_head, length);
264                    current_head = offset_head + offset;
265                }
266            }
267        }
268    }
269
270    if best_length > prev_length {
271        (best_length, best_distance)
272    } else {
273        (0, 0)
274    }
275}
276
277// Get the longest match from the current position of the hash table.
278#[inline]
279#[cfg(test)]
280pub fn longest_match_current(data: &[u8], hash_table: &ChainedHashTable) -> (usize, usize) {
281    use crate::compression_options::MAX_HASH_CHECKS;
282    longest_match(
283        data,
284        hash_table,
285        hash_table.current_head() as usize,
286        MIN_MATCH as usize - 1,
287        MAX_HASH_CHECKS,
288    )
289}
290
291#[cfg(test)]
292mod test {
293    use super::{get_match_length, longest_match, longest_match_fast};
294    use crate::chained_hash_table::{filled_hash_table, ChainedHashTable, HASH_BYTES};
295
296    /// Test that match lengths are calculated correctly
297    #[test]
298    fn match_length() {
299        let test_arr = [5u8, 5, 5, 5, 5, 9, 9, 2, 3, 5, 5, 5, 5, 5];
300        let l = get_match_length(&test_arr, 9, 0);
301        assert_eq!(l, 5);
302        let l2 = get_match_length(&test_arr, 9, 7);
303        assert_eq!(l2, 0);
304        let l3 = get_match_length(&test_arr, 10, 0);
305        assert_eq!(l3, 4);
306    }
307
308    /// Test that we get the longest of the matches
309    #[test]
310    fn get_longest_match() {
311        let test_data = b"xTest data, Test_data,zTest data";
312        let hash_table = filled_hash_table(&test_data[..23 + 1 + HASH_BYTES - 1]);
313
314        let (length, distance) = super::longest_match_current(test_data, &hash_table);
315
316        // We check that we get the longest match, rather than the shorter, but closer one.
317        assert_eq!(distance, 22);
318        assert_eq!(length, 9);
319        let test_arr2 = [
320            10u8, 10, 10, 10, 10, 10, 10, 10, 2, 3, 5, 10, 10, 10, 10, 10,
321        ];
322        let hash_table = filled_hash_table(&test_arr2[..HASH_BYTES + 1 + 1 + 2]);
323        let (length, distance) = super::longest_match_current(&test_arr2, &hash_table);
324
325        assert_eq!(distance, 1);
326        assert_eq!(length, 4);
327    }
328
329    /// Make sure we can get a match at index zero
330    #[test]
331    fn match_index_zero() {
332        let test_data = b"AAAAAAA";
333
334        let mut hash_table = ChainedHashTable::from_starting_values(test_data[0], test_data[1]);
335        for (n, &b) in test_data[2..5].iter().enumerate() {
336            hash_table.add_hash_value(n, b);
337        }
338
339        let (match_length, match_dist) = longest_match(test_data, &hash_table, 1, 0, 4096);
340
341        assert_eq!(match_dist, 1);
342        assert!(match_length == 6);
343    }
344
345    /// Test for fast_zlib algorithm.
346    /// Check that it doesn't give worse matches than the default one.
347    /// ignored by default as it's slow, and best ran in release mode.
348    #[ignore]
349    #[test]
350    fn fast_match_at_least_equal() {
351        use crate::test_utils::get_test_data;
352        for start_pos in 10000..50000 {
353            const NUM_CHECKS: u16 = 400;
354            let data = get_test_data();
355            let hash_table = filled_hash_table(&data[..start_pos + 1]);
356            let pos = hash_table.current_head() as usize;
357
358            let naive_match = longest_match(&data[..], &hash_table, pos, 0, NUM_CHECKS);
359            let fast_match = longest_match_fast(&data[..], &hash_table, pos, 0, NUM_CHECKS);
360
361            if fast_match.0 > naive_match.0 {
362                println!("Fast match found better match!");
363            }
364
365            assert!(
366                fast_match.0 >= naive_match.0,
367                "naive match had better length! start_pos: {}, naive: {:?}, fast {:?}",
368                start_pos,
369                naive_match,
370                fast_match
371            );
372            assert!(
373                fast_match.1 >= naive_match.1,
374                "naive match had better dist! start_pos: {} naive {:?}, fast {:?}",
375                start_pos,
376                naive_match,
377                fast_match
378            );
379        }
380    }
381}
382
383#[cfg(all(test, feature = "benchmarks"))]
384mod bench {
385    use super::{longest_match, longest_match_fast};
386    use chained_hash_table::filled_hash_table;
387    use test_std::Bencher;
388    use test_utils::get_test_data;
389    #[bench]
390    fn matching(b: &mut Bencher) {
391        const POS: usize = 29000;
392        let data = get_test_data();
393        let hash_table = filled_hash_table(&data[..POS + 1]);
394        let pos = hash_table.current_head() as usize;
395        println!(
396            "M: {:?}",
397            longest_match(&data[..], &hash_table, pos, 0, 4096)
398        );
399        b.iter(|| longest_match(&data[..], &hash_table, pos, 0, 4096));
400    }
401
402    #[bench]
403    fn fast_matching(b: &mut Bencher) {
404        const POS: usize = 29000;
405        let data = get_test_data();
406        let hash_table = filled_hash_table(&data[..POS + 1]);
407        let pos = hash_table.current_head() as usize;
408        println!(
409            "M: {:?}",
410            longest_match_fast(&data[..], &hash_table, pos, 0, 4096)
411        );
412        b.iter(|| longest_match_fast(&data[..], &hash_table, pos, 0, 4096));
413    }
414}