2 * hc_matchfinder.h - Lempel-Ziv matchfinding with a hash table of linked lists
4 * Copyright 2022 Eric Biggers
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
27 * ---------------------------------------------------------------------------
31 * This is a Hash Chains (hc) based matchfinder.
33 * The main data structure is a hash table where each hash bucket contains a
34 * linked list (or "chain") of sequences whose first 4 bytes share the same hash
35 * code. Each sequence is identified by its starting position in the input
38 * The algorithm processes the input buffer sequentially. At each byte
39 * position, the hash code of the first 4 bytes of the sequence beginning at
40 * that position (the sequence being matched against) is computed. This
41 * identifies the hash bucket to use for that position. Then, this hash
42 * bucket's linked list is searched for matches. Then, a new linked list node
43 * is created to represent the current sequence and is prepended to the list.
45 * This algorithm has several useful properties:
47 * - It only finds true Lempel-Ziv matches; i.e., those where the matching
48 * sequence occurs prior to the sequence being matched against.
50 * - The sequences in each linked list are always sorted by decreasing starting
51 * position. Therefore, the closest (smallest offset) matches are found
52 * first, which in many compression formats tend to be the cheapest to encode.
54 * - Although fast running time is not guaranteed due to the possibility of the
55 * lists getting very long, the worst degenerate behavior can be easily
56 * prevented by capping the number of nodes searched at each position.
58 * - If the compressor decides not to search for matches at a certain position,
59 * then that position can be quickly inserted without searching the list.
61 * - The algorithm is adaptable to sliding windows: just store the positions
62 * relative to a "base" value that is updated from time to time, and stop
63 * searching each list when the sequences get too far away.
65 * ---------------------------------------------------------------------------
69 * Before including this header, you must define 'mf_pos_t' to an integer type
70 * that can represent all possible positions. This can be a 16-bit or 32-bit
71 * unsigned integer. When possible, the former should be used due to the
72 * reduced cache pressure. This header can be included multiple times in a
73 * single .c file with different 'mf_pos_t' definitions; however, you must
74 * define a different MF_SUFFIX each time to generate different names for the
75 * matchfinder structure and functions.
77 * The number of bytes that must be allocated for a given 'struct
78 * hc_matchfinder' must be gotten by calling hc_matchfinder_size().
80 * ----------------------------------------------------------------------------
84 * The main hash table and chains handle length 4+ matches. Length 3 matches
85 * are handled by a separate hash table with no chains. This works well for
86 * typical "greedy" or "lazy"-style compressors, where length 3 matches are
87 * often only helpful if they have small offsets. Instead of searching a full
88 * chain for length 3+ matches, the algorithm just checks for one close length 3
89 * match, then focuses on finding length 4+ matches.
91 * The longest_match() and skip_bytes() functions are inlined into the
92 * compressors that use them. This isn't just about saving the overhead of a
93 * function call. These functions are intended to be called from the inner
94 * loops of compressors, where giving the compiler more control over register
95 * allocation is very helpful. There is also significant benefit to be gained
96 * from allowing the CPU to predict branches independently at each call site.
97 * For example, "lazy"-style compressors can be written with two calls to
98 * longest_match(), each of which starts with a different 'best_len' and
99 * therefore has significantly different performance characteristics.
101 * Although any hash function can be used, a multiplicative hash is fast and
104 * On some processors, it is significantly faster to extend matches by whole
105 * words (32 or 64 bits) instead of by individual bytes. For this to be the
106 * case, the processor must implement unaligned memory accesses efficiently and
107 * must have either a fast "find first set bit" instruction or a fast "find last
108 * set bit" instruction, depending on the processor's endianness.
110 * The code uses one loop for finding the first match and one loop for finding a
111 * longer match. Each of these loops is tuned for its respective task and in
112 * combination are faster than a single generalized loop that handles both
115 * The code also uses a tight inner loop that only compares the last and first
116 * bytes of a potential match. It is only when these bytes match that a full
117 * match extension is attempted.
119 * ----------------------------------------------------------------------------
124 #include "wimlib/matchfinder_common.h"
126 #define HC_MATCHFINDER_HASH3_ORDER 15
127 #define HC_MATCHFINDER_HASH4_ORDER 16
129 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name. */
131 #define TEMPLATED(name) CONCAT(name, MF_SUFFIX)
133 struct TEMPLATED(hc_matchfinder) {
135 /* The hash table for finding length 3 matches */
136 mf_pos_t hash3_tab[1UL << HC_MATCHFINDER_HASH3_ORDER];
138 /* The hash table which contains the first nodes of the linked lists for
139 * finding length 4+ matches */
140 mf_pos_t hash4_tab[1UL << HC_MATCHFINDER_HASH4_ORDER];
142 /* The "next node" references for the linked lists. The "next node" of
143 * the node for the sequence with position 'pos' is 'next_tab[pos]'. */
147 /* Return the number of bytes that must be allocated for a 'hc_matchfinder' that
148 * can work with buffers up to the specified size. */
149 static forceinline size_t
150 TEMPLATED(hc_matchfinder_size)(size_t max_bufsize)
152 return sizeof(struct TEMPLATED(hc_matchfinder)) +
153 (max_bufsize * sizeof(mf_pos_t));
156 /* Prepare the matchfinder for a new input buffer. */
157 static forceinline void
158 TEMPLATED(hc_matchfinder_init)(struct TEMPLATED(hc_matchfinder) *mf)
160 memset(mf, 0, sizeof(*mf));
164 * Find the longest match longer than 'best_len' bytes.
167 * The matchfinder structure.
169 * Pointer to the beginning of the input buffer.
171 * Pointer to the next position in the input buffer, i.e. the sequence
172 * being matched against.
174 * Require a match longer than this length.
176 * The maximum permissible match length at this position.
178 * Stop searching if a match of at least this length is found.
179 * Must be <= @max_len.
181 * Limit on the number of potential matches to consider. Must be >= 1.
183 * The precomputed hash codes for the sequence beginning at @in_next.
184 * These will be used and then updated with the precomputed hashcodes for
185 * the sequence beginning at @in_next + 1.
187 * If a match is found, its offset is returned in this location.
189 * Return the length of the match found, or 'best_len' if no match longer than
190 * 'best_len' was found.
192 static forceinline u32
193 TEMPLATED(hc_matchfinder_longest_match)(struct TEMPLATED(hc_matchfinder) * const mf,
194 const u8 * const in_begin,
195 const u8 * const in_next,
199 const u32 max_search_depth,
200 u32 * const next_hashes,
201 u32 * const offset_ret)
203 u32 depth_remaining = max_search_depth;
204 const u8 *best_matchptr = in_next;
205 mf_pos_t cur_node3, cur_node4;
211 u32 cur_pos = in_next - in_begin;
213 if (unlikely(max_len < 5)) /* can we read 4 bytes from 'in_next + 1'? */
216 /* Get the precomputed hash codes. */
217 hash3 = next_hashes[0];
218 hash4 = next_hashes[1];
220 /* From the hash buckets, get the first node of each linked list. */
221 cur_node3 = mf->hash3_tab[hash3];
222 cur_node4 = mf->hash4_tab[hash4];
224 /* Update for length 3 matches. This replaces the singleton node in the
225 * 'hash3' bucket with the node for the current sequence. */
226 mf->hash3_tab[hash3] = cur_pos;
228 /* Update for length 4 matches. This prepends the node for the current
229 * sequence to the linked list in the 'hash4' bucket. */
230 mf->hash4_tab[hash4] = cur_pos;
231 mf->next_tab[cur_pos] = cur_node4;
233 /* Compute the next hash codes. */
234 next_hashseq = get_unaligned_le32(in_next + 1);
235 next_hashes[0] = lz_hash(next_hashseq & 0xFFFFFF, HC_MATCHFINDER_HASH3_ORDER);
236 next_hashes[1] = lz_hash(next_hashseq, HC_MATCHFINDER_HASH4_ORDER);
237 prefetchw(&mf->hash3_tab[next_hashes[0]]);
238 prefetchw(&mf->hash4_tab[next_hashes[1]]);
240 if (best_len < 4) { /* No match of length >= 4 found yet? */
242 /* Check for a length 3 match if needed. */
247 seq4 = load_u32_unaligned(in_next);
250 matchptr = &in_begin[cur_node3];
251 if (load_u24_unaligned(matchptr) == loaded_u32_to_u24(seq4)) {
253 best_matchptr = matchptr;
257 /* Check for a length 4 match. */
263 /* No length 4 match found yet. Check the first 4 bytes. */
264 matchptr = &in_begin[cur_node4];
266 if (load_u32_unaligned(matchptr) == seq4)
269 /* The first 4 bytes did not match. Keep trying. */
270 cur_node4 = mf->next_tab[cur_node4];
271 if (!cur_node4 || !--depth_remaining)
275 /* Found a match of length >= 4. Extend it to its full length. */
276 best_matchptr = matchptr;
277 best_len = lz_extend(in_next, best_matchptr, 4, max_len);
278 if (best_len >= nice_len)
280 cur_node4 = mf->next_tab[cur_node4];
281 if (!cur_node4 || !--depth_remaining)
284 if (!cur_node4 || best_len >= nice_len)
288 /* Check for matches of length >= 5. */
292 matchptr = &in_begin[cur_node4];
294 /* Already found a length 4 match. Try for a longer
295 * match; start by checking either the last 4 bytes and
296 * the first 4 bytes, or the last byte. (The last byte,
297 * the one which would extend the match length by 1, is
298 * the most important.) */
299 #if UNALIGNED_ACCESS_IS_FAST
300 if ((load_u32_unaligned(matchptr + best_len - 3) ==
301 load_u32_unaligned(in_next + best_len - 3)) &&
302 (load_u32_unaligned(matchptr) ==
303 load_u32_unaligned(in_next)))
305 if (matchptr[best_len] == in_next[best_len])
309 /* Continue to the next node in the list. */
310 cur_node4 = mf->next_tab[cur_node4];
311 if (!cur_node4 || !--depth_remaining)
315 #if UNALIGNED_ACCESS_IS_FAST
320 len = lz_extend(in_next, matchptr, len, max_len);
321 if (len > best_len) {
322 /* This is the new longest match. */
324 best_matchptr = matchptr;
325 if (best_len >= nice_len)
329 /* Continue to the next node in the list. */
330 cur_node4 = mf->next_tab[cur_node4];
331 if (!cur_node4 || !--depth_remaining)
335 *offset_ret = in_next - best_matchptr;
340 * Advance the matchfinder, but don't search for matches.
343 * The matchfinder structure.
345 * Pointer to the beginning of the input buffer.
347 * Pointer to the next position in the input buffer.
349 * Pointer to the end of the input buffer.
351 * The number of bytes to advance. Must be > 0.
353 * The precomputed hash codes for the sequence beginning at @in_next.
354 * These will be used and then updated with the precomputed hashcodes for
355 * the sequence beginning at @in_next + @count.
357 static forceinline void
358 TEMPLATED(hc_matchfinder_skip_bytes)(struct TEMPLATED(hc_matchfinder) * const mf,
359 const u8 * const in_begin,
361 const u8 * const in_end,
363 u32 * const next_hashes)
368 u32 remaining = count;
370 if (unlikely(count + 5 > in_end - in_next))
373 cur_pos = in_next - in_begin;
374 hash3 = next_hashes[0];
375 hash4 = next_hashes[1];
377 mf->hash3_tab[hash3] = cur_pos;
378 mf->next_tab[cur_pos] = mf->hash4_tab[hash4];
379 mf->hash4_tab[hash4] = cur_pos;
381 next_hashseq = get_unaligned_le32(++in_next);
382 hash3 = lz_hash(next_hashseq & 0xFFFFFF, HC_MATCHFINDER_HASH3_ORDER);
383 hash4 = lz_hash(next_hashseq, HC_MATCHFINDER_HASH4_ORDER);
385 } while (--remaining);
387 prefetchw(&mf->hash3_tab[hash3]);
388 prefetchw(&mf->hash4_tab[hash4]);
389 next_hashes[0] = hash3;
390 next_hashes[1] = hash4;