From: Eric Biggers Date: Wed, 1 Jan 2014 21:39:22 +0000 (-0600) Subject: lz_sarray.{c,h}: Cleanup, better comments X-Git-Tag: v1.6.0~30 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=b527a1721ea8fb45d34df6a9c2d7ab5cb3eef143 lz_sarray.{c,h}: Cleanup, better comments --- diff --git a/include/wimlib/lz_sarray.h b/include/wimlib/lz_sarray.h index 925285b0..74f77a10 100644 --- a/include/wimlib/lz_sarray.h +++ b/include/wimlib/lz_sarray.h @@ -1,7 +1,7 @@ /* * lz_sarray.h * - * Suffix array match-finder for LZ (Lempel-Ziv) compression. + * Suffix array match-finder for Lempel-Ziv compression. */ /* @@ -34,15 +34,26 @@ #ifndef _WIMLIB_LZ_SARRAY_H #define _WIMLIB_LZ_SARRAY_H -#include "wimlib/compiler.h" -#include "wimlib/lz.h" -#include "wimlib/types.h" +#include "wimlib/compiler.h" /* must define '_always_inline_attribute' */ +#include "wimlib/lz.h" /* must define 'struct raw_match', 'input_idx_t', + and LZ_ASSERT(). */ +#include "wimlib/types.h" /* must define 'bool', 'u8', 'u32' */ struct salink; -/* Suffix array LZ (Lempel-Ziv) match-finder. */ +/* State of the suffix array LZ (Lempel-Ziv) match-finder. + * + * This is defined here for benefit of the inlined code. It's not intended for + * code outside the match-finder itself to read or write members from this + * structure. */ struct lz_sarray { - /* Allocated window size for the match-finder. */ + /* Allocated window size for the match-finder. + * + * Note: this match-finder does not store the window itself, as the + * suffix array (@SA) and associated arrays (@ISA, @LCP, @salink) are + * sufficient to find matches. This number is the maximum length of + * those arrays, or also the maximum window (block) size that can be + * passed to lz_sarray_load_window(). */ input_idx_t max_window_size; /* Minimum match length to return. */ @@ -57,27 +68,21 @@ struct lz_sarray { /* Maximum number of matches to return at each position. */ u32 max_matches_to_return; - /* Current position in the window */ + /* Current position in the window. */ input_idx_t cur_pos; /* Current window size. */ input_idx_t window_size; - /* Suffix array for window. + /* Suffix array for the current window. * This is a mapping from suffix rank to suffix position. */ input_idx_t *SA; - /* Inverse suffix array for window. + /* Inverse suffix array for the current window. * This is a mapping from suffix position to suffix rank. * If 0 <= r < window_size, then ISA[SA[r]] == r. */ input_idx_t *ISA; - /* Longest common prefix array corresponding to the suffix array SA. - * LCP[i] is the length of the longest common prefix between the - * suffixes with positions SA[i - 1] and SA[i]. LCP[0] is undefined. - */ - input_idx_t *LCP; - /* Suffix array links. * * During a linear scan of the input string to find matches, this array @@ -88,49 +93,67 @@ struct lz_sarray { struct salink *salink; }; -/* Suffix array link */ +/* Suffix array link; one of these exists for each position in the suffix array. + */ struct salink { /* Rank of highest ranked suffix that has rank lower than the suffix * corresponding to this structure and either has a lower position * (initially) or has a position lower than the highest position at - * which matches have been searched for so far, or -1 if there is no - * such suffix. */ + * which matches have been searched for so far, or ~(input_idx_t)0 if + * there is no such suffix. + * + * Think of this as a pointer to the closest position in the suffix + * array to the left that corresponds to a suffix that begins at a + * position in the current dictionary (i.e. before the current position + * in the window). */ input_idx_t prev; /* Rank of lowest ranked suffix that has rank greater than the suffix * corresponding to this structure and either has a lower position * (intially) or has a position lower than the highest position at which - * matches have been searched for so far, or -1 if there is no such - * suffix. */ + * matches have been searched for so far, or ~(input_idx_t)0 if there is + * no such suffix. + + * Think of this as a pointer to the closest position in the suffix + * array to the right that corresponds to a suffix that begins at a + * position in the current dictionary (i.e. before the current position + * in the window). */ input_idx_t next; /* Length of longest common prefix between the suffix corresponding to - * this structure and the suffix with rank @prev, or 0 if @prev is -1. - */ + * this structure and the suffix with rank @prev, or 0 if @prev is + * ~(input_idx_t)0. */ input_idx_t lcpprev; /* Length of longest common prefix between the suffix corresponding to - * this structure and the suffix with rank @next, or 0 if @next is -1. - */ + * this structure and the suffix with rank @next, or 0 if @next is + * ~(input_idx_t)0. */ input_idx_t lcpnext; }; +/*-----------------------------------*/ +/* Functions defined in lz_sarray.c */ +/*-----------------------------------*/ + extern bool lz_sarray_init(struct lz_sarray *mf, - input_idx_t max_window_size, - input_idx_t min_match_len, - input_idx_t max_match_len, - u32 max_matches_to_consider, - u32 max_matches_to_return); + input_idx_t max_window_size, + input_idx_t min_match_len, + input_idx_t max_match_len, + u32 max_matches_to_consider, + u32 max_matches_to_return); extern void lz_sarray_destroy(struct lz_sarray *mf); extern void -lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], - input_idx_t window_size); +lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n); -static inline input_idx_t +/*-------------------*/ +/* Inline functions */ +/*-------------------*/ + +static _always_inline_attribute input_idx_t lz_sarray_get_pos(const struct lz_sarray *mf) { return mf->cur_pos; @@ -147,27 +170,24 @@ lz_sarray_update_salink(const input_idx_t i, const input_idx_t r = ISA[i]; /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the - * current suffix AND has a LOWER position, or -1 if none exists. */ + * current suffix AND has a LOWER position, or ~(input_idx_t)0 if none + * exists. */ const input_idx_t next = link[r].next; /* prev = rank of HIGHEST ranked suffix that is ranked LOWER than the - * current suffix AND has a LOWER position, or -1 if none exists. */ + * current suffix AND has a LOWER position, or ~(input_idx_t)0 if none + * exists. */ const input_idx_t prev = link[r].prev; /* Link the suffix at the current position into the linked list that - * contains all suffixes in the suffix array that are appear at or - * before the current position, sorted by rank. - * - * Save the values of all fields we overwrite so that rollback is - * possible. */ + * contains all suffixes referenced by the suffix array that appear at + * or before the current position, sorted by rank. */ if (next != ~(input_idx_t)0) { - link[next].prev = r; link[next].lcpprev = link[r].lcpnext; } if (prev != ~(input_idx_t)0) { - link[prev].next = r; link[prev].lcpnext = link[r].lcpprev; } @@ -185,21 +205,20 @@ typedef input_idx_t lz_sarray_cost_t; #define LZ_SARRAY_INFINITE_COST (~(lz_sarray_cost_t)0) /* - * Use the suffix array match-finder to retrieve a list of LZ matches at the + * Use the suffix array match-finder to retrieve a list of matches at the * current position. * * Returns the number of matches written into @matches. The matches are * returned in decreasing order by length, and each will be of unique length - * between the minimum and maximum match lengths passed to lz_sarray_init(). Up - * to @max_matches_to_return (passed to lz_sarray_init()) matches will be - * returned. + * between the minimum and maximum match lengths (inclusively) passed to + * lz_sarray_init(). Up to @max_matches_to_return (passed to lz_sarray_init()) + * matches will be returned. * * @eval_match_cost is a function for evaluating the cost of a match when - * deciding which ones to return. It is only used for comparing matches of the - * same length. It needs to be fast, and need not be exact; an implementation - * might simply rank matches by their offset, for example, although - * implementations may choose to take into account additional information such - * as repeat offsets. + * deciding which ones to return. It needs to be fast, and need not be exact; + * an implementation might simply rank matches by their offset, for example, + * although implementations may choose to take into account additional + * information such as repeat offsets. */ static _always_inline_attribute u32 lz_sarray_get_matches(struct lz_sarray *mf, @@ -250,8 +269,7 @@ lz_sarray_get_matches(struct lz_sarray *mf, /* best_cost = cost of lowest-cost match found so far. * * We keep track of this so that we can ignore shorter matches that do - * not have lower costs than a longer matches already found. - */ + * not have lower costs than longer matches already found. */ lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST; /* count_remaining = maximum number of possible matches remaining to be diff --git a/src/lz_sarray.c b/src/lz_sarray.c index 1428ebaa..ffffcd16 100644 --- a/src/lz_sarray.c +++ b/src/lz_sarray.c @@ -1,7 +1,7 @@ /* * lz_sarray.c * - * Suffix array match-finder for LZ (Lempel-Ziv) compression. + * Suffix array match-finder for Lempel-Ziv compression. */ /* @@ -40,89 +40,35 @@ #include "divsufsort/divsufsort.h" #include -/* Initialize the suffix array match-finder with the specified parameters. +/* If ENABLE_LZ_DEBUG is defined, verify that the suffix array satisfies its + * definition. * - * After initialization, it can be used for any number of input strings of - * length less than or equal to @max_window_size. */ -bool -lz_sarray_init(struct lz_sarray *mf, - input_idx_t max_window_size, - input_idx_t min_match_len, - input_idx_t max_match_len, - u32 max_matches_to_consider, - u32 max_matches_to_return) -{ - mf->max_window_size = max_window_size; - mf->min_match_len = min_match_len; - mf->max_match_len = max_match_len; - mf->max_matches_to_consider = max_matches_to_consider; - mf->max_matches_to_return = max_matches_to_return; - - mf->SA = MALLOC(3U * max_window_size * sizeof(mf->SA[0])); - if (mf->SA == NULL) - return false; - - mf->salink = MALLOC(max_window_size * sizeof(mf->salink[0])); - if (mf->salink == NULL) - return false; - - return true; -} - -/* Free memory allocated for the suffix array match-finder. */ -void -lz_sarray_destroy(struct lz_sarray *mf) -{ - FREE(mf->SA); - FREE(mf->salink); -} - -/* Initialize the suffix array match-finder for the specified input. */ -void -lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], - input_idx_t window_size) + * @SA The constructed suffix array. + * @T The original data. + * @found Temporary 'bool' array of length @n. + * @n Length of the data (length of @SA, @T, and @found arrays). + * + * WARNING: this is for debug use only as it does not necessarily run in linear + * time!!! */ +static void +verify_suffix_array(const input_idx_t SA[restrict], + const u8 T[restrict], + bool found[restrict], + input_idx_t n) { - /* Load variables */ - const u8 * const restrict T = window; - const input_idx_t n = window_size; - const input_idx_t max_match_len = mf->max_match_len; - input_idx_t * const restrict SA = mf->SA; - input_idx_t * const restrict ISA = mf->ISA = SA + window_size; - input_idx_t * const restrict LCP = mf->LCP = ISA + window_size; - struct salink * const restrict link = mf->salink; - - /* Compute SA (Suffix Array). */ - { - /* ISA and link are used as temporary space. */ - LZ_ASSERT(mf->max_window_size * sizeof(ISA[0]) >= 256 * sizeof(saidx_t)); - LZ_ASSERT(mf->max_window_size * 2 * sizeof(link[0]) >= 256 * 256 * sizeof(saidx_t)); - - if (sizeof(input_idx_t) == sizeof(saidx_t)) { - divsufsort(T, SA, n, (saidx_t*)ISA, (saidx_t*)link); - } else { - saidx_t sa[n]; - divsufsort(T, sa, n, (saidx_t*)ISA, (saidx_t*)link); - for (input_idx_t i = 0; i < n; i++) - SA[i] = sa[i]; - } - } - #ifdef ENABLE_LZ_DEBUG - - LZ_ASSERT(n > 0); - - /* Verify suffix array. */ - { - bool found[n]; - ZERO_ARRAY(found); - for (input_idx_t r = 0; r < n; r++) { - input_idx_t i = SA[r]; - LZ_ASSERT(i < n); - LZ_ASSERT(!found[i]); - found[i] = true; - } + /* Ensure the SA contains exactly one of each i in [0, n - 1]. */ + for (input_idx_t i = 0; i < n; i++) + found[i] = false; + for (input_idx_t r = 0; r < n; r++) { + input_idx_t i = SA[r]; + LZ_ASSERT(i < n); + LZ_ASSERT(!found[i]); + found[i] = true; } + /* Ensure the suffix with rank r is lexicographically lesser than the + * suffix with rank (r + 1) for all r in [0, n - 2]. */ for (input_idx_t r = 0; r < n - 1; r++) { input_idx_t i1 = SA[r]; @@ -131,44 +77,77 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], input_idx_t n1 = n - i1; input_idx_t n2 = n - i2; - LZ_ASSERT(memcmp(&T[i1], &T[i2], min(n1, n2)) <= 0); + int res = memcmp(&T[i1], &T[i2], min(n1, n2)); + LZ_ASSERT(res < 0 || (res == 0 && n1 < n2)); } - LZ_DEBUG("Verified SA (len %u)", n); -#endif /* ENABLE_LZ_DEBUG */ +#endif /* ENABLE_LZ_DEBUG */ +} + +/* Compute the inverse suffix array @ISA from the suffix array @SA in linear + * time. + * + * Whereas the suffix array is a mapping from suffix rank to suffix position, + * the inverse suffix array is a mapping from suffix position to suffix rank. + */ +static void +compute_inverse_suffix_array(input_idx_t ISA[restrict], + const input_idx_t SA[restrict], + input_idx_t n) +{ + input_idx_t i; - /* Compute ISA (Inverse Suffix Array) */ - for (input_idx_t r = 0; r < n; r++) - ISA[SA[r]] = r; + for (i = 0; i < n; i++) + ISA[SA[i]] = i; +} - /* Compute LCP (longest common prefix) array. - * - * Algorithm adapted from Kasai et al. 2001: "Linear-Time - * Longest-Common-Prefix Computation in Suffix Arrays and Its - * Applications". */ - { - input_idx_t h = 0; - for (input_idx_t i = 0; i < n; i++) { - input_idx_t r = ISA[i]; - if (r > 0) { - input_idx_t j = SA[r - 1]; - - input_idx_t lim = min(n - i, n - j); - - while (h < lim && T[i + h] == T[j + h]) - h++; - LCP[r] = h; - if (h > 0) - h--; - } + +/* Compute the LCP (Longest Common Prefix) array in linear time. + * + * LCP[r] will be the length of the longest common prefix between the suffixes + * with positions SA[r - 1] and SA[r]. LCP[0] will be undefined. + * + * Algorithm adapted from Kasai et al. 2001: "Linear-Time Longest-Common-Prefix + * Computation in Suffix Arrays and Its Applications". Modified slightly to + * take into account that with bytes in the real world, there is no unique + * symbol at the end of the string. */ +static void +compute_lcp_array(input_idx_t LCP[restrict], + const input_idx_t SA[restrict], + const input_idx_t ISA[restrict], + const u8 T[restrict], + input_idx_t n) +{ + input_idx_t h, i, r, j, lim; + + h = 0; + for (i = 0; i < n; i++) { + r = ISA[i]; + if (r > 0) { + j = SA[r - 1]; + lim = min(n - i, n - j); + + while (h < lim && T[i + h] == T[j + h]) + h++; + LCP[r] = h; + if (h > 0) + h--; } } +} +/* If ENABLE_LZ_DEBUG is defined, verify that the LCP (Longest Common Prefix) + * array satisfies its definition. + * + * WARNING: this is for debug use only as it does not necessarily run in linear + * time!!! */ +static void +verify_lcp_array(input_idx_t LCP[restrict], + const input_idx_t SA[restrict], + const u8 T[restrict], + input_idx_t n) +{ #ifdef ENABLE_LZ_DEBUG - /* Verify LCP array. */ for (input_idx_t r = 0; r < n - 1; r++) { - LZ_ASSERT(ISA[SA[r]] == r); - LZ_ASSERT(ISA[SA[r + 1]] == r + 1); - input_idx_t i1 = SA[r]; input_idx_t i2 = SA[r + 1]; input_idx_t lcp = LCP[r + 1]; @@ -183,18 +162,36 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], LZ_ASSERT(T[i1 + lcp] != T[i2 + lcp]); } #endif /* ENABLE_LZ_DEBUG */ +} - /* Compute salink.next and salink.lcpnext. - * - * Algorithm adapted from Crochemore et al. 2009: - * "LPF computation revisited". - * - * Note: we cap lcpnext to the maximum match length so that the - * match-finder need not worry about it later. */ +/* Initialize the SA link array in linear time. + * + * This is similar to computing the LPF (Longest Previous Factor) array, which + * is addressed in several papers. In particular the algorithms below are based + * on Crochemore et al. 2009: "LPF computation revisited". However, this + * match-finder does not actually compute or use the LPF array per se. Rather, + * this function sets up some information necessary to compute the LPF array, + * but later lz_sarray_get_matches() actually uses this information to search + * the suffix array directly and can keep searching beyond the first (longest) + * match whose length would be placed in the LPF array. This difference from + * the theoretical work is necessary because in many real compression formats + * matches take variable numbers of bits to encode, so a decent parser needs to + * consider more than just the longest match with unspecified offset. + * + * Note: We cap the lcpprev and lcpnext values to the maximum match length so + * that the match-finder need not worry about it later, in the inner loop. + */ +static void +init_salink(struct salink link[restrict], + const input_idx_t LCP[restrict], + const input_idx_t SA[restrict], + const u8 T[restrict], + input_idx_t n, + input_idx_t max_match_len) +{ + /* Compute salink.next and salink.lcpnext. */ link[n - 1].next = ~(input_idx_t)0; - link[n - 1].prev = ~(input_idx_t)0; link[n - 1].lcpnext = 0; - link[n - 1].lcpprev = 0; for (input_idx_t r = n - 2; r != ~(input_idx_t)0; r--) { input_idx_t t = r + 1; input_idx_t l = LCP[t]; @@ -204,25 +201,11 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], } link[r].next = t; link[r].lcpnext = min(l, max_match_len); - LZ_ASSERT(t == ~(input_idx_t)0 || l <= n - SA[t]); - LZ_ASSERT(l <= n - SA[r]); - if (t == ~(input_idx_t)0) - LZ_ASSERT(l == 0); - else - LZ_ASSERT(memcmp(&T[SA[r]], &T[SA[t]], l) == 0); } - /* Compute salink.prev and salink.lcpprev. - * - * Algorithm adapted from Crochemore et al. 2009: - * "LPF computation revisited". - * - * Note: we cap lcpprev to the maximum match length so that the - * match-finder need not worry about it later. */ + /* Compute salink.prev and salink.lcpprev. */ link[0].prev = ~(input_idx_t)0; - link[0].next = ~(input_idx_t)0; link[0].lcpprev = 0; - link[0].lcpnext = 0; for (input_idx_t r = 1; r < n; r++) { input_idx_t t = r - 1; input_idx_t l = LCP[r]; @@ -232,14 +215,245 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 window[], } link[r].prev = t; link[r].lcpprev = min(l, max_match_len); - LZ_ASSERT(t == ~(input_idx_t)0 || l <= n - SA[t]); - LZ_ASSERT(l <= n - SA[r]); - if (t == ~(input_idx_t)0) - LZ_ASSERT(l == 0); - else - LZ_ASSERT(memcmp(&T[SA[r]], &T[SA[t]], l) == 0); } +} +/* If ENABLE_LZ_DEBUG is defined, verify the values computed by init_salink(). + * + * WARNING: this is for debug use only as it does not necessarily run in linear + * time!!! */ +static void +verify_salink(const struct salink link[], + const input_idx_t SA[], + const u8 T[], + input_idx_t n, + input_idx_t max_match_len) +{ +#ifdef ENABLE_LZ_DEBUG + for (input_idx_t r = 0; r < n; r++) { + for (input_idx_t prev = r; ; ) { + if (prev == 0) { + LZ_ASSERT(link[r].prev == ~(input_idx_t)0); + LZ_ASSERT(link[r].lcpprev == 0); + break; + } + + prev--; + + if (SA[prev] < SA[r]) { + LZ_ASSERT(link[r].prev == prev); + LZ_ASSERT(link[r].lcpprev <= n - SA[prev]); + LZ_ASSERT(link[r].lcpprev <= n - SA[r]); + LZ_ASSERT(link[r].lcpprev <= max_match_len); + LZ_ASSERT(0 == memcmp(&T[SA[prev]], + &T[SA[r]], + link[r].lcpprev)); + if (link[r].lcpprev < n - SA[prev] && + link[r].lcpprev < n - SA[r] && + link[r].lcpprev < max_match_len) + { + LZ_ASSERT(T[SA[prev] + link[r].lcpprev] != + T[SA[r] + link[r].lcpprev]); + } + break; + } + } + + for (input_idx_t next = r; ; ) { + if (next == n - 1) { + LZ_ASSERT(link[r].next == ~(input_idx_t)0); + LZ_ASSERT(link[r].lcpnext == 0); + break; + } + + next++; + + if (SA[next] < SA[r]) { + LZ_ASSERT(link[r].next == next); + LZ_ASSERT(link[r].lcpnext <= n - SA[next]); + LZ_ASSERT(link[r].lcpnext <= n - SA[r]); + LZ_ASSERT(link[r].lcpnext <= max_match_len); + LZ_ASSERT(0 == memcmp(&T[SA[next]], + &T[SA[r]], + link[r].lcpnext)); + if (link[r].lcpnext < n - SA[next] && + link[r].lcpnext < n - SA[r] && + link[r].lcpnext < max_match_len) + { + LZ_ASSERT(T[SA[next] + link[r].lcpnext] != + T[SA[r] + link[r].lcpnext]); + + } + break; + } + } + } +#endif +} + +/* + * Initialize the suffix array match-finder. + * + * @mf + * The suffix array match-finder structure to initialize. This structure + * is expected to be zeroed before this function is called. In the case + * that this function fails, lz_sarray_destroy() should be called to free + * any memory that may have been allocated. + * + * @max_window_size + * The maximum window size to support. + * + * In the current implementation, the memory needed will be + * (6 * sizeof(input_idx_t) * @max_window_size) bytes. + * For (sizeof(input_idx_t) == 4) that's 24 times the window size. + * + * Memory is saved by saving neither the original window nor the LCP + * (Longest Common Prefix) array; otherwise 29 times the window size would + * be required. (In practice the compressor will likely keep the original + * window around anyway, although based on this property of the + * match-finder it theoretically it could overwrite it with the compressed + * data.) + * + * @min_match_len + * The minimum length of each match to be found. + * + * @max_match_len + * The maximum length of each match to be found. + * + * @max_matches_to_consider + * The maximum number of matches to consider at each position. This should + * be greater than @max_matches_to_return because @max_matches_to_consider + * counts all the returned matches as well as matches of equal length to + * returned matches that were not returned. This parameter bounds the + * amount of work the match-finder does at any one position. This could be + * anywhere from 1 to 100+ depending on the compression ratio and + * performance desired. + * + * @max_matches_to_return + * Maximum number of matches to return at each position. Because of the + * suffix array search algorithm, the order in which matches are returned + * will be from longest to shortest, so cut-offs due to this parameter will + * only result in shorter matches being discarded. This parameter could be + * anywhere from 1 to (@max_match_len - @min_match_len + 1) depending on + * the compression performance desired. However, making it even moderately + * large (say, greater than 3) may not be very helpful due to the property + * that the matches are returned from longest to shortest. But the main + * thing to keep in mind is that if the compressor decides to output a + * shorter-than-possible match, ideally it would be best to choose the best + * match of the desired length rather than truncate a longer match to that + * length. + * + * After initialization, the suffix-array match-finder can be used for any + * number of input strings (windows) of length less than or equal to + * @max_window_size by successive calls to lz_sarray_load_window(). + * + * Returns %true on success, or %false if sufficient memory could not be + * allocated. See the note for @max_window_size above regarding the needed + * memory size. + */ +bool +lz_sarray_init(struct lz_sarray *mf, + input_idx_t max_window_size, + input_idx_t min_match_len, + input_idx_t max_match_len, + u32 max_matches_to_consider, + u32 max_matches_to_return) +{ + mf->max_window_size = max_window_size; + mf->min_match_len = min_match_len; + mf->max_match_len = max_match_len; + mf->max_matches_to_consider = max_matches_to_consider; + mf->max_matches_to_return = max_matches_to_return; + + /* SA and ISA will share the same storage block. */ + mf->SA = MALLOC(2 * max_window_size * sizeof(mf->SA[0])); + if (mf->SA == NULL) + return false; + + mf->salink = MALLOC(max_window_size * sizeof(mf->salink[0])); + if (mf->salink == NULL) + return false; + + return true; +} + +/* + * Prepare the suffix array match-finder to scan the specified window for + * matches. + * + * @mf Suffix array match-finder previously initialized with lz_sarray_init(). + * + * @T Window, or "block", in which to find matches. + * + * @n Size of window in bytes. This must be positive and less than or equal + * to the @max_window_size passed to lz_sarray_init(). + * + * This function runs in linear time (relative to @n). + */ +void +lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n) +{ + input_idx_t *ISA, *LCP; + + LZ_ASSERT(n > 0 && n <= mf->max_window_size); + + /* Compute SA (Suffix Array). + * + * divsufsort() needs temporary space --- one array with 256 spaces and + * one array with 65536 spaces. The implementation has been modified + * from the original to use the provided temporary space instead of + * allocating its own. + * + * We also check at build-time that divsufsort() uses the same integer + * size expected by this code. Unfortunately, divsufsort breaks if + * 'sa_idx_t' is defined to be a 16-bit integer; however, that would + * limit blocks to only 65536 bytes anyway. */ + LZ_ASSERT(mf->max_window_size * sizeof(mf->SA[0]) + >= 256 * sizeof(saidx_t)); + LZ_ASSERT(mf->max_window_size * sizeof(mf->salink[0]) + >= 256 * 256 * sizeof(saidx_t)); + BUILD_BUG_ON(sizeof(input_idx_t) != sizeof(saidx_t)); + + divsufsort(T, mf->SA, n, (saidx_t*)&mf->SA[n], (saidx_t*)mf->salink); + + BUILD_BUG_ON(sizeof(bool) > sizeof(mf->salink[0])); + verify_suffix_array(mf->SA, T, (bool*)mf->salink, n); + + /* Compute ISA (Inverse Suffix Array) in a preliminary position. + * + * This is just a trick to save memory. Since LCP is unneeded after + * this function, it can be computed in any available space. The + * storage for the ISA is the best choice because the ISA can be built + * quickly in salink for now, then re-built in its real location at the + * end. This is probably worth it because computing the ISA from the SA + * is very fast, and since this match-finder is memory-hungry we'd like + * to save as much memory as possible. */ + ISA = (input_idx_t*)mf->salink; + compute_inverse_suffix_array(ISA, mf->SA, n); + + /* Compute LCP (Longest Common Prefix) array. */ + LCP = mf->SA + n; + compute_lcp_array(LCP, mf->SA, ISA, T, n); + verify_lcp_array(LCP, mf->SA, T, n); + + /* Initialize suffix array links. */ + init_salink(mf->salink, LCP, mf->SA, T, n, mf->max_match_len); + verify_salink(mf->salink, mf->SA, T, n, mf->max_match_len); + + /* Compute ISA (Inverse Suffix Array) in its final position. */ + ISA = mf->SA + n; + compute_inverse_suffix_array(ISA, mf->SA, n); + + /* Save new variables and return. */ + mf->ISA = ISA; mf->cur_pos = 0; mf->window_size = n; } + +/* Free memory allocated for the suffix array match-finder. */ +void +lz_sarray_destroy(struct lz_sarray *mf) +{ + FREE(mf->SA); + FREE(mf->salink); +}