4 * Suffix array match-finder for Lempel-Ziv compression.
8 * Copyright (c) 2013, 2014 Eric Biggers. All rights reserved.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
28 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #ifndef _WIMLIB_LZ_SARRAY_H
35 #define _WIMLIB_LZ_SARRAY_H
37 #include "wimlib/compiler.h" /* must define '_always_inline_attribute' */
38 #include "wimlib/lz.h" /* must define 'struct raw_match' and LZ_ASSERT() */
39 #include "wimlib/types.h" /* must define 'bool', 'u8', 'u16, and 'u32' */
43 /* Position type --- must be an unsigned type large enough to hold the length of
44 * longest window for which the suffix array match-finder will be used. */
45 typedef u32 lz_sarray_pos_t;
47 /* Length type --- must be an unsigned type large enough to hold the maximum
49 typedef u16 lz_sarray_len_t;
51 /* Cost type, for the user-provided match cost evaluation function. */
52 typedef lz_sarray_pos_t lz_sarray_cost_t;
54 #define LZ_SARRAY_LEN_MAX ((lz_sarray_len_t)~0UL)
55 #define LZ_SARRAY_POS_MAX ((lz_sarray_pos_t)~0UL)
56 #define LZ_SARRAY_INFINITE_COST ((lz_sarray_cost_t)~0UL)
58 /* State of the suffix array LZ (Lempel-Ziv) match-finder.
60 * This is defined here for benefit of the inlined code. It's not intended for
61 * code outside the match-finder itself to read or write members from this
64 /* Allocated window size for the match-finder.
66 * Note: this match-finder does not store the window itself, as the
67 * suffix array (@SA) and associated arrays (@ISA, @LCP, @salink) are
68 * sufficient to find matches. This number is the maximum length of
69 * those arrays, or also the maximum window (block) size that can be
70 * passed to lz_sarray_load_window(). */
71 lz_sarray_pos_t max_window_size;
73 /* Minimum length of matches to return. */
74 lz_sarray_len_t min_match_len;
76 /* Maximum length of matches to return. */
77 lz_sarray_len_t max_match_len;
79 /* Maximum matches to consider at each position (max search depth). */
80 u32 max_matches_to_consider;
82 /* Maximum number of matches to return at each position. */
83 u32 max_matches_to_return;
85 /* Current position in the window. */
86 lz_sarray_pos_t cur_pos;
88 /* Current window size. */
89 lz_sarray_pos_t window_size;
91 /* Suffix array for the current window.
92 * This is a mapping from suffix rank to suffix position. */
95 /* Inverse suffix array for the current window.
96 * This is a mapping from suffix position to suffix rank.
97 * If 0 <= r < window_size, then ISA[SA[r]] == r. */
100 /* Suffix array links.
102 * During a linear scan of the input string to find matches, this array
103 * used to keep track of which rank suffixes in the suffix array appear
104 * before the current position. Instead of searching in the original
105 * suffix array, scans for matches at a given position traverse a linked
106 * list containing only suffixes that appear before that position. */
107 struct salink *salink;
110 /* Suffix array link; one of these exists for each position in the suffix array.
113 /* Rank of highest ranked suffix that has rank lower than the suffix
114 * corresponding to this structure and either has a lower position
115 * (initially) or has a position lower than the highest position at
116 * which matches have been searched for so far, or LZ_SARRAY_POS_MAX if
117 * there is no such suffix.
119 * Think of this as a pointer to the closest position in the suffix
120 * array to the left that corresponds to a suffix that begins at a
121 * position in the current dictionary (i.e. before the current position
123 lz_sarray_pos_t prev;
125 /* Rank of lowest ranked suffix that has rank greater than the suffix
126 * corresponding to this structure and either has a lower position
127 * (intially) or has a position lower than the highest position at which
128 * matches have been searched for so far, or LZ_SARRAY_POS_MAX if there
131 * Think of this as a pointer to the closest position in the suffix
132 * array to the right that corresponds to a suffix that begins at a
133 * position in the current dictionary (i.e. before the current position
135 lz_sarray_pos_t next;
137 /* Length of longest common prefix between the suffix corresponding to
138 * this structure and the suffix with rank @prev, or 0 if @prev is
139 * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */
140 lz_sarray_len_t lcpprev;
142 /* Length of longest common prefix between the suffix corresponding to
143 * this structure and the suffix with rank @next, or 0 if @next is
144 * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */
145 lz_sarray_len_t lcpnext;
148 /*-----------------------------------*/
149 /* Functions defined in lz_sarray.c */
150 /*-----------------------------------*/
153 lz_sarray_init(struct lz_sarray *mf,
154 lz_sarray_pos_t max_window_size,
155 lz_sarray_len_t min_match_len,
156 lz_sarray_len_t max_match_len,
157 u32 max_matches_to_consider,
158 u32 max_matches_to_return);
161 lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size);
164 lz_sarray_destroy(struct lz_sarray *mf);
167 lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n);
169 /*-------------------*/
170 /* Inline functions */
171 /*-------------------*/
173 static _always_inline_attribute lz_sarray_pos_t
174 lz_sarray_get_pos(const struct lz_sarray *mf)
179 /* Advance the suffix array match-finder to the next position. */
180 static _always_inline_attribute void
181 lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[])
183 /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the
184 * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none
186 const lz_sarray_pos_t next = link[r].next;
188 /* prev = rank of HIGHEST ranked suffix that is ranked LOWER than the
189 * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none
191 const lz_sarray_pos_t prev = link[r].prev;
193 /* Link the suffix at the current position into the linked list that
194 * contains all suffixes referenced by the suffix array that appear at
195 * or before the current position, sorted by rank. */
196 if (next != LZ_SARRAY_POS_MAX) {
198 link[next].lcpprev = link[r].lcpnext;
201 if (prev != LZ_SARRAY_POS_MAX) {
203 link[prev].lcpnext = link[r].lcpprev;
207 /* Skip the current position in the suffix array match-finder. */
208 static _always_inline_attribute void
209 lz_sarray_skip_position(struct lz_sarray *mf)
211 LZ_ASSERT(mf->cur_pos < mf->window_size);
212 lz_sarray_update_salink(mf->ISA[mf->cur_pos++], mf->salink);
216 * Use the suffix array match-finder to retrieve a list of matches at the
219 * Returns the number of matches written into @matches. The matches are
220 * returned in decreasing order by length, and each will be of unique length
221 * between the minimum and maximum match lengths (inclusively) passed to
222 * lz_sarray_init(). Up to @max_matches_to_return (passed to lz_sarray_init())
223 * matches will be returned.
225 * @eval_match_cost is a function for evaluating the cost of a match when
226 * deciding which ones to return. It needs to be fast, and need not be exact;
227 * an implementation might simply rank matches by their offset, for example,
228 * although implementations may choose to take into account additional
229 * information such as repeat offsets.
231 static _always_inline_attribute u32
232 lz_sarray_get_matches(struct lz_sarray *mf,
233 struct raw_match matches[],
234 lz_sarray_cost_t (*eval_match_cost)
235 (lz_sarray_pos_t length,
236 lz_sarray_pos_t offset,
238 const void *eval_match_cost_ctx)
240 LZ_ASSERT(mf->cur_pos < mf->window_size);
241 const lz_sarray_pos_t i = mf->cur_pos++;
243 const lz_sarray_pos_t * const restrict SA = mf->SA;
244 const lz_sarray_pos_t * const restrict ISA = mf->ISA;
245 struct salink * const restrict link = mf->salink;
246 const lz_sarray_pos_t min_match_len = mf->min_match_len;
247 const u32 max_matches_to_consider = mf->max_matches_to_consider;
248 const u32 max_matches_to_return = mf->max_matches_to_return;
250 /* r = Rank of the suffix at the current position. */
251 const lz_sarray_pos_t r = ISA[i];
253 /* Prepare for searching the current position. */
254 lz_sarray_update_salink(r, link);
256 /* L = rank of next suffix to the left;
257 * R = rank of next suffix to the right;
258 * lenL = length of match between current position and the suffix with rank L;
259 * lenR = length of match between current position and the suffix with rank R.
261 * This is left and right relative to the rank of the current suffix.
262 * Since the suffixes in the suffix array are sorted, the longest
263 * matches are immediately to the left and right (using the linked list
264 * to ignore all suffixes that occur later in the window). The match
265 * length decreases the farther left and right we go. We shall keep the
266 * length on both sides in sync in order to choose the lowest-cost match
269 lz_sarray_pos_t L = link[r].prev;
270 lz_sarray_pos_t R = link[r].next;
271 lz_sarray_pos_t lenL = link[r].lcpprev;
272 lz_sarray_pos_t lenR = link[r].lcpnext;
274 /* nmatches = number of matches found so far. */
277 /* best_cost = cost of lowest-cost match found so far.
279 * We keep track of this so that we can ignore shorter matches that do
280 * not have lower costs than longer matches already found. */
281 lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
283 /* count_remaining = maximum number of possible matches remaining to be
285 u32 count_remaining = max_matches_to_consider;
287 /* pending = match currently being considered for a specific length. */
288 struct raw_match pending;
289 lz_sarray_cost_t pending_cost;
291 while (lenL >= min_match_len || lenR >= min_match_len)
294 pending_cost = LZ_SARRAY_INFINITE_COST;
295 lz_sarray_cost_t cost;
298 if (lenL >= min_match_len && lenL >= lenR) {
301 if (--count_remaining == 0)
302 goto out_save_pending;
304 lz_sarray_pos_t offset = i - SA[L];
306 /* Save match if it has smaller cost. */
307 cost = (*eval_match_cost)(lenL, offset,
308 eval_match_cost_ctx);
309 if (cost < pending_cost) {
310 pending.offset = offset;
314 if (link[L].lcpprev < lenL) {
315 /* Match length decreased. */
317 lenL = link[L].lcpprev;
319 /* Save the pending match unless the
320 * right side still may have matches of
321 * this length to be scanned, or if a
322 * previous (longer) match had lower
324 if (pending.len > lenR) {
325 if (pending_cost < best_cost) {
326 best_cost = pending_cost;
327 matches[nmatches++] = pending;
328 if (nmatches == max_matches_to_return)
332 pending_cost = LZ_SARRAY_INFINITE_COST;
334 if (lenL < min_match_len || lenL < lenR)
344 if (lenR >= min_match_len && lenR > lenL) {
347 if (--count_remaining == 0)
348 goto out_save_pending;
350 lz_sarray_pos_t offset = i - SA[R];
352 /* Save match if it has smaller cost. */
353 cost = (*eval_match_cost)(lenR,
355 eval_match_cost_ctx);
356 if (cost < pending_cost) {
357 pending.offset = offset;
361 if (link[R].lcpnext < lenR) {
362 /* Match length decreased. */
364 lenR = link[R].lcpnext;
366 /* Save the pending match unless a
367 * previous (longer) match had lower
369 if (pending_cost < best_cost) {
370 matches[nmatches++] = pending;
371 best_cost = pending_cost;
372 if (nmatches == max_matches_to_return)
376 if (lenR < min_match_len || lenR <= lenL)
380 pending_cost = LZ_SARRAY_INFINITE_COST;
389 if (pending_cost != LZ_SARRAY_INFINITE_COST)
390 matches[nmatches++] = pending;
396 #endif /* _WIMLIB_LZ_SARRAY_H */