1 use std::cmp;
2
3 use crate::chained_hash_table::{ChainedHashTable, WINDOW_SIZE};
4
5 const MAX_MATCH: usize = crate::huffman_table::MAX_MATCH as usize;
6 #[cfg(test)]
7 const 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]
get_match_length(data: &[u8], current_pos: usize, pos_to_check: usize) -> usize13 pub 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.
longest_match( data: &[u8], hash_table: &ChainedHashTable, position: usize, prev_length: usize, max_hash_checks: u16, ) -> (usize, usize)87 pub 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)]
longest_match_fast( data: &[u8], hash_table: &ChainedHashTable, position: usize, prev_length: usize, max_hash_checks: u16, ) -> (usize, usize)182 pub 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)]
longest_match_current(data: &[u8], hash_table: &ChainedHashTable) -> (usize, usize)280 pub 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)]
292 mod 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]
match_length()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]
get_longest_match()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]
match_index_zero()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]
fast_match_at_least_equal()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"))]
384 mod 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]
matching(b: &mut Bencher)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]
fast_matching(b: &mut Bencher)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 }
415