lz_sarray: Performance and memory usage optimizations
authorEric Biggers <ebiggers3@gmail.com>
Fri, 10 Jan 2014 08:02:05 +0000 (02:02 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 10 Jan 2014 08:03:50 +0000 (02:03 -0600)
NEWS
include/wimlib/lz_sarray.h
src/lz_sarray.c

diff --git a/NEWS b/NEWS
index e9d946a..3c4d23f 100644 (file)
--- 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
index 6e06e42..6f878dd 100644 (file)
@@ -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 */
index 5e0fa7f..33acd61 100644 (file)
@@ -40,6 +40,9 @@
 #include "divsufsort/divsufsort.h"
 #include <string.h>
 
+#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;