4 * This file provides the code to analyze a buffer of uncompressed data for
5 * matches, as per the LZ77 algorithm. It uses a hash table to accelerate the
6 * process. This is based on code from zlib (v. 1.2.5).
10 * Copyright (C) 2012, 2013 Eric Biggers
11 * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler
13 * This file is part of wimlib, a library for working with WIM files.
15 * wimlib is free software; you can redistribute it and/or modify it under the
16 * terms of the GNU General Public License as published by the Free
17 * Software Foundation; either version 3 of the License, or (at your option)
20 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
21 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
22 * A PARTICULAR PURPOSE. See the GNU General Public License for more
25 * You should have received a copy of the GNU General Public License
26 * along with wimlib; if not, see http://www.gnu.org/licenses/.
33 #include "wimlib/compress.h"
34 #include "wimlib/util.h"
38 #define LZ_MIN_MATCH 3
41 #define HASH_SIZE (1 << HASH_BITS)
42 #define HASH_MASK (HASH_SIZE - 1)
46 #elif LZ_MIN_MATCH == 3
49 #error "Invalid LZ_MIN_MATCH"
52 /* Hash function, based on code from zlib. This function will update and return
53 * the hash value @hash for the string ending on the additional input character
54 * @c. This function must be called for each consecutive character, because it
55 * uses a running hash value rather than computing it separately for each
58 * The AND operation guarantees that only 3 characters will affect the hash
59 * value, so every identical 3-character string will have the same hash value.
61 static inline unsigned
62 update_hash(unsigned hash, u8 c)
64 return ((hash << HASH_SHIFT) ^ c) & HASH_MASK;
68 /* Insert a 3-character string at position @str_pos in @window and with hash
69 * code @hash into the hash table described by @hash_tab and @prev_tab. Based
72 * The hash table uses chains (linked lists) for the hash buckets, but there are
73 * no real pointers involved. Indexing `hash_tab' by hash value gives the index
74 * within the window of the last string in the hash bucket. To find the index
75 * of the previous string in the hash chain, the `prev_tab' array is indexed by
76 * the string index. `prev_tab' can be indexed repeatedly by the string index
77 * to walk through the hash chain, until the special index `0' is reached,
78 * indicating the end of the hash chain.
80 static inline unsigned
81 insert_string(input_idx_t hash_tab[], input_idx_t prev_tab[],
82 const u8 window[], unsigned str_pos,
85 hash = update_hash(hash, window[str_pos + LZ_MIN_MATCH - 1]);
86 prev_tab[str_pos] = hash_tab[hash];
87 hash_tab[hash] = str_pos;
93 * Returns the longest match for a given input position.
95 * @window: The window of uncompressed data.
96 * @bytes_remaining: The number of bytes remaining in the window.
97 * @strstart: The index of the start of the string in the window that
98 * we are trying to find a match for.
99 * @prev_tab: The array of prev pointers for the hash table.
100 * @cur_match: The index of the head of the hash chain for matches
101 * having the hash value of the string beginning
102 * at index @strstart.
103 * @prev_len: The length of the match that was found for the string
104 * beginning at (@strstart - 1).
105 * @match_start_ret: A location into which the index of the start of the
106 * match will be returned.
107 * @params: Parameters that affect how long the search will proceed
108 * before going with the best that has been found
111 * Returns the length of the match that was found.
114 longest_match(const u8 window[], unsigned bytes_remaining,
115 unsigned strstart, const input_idx_t prev_tab[],
116 unsigned cur_match, unsigned prev_len,
117 unsigned *match_start_ret,
118 const struct lz_params *params)
120 unsigned chain_len = params->max_chain_len;
122 const u8 *scan = window + strstart;
125 unsigned best_len = prev_len;
126 unsigned match_start = cur_match;
128 unsigned nice_match = min(params->nice_match, bytes_remaining);
130 const u8 *strend = scan + min(params->max_match, bytes_remaining);
132 u8 scan_end1 = scan[best_len - 1];
133 u8 scan_end = scan[best_len];
136 /* Do not waste too much time if we already have a good match: */
137 if (best_len >= params->good_match)
141 match = &window[cur_match];
143 /* Skip to next match if the match length cannot increase or if
144 * the match length is less than 2. Note that the checks below
145 * for insufficient lookahead only occur occasionally for
146 * performance reasons. Therefore uninitialized memory will be
147 * accessed, and conditional jumps will be made that depend on
148 * those values. However the length of the match is limited to
149 * the lookahead, so the output of deflate is not affected by
150 * the uninitialized values.
153 if (match[best_len] != scan_end
154 || match[best_len - 1] != scan_end1
156 || *++match != scan[1])
162 } while (scan < strend && *++match == *++scan);
167 *++match == *++scan && *++match == *++scan &&
168 *++match == *++scan && *++match == *++scan &&
169 *++match == *++scan && *++match == *++scan &&
170 *++match == *++scan && *++match == *++scan &&
173 len = match - &window[cur_match];
175 scan = &window[strstart];
177 if (len > best_len) {
178 match_start = cur_match;
180 if (len >= nice_match)
182 scan_end1 = scan[best_len - 1];
183 scan_end = scan[best_len];
185 } while (--chain_len != 0 && (cur_match = prev_tab[cur_match]) != 0);
186 *match_start_ret = match_start;
187 return min(min(best_len, bytes_remaining), params->max_match);
193 * Determines the sequence of matches and literals that a block of data will be
196 * @window: The data that is to be compressed.
197 * @window_size: The length of @window, in bytes.
198 * @record_match: Consumer for matches.
199 * @record_literal: Consumer for literals.
200 * @record_ctx: Context passed to @record_match and @record_literal.
201 * @params: Structure that contains parameters that affect how the
202 * analysis proceeds (mainly how good the matches
206 lz_analyze_block(const u8 window[],
207 input_idx_t window_size,
208 lz_record_match_t record_match,
209 lz_record_literal_t record_literal,
211 const struct lz_params *params)
213 unsigned cur_input_pos = 0;
215 unsigned hash_head = 0;
216 unsigned prev_len = params->min_match - 1;
218 unsigned match_len = params->min_match - 1;
219 unsigned match_start = 0;
220 bool match_available = false;
221 input_idx_t hash_tab[HASH_SIZE];
222 input_idx_t prev_tab[window_size];
224 ZERO_ARRAY(hash_tab);
227 /* If there are at least 3 characters remaining in the input,
228 * insert the 3-character string beginning at
229 * window[cur_input_pos] into the hash table.
231 * hash_head is set to the index of the previous string in the
232 * hash bucket, or 0 if there is no such string */
233 if (window_size - cur_input_pos >= params->min_match) {
234 hash = insert_string(hash_tab, prev_tab,
236 cur_input_pos, hash);
237 hash_head = prev_tab[cur_input_pos];
243 /* Find the longest match, discarding those <= prev_len. */
244 prev_len = match_len;
245 prev_start = match_start;
246 match_len = params->min_match - 1;
248 if (hash_head != 0 && prev_len < params->max_lazy_match) {
249 /* To simplify the code, we prevent matches with the
250 * string of window index 0 (in particular we have to
251 * avoid a match of the string with itself at the start
252 * of the input file). */
253 match_len = longest_match(window,
254 window_size - cur_input_pos,
255 cur_input_pos, prev_tab,
257 &match_start, params);
259 if (match_len == params->min_match &&
260 cur_input_pos - match_start > params->too_far)
261 match_len = params->min_match - 1;
264 /* If there was a match at the previous step and the current
265 * match is not better, output the previous match:
267 if (prev_len >= params->min_match && match_len <= prev_len) {
270 (*record_match)(prev_len,
271 cur_input_pos - 1 - prev_start,
274 /* Insert in hash table all strings up to the end of the
275 * match. strstart-1 and strstart are already inserted.
276 * If there is not enough lookahead, the last two
277 * strings are not inserted in the hash table. */
279 /* Do not insert strings in hash table beyond this. */
280 unsigned max_insert = window_size - params->min_match;
281 #if LZ_MIN_MATCH == 2
288 if (++cur_input_pos <= max_insert) {
289 hash = insert_string(hash_tab, prev_tab,
294 } while (--prev_len != 0);
296 match_available = false;
297 match_len = params->min_match - 1;
298 } else if (match_available) {
299 /* If there was no match at the previous position,
300 * output a single literal. If there was a match but the
301 * current match is longer, truncate the previous match
302 * to a single literal. */
303 (*record_literal)(window[cur_input_pos - 1], record_ctx);
305 /* There is no previous match to compare with, wait for
306 * the next step to decide. */
307 match_available = true;
309 } while (++cur_input_pos < window_size);
312 (*record_literal)(window[cur_input_pos - 1], record_ctx);