From: Eric Biggers Date: Fri, 10 Jan 2014 08:02:05 +0000 (-0600) Subject: lz_sarray: Performance and memory usage optimizations X-Git-Tag: v1.6.1~74 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=31274ba5cbf4de73c8a68e7d17f490c3b0df6cff lz_sarray: Performance and memory usage optimizations --- diff --git a/NEWS b/NEWS index e9d946ae..3c4d23f3 100644 --- a/NEWS +++ b/NEWS @@ -10,7 +10,7 @@ Version 1.6.1: Fixed a potential stack overflow when extracting solid archives (packed streams) containing more than about 100000 files. - Memory usage for LZMS and LZX compression has been decreased slightly. + Memory usage for LZMS and LZX compression has been decreased. Version 1.6.0: Support for extracting and updating the new version 3584 WIMs has been diff --git a/include/wimlib/lz_sarray.h b/include/wimlib/lz_sarray.h index 6e06e42b..6f878dd2 100644 --- a/include/wimlib/lz_sarray.h +++ b/include/wimlib/lz_sarray.h @@ -51,8 +51,16 @@ typedef u16 lz_sarray_len_t; /* Cost type, for the user-provided match cost evaluation function. */ typedef lz_sarray_pos_t lz_sarray_cost_t; +/* Type of distances in suffix array links. A larger type would allow skipping + * irrelevant suffixes more quickly, which is especially helpful towards the + * start of the window. However, even a single byte allows skipping 255 at a + * time, which where it matters is already a big improvement over the + * alternative of searching the suffixes consecutively. */ +typedef u8 lz_sarray_delta_t; + #define LZ_SARRAY_LEN_MAX ((lz_sarray_len_t)~0UL) #define LZ_SARRAY_POS_MAX ((lz_sarray_pos_t)~0UL) +#define LZ_SARRAY_DELTA_MAX ((lz_sarray_delta_t)~0UL) #define LZ_SARRAY_INFINITE_COST ((lz_sarray_cost_t)~0UL) /* State of the suffix array LZ (Lempel-Ziv) match-finder. @@ -103,48 +111,80 @@ struct lz_sarray { * used to keep track of which rank suffixes in the suffix array appear * before the current position. Instead of searching in the original * suffix array, scans for matches at a given position traverse a linked - * list containing only suffixes that appear before that position. */ + * list containing (usually) only suffixes that appear before that + * position. */ struct salink *salink; }; -/* Suffix array link; one of these exists for each position in the suffix array. - */ +/* Suffix array link. An array of these structures, one per suffix rank, is + * used as a replacement for the raw LCP (Longest Common Prefix) array to allow + * skipping over suffixes that appear later in the window and hence cannot be + * used as LZ77 matches. */ 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 LZ_SARRAY_POS_MAX 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). */ - lz_sarray_pos_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 LZ_SARRAY_POS_MAX 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). */ - lz_sarray_pos_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 - * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */ - lz_sarray_len_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 - * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */ - lz_sarray_len_t lcpnext; + union { + /* Temporary fields used while this structure is being + * initialized. + * + * Note: we want the entire `struct salink' to be only 6 bytes, + * even though this makes "next_initial" unaligned. */ + struct { + lz_sarray_pos_t next_initial; + lz_sarray_len_t lcpnext_initial; + } _packed_attribute; + + struct { + /* Intially, the length, in bytes, of the longest common + * prefix (LCP) between the suffix having this rank and + * the suffix with the the smallest larger rank that + * starts earlier in the window than the suffix having + * this rank. + * + * Later, during match-finding, after the corresponding + * suffix has entered the LZ77 dictionary, this value + * may be updated by lz_sarray_update_salink() to refer + * instead to a lexicographically closer (but still + * larger) suffix that begins at a later position that + * has entered the LZ77 dictionary. */ + lz_sarray_len_t lcpnext; + + /* Initially, the length, in bytes, of the longest + * common prefix (LCP) between the suffix having this + * rank and the suffix with the the largest smaller rank + * that starts earlier in the window than the suffix + * having this rank. + * + * Later, during match-finding, after the corresponding + * suffix has entered the LZ77 dictionary, this value + * may be updated by lz_sarray_update_salink() to refer + * instead to a lexicographically closer (but still + * smaller) suffix that begins at a later position that + * has entered the LZ77 dictionary. */ + lz_sarray_len_t lcpprev; + + /* Distance to the suffix referred to in the description + * of "lcpnext" above, but capped to a maximum value to + * save memory. If the true distance was truncated, + * this will give the distance to the rank of a suffix + * that is lexicographically closer to the current + * suffix than the desired suffix, but appears *later* + * in the window and hence cannot be used as the basis + * for a LZ77 match. */ + lz_sarray_delta_t dist_to_next; + + /* Distance to the suffix referred to in the description + * of "lcpprev" above, but capped to a maximum value to + * save memory. If the true distance was truncated, + * this will give the distance to the rank of a suffix + * that is lexicographically closer to the current + * suffix than the desired suffix, but appears *later* + * in the window and hence cannot be used as the basis + * for a LZ77 match. */ + lz_sarray_delta_t dist_to_prev; + }; + }; }; + /*-----------------------------------*/ /* Functions defined in lz_sarray.c */ /*-----------------------------------*/ @@ -180,26 +220,16 @@ lz_sarray_get_pos(const struct lz_sarray *mf) static _always_inline_attribute void lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[]) { - /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the - * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none - * exists. */ - const lz_sarray_pos_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 LZ_SARRAY_POS_MAX if none - * exists. */ - const lz_sarray_pos_t prev = link[r].prev; - - /* Link the suffix at the current position into the linked list that - * contains all suffixes referenced by the suffix array that appear at - * or before the current position, sorted by rank. */ - if (next != LZ_SARRAY_POS_MAX) { - link[next].prev = r; + const lz_sarray_pos_t next = r + link[r].dist_to_next; + const lz_sarray_pos_t prev = r - link[r].dist_to_prev; + + if (next != r && link[r].dist_to_next < link[next].dist_to_prev) { + link[next].dist_to_prev = link[r].dist_to_next; link[next].lcpprev = link[r].lcpnext; } - if (prev != LZ_SARRAY_POS_MAX) { - link[prev].next = r; + if (prev != r && link[r].dist_to_prev < link[prev].dist_to_next) { + link[prev].dist_to_next = link[r].dist_to_prev; link[prev].lcpnext = link[r].lcpprev; } } @@ -243,7 +273,6 @@ lz_sarray_get_matches(struct lz_sarray *mf, const lz_sarray_pos_t * const restrict SA = mf->SA; const lz_sarray_pos_t * const restrict ISA = mf->ISA; struct salink * const restrict link = mf->salink; - const lz_sarray_pos_t min_match_len = mf->min_match_len; const u32 max_matches_to_consider = mf->max_matches_to_consider; const u32 max_matches_to_return = mf->max_matches_to_return; @@ -266,8 +295,8 @@ lz_sarray_get_matches(struct lz_sarray *mf, * length on both sides in sync in order to choose the lowest-cost match * of each length. */ - lz_sarray_pos_t L = link[r].prev; - lz_sarray_pos_t R = link[r].next; + lz_sarray_pos_t L = r - link[r].dist_to_prev; + lz_sarray_pos_t R = r + link[r].dist_to_next; lz_sarray_pos_t lenL = link[r].lcpprev; lz_sarray_pos_t lenR = link[r].lcpnext; @@ -276,121 +305,197 @@ 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 longer matches already found. */ + * Shorter matches that do not have a lower cost than this are + * discarded, since presumably it would be cheaper to output the bytes + * from the longer match instead. */ lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST; /* count_remaining = maximum number of possible matches remaining to be * considered. */ u32 count_remaining = max_matches_to_consider; - /* pending = match currently being considered for a specific length. */ - struct raw_match pending; - lz_sarray_cost_t pending_cost; - - while (lenL >= min_match_len || lenR >= min_match_len) - { - pending.len = lenL; - pending_cost = LZ_SARRAY_INFINITE_COST; + /* pending_offset = offset of lowest-cost match found for the current + * length, or 0 if no match has been found yet. */ + lz_sarray_pos_t pending_offset = 0; + + /* Note: some 'goto' statements are used in the remainder of this + * function to remove unnecessary checks and create branches that the + * CPU may predict better. (This function is performance critical.) */ + + if (lenL != 0 && lenL >= lenR) + goto extend_left; + else if (lenR != 0) + goto extend_right; + else + return 0; + +extend_left: + /* Search suffixes on the left until the match length has decreased + * below the next match length on the right or to below the minimum + * match length. */ + for (;;) { + lz_sarray_pos_t offset; lz_sarray_cost_t cost; + lz_sarray_pos_t old_L; + lz_sarray_pos_t old_lenL; + + /* Check for hard cutoff on amount of work done. */ + if (count_remaining-- == 0) { + if (pending_offset != 0) { + /* Save pending match. */ + matches[nmatches++] = (struct raw_match){ + .len = lenL, + .offset = pending_offset, + }; + } + return nmatches; + } + + if (SA[L] < i) { + /* Suffix is in LZ77 dictionary. (Check was needed + * because the salink array caps distances to save + * memory.) */ + + offset = i - SA[L]; + + /* Save match offset if it results in lower cost. */ + cost = (*eval_match_cost)(lenL, offset, + eval_match_cost_ctx); + if (cost < best_cost) { + best_cost = cost; + pending_offset = offset; + } + } + + /* Advance left to next suffix. */ + + old_L = L; + old_lenL = lenL; - /* Extend left. */ - if (lenL >= min_match_len && lenL >= lenR) { - for (;;) { + L -= link[L].dist_to_prev; - if (--count_remaining == 0) - goto out_save_pending; + if (link[old_L].lcpprev < old_lenL) { + /* Match length decreased. */ - lz_sarray_pos_t offset = i - SA[L]; + lenL = link[old_L].lcpprev; - /* Save match if it has smaller cost. */ - cost = (*eval_match_cost)(lenL, offset, - eval_match_cost_ctx); - if (cost < pending_cost) { - pending.offset = offset; - pending_cost = cost; + if (old_lenL > lenR) { + /* Neither the right side nor the left size has + * any more matches of length @old_lenL. If a + * pending match exists, save it. */ + if (pending_offset != 0) { + matches[nmatches++] = (struct raw_match){ + .len = old_lenL, + .offset = pending_offset, + }; + if (nmatches == max_matches_to_return) + return nmatches; + + pending_offset = 0; } - if (link[L].lcpprev < lenL) { - /* Match length decreased. */ - - lenL = link[L].lcpprev; - - /* Save the pending match unless the - * right side still may have matches of - * this length to be scanned, or if a - * previous (longer) match had lower - * cost. */ - if (pending.len > lenR) { - if (pending_cost < best_cost) { - best_cost = pending_cost; - matches[nmatches++] = pending; - if (nmatches == max_matches_to_return) - return nmatches; - } - pending.len = lenL; - pending_cost = LZ_SARRAY_INFINITE_COST; - } - if (lenL < min_match_len || lenL < lenR) - break; + if (lenL >= lenR) { + /* New match length on left is still at + * least as large as the next match + * length on the right: Keep extending + * left, unless the minimum match length + * would be underrun. */ + if (lenL == 0) + return nmatches; + goto extend_left; } - L = link[L].prev; } + + /* Here we have lenL < lenR. Extend right, unless the + * minimum match length would be underrun. */ + if (lenR == 0) + return nmatches; + goto extend_right; } + } - pending.len = lenR; +extend_right: + /* Search suffixes on the right until the match length has decreased to + * the next match length on the left or to below the minimum match + * length. */ + for (;;) { + lz_sarray_pos_t offset; + lz_sarray_cost_t cost; + lz_sarray_pos_t old_R; + lz_sarray_pos_t old_lenR; + + /* Check for hard cutoff on amount of work done. */ + if (count_remaining-- == 0) { + if (pending_offset != 0) { + /* Save pending match. */ + matches[nmatches++] = (struct raw_match){ + .len = lenR, + .offset = pending_offset, + }; + } + return nmatches; + } - /* Extend right. */ - if (lenR >= min_match_len && lenR > lenL) { - for (;;) { + if (SA[R] < i) { + /* Suffix is in LZ77 dictionary. (Check was needed + * because the salink array caps distances to save + * memory.) */ - if (--count_remaining == 0) - goto out_save_pending; + offset = i - SA[R]; - lz_sarray_pos_t offset = i - SA[R]; + /* Save match offset if it results in lower cost. */ + cost = (*eval_match_cost)(lenR, + offset, + eval_match_cost_ctx); + if (cost < best_cost) { + best_cost = cost; + pending_offset = offset; + } + } - /* Save match if it has smaller cost. */ - cost = (*eval_match_cost)(lenR, - offset, - eval_match_cost_ctx); - if (cost < pending_cost) { - pending.offset = offset; - pending_cost = cost; - } + /* Advance right to next suffix. */ - if (link[R].lcpnext < lenR) { - /* Match length decreased. */ + old_R = R; + old_lenR = lenR; - lenR = link[R].lcpnext; + R += link[R].dist_to_next; - /* Save the pending match unless a - * previous (longer) match had lower - * cost. */ - if (pending_cost < best_cost) { - matches[nmatches++] = pending; - best_cost = pending_cost; - if (nmatches == max_matches_to_return) - return nmatches; - } + if (link[old_R].lcpnext < lenR) { + /* Match length decreased. */ - if (lenR < min_match_len || lenR <= lenL) - break; + lenR = link[old_R].lcpnext; - pending.len = lenR; - pending_cost = LZ_SARRAY_INFINITE_COST; - } - R = link[R].next; + /* Neither the right side nor the left size has any more + * matches of length @old_lenR. If a pending match + * exists, save it. */ + if (pending_offset != 0) { + matches[nmatches++] = (struct raw_match){ + .len = old_lenR, + .offset = pending_offset, + }; + if (nmatches == max_matches_to_return) + return nmatches; + + pending_offset = 0; + } + + if (lenR > lenL) { + /* lenR > lenL: Keep extending right, unless + * the minimum match length would be underrun. + */ + if (lenR == 0) + return nmatches; + } else { + /* lenL >= lenR: Extend left, unless the + * minimum match length would be underrun, in + * which case we are done. */ + if (lenL == 0) + return nmatches; + + goto extend_left; } } } - goto out; - -out_save_pending: - if (pending_cost != LZ_SARRAY_INFINITE_COST) - matches[nmatches++] = pending; - -out: - return nmatches; } #endif /* _WIMLIB_LZ_SARRAY_H */ diff --git a/src/lz_sarray.c b/src/lz_sarray.c index 5e0fa7fa..33acd612 100644 --- a/src/lz_sarray.c +++ b/src/lz_sarray.c @@ -40,6 +40,9 @@ #include "divsufsort/divsufsort.h" #include +#define DIVSUFSORT_TMP1_SIZE (256 * sizeof(saidx_t)) +#define DIVSUFSORT_TMP2_SIZE (256 * 256 * sizeof(saidx_t)) + /* If ENABLE_LZ_DEBUG is defined, verify that the suffix array satisfies its * definition. * @@ -180,41 +183,112 @@ verify_lcp_array(lz_sarray_pos_t LCP[restrict], * * 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. + * + * Note: the LCP array is one of the inputs to this function, but it is used as + * temporary space and therefore will be invalidated. */ static void init_salink(struct salink link[restrict], - const lz_sarray_pos_t LCP[restrict], + lz_sarray_pos_t LCP[restrict], const lz_sarray_pos_t SA[restrict], const u8 T[restrict], lz_sarray_pos_t n, + lz_sarray_len_t min_match_len, lz_sarray_len_t max_match_len) { - /* Compute salink.next and salink.lcpnext. */ - link[n - 1].next = LZ_SARRAY_POS_MAX; - link[n - 1].lcpnext = 0; + /* Calculate salink.dist_to_next and salink.lcpnext. + * + * Pass 1 calculates, for each suffix rank, the corresponding + * "next_initial" value which is the smallest larger rank that + * corresponds to a suffix starting earlier in the string. It also + * calculates "lcpnext_initial", which is the number of bytes shared + * with that suffix, although to eliminate checks in + * lz_sarray_get_matches(), "lcpnext_initial" is set to 0 if it's less + * than the minimum match length or set to the maximum match length if + * it's greater than the maximum match length. + * + * Pass 2 translates each absolute "next_initial", a 4-byte value, into + * a relative "dist_to_next", a 1-byte value. This is done to save + * memory. In the case that the true relative distance cannot be + * encoded in 1 byte, it is capped to 255. This is valid as long as + * lz_sarray_get_matches() validates each position before using it. + * Note that "lcpnext" need not be updated in this case because it will + * not be used until the actual next rank has been found anyway. + */ + link[n - 1].next_initial = LZ_SARRAY_POS_MAX; + link[n - 1].lcpnext_initial = 0; for (lz_sarray_pos_t r = n - 2; r != LZ_SARRAY_POS_MAX; r--) { lz_sarray_pos_t t = r + 1; lz_sarray_pos_t l = LCP[t]; while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) { - l = min(l, link[t].lcpnext); - t = link[t].next; + l = min(l, link[t].lcpnext_initial); + t = link[t].next_initial; } - link[r].next = t; - link[r].lcpnext = min(l, max_match_len); + link[r].next_initial = t; + + if (l < min_match_len) + l = 0; + else if (l > max_match_len) + l = max_match_len; + link[r].lcpnext_initial = l; + } + for (lz_sarray_pos_t r = 0; r < n; r++) { + lz_sarray_pos_t next; + lz_sarray_len_t l; + lz_sarray_delta_t dist_to_next; + + next = link[r].next_initial; + l = link[r].lcpnext_initial; + + if (next == LZ_SARRAY_POS_MAX) + dist_to_next = 0; + else if (next - r <= LZ_SARRAY_DELTA_MAX) + dist_to_next = next - r; + else + dist_to_next = LZ_SARRAY_DELTA_MAX; + + link[r].lcpnext = l; + link[r].dist_to_next = dist_to_next; } - /* Compute salink.prev and salink.lcpprev. */ - link[0].prev = LZ_SARRAY_POS_MAX; + /* Calculate salink.dist_to_prev and salink.lcpprev. + * + * This is analgous to dist_to_next and lcpnext as described above, but + * in the other direction. That is, here we're interested in, for each + * rank, the largest smaller rank that corresponds to a suffix starting + * earlier in the string. + * + * To save memory we don't have a "prev_initial" field, but rather store + * those values in the LCP array. + */ + LCP[0] = LZ_SARRAY_POS_MAX; link[0].lcpprev = 0; for (lz_sarray_pos_t r = 1; r < n; r++) { lz_sarray_pos_t t = r - 1; lz_sarray_pos_t l = LCP[r]; while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) { l = min(l, link[t].lcpprev); - t = link[t].prev; + t = LCP[t]; } - link[r].prev = t; - link[r].lcpprev = min(l, max_match_len); + LCP[r] = t; + + if (l < min_match_len) + l = 0; + else if (l > max_match_len) + l = max_match_len; + + link[r].lcpprev = l; + } + for (lz_sarray_pos_t r = 0; r < n; r++) { + + lz_sarray_pos_t prev = LCP[r]; + + if (prev == LZ_SARRAY_POS_MAX) + link[r].dist_to_prev = 0; + else if (r - prev <= LZ_SARRAY_DELTA_MAX) + link[r].dist_to_prev = r - prev; + else + link[r].dist_to_prev = LZ_SARRAY_DELTA_MAX; } } @@ -227,13 +301,14 @@ verify_salink(const struct salink link[], const lz_sarray_pos_t SA[], const u8 T[], lz_sarray_pos_t n, + lz_sarray_len_t min_match_len, lz_sarray_len_t max_match_len) { #ifdef ENABLE_LZ_DEBUG for (lz_sarray_pos_t r = 0; r < n; r++) { for (lz_sarray_pos_t prev = r; ; ) { if (prev == 0) { - LZ_ASSERT(link[r].prev == LZ_SARRAY_POS_MAX); + LZ_ASSERT(link[r].dist_to_prev == 0); LZ_ASSERT(link[r].lcpprev == 0); break; } @@ -241,27 +316,27 @@ verify_salink(const struct salink link[], 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]); - } + LZ_ASSERT(link[r].dist_to_prev == min(r - prev, LZ_SARRAY_DELTA_MAX)); + + lz_sarray_pos_t lcpprev; + for (lcpprev = 0; + lcpprev < min(n - SA[prev], n - SA[r]) && + T[SA[prev] + lcpprev] == T[SA[r] + lcpprev]; + lcpprev++) + ; + if (lcpprev < min_match_len) + lcpprev = 0; + else if (lcpprev > max_match_len) + lcpprev = max_match_len; + + LZ_ASSERT(lcpprev == link[r].lcpprev); break; } } for (lz_sarray_pos_t next = r; ; ) { if (next == n - 1) { - LZ_ASSERT(link[r].next == LZ_SARRAY_POS_MAX); + LZ_ASSERT(link[r].dist_to_next == 0); LZ_ASSERT(link[r].lcpnext == 0); break; } @@ -269,21 +344,20 @@ verify_salink(const struct salink link[], 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]); - - } + LZ_ASSERT(link[r].dist_to_next == min(next - r, LZ_SARRAY_DELTA_MAX)); + + lz_sarray_pos_t lcpnext; + for (lcpnext = 0; + lcpnext < min(n - SA[next], n - SA[r]) && + T[SA[next] + lcpnext] == T[SA[r] + lcpnext]; + lcpnext++) + ; + if (lcpnext < min_match_len) + lcpnext = 0; + else if (lcpnext > max_match_len) + lcpnext = max_match_len; + + LZ_ASSERT(lcpnext == link[r].lcpnext); break; } } @@ -366,14 +440,17 @@ lz_sarray_init(struct lz_sarray *mf, if ((u64)2 * max_window_size * sizeof(mf->SA[0]) != 2 * max_window_size * sizeof(mf->SA[0])) return false; - mf->SA = MALLOC(2 * max_window_size * sizeof(mf->SA[0])); + mf->SA = MALLOC(max_window_size * sizeof(mf->SA[0]) + + max(DIVSUFSORT_TMP1_SIZE, + max_window_size * sizeof(mf->SA[0]))); if (mf->SA == NULL) return false; if ((u64)max_window_size * sizeof(mf->salink[0]) != max_window_size * sizeof(mf->salink[0])) return false; - mf->salink = MALLOC(max_window_size * sizeof(mf->salink[0])); + mf->salink = MALLOC(max(DIVSUFSORT_TMP2_SIZE, + max_window_size * sizeof(mf->salink[0]))); if (mf->salink == NULL) return false; @@ -384,7 +461,7 @@ lz_sarray_init(struct lz_sarray *mf, * Return the number of bytes of memory that lz_sarray_init() would allocate for * the specified maximum window size. * - * This should be (20 * @max_window_size) unless the type definitions have been + * This should be (14 * @max_window_size) unless the type definitions have been * changed. */ u64 @@ -393,10 +470,13 @@ lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size) u64 size = 0; /* SA and ISA: 8 bytes per position */ - size += (u64)max_window_size * 2 * sizeof(((struct lz_sarray*)0)->SA[0]); + size += (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0]) + + max(DIVSUFSORT_TMP1_SIZE, + (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0])); - /* salink: 12 bytes per position */ - size += (u64)max_window_size * sizeof(((struct lz_sarray*)0)->salink[0]); + /* salink: 6 bytes per position */ + size += max(DIVSUFSORT_TMP2_SIZE, + (u64)max_window_size * sizeof(((struct lz_sarray*)0)->salink[0])); return size; } @@ -424,18 +504,14 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n) /* 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. + * one array with 65536 spaces. The implementation of divsufsort() 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(lz_sarray_pos_t) != sizeof(saidx_t)); divsufsort(T, mf->SA, n, (saidx_t*)&mf->SA[n], (saidx_t*)mf->salink); @@ -452,6 +528,7 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n) * 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. */ + BUILD_BUG_ON(sizeof(mf->salink[0]) < sizeof(mf->ISA[0])); ISA = (lz_sarray_pos_t*)mf->salink; compute_inverse_suffix_array(ISA, mf->SA, n); @@ -461,8 +538,10 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_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); + init_salink(mf->salink, LCP, mf->SA, T, n, + mf->min_match_len, mf->max_match_len); + verify_salink(mf->salink, mf->SA, T, n, + mf->min_match_len, mf->max_match_len); /* Compute ISA (Inverse Suffix Array) in its final position. */ ISA = mf->SA + n;