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.
38 #include "wimlib/lz_sarray.h"
39 #include "wimlib/util.h"
40 #include "divsufsort/divsufsort.h"
43 #define DIVSUFSORT_TMP1_SIZE (256 * sizeof(saidx_t)) /* bucket_A */
44 #define DIVSUFSORT_TMP2_SIZE (256 * 256 * sizeof(saidx_t)) /* bucket_B */
46 /* If ENABLE_LZ_DEBUG is defined, verify that the suffix array satisfies its
49 * @SA The constructed suffix array.
50 * @T The original data.
51 * @found Temporary 'bool' array of length @n.
52 * @n Length of the data (length of @SA, @T, and @found arrays).
54 * WARNING: this is for debug use only as it does not necessarily run in linear
57 verify_suffix_array(const lz_sarray_pos_t SA[restrict],
62 #ifdef ENABLE_LZ_DEBUG
63 /* Ensure the SA contains exactly one of each i in [0, n - 1]. */
64 for (lz_sarray_pos_t i = 0; i < n; i++)
66 for (lz_sarray_pos_t r = 0; r < n; r++) {
67 lz_sarray_pos_t i = SA[r];
73 /* Ensure the suffix with rank r is lexicographically lesser than the
74 * suffix with rank (r + 1) for all r in [0, n - 2]. */
75 for (lz_sarray_pos_t r = 0; r < n - 1; r++) {
77 lz_sarray_pos_t i1 = SA[r];
78 lz_sarray_pos_t i2 = SA[r + 1];
80 lz_sarray_pos_t n1 = n - i1;
81 lz_sarray_pos_t n2 = n - i2;
83 int res = memcmp(&T[i1], &T[i2], min(n1, n2));
84 LZ_ASSERT(res < 0 || (res == 0 && n1 < n2));
86 #endif /* ENABLE_LZ_DEBUG */
89 /* Compute the inverse suffix array @ISA from the suffix array @SA in linear
92 * Whereas the suffix array is a mapping from suffix rank to suffix position,
93 * the inverse suffix array is a mapping from suffix position to suffix rank.
96 compute_inverse_suffix_array(lz_sarray_pos_t ISA[restrict],
97 const lz_sarray_pos_t SA[restrict],
102 for (r = 0; r < n; r++)
107 /* Compute the LCP (Longest Common Prefix) array in linear time.
109 * LCP[r] will be the length of the longest common prefix between the suffixes
110 * with positions SA[r - 1] and SA[r]. LCP[0] will be undefined.
112 * Algorithm adapted from Kasai et al. 2001: "Linear-Time Longest-Common-Prefix
113 * Computation in Suffix Arrays and Its Applications". Modified slightly to
114 * take into account that with bytes in the real world, there is no unique
115 * symbol at the end of the string. */
117 compute_lcp_array(lz_sarray_pos_t LCP[restrict],
118 const lz_sarray_pos_t SA[restrict],
119 const lz_sarray_pos_t ISA[restrict],
120 const u8 T[restrict],
123 lz_sarray_pos_t h, i, r, j, lim;
126 for (i = 0; i < n; i++) {
130 lim = min(n - i, n - j);
132 while (h < lim && T[i + h] == T[j + h])
141 /* If ENABLE_LZ_DEBUG is defined, verify that the LCP (Longest Common Prefix)
142 * array satisfies its definition.
144 * WARNING: this is for debug use only as it does not necessarily run in linear
147 verify_lcp_array(lz_sarray_pos_t LCP[restrict],
148 const lz_sarray_pos_t SA[restrict],
149 const u8 T[restrict],
152 #ifdef ENABLE_LZ_DEBUG
153 for (lz_sarray_pos_t r = 0; r < n - 1; r++) {
154 lz_sarray_pos_t i1 = SA[r];
155 lz_sarray_pos_t i2 = SA[r + 1];
156 lz_sarray_pos_t lcp = LCP[r + 1];
158 lz_sarray_pos_t n1 = n - i1;
159 lz_sarray_pos_t n2 = n - i2;
161 LZ_ASSERT(lcp <= min(n1, n2));
163 LZ_ASSERT(memcmp(&T[i1], &T[i2], lcp) == 0);
164 if (lcp < min(n1, n2))
165 LZ_ASSERT(T[i1 + lcp] != T[i2 + lcp]);
167 #endif /* ENABLE_LZ_DEBUG */
170 /* Initialize the SA link array in linear time.
172 * This is similar to computing the LPF (Longest Previous Factor) array, which
173 * is addressed in several papers. In particular the algorithms below are based
174 * on Crochemore et al. 2009: "LPF computation revisited". However, this
175 * match-finder does not actually compute or use the LPF array per se. Rather,
176 * this function sets up some information necessary to compute the LPF array,
177 * but later lz_sarray_get_matches() actually uses this information to search
178 * the suffix array directly and can keep searching beyond the first (longest)
179 * match whose length would be placed in the LPF array. This difference from
180 * the theoretical work is necessary because in many real compression formats
181 * matches take variable numbers of bits to encode, so a decent parser needs to
182 * consider more than just the longest match with unspecified offset.
184 * Note: We cap the lcpprev and lcpnext values to the maximum match length so
185 * that the match-finder need not worry about it later, in the inner loop.
187 * Note: the LCP array is one of the inputs to this function, but it is used as
188 * temporary space and therefore will be invalidated.
191 init_salink(struct salink link[restrict],
192 lz_sarray_pos_t LCP[restrict],
193 const lz_sarray_pos_t SA[restrict],
194 const u8 T[restrict],
196 lz_sarray_len_t min_match_len,
197 lz_sarray_len_t max_match_len)
199 /* Calculate salink.dist_to_next and salink.lcpnext.
201 * Pass 1 calculates, for each suffix rank, the corresponding
202 * "next_initial" value which is the smallest larger rank that
203 * corresponds to a suffix starting earlier in the string. It also
204 * calculates "lcpnext_initial", which is the longest common prefix with
205 * that suffix, although to eliminate checks in lz_sarray_get_matches(),
206 * "lcpnext_initial" is set to 0 if it's less than the minimum match
207 * length or set to the maximum match length if it's greater than the
208 * maximum match length.
210 * Pass 2 translates each absolute "next_initial", a 4-byte value, into
211 * a relative "dist_to_next", a 1-byte value. This is done to save
212 * memory. In the case that the exact relative distance cannot be
213 * encoded in 1 byte, it is capped to 255. This is valid as long as
214 * lz_sarray_get_matches() validates each position before using it.
215 * Note that "lcpnext" need not be updated in this case because it will
216 * not be used until the actual next rank has been found anyway.
218 link[n - 1].next_initial = LZ_SARRAY_POS_MAX;
219 link[n - 1].lcpnext_initial = 0;
220 for (lz_sarray_pos_t r = n - 2; r != LZ_SARRAY_POS_MAX; r--) {
221 lz_sarray_pos_t t = r + 1;
222 lz_sarray_pos_t l = LCP[t];
223 while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) {
224 l = min(l, link[t].lcpnext_initial);
225 t = link[t].next_initial;
227 link[r].next_initial = t;
229 if (l < min_match_len)
231 else if (l > max_match_len)
233 link[r].lcpnext_initial = l;
235 for (lz_sarray_pos_t r = 0; r < n; r++) {
236 lz_sarray_pos_t next;
238 lz_sarray_delta_t dist_to_next;
240 next = link[r].next_initial;
241 l = link[r].lcpnext_initial;
243 if (next == LZ_SARRAY_POS_MAX)
245 else if (next - r <= LZ_SARRAY_DELTA_MAX)
246 dist_to_next = next - r;
248 dist_to_next = LZ_SARRAY_DELTA_MAX;
251 link[r].dist_to_next = dist_to_next;
254 /* Calculate salink.dist_to_prev and salink.lcpprev.
256 * This is analgous to dist_to_next and lcpnext as described above, but
257 * in the other direction. That is, here we're interested in, for each
258 * rank, the largest smaller rank that corresponds to a suffix starting
259 * earlier in the string.
261 * To save memory we don't have a "prev_initial" field, but rather store
262 * those values in the LCP array. */
263 LCP[0] = LZ_SARRAY_POS_MAX;
265 for (lz_sarray_pos_t r = 1; r < n; r++) {
266 lz_sarray_pos_t t = r - 1;
267 lz_sarray_pos_t l = LCP[r];
268 while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) {
269 l = min(l, link[t].lcpprev);
274 if (l < min_match_len)
276 else if (l > max_match_len)
281 for (lz_sarray_pos_t r = 0; r < n; r++) {
283 lz_sarray_pos_t prev = LCP[r];
285 if (prev == LZ_SARRAY_POS_MAX)
286 link[r].dist_to_prev = 0;
287 else if (r - prev <= LZ_SARRAY_DELTA_MAX)
288 link[r].dist_to_prev = r - prev;
290 link[r].dist_to_prev = LZ_SARRAY_DELTA_MAX;
294 /* If ENABLE_LZ_DEBUG is defined, verify the values computed by init_salink().
296 * WARNING: this is for debug use only as it does not necessarily run in linear
299 verify_salink(const struct salink link[],
300 const lz_sarray_pos_t SA[],
303 lz_sarray_len_t min_match_len,
304 lz_sarray_len_t max_match_len)
306 #ifdef ENABLE_LZ_DEBUG
307 for (lz_sarray_pos_t r = 0; r < n; r++) {
308 for (lz_sarray_pos_t prev = r; ; ) {
310 LZ_ASSERT(link[r].dist_to_prev == 0);
311 LZ_ASSERT(link[r].lcpprev == 0);
317 if (SA[prev] < SA[r]) {
318 LZ_ASSERT(link[r].dist_to_prev == min(r - prev, LZ_SARRAY_DELTA_MAX));
320 lz_sarray_pos_t lcpprev;
322 lcpprev < min(n - SA[prev], n - SA[r]) &&
323 T[SA[prev] + lcpprev] == T[SA[r] + lcpprev];
326 if (lcpprev < min_match_len)
328 else if (lcpprev > max_match_len)
329 lcpprev = max_match_len;
331 LZ_ASSERT(lcpprev == link[r].lcpprev);
336 for (lz_sarray_pos_t next = r; ; ) {
338 LZ_ASSERT(link[r].dist_to_next == 0);
339 LZ_ASSERT(link[r].lcpnext == 0);
345 if (SA[next] < SA[r]) {
346 LZ_ASSERT(link[r].dist_to_next == min(next - r, LZ_SARRAY_DELTA_MAX));
348 lz_sarray_pos_t lcpnext;
350 lcpnext < min(n - SA[next], n - SA[r]) &&
351 T[SA[next] + lcpnext] == T[SA[r] + lcpnext];
354 if (lcpnext < min_match_len)
356 else if (lcpnext > max_match_len)
357 lcpnext = max_match_len;
359 LZ_ASSERT(lcpnext == link[r].lcpnext);
368 * Initialize the suffix array match-finder.
371 * The suffix array match-finder structure to initialize. This structure
372 * is expected to be zeroed before this function is called. In the case
373 * that this function fails, lz_sarray_destroy() should be called to free
374 * any memory that may have been allocated.
377 * The maximum window size to support. This must be greater than 0.
379 * The amount of needed memory will depend on this value; see
380 * lz_sarray_get_needed_memory() for details.
383 * The minimum length of each match to be found. Must be greater than 0.
386 * The maximum length of each match to be found. Must be greater than or
387 * equal to @min_match_len.
389 * @max_matches_to_consider
390 * The maximum number of matches to consider at each position. This should
391 * be greater than @max_matches_to_return because @max_matches_to_consider
392 * counts all the returned matches as well as matches of equal length to
393 * returned matches that were not returned. This parameter bounds the
394 * amount of work the match-finder does at any one position. This could be
395 * anywhere from 1 to 100+ depending on the compression ratio and
396 * performance desired.
398 * @max_matches_to_return
399 * Maximum number of matches to return at each position. Because of the
400 * suffix array search algorithm, the order in which matches are returned
401 * will be from longest to shortest, so cut-offs due to this parameter will
402 * only result in shorter matches being discarded. This parameter could be
403 * anywhere from 1 to (@max_match_len - @min_match_len + 1) depending on
404 * the compression performance desired. However, making it even moderately
405 * large (say, greater than 3) may not be very helpful due to the property
406 * that the matches are returned from longest to shortest. But the main
407 * thing to keep in mind is that if the compressor decides to output a
408 * shorter-than-possible match, ideally it would be best to choose the best
409 * match of the desired length rather than truncate a longer match to that
412 * After initialization, the suffix-array match-finder can be used for any
413 * number of input strings (windows) of length less than or equal to
414 * @max_window_size by successive calls to lz_sarray_load_window().
416 * Returns %true on success, or %false if sufficient memory could not be
417 * allocated. See the note for @max_window_size above regarding the needed
421 lz_sarray_init(struct lz_sarray *mf,
422 lz_sarray_pos_t max_window_size,
423 lz_sarray_len_t min_match_len,
424 lz_sarray_len_t max_match_len,
425 u32 max_matches_to_consider,
426 u32 max_matches_to_return)
428 LZ_ASSERT(min_match_len > 0);
429 LZ_ASSERT(max_window_size > 0);
430 LZ_ASSERT(max_match_len >= min_match_len);
432 mf->max_window_size = max_window_size;
433 mf->min_match_len = min_match_len;
434 mf->max_match_len = max_match_len;
435 mf->max_matches_to_consider = max_matches_to_consider;
436 mf->max_matches_to_return = max_matches_to_return;
438 /* SA and ISA will share the same storage block. */
439 if ((u64)2 * max_window_size * sizeof(mf->SA[0]) !=
440 2 * max_window_size * sizeof(mf->SA[0]))
442 mf->SA = MALLOC(max_window_size * sizeof(mf->SA[0]) +
443 max(DIVSUFSORT_TMP1_SIZE,
444 max_window_size * sizeof(mf->SA[0])));
448 if ((u64)max_window_size * sizeof(mf->salink[0]) !=
449 max_window_size * sizeof(mf->salink[0]))
451 mf->salink = MALLOC(max(DIVSUFSORT_TMP2_SIZE,
452 max_window_size * sizeof(mf->salink[0])));
453 if (mf->salink == NULL)
460 * Return the number of bytes of memory that lz_sarray_init() would allocate for
461 * the specified maximum window size.
463 * This should be (14 * @max_window_size) unless the type definitions have been
467 lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size)
471 /* SA and ISA: 8 bytes per position */
472 size += (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0]) +
473 max(DIVSUFSORT_TMP1_SIZE,
474 (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0]));
476 /* salink: 6 bytes per position */
477 size += max(DIVSUFSORT_TMP2_SIZE,
478 (u64)max_window_size * sizeof(((struct lz_sarray*)0)->salink[0]));
484 * Prepare the suffix array match-finder to scan the specified window for
487 * @mf Suffix array match-finder previously initialized with lz_sarray_init().
489 * @T Window, or "block", in which to find matches.
491 * @n Size of window in bytes. This must be positive and less than or equal
492 * to the @max_window_size passed to lz_sarray_init().
494 * This function runs in linear time (relative to @n).
497 lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n)
499 lz_sarray_pos_t *ISA, *LCP;
501 LZ_ASSERT(n > 0 && n <= mf->max_window_size);
503 /* Compute SA (Suffix Array).
505 * divsufsort() needs temporary space --- one array with 256 spaces and
506 * one array with 65536 spaces. The implementation of divsufsort() has
507 * been modified from the original to use the provided temporary space
508 * instead of allocating its own.
510 * We also check at build-time that divsufsort() uses the same integer
511 * size expected by this code. Unfortunately, divsufsort breaks if
512 * 'sa_idx_t' is defined to be a 16-bit integer; however, that would
513 * limit blocks to only 65536 bytes anyway. */
514 BUILD_BUG_ON(sizeof(lz_sarray_pos_t) != sizeof(saidx_t));
516 divsufsort(T, mf->SA, n, (saidx_t*)&mf->SA[n], (saidx_t*)mf->salink);
518 BUILD_BUG_ON(sizeof(bool) > sizeof(mf->salink[0]));
519 verify_suffix_array(mf->SA, T, (bool*)mf->salink, n);
521 /* Compute ISA (Inverse Suffix Array) in a preliminary position.
523 * This is just a trick to save memory. Since LCP is unneeded after
524 * this function, it can be computed in any available space. The
525 * storage for the ISA is the best choice because the ISA can be built
526 * quickly in salink for now, then re-built in its real location at the
527 * end. This is probably worth it because computing the ISA from the SA
528 * is very fast, and since this match-finder is memory-hungry we'd like
529 * to save as much memory as possible. */
530 BUILD_BUG_ON(sizeof(mf->salink[0]) < sizeof(mf->ISA[0]));
531 ISA = (lz_sarray_pos_t*)mf->salink;
532 compute_inverse_suffix_array(ISA, mf->SA, n);
534 /* Compute LCP (Longest Common Prefix) array. */
536 compute_lcp_array(LCP, mf->SA, ISA, T, n);
537 verify_lcp_array(LCP, mf->SA, T, n);
539 /* Initialize suffix array links. */
540 init_salink(mf->salink, LCP, mf->SA, T, n,
541 mf->min_match_len, mf->max_match_len);
542 verify_salink(mf->salink, mf->SA, T, n,
543 mf->min_match_len, mf->max_match_len);
545 /* Compute ISA (Inverse Suffix Array) in its final position. */
547 compute_inverse_suffix_array(ISA, mf->SA, n);
549 /* Save new variables and return. */
555 /* Free memory allocated for the suffix array match-finder. */
557 lz_sarray_destroy(struct lz_sarray *mf)