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/lz_extend.h"
125 #include "wimlib/lz_hash.h"
126 #include "wimlib/unaligned.h"
128 #define HC_MATCHFINDER_HASH3_ORDER 15
129 #define HC_MATCHFINDER_HASH4_ORDER 16
131 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name. */
133 #define TEMPLATED(name) CONCAT(name, MF_SUFFIX)
135 struct TEMPLATED(hc_matchfinder) {
137 /* The hash table for finding length 3 matches */
138 mf_pos_t hash3_tab[1UL << HC_MATCHFINDER_HASH3_ORDER];
140 /* The hash table which contains the first nodes of the linked lists for
141 * finding length 4+ matches */
142 mf_pos_t hash4_tab[1UL << HC_MATCHFINDER_HASH4_ORDER];
144 /* The "next node" references for the linked lists. The "next node" of
145 * the node for the sequence with position 'pos' is 'next_tab[pos]'. */
149 /* Return the number of bytes that must be allocated for a 'hc_matchfinder' that
150 * can work with buffers up to the specified size. */
151 static forceinline size_t
152 TEMPLATED(hc_matchfinder_size)(size_t max_bufsize)
154 return sizeof(struct TEMPLATED(hc_matchfinder)) +
155 (max_bufsize * sizeof(mf_pos_t));
158 /* Prepare the matchfinder for a new input buffer. */
159 static forceinline void
160 TEMPLATED(hc_matchfinder_init)(struct TEMPLATED(hc_matchfinder) *mf)
162 memset(mf, 0, sizeof(*mf));
166 * Find the longest match longer than 'best_len' bytes.
169 * The matchfinder structure.
171 * Pointer to the beginning of the input buffer.
173 * Pointer to the next position in the input buffer, i.e. the sequence
174 * being matched against.
176 * Require a match longer than this length.
178 * The maximum permissible match length at this position.
180 * Stop searching if a match of at least this length is found.
181 * Must be <= @max_len.
183 * Limit on the number of potential matches to consider. Must be >= 1.
185 * The precomputed hash codes for the sequence beginning at @in_next.
186 * These will be used and then updated with the precomputed hashcodes for
187 * the sequence beginning at @in_next + 1.
189 * If a match is found, its offset is returned in this location.
191 * Return the length of the match found, or 'best_len' if no match longer than
192 * 'best_len' was found.
194 static forceinline u32
195 TEMPLATED(hc_matchfinder_longest_match)(struct TEMPLATED(hc_matchfinder) * const mf,
196 const u8 * const in_begin,
197 const u8 * const in_next,
201 const u32 max_search_depth,
202 u32 * const next_hashes,
203 u32 * const offset_ret)
205 u32 depth_remaining = max_search_depth;
206 const u8 *best_matchptr = in_next;
207 mf_pos_t cur_node3, cur_node4;
213 u32 cur_pos = in_next - in_begin;
215 if (unlikely(max_len < 5)) /* can we read 4 bytes from 'in_next + 1'? */
218 /* Get the precomputed hash codes. */
219 hash3 = next_hashes[0];
220 hash4 = next_hashes[1];
222 /* From the hash buckets, get the first node of each linked list. */
223 cur_node3 = mf->hash3_tab[hash3];
224 cur_node4 = mf->hash4_tab[hash4];
226 /* Update for length 3 matches. This replaces the singleton node in the
227 * 'hash3' bucket with the node for the current sequence. */
228 mf->hash3_tab[hash3] = cur_pos;
230 /* Update for length 4 matches. This prepends the node for the current
231 * sequence to the linked list in the 'hash4' bucket. */
232 mf->hash4_tab[hash4] = cur_pos;
233 mf->next_tab[cur_pos] = cur_node4;
235 /* Compute the next hash codes. */
236 next_hashseq = get_unaligned_le32(in_next + 1);
237 next_hashes[0] = lz_hash(next_hashseq & 0xFFFFFF, HC_MATCHFINDER_HASH3_ORDER);
238 next_hashes[1] = lz_hash(next_hashseq, HC_MATCHFINDER_HASH4_ORDER);
239 prefetchw(&mf->hash3_tab[next_hashes[0]]);
240 prefetchw(&mf->hash4_tab[next_hashes[1]]);
242 if (best_len < 4) { /* No match of length >= 4 found yet? */
244 /* Check for a length 3 match if needed. */
249 seq4 = load_u32_unaligned(in_next);
252 matchptr = &in_begin[cur_node3];
253 if (load_u24_unaligned(matchptr) == loaded_u32_to_u24(seq4)) {
255 best_matchptr = matchptr;
259 /* Check for a length 4 match. */
265 /* No length 4 match found yet. Check the first 4 bytes. */
266 matchptr = &in_begin[cur_node4];
268 if (load_u32_unaligned(matchptr) == seq4)
271 /* The first 4 bytes did not match. Keep trying. */
272 cur_node4 = mf->next_tab[cur_node4];
273 if (!cur_node4 || !--depth_remaining)
277 /* Found a match of length >= 4. Extend it to its full length. */
278 best_matchptr = matchptr;
279 best_len = lz_extend(in_next, best_matchptr, 4, max_len);
280 if (best_len >= nice_len)
282 cur_node4 = mf->next_tab[cur_node4];
283 if (!cur_node4 || !--depth_remaining)
286 if (!cur_node4 || best_len >= nice_len)
290 /* Check for matches of length >= 5. */
294 matchptr = &in_begin[cur_node4];
296 /* Already found a length 4 match. Try for a longer
297 * match; start by checking either the last 4 bytes and
298 * the first 4 bytes, or the last byte. (The last byte,
299 * the one which would extend the match length by 1, is
300 * the most important.) */
301 #if UNALIGNED_ACCESS_IS_FAST
302 if ((load_u32_unaligned(matchptr + best_len - 3) ==
303 load_u32_unaligned(in_next + best_len - 3)) &&
304 (load_u32_unaligned(matchptr) ==
305 load_u32_unaligned(in_next)))
307 if (matchptr[best_len] == in_next[best_len])
311 /* Continue to the next node in the list. */
312 cur_node4 = mf->next_tab[cur_node4];
313 if (!cur_node4 || !--depth_remaining)
317 #if UNALIGNED_ACCESS_IS_FAST
322 len = lz_extend(in_next, matchptr, len, max_len);
323 if (len > best_len) {
324 /* This is the new longest match. */
326 best_matchptr = matchptr;
327 if (best_len >= nice_len)
331 /* Continue to the next node in the list. */
332 cur_node4 = mf->next_tab[cur_node4];
333 if (!cur_node4 || !--depth_remaining)
337 *offset_ret = in_next - best_matchptr;
342 * Advance the matchfinder, but don't search for matches.
345 * The matchfinder structure.
347 * Pointer to the beginning of the input buffer.
349 * Pointer to the next position in the input buffer.
351 * Pointer to the end of the input buffer.
353 * The number of bytes to advance. Must be > 0.
355 * The precomputed hash codes for the sequence beginning at @in_next.
356 * These will be used and then updated with the precomputed hashcodes for
357 * the sequence beginning at @in_next + @count.
359 static forceinline void
360 TEMPLATED(hc_matchfinder_skip_bytes)(struct TEMPLATED(hc_matchfinder) * const mf,
361 const u8 * const in_begin,
363 const u8 * const in_end,
365 u32 * const next_hashes)
370 u32 remaining = count;
372 if (unlikely(count + 5 > in_end - in_next))
375 cur_pos = in_next - in_begin;
376 hash3 = next_hashes[0];
377 hash4 = next_hashes[1];
379 mf->hash3_tab[hash3] = cur_pos;
380 mf->next_tab[cur_pos] = mf->hash4_tab[hash4];
381 mf->hash4_tab[hash4] = cur_pos;
383 next_hashseq = get_unaligned_le32(++in_next);
384 hash3 = lz_hash(next_hashseq & 0xFFFFFF, HC_MATCHFINDER_HASH3_ORDER);
385 hash4 = lz_hash(next_hashseq, HC_MATCHFINDER_HASH4_ORDER);
387 } while (--remaining);
389 prefetchw(&mf->hash3_tab[hash3]);
390 prefetchw(&mf->hash4_tab[hash4]);
391 next_hashes[0] = hash3;
392 next_hashes[1] = hash4;