4 * Near-optimal LZ (Lempel-Ziv) parsing, or "match choosing".
5 * See lz_get_near_optimal_match() for details of the algorithm.
7 * This code is not concerned with actually *finding* LZ matches, as it relies
8 * on an underlying match-finder implementation that can do so.
12 * Copyright (c) 2013 Eric Biggers. All rights reserved.
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
18 * 1. Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
25 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
32 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
33 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
34 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
35 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 /* Define the following structures before including this header:
43 * Also, the type lz_mc_cost_t can be optionally overridden by providing an
44 * appropriate typedef and defining LZ_MC_COST_T_DEFINED. */
49 #include "wimlib/lz.h"
51 #ifndef LZ_MC_COST_T_DEFINED
52 typedef input_idx_t lz_mc_cost_t;
55 #define LZ_MC_INFINITE_COST (~(lz_mc_cost_t)0)
57 struct lz_mc_pos_data;
59 /* State of the Lempel-Ziv match-chooser.
61 * This is defined here for benefit of the inlined code. It's not intended for
62 * code outside the match-chooser itself to read or write members from this
64 struct lz_match_chooser {
65 /* Temporary space used for the match-choosing algorithm. The size of
66 * this array must be at least one more than @nice_len but otherwise is
67 * arbitrary. More space decreases the frequency at which the algorithm
68 * is forced to terminate early. 4096 spaces seems sufficient for most
70 struct lz_mc_pos_data *optimum;
71 input_idx_t array_space;
73 /* When a match with length greater than or equal to this length is
74 * found, choose it immediately without further consideration. */
77 /* When matches have been chosen, optimum_cur_idx is set to the position
78 * in the window of the next match/literal to return and optimum_end_idx
79 * is set to the position in the window at the end of the last
80 * match/literal to return. */
81 input_idx_t optimum_cur_idx;
82 input_idx_t optimum_end_idx;
86 * Match chooser position data:
88 * An array of these structures is used during the match-choosing algorithm.
89 * They correspond to consecutive positions in the window and are used to keep
90 * track of the cost to reach each position, and the match/literal choices that
91 * need to be chosen to reach that position.
93 struct lz_mc_pos_data {
94 /* The approximate minimum cost, in bits, to reach this position in the
95 * window which has been found so far. */
98 /* The union here is just for clarity, since the fields are used in two
99 * slightly different ways. Initially, the @prev structure is filled in
100 * first, and links go from later in the window to earlier in the
101 * window. Later, @next structure is filled in and links go from
102 * earlier in the window to later in the window. */
105 /* Position of the start of the match or literal that
106 * was taken to get to this position in the approximate
107 * minimum-cost parse. */
110 /* Offset (as in an LZ (length, offset) pair) of the
111 * match or literal that was taken to get to this
112 * position in the approximate minimum-cost parse. */
113 input_idx_t match_offset;
116 /* Position at which the match or literal starting at
117 * this position ends in the minimum-cost parse. */
120 /* Offset (as in an LZ (length, offset) pair) of the
121 * match or literal starting at this position in the
122 * approximate minimum-cost parse. */
123 input_idx_t match_offset;
127 /* Format-dependent adaptive state that exists after an approximate
128 * minimum-cost path to reach this position is taken. For example, for
129 * LZX this is the list of recently used match offsets. If the format
130 * does not have any adaptive state that affects match costs,
131 * LZ_ADAPTIVE_STATE could be set to a dummy structure of size 0. */
132 LZ_ADAPTIVE_STATE state;
135 /* Initialize the match-chooser.
137 * After calling this, multiple data buffers can be scanned with it if each is
138 * preceded with a call to lz_match_chooser_begin(). */
140 lz_match_chooser_init(struct lz_match_chooser *mc,
141 input_idx_t array_space,
142 input_idx_t nice_len, input_idx_t max_match_len)
144 input_idx_t extra_len = min(nice_len, max_match_len);
146 LZ_ASSERT(array_space > 0);
147 mc->optimum = MALLOC((array_space + extra_len) * sizeof(mc->optimum[0]));
148 if (mc->optimum == NULL)
150 mc->array_space = array_space;
151 mc->nice_len = nice_len;
156 lz_match_chooser_get_needed_memory(input_idx_t array_space,
157 input_idx_t nice_len,
158 input_idx_t max_match_len)
160 input_idx_t extra_len = min(nice_len, max_match_len);
161 return ((u64)(array_space + extra_len) *
162 sizeof(((struct lz_match_chooser*)0)->optimum[0]));
165 /* Free memory allocated in lz_match_chooser_init(). */
167 lz_match_chooser_destroy(struct lz_match_chooser *mc)
172 /* Call this before starting to parse each new input string. */
174 lz_match_chooser_begin(struct lz_match_chooser *mc)
176 mc->optimum_cur_idx = 0;
177 mc->optimum_end_idx = 0;
181 * Reverse the linked list of near-optimal matches so that they can be returned
184 * Returns the first match in the list.
186 static _always_inline_attribute struct raw_match
187 lz_match_chooser_reverse_list(struct lz_match_chooser *mc, input_idx_t cur_pos)
189 unsigned prev_link, saved_prev_link;
190 unsigned prev_match_offset, saved_prev_match_offset;
192 mc->optimum_end_idx = cur_pos;
194 saved_prev_link = mc->optimum[cur_pos].prev.link;
195 saved_prev_match_offset = mc->optimum[cur_pos].prev.match_offset;
198 prev_link = saved_prev_link;
199 prev_match_offset = saved_prev_match_offset;
201 saved_prev_link = mc->optimum[prev_link].prev.link;
202 saved_prev_match_offset = mc->optimum[prev_link].prev.match_offset;
204 mc->optimum[prev_link].next.link = cur_pos;
205 mc->optimum[prev_link].next.match_offset = prev_match_offset;
208 } while (cur_pos != 0);
210 mc->optimum_cur_idx = mc->optimum[0].next.link;
212 return (struct raw_match)
213 { .len = mc->optimum_cur_idx,
214 .offset = mc->optimum[0].next.match_offset,
218 /* Format-specific functions inlined into lz_get_near_optimal_match(). */
220 /* Get the list of possible matches at the next position. The return value must
221 * be the number of matches found (which may be 0) and a pointer to the returned
222 * matches must be written into @matches_ret. Matches must be of distinct
223 * lengths and sorted in decreasing order by length. Furthermore, match lengths
224 * may not exceed the @max_match_len passed to lz_match_chooser_init(), and all
225 * match lengths must be at least 2. */
226 typedef u32 (*lz_get_matches_t)(LZ_COMPRESSOR *ctx,
227 const LZ_ADAPTIVE_STATE *state,
228 struct raw_match **matches_ret);
230 /* Skip the specified number of bytes (don't search for matches at them). This
231 * is expected to be faster than simply getting the matches at each position,
232 * but the exact performance difference will be dependent on the match-finder
234 typedef void (*lz_skip_bytes_t)(LZ_COMPRESSOR *ctx, input_idx_t n);
236 /* Get the cost of the literal located at the position at which matches have
237 * most recently been searched. This can optionally update the @state to take
238 * into account format-dependent state that affects match costs, such as repeat
240 typedef lz_mc_cost_t (*lz_get_prev_literal_cost_t)(LZ_COMPRESSOR *ctx,
241 LZ_ADAPTIVE_STATE *state);
243 /* Get the cost of a match. This can optionally update the @state to take into
244 * account format-dependent state that affects match costs, such as repeat
246 typedef lz_mc_cost_t (*lz_get_match_cost_t)(LZ_COMPRESSOR *ctx,
247 LZ_ADAPTIVE_STATE *state,
252 * lz_get_near_optimal_match() -
254 * Choose an approximately optimal match or literal to use at the next position
255 * in the string, or "window", being LZ-encoded.
257 * This is based on the algorithm used in 7-Zip's DEFLATE encoder, written by
258 * Igor Pavlov. However it also attempts to account for adaptive state, such as
259 * a LRU queue of recent match offsets.
261 * Unlike a greedy parser that always takes the longest match, or even a "lazy"
262 * parser with one match/literal look-ahead like zlib, the algorithm used here
263 * may look ahead many matches/literals to determine the approximately optimal
264 * match/literal to code next. The motivation is that the compression ratio is
265 * improved if the compressor can do things like use a shorter-than-possible
266 * match in order to allow a longer match later, and also take into account the
267 * estimated real cost of coding each match/literal based on the underlying
270 * Still, this is not a true optimal parser for several reasons:
272 * - Very long matches (at least @nice_len) are taken immediately. This is
273 * because locations with long matches are likely to have many possible
274 * alternatives that would cause slow optimal parsing, but also such locations
275 * are already highly compressible so it is not too harmful to just grab the
278 * - Not all possible matches at each location are considered. Users of this
279 * code are expected to provide a @get_matches() function that returns a list
280 * of potentially good matches at the current position, but no more than one
281 * per length. It therefore must use some sort of heuristic (e.g. smallest or
282 * repeat offset) to choose a good match to consider for a given length, if
283 * multiple exist. Furthermore, the @get_matches() implementation may limit
284 * the total number of matches returned and/or the number of computational
285 * steps spent searching for matches at each position.
287 * - This function relies on the user-provided @get_match_cost() and
288 * @get_prev_literal_cost() functions to evaluate match and literal costs,
289 * respectively, but real compression formats use entropy encoding of the
290 * literal/match sequence, so the real cost of coding each match or literal is
291 * unknown until the parse is fully determined. It can be approximated based
292 * on iterative parses, but the end result is not guaranteed to be globally
295 * - Although this function allows @get_match_cost() and
296 * @get_prev_literal_cost() to take into account adaptive state, coding
297 * decisions made with respect to the adaptive state will be locally optimal
298 * but will not necessarily be globally optimal. This is because the
299 * algorithm only keeps the least-costly path to get to a given location and
300 * does not take into account that a slightly more costly path could result in
301 * a different adaptive state that ultimately results in a lower global cost.
303 * - The array space used by this function is bounded, so in degenerate cases it
304 * is forced to start returning matches/literals before the algorithm has
307 * Each call to this function does one of two things:
309 * 1. Build a sequence of near-optimal matches/literals, up to some point, that
310 * will be returned by subsequent calls to this function, then return the
315 * 2. Return the next match/literal previously computed by a call to this
318 * The return value is a (length, offset) pair specifying the match or literal
319 * chosen. For literals, the length is 0 or 1 and the offset is meaningless.
321 * NOTE: this code has been factored out of the LZX compressor so that it can be
322 * shared by other formats such as LZMS. It is inlined so there is no loss of
323 * performance, especially with the different implementations of match-finding,
324 * cost evaluation, and adaptive state.
326 static _always_inline_attribute struct raw_match
327 lz_get_near_optimal_match(struct lz_match_chooser *mc,
328 lz_get_matches_t get_matches,
329 lz_skip_bytes_t skip_bytes,
330 lz_get_prev_literal_cost_t get_prev_literal_cost,
331 lz_get_match_cost_t get_match_cost,
333 const LZ_ADAPTIVE_STATE *initial_state)
335 u32 num_possible_matches;
336 struct raw_match *possible_matches;
337 struct raw_match match;
338 input_idx_t longest_match_len;
340 if (mc->optimum_cur_idx != mc->optimum_end_idx) {
341 /* Case 2: Return the next match/literal already found. */
342 match.len = mc->optimum[mc->optimum_cur_idx].next.link -
344 match.offset = mc->optimum[mc->optimum_cur_idx].next.match_offset;
346 mc->optimum_cur_idx = mc->optimum[mc->optimum_cur_idx].next.link;
350 /* Case 1: Compute a new list of matches/literals to return. */
352 mc->optimum_cur_idx = 0;
353 mc->optimum_end_idx = 0;
355 /* Get matches at this position. */
356 num_possible_matches = (*get_matches)(ctx,
360 /* If no matches found, return literal. */
361 if (num_possible_matches == 0)
362 return (struct raw_match){ .len = 0 };
364 /* The matches that were found are sorted in decreasing order by length.
365 * Get the length of the longest one. */
366 longest_match_len = possible_matches[0].len;
368 /* Greedy heuristic: if the longest match that was found is greater
369 * than nice_len, return it immediately; don't both doing more work. */
370 if (longest_match_len >= mc->nice_len) {
371 (*skip_bytes)(ctx, longest_match_len - 1);
372 return possible_matches[0];
375 /* Calculate the cost to reach the next position by coding a literal.
377 mc->optimum[1].state = *initial_state;
378 mc->optimum[1].cost = (*get_prev_literal_cost)(ctx, &mc->optimum[1].state);
379 mc->optimum[1].prev.link = 0;
381 /* Calculate the cost to reach any position up to and including that
382 * reached by the longest match. Use the shortest available match that
383 * reaches each position, assuming that @get_matches() only returned
384 * shorter matches because their estimated costs were less than that of
385 * the longest match. */
386 for (input_idx_t len = 2, match_idx = num_possible_matches - 1;
387 len <= longest_match_len; len++)
390 LZ_ASSERT(match_idx < num_possible_matches);
391 LZ_ASSERT(len <= possible_matches[match_idx].len);
393 mc->optimum[len].state = *initial_state;
394 mc->optimum[len].prev.link = 0;
395 mc->optimum[len].prev.match_offset = possible_matches[match_idx].offset;
396 mc->optimum[len].cost = (*get_match_cost)(ctx,
397 &mc->optimum[len].state,
399 possible_matches[match_idx].offset);
400 if (len == possible_matches[match_idx].len)
404 /* Step forward, calculating the estimated minimum cost to reach each
405 * position. The algorithm may find multiple paths to reach each
406 * position; only the lowest-cost path is saved.
408 * The progress of the parse is tracked in the @mc->optimum array, which
409 * for each position contains the minimum cost to reach that position,
410 * the index of the start of the match/literal taken to reach that
411 * position through the minimum-cost path, the offset of the match taken
412 * (not relevant for literals), and the adaptive state that will exist
413 * at that position after the minimum-cost path is taken. The @cur_pos
414 * variable stores the position at which the algorithm is currently
415 * considering coding choices, and the @len_end variable stores the
416 * greatest position at which the costs of coding choices have been
417 * saved. (Actually, the algorithm guarantees that all positions up to
418 * and including @len_end are reachable by at least one path.)
420 * The loop terminates when any one of the following conditions occurs:
422 * 1. A match with length greater than or equal to @nice_len is found.
423 * When this occurs, the algorithm chooses this match
424 * unconditionally, and consequently the near-optimal match/literal
425 * sequence up to and including that match is fully determined and it
426 * can begin returning the match/literal list.
428 * 2. @cur_pos reaches a position not overlapped by a preceding match.
429 * In such cases, the near-optimal match/literal sequence up to
430 * @cur_pos is fully determined and it can begin returning the
431 * match/literal list.
433 * 3. Failing either of the above in a degenerate case, the loop
434 * terminates when space in the @mc->optimum array is exhausted.
435 * This terminates the algorithm and forces it to start returning
436 * matches/literals even though they may not be globally optimal.
438 * Upon loop termination, a nonempty list of matches/literals will have
439 * been produced and stored in the @optimum array. These
440 * matches/literals are linked in reverse order, so the last thing this
441 * function does is reverse this list and return the first
442 * match/literal, leaving the rest to be returned immediately by
443 * subsequent calls to this function.
445 input_idx_t cur_pos = 0;
446 input_idx_t len_end = longest_match_len;
448 /* Advance to next position. */
451 /* Check termination conditions (2) and (3) noted above. */
452 if (cur_pos == len_end || cur_pos == mc->array_space)
453 return lz_match_chooser_reverse_list(mc, cur_pos);
455 /* Retrieve a (possibly empty) list of potentially useful
456 * matches available at this position. */
457 num_possible_matches = (*get_matches)(ctx,
458 &mc->optimum[cur_pos].state,
461 if (num_possible_matches == 0)
462 longest_match_len = 0;
464 longest_match_len = possible_matches[0].len;
466 /* Greedy heuristic and termination condition (1) noted above:
467 * if we found a match greater than @nice_len, choose it
468 * unconditionally and begin returning matches/literals. */
469 if (longest_match_len >= mc->nice_len) {
470 /* Build the list of matches to return and get
472 match = lz_match_chooser_reverse_list(mc, cur_pos);
474 /* Append the long match to the end of the list. */
475 mc->optimum[cur_pos].next.match_offset =
476 possible_matches[0].offset;
477 mc->optimum[cur_pos].next.link = cur_pos + longest_match_len;
478 mc->optimum_end_idx = cur_pos + longest_match_len;
480 /* Skip over the remaining bytes of the long match. */
481 (*skip_bytes)(ctx, longest_match_len - 1);
483 /* Return first match in the list. */
487 /* Load minimum cost to reach the current position. */
488 input_idx_t cur_cost = mc->optimum[cur_pos].cost;
490 /* Consider proceeding with a literal byte. */
492 LZ_ADAPTIVE_STATE state;
495 state = mc->optimum[cur_pos].state;
496 cost = cur_cost + (*get_prev_literal_cost)(ctx, &state);
498 if (cost < mc->optimum[cur_pos + 1].cost) {
499 mc->optimum[cur_pos + 1].cost = cost;
500 mc->optimum[cur_pos + 1].prev.link = cur_pos;
501 mc->optimum[cur_pos + 1].state = state;
505 /* If no matches were found, continue to the next position.
506 * Otherwise, consider proceeding with a match. */
508 if (num_possible_matches == 0)
511 /* Initialize any uninitialized costs up to the length of the
512 * longest match found. */
513 while (len_end < cur_pos + longest_match_len)
514 mc->optimum[++len_end].cost = LZ_MC_INFINITE_COST;
516 /* Calculate the minimum cost to reach any position up to and
517 * including that reached by the longest match. Use the
518 * shortest available match that reaches each position, assuming
519 * that @get_matches() only returned shorter matches because
520 * their estimated costs were less than that of the longest
522 for (input_idx_t len = 2, match_idx = num_possible_matches - 1;
523 len <= longest_match_len; len++)
525 LZ_ASSERT(match_idx < num_possible_matches);
526 LZ_ASSERT(len <= possible_matches[match_idx].len);
528 LZ_ADAPTIVE_STATE state;
531 state = mc->optimum[cur_pos].state;
532 cost = cur_cost + (*get_match_cost)(ctx,
535 possible_matches[match_idx].offset);
537 if (cost < mc->optimum[cur_pos + len].cost) {
538 mc->optimum[cur_pos + len].cost = cost;
539 mc->optimum[cur_pos + len].prev.link = cur_pos;
540 mc->optimum[cur_pos + len].prev.match_offset =
541 possible_matches[match_idx].offset;
542 mc->optimum[cur_pos + len].state = state;
545 if (len == possible_matches[match_idx].len)
551 #endif /* _LZ_OPTIMAL_H */