b67bbeb539071ed5dcc6642a5090476b462ab2fb
[wimlib] / src / lz_linked_suffix_array.c
1 /*
2  * lz_linked_suffix_array.c
3  *
4  * Linked suffix array match-finder for Lempel-Ziv compression.
5  *
6  * Copyright (c) 2013, 2014 Eric Biggers.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 #include "wimlib/lz_mf.h"
33 #include "wimlib/lz_suffix_array_utils.h"
34 #include "wimlib/util.h"
35
36 struct salink;
37
38 /* Length type --- must be an unsigned type large enough to hold the maximum
39  * match length.  */
40 typedef u16 lz_lsa_len_t;
41
42 /* Type of distances in suffix array links.  A larger type would allow skipping
43  * irrelevant suffixes more quickly, which is especially helpful towards the
44  * start of the window.  However, even a single byte allows skipping 255 at a
45  * time, which where it matters is already a big improvement over the
46  * alternative of searching the suffixes consecutively.  */
47 typedef u8 lz_lsa_delta_t;
48
49 #define LZ_LSA_LEN_MAX          ((lz_lsa_len_t)~0UL)
50 #define LZ_LSA_POS_MAX          ((u32)~0UL)
51 #define LZ_LSA_DELTA_MAX        ((lz_lsa_delta_t)~0UL)
52
53 /* State of the linked suffix array match-finder.  */
54 struct lz_lsa {
55
56         struct lz_mf base;
57
58         /* Suffix array for the current window.
59          * This is a mapping from suffix rank to suffix position.  */
60         u32 *SA;
61
62         /* Inverse suffix array for the current window.
63          * This is a mapping from suffix position to suffix rank.
64          * If 0 <= r < window_size, then ISA[SA[r]] == r.  */
65         u32 *ISA;
66
67         /* Suffix array links.
68          *
69          * During a linear scan of the input string to find matches, this array
70          * used to keep track of which rank suffixes in the suffix array appear
71          * before the current position.  Instead of searching in the original
72          * suffix array, scans for matches at a given position traverse a linked
73          * list containing (usually) only suffixes that appear before that
74          * position.  */
75         struct salink *salink;
76 };
77
78 /* Suffix array link.  An array of these structures, one per suffix rank, is
79  * used as a replacement for the raw LCP (Longest Common Prefix) array to allow
80  * skipping over suffixes that appear later in the window and hence cannot be
81  * used as LZ77 matches.  */
82 struct salink {
83         union {
84                 /* Temporary fields used while this structure is being
85                  * initialized.
86                  *
87                  * Note: we want the entire `struct salink' to be only 6 bytes,
88                  * even though this makes "next_initial" unaligned.  */
89                 struct {
90                         u32 next_initial;
91                         lz_lsa_len_t lcpnext_initial;
92                 } _packed_attribute;
93
94                 struct {
95                         /* Intially, the length, in bytes, of the longest common
96                          * prefix (LCP) between the suffix having this rank and
97                          * the suffix with the smallest larger rank that
98                          * starts earlier in the window than the suffix having
99                          * this rank.  If no such suffix exists, this will be 0.
100                          *
101                          * Later, during match-finding, after the corresponding
102                          * suffix has entered the LZ77 dictionary, this value
103                          * may be updated by lz_lsa_update_salink() to refer
104                          * instead to a lexicographically closer (but still
105                          * larger) suffix that begins at a later position that
106                          * has entered the LZ77 dictionary.  */
107                         lz_lsa_len_t   lcpnext;
108
109                         /* Initially, the length, in bytes, of the longest
110                          * common prefix (LCP) between the suffix having this
111                          * rank and the suffix with the largest smaller rank
112                          * that starts earlier in the window than the suffix
113                          * having this rank.  If no such suffix exists, this
114                          * will be 0.
115                          *
116                          * Later, during match-finding, after the corresponding
117                          * suffix has entered the LZ77 dictionary, this value
118                          * may be updated by lz_lsa_update_salink() to refer
119                          * instead to a lexicographically closer (but still
120                          * smaller) suffix that begins at a later position that
121                          * has entered the LZ77 dictionary.  */
122                         lz_lsa_len_t   lcpprev;
123
124                         /* Distance to the suffix referred to in the description
125                          * of "lcpnext" above, but capped to a maximum value to
126                          * save memory; or, 0 if no such suffix exists.  If the
127                          * true distance was truncated, this will give the
128                          * distance to the rank of a suffix that is
129                          * lexicographically closer to the current suffix than
130                          * the desired suffix, but appears *later* in the window
131                          * and hence cannot be used as the basis for an LZ77
132                          * match.  */
133                         lz_lsa_delta_t dist_to_next;
134
135                         /* Distance to the suffix referred to in the description
136                          * of "lcpprev" above, but capped to a maximum value to
137                          * save memory; or, 0 if no such suffix exists.  If the
138                          * true distance was truncated, this will give the
139                          * distance to the rank of a suffix that is
140                          * lexicographically closer to the current suffix than
141                          * the desired suffix, but appears *later* in the window
142                          * and hence cannot be used as the basis for an LZ77
143                          * match.  */
144                         lz_lsa_delta_t dist_to_prev;
145                 };
146         };
147 };
148
149 /* Initialize the SA link array in linear time.
150  *
151  * This is similar to computing the LPF (Longest Previous Factor) array, which
152  * is addressed in several papers.  In particular the algorithms below are based
153  * on Crochemore et al. 2009: "LPF computation revisited".  However, this
154  * match-finder does not actually compute or use the LPF array per se.  Rather,
155  * this function sets up some information necessary to compute the LPF array,
156  * but later lz_lsa_get_matches() actually uses this information to search
157  * the suffix array directly and can keep searching beyond the first (longest)
158  * match whose length would be placed in the LPF array.  This difference from
159  * the theoretical work is necessary because in many real compression formats
160  * matches take variable numbers of bits to encode, so a decent parser needs to
161  * consider more than just the longest match with unspecified offset.
162  *
163  * Note: We cap the lcpprev and lcpnext values to the maximum match length so
164  * that the match-finder need not worry about it later, in the inner loop.
165  *
166  * Note: the LCP array is one of the inputs to this function, but it is used as
167  * temporary space and therefore will be invalidated.
168  */
169 static void
170 init_salink(struct salink link[restrict], u32 LCP[restrict],
171             const u32 SA[restrict], const u8 T[restrict], u32 n,
172             lz_lsa_len_t min_match_len, lz_lsa_len_t max_match_len)
173 {
174         /* Calculate salink.dist_to_next and salink.lcpnext.
175          *
176          * Pass 1 calculates, for each suffix rank, the corresponding
177          * "next_initial" value which is the smallest larger rank that
178          * corresponds to a suffix starting earlier in the string.  It also
179          * calculates "lcpnext_initial", which is the longest common prefix with
180          * that suffix, although to eliminate checks in lz_lsa_get_matches(),
181          * "lcpnext_initial" is set to 0 if it's less than the minimum match
182          * length or set to the maximum match length if it's greater than the
183          * maximum match length.
184          *
185          * Pass 2 translates each absolute "next_initial", a 4-byte value, into
186          * a relative "dist_to_next", a 1-byte value.  This is done to save
187          * memory.  In the case that the exact relative distance cannot be
188          * encoded in 1 byte, it is capped to 255.  This is valid as long as
189          * lz_lsa_get_matches() validates each position before using it.
190          * Note that "lcpnext" need not be updated in this case because it will
191          * not be used until the actual next rank has been found anyway.
192          */
193         link[n - 1].next_initial = LZ_LSA_POS_MAX;
194         link[n - 1].lcpnext_initial = 0;
195         for (u32 r = n - 2; r != LZ_LSA_POS_MAX; r--) {
196                 u32 t = r + 1;
197                 u32 l = LCP[t];
198                 while (t != LZ_LSA_POS_MAX && SA[t] > SA[r]) {
199                         l = min(l, link[t].lcpnext_initial);
200                         t = link[t].next_initial;
201                 }
202                 link[r].next_initial = t;
203
204                 if (l < min_match_len)
205                         l = 0;
206                 else if (l > max_match_len)
207                         l = max_match_len;
208                 link[r].lcpnext_initial = l;
209         }
210         for (u32 r = 0; r < n; r++) {
211                 u32 next;
212                 lz_lsa_len_t l;
213                 lz_lsa_delta_t dist_to_next;
214
215                 next = link[r].next_initial;
216                 l = link[r].lcpnext_initial;
217
218                 if (next == LZ_LSA_POS_MAX)
219                         dist_to_next = 0;
220                 else if (next - r <= LZ_LSA_DELTA_MAX)
221                         dist_to_next = next - r;
222                 else
223                         dist_to_next = LZ_LSA_DELTA_MAX;
224
225                 link[r].lcpnext = l;
226                 link[r].dist_to_next = dist_to_next;
227         }
228
229         /* Calculate salink.dist_to_prev and salink.lcpprev.
230          *
231          * This is analgous to dist_to_next and lcpnext as described above, but
232          * in the other direction.  That is, here we're interested in, for each
233          * rank, the largest smaller rank that corresponds to a suffix starting
234          * earlier in the string.
235          *
236          * To save memory we don't have a "prev_initial" field, but rather store
237          * those values in the LCP array.  */
238         LCP[0] = LZ_LSA_POS_MAX;
239         link[0].lcpprev = 0;
240         for (u32 r = 1; r < n; r++) {
241                 u32 t = r - 1;
242                 u32 l = LCP[r];
243                 while (t != LZ_LSA_POS_MAX && SA[t] > SA[r]) {
244                         l = min(l, link[t].lcpprev);
245                         t = LCP[t];
246                 }
247                 LCP[r] = t;
248
249                 if (l < min_match_len)
250                         l = 0;
251                 else if (l > max_match_len)
252                         l = max_match_len;
253
254                 link[r].lcpprev = l;
255         }
256         for (u32 r = 0; r < n; r++) {
257
258                 u32 prev = LCP[r];
259
260                 if (prev == LZ_LSA_POS_MAX)
261                         link[r].dist_to_prev = 0;
262                 else if (r - prev <= LZ_LSA_DELTA_MAX)
263                         link[r].dist_to_prev = r - prev;
264                 else
265                         link[r].dist_to_prev = LZ_LSA_DELTA_MAX;
266         }
267 }
268
269 /* If ENABLE_LZ_DEBUG is defined, verify the values computed by init_salink().
270  *
271  * WARNING: this is for debug use only as it does not necessarily run in linear
272  * time!!!  */
273 static void
274 verify_salink(const struct salink link[], const u32 SA[], const u8 T[], u32 n,
275               lz_lsa_len_t min_match_len, lz_lsa_len_t max_match_len)
276 {
277 #ifdef ENABLE_LZ_DEBUG
278         for (u32 r = 0; r < n; r++) {
279                 for (u32 prev = r; ; ) {
280                         if (prev == 0) {
281                                 LZ_ASSERT(link[r].dist_to_prev == 0);
282                                 LZ_ASSERT(link[r].lcpprev == 0);
283                                 break;
284                         }
285
286                         prev--;
287
288                         if (SA[prev] < SA[r]) {
289                                 LZ_ASSERT(link[r].dist_to_prev == min(r - prev, LZ_LSA_DELTA_MAX));
290
291                                 u32 lcpprev;
292                                 for (lcpprev = 0;
293                                      lcpprev < min(n - SA[prev], n - SA[r]) &&
294                                              T[SA[prev] + lcpprev] == T[SA[r] + lcpprev];
295                                      lcpprev++)
296                                         ;
297                                 if (lcpprev < min_match_len)
298                                         lcpprev = 0;
299                                 else if (lcpprev > max_match_len)
300                                         lcpprev = max_match_len;
301
302                                 LZ_ASSERT(lcpprev == link[r].lcpprev);
303                                 break;
304                         }
305                 }
306
307                 for (u32 next = r; ; ) {
308                         if (next == n - 1) {
309                                 LZ_ASSERT(link[r].dist_to_next == 0);
310                                 LZ_ASSERT(link[r].lcpnext == 0);
311                                 break;
312                         }
313
314                         next++;
315
316                         if (SA[next] < SA[r]) {
317                                 LZ_ASSERT(link[r].dist_to_next == min(next - r, LZ_LSA_DELTA_MAX));
318
319                                 u32 lcpnext;
320                                 for (lcpnext = 0;
321                                      lcpnext < min(n - SA[next], n - SA[r]) &&
322                                              T[SA[next] + lcpnext] == T[SA[r] + lcpnext];
323                                      lcpnext++)
324                                         ;
325                                 if (lcpnext < min_match_len)
326                                         lcpnext = 0;
327                                 else if (lcpnext > max_match_len)
328                                         lcpnext = max_match_len;
329
330                                 LZ_ASSERT(lcpnext == link[r].lcpnext);
331                                 break;
332                         }
333                 }
334         }
335 #endif
336 }
337
338 static inline void
339 lz_lsa_update_salink(const u32 r, struct salink link[])
340 {
341         const u32 next = r + link[r].dist_to_next;
342         const u32 prev = r - link[r].dist_to_prev;
343
344         if (next != r && link[r].dist_to_next < link[next].dist_to_prev) {
345                 link[next].dist_to_prev = link[r].dist_to_next;
346                 link[next].lcpprev = link[r].lcpnext;
347         }
348
349         if (prev != r && link[r].dist_to_prev < link[prev].dist_to_next) {
350                 link[prev].dist_to_next = link[r].dist_to_prev;
351                 link[prev].lcpnext = link[r].lcpprev;
352         }
353 }
354
355 static void
356 lz_lsa_set_default_params(struct lz_mf_params *params)
357 {
358         if (params->min_match_len == 0)
359                 params->min_match_len = 2;
360
361         if (params->max_match_len == 0)
362                 params->max_match_len = UINT32_MAX;
363
364         if (params->max_match_len > LZ_LSA_LEN_MAX)
365                 params->max_match_len = LZ_LSA_LEN_MAX;
366
367         if (params->max_search_depth == 0)
368                 params->max_search_depth = 32;
369
370         /* Scale max_search_depth down since this algorithm finds the longest
371          * matches first.  */
372         params->max_search_depth = DIV_ROUND_UP(params->max_search_depth, 5);
373 }
374
375 static u64
376 lz_lsa_get_needed_memory(u32 max_window_size)
377 {
378         u64 size = 0;
379
380         /* SA */
381         size += (u64)max_window_size * sizeof(u32);
382
383         /* ISA */
384         size += (u64)max_window_size * sizeof(u32);
385
386         /* salink and minimum temporary space for divsufsort  */
387         size += max(BUILD_SA_MIN_TMP_LEN * sizeof(u32),
388                     (u64)max_window_size * sizeof(struct salink));
389
390         return size;
391 }
392
393 static bool
394 lz_lsa_params_valid(const struct lz_mf_params *params)
395 {
396         return true;
397 }
398
399 static bool
400 lz_lsa_init(struct lz_mf *_mf)
401 {
402         struct lz_lsa *mf = (struct lz_lsa *)_mf;
403         const u32 max_window_size = mf->base.params.max_window_size;
404
405         lz_lsa_set_default_params(&mf->base.params);
406
407         /* SA and ISA will share the same allocation.  */
408         mf->SA = MALLOC(max_window_size * 2 * sizeof(u32));
409         if (!mf->SA)
410                 return false;
411
412         mf->salink = MALLOC(max(BUILD_SA_MIN_TMP_LEN * sizeof(u32),
413                                 max_window_size * sizeof(struct salink)));
414         if (!mf->salink) {
415                 FREE(mf->SA);
416                 return false;
417         }
418
419         return true;
420 }
421
422 static void
423 lz_lsa_load_window(struct lz_mf *_mf, const u8 T[], u32 n)
424 {
425         struct lz_lsa *mf = (struct lz_lsa *)_mf;
426         u32 *ISA, *LCP;
427
428         build_SA(mf->SA, T, n, (u32 *)mf->salink);
429
430         /* Compute ISA (Inverse Suffix Array) in a preliminary position.
431          *
432          * This is just a trick to save memory.  Since LCP is unneeded after
433          * this function, it can be computed in any available space.  The
434          * storage for the ISA is the best choice because the ISA can be built
435          * quickly in salink for now, then re-built in its real location at the
436          * end.  This is probably worth it because computing the ISA from the SA
437          * is very fast, and since this match-finder is memory-hungry we'd like
438          * to save as much memory as possible.  */
439         BUILD_BUG_ON(sizeof(mf->salink[0]) < sizeof(mf->ISA[0]));
440         ISA = (u32 *)mf->salink;
441         build_ISA(ISA, mf->SA, n);
442
443         /* Compute LCP (Longest Common Prefix) array.  */
444         LCP = mf->SA + n;
445         build_LCP(LCP, mf->SA, ISA, T, n);
446
447         /* Initialize suffix array links.  */
448         init_salink(mf->salink, LCP, mf->SA, T, n,
449                     mf->base.params.min_match_len,
450                     mf->base.params.max_match_len);
451         verify_salink(mf->salink, mf->SA, T, n,
452                       mf->base.params.min_match_len,
453                       mf->base.params.max_match_len);
454
455         /* Compute ISA (Inverse Suffix Array) in its final position.  */
456         ISA = mf->SA + n;
457         build_ISA(ISA, mf->SA, n);
458
459         /* Save new variables and return.  */
460         mf->ISA = ISA;
461 }
462
463 static u32
464 lz_lsa_get_matches(struct lz_mf *_mf, struct lz_match matches[])
465 {
466         struct lz_lsa *mf = (struct lz_lsa *)_mf;
467         const u32 i = mf->base.cur_window_pos++;
468
469         const u32 * const restrict SA = mf->SA;
470         const u32 * const restrict ISA = mf->ISA;
471         struct salink * const restrict link = mf->salink;
472
473         /* r = Rank of the suffix at the current position.  */
474         const u32 r = ISA[i];
475
476         /* Prepare for searching the current position.  */
477         lz_lsa_update_salink(r, link);
478
479         /* Prefetch next position in SA and link.
480          *
481          * This can improve performance on large windows since the locations in
482          * SA and link at which each successive search begins are in general
483          * randomly distributed.  */
484         if (likely(i + 1 < mf->base.cur_window_size)) {
485                 const u32 next_r = ISA[i + 1];
486                 prefetch(&SA[next_r]);
487                 prefetch(&link[next_r]);
488         }
489
490         /* L = rank of next suffix to the left;
491          * R = rank of next suffix to the right;
492          * lenL = length of match between current position and the suffix with rank L;
493          * lenR = length of match between current position and the suffix with rank R.
494          *
495          * This is left and right relative to the rank of the current suffix.
496          * Since the suffixes in the suffix array are sorted, the longest
497          * matches are immediately to the left and right (using the linked list
498          * to ignore all suffixes that occur later in the window).  The match
499          * length decreases the farther left and right we go.  We shall keep the
500          * length on both sides in sync in order to choose the lowest-cost match
501          * of each length.
502          */
503         u32 L = r - link[r].dist_to_prev;
504         u32 R = r + link[r].dist_to_next;
505         u32 lenL = link[r].lcpprev;
506         u32 lenR = link[r].lcpnext;
507
508         /* num_matches = number of matches found so far.  */
509         u32 num_matches = 0;
510
511         /* best_offset = offset of lowest-cost match found so far.
512          *
513          * Shorter matches that do not have a lower offset than this are
514          * discarded, since presumably it would be cheaper to output the bytes
515          * from the longer match instead.  */
516         u32 best_offset = LZ_LSA_POS_MAX;
517
518         /* count_remaining = maximum number of possible matches remaining to be
519          * considered.  */
520         u32 count_remaining = mf->base.params.max_search_depth;
521
522         /* pending_offset = offset of lowest-cost match found for the current
523          * length, or 0 if none found yet.  */
524         u32 pending_offset = 0;
525
526         /* Note: some 'goto' statements are used in the remainder of this
527          * function to remove unnecessary checks and create branches that the
528          * CPU may predict better.  (This function is performance critical.)  */
529
530         if (lenL != 0 && lenL >= lenR)
531                 goto extend_left;
532         else if (lenR != 0)
533                 goto extend_right;
534         else
535                 return 0;
536
537 extend_left:
538         /* Search suffixes on the left until the match length has decreased
539          * below the next match length on the right or to below the minimum
540          * match length.  */
541         for (;;) {
542                 u32 offset;
543                 u32 old_L;
544                 u32 old_lenL;
545
546                 /* Check for hard cutoff on amount of work done.  */
547                 if (count_remaining-- == 0) {
548                         if (pending_offset != 0) {
549                                 /* Save pending match.  */
550                                 matches[num_matches++] = (struct lz_match) {
551                                         .len = lenL,
552                                         .offset = pending_offset,
553                                 };
554                         }
555                         goto out;
556                 }
557
558                 if (SA[L] < i) {
559                         /* Suffix is in LZ77 dictionary.  (Check was needed
560                          * because the salink array caps distances to save
561                          * memory.)  */
562
563                         offset = i - SA[L];
564
565                         /* Save match offset if it results in lower cost.  */
566                         if (offset < best_offset) {
567                                 best_offset = offset;
568                                 pending_offset = offset;
569                         }
570                 }
571
572                 /* Advance left to previous suffix.  */
573
574                 old_L = L;
575                 old_lenL = lenL;
576
577                 L -= link[L].dist_to_prev;
578
579                 if (link[old_L].lcpprev < old_lenL) {
580                         /* Match length decreased.  */
581
582                         lenL = link[old_L].lcpprev;
583
584                         if (old_lenL > lenR) {
585                                 /* Neither the right side nor the left size has
586                                  * any more matches of length @old_lenL.  If a
587                                  * pending match exists, save it.  */
588                                 if (pending_offset != 0) {
589                                         matches[num_matches++] = (struct lz_match) {
590                                                 .len = old_lenL,
591                                                 .offset = pending_offset,
592                                         };
593                                         pending_offset = 0;
594                                 }
595
596                                 if (lenL >= lenR) {
597                                         /* New match length on left is still at
598                                          * least as large as the next match
599                                          * length on the right:  Keep extending
600                                          * left, unless the minimum match length
601                                          * would be underrun.  */
602                                         if (lenL == 0)
603                                                 goto out;
604                                         goto extend_left;
605                                 }
606                         }
607
608                         /* Here we have lenL < lenR.  Extend right.
609                          * (No check for whether the minimum match length has
610                          * been underrun is needed, provided that such lengths
611                          * are marked as 0.)  */
612                         goto extend_right;
613                 }
614         }
615
616 extend_right:
617         /* Search suffixes on the right until the match length has decreased to
618          * the next match length on the left or to below the minimum match
619          * length.  */
620         for (;;) {
621                 u32 offset;
622                 u32 old_R;
623                 u32 old_lenR;
624
625                 /* Check for hard cutoff on amount of work done.  */
626                 if (count_remaining-- == 0) {
627                         if (pending_offset != 0) {
628                                 /* Save pending match.  */
629                                 matches[num_matches++] = (struct lz_match) {
630                                         .len = lenR,
631                                         .offset = pending_offset,
632                                 };
633                         }
634                         goto out;
635                 }
636
637                 if (SA[R] < i) {
638                         /* Suffix is in LZ77 dictionary.  (Check was needed
639                          * because the salink array caps distances to save
640                          * memory.)  */
641
642                         offset = i - SA[R];
643
644                         if (offset < best_offset) {
645                                 best_offset = offset;
646                                 pending_offset = offset;
647                         }
648                 }
649
650                 /* Advance right to next suffix.  */
651
652                 old_R = R;
653                 old_lenR = lenR;
654
655                 R += link[R].dist_to_next;
656
657                 if (link[old_R].lcpnext < lenR) {
658                         /* Match length decreased.  */
659
660                         lenR = link[old_R].lcpnext;
661
662                         /* Neither the right side nor the left size has any more
663                          * matches of length @old_lenR.  If a pending match
664                          * exists, save it.  */
665                         if (pending_offset != 0) {
666                                 matches[num_matches++] = (struct lz_match) {
667                                         .len = old_lenR,
668                                         .offset = pending_offset,
669                                 };
670                                 pending_offset = 0;
671                         }
672
673                         if (lenL >= lenR) {
674                                 /* lenL >= lenR:  Extend left, unless the
675                                  * minimum match length would be underrun, in
676                                  * which case we are done.  */
677                                 if (lenL == 0)
678                                         goto out;
679
680                                 goto extend_left;
681                         }
682                         /* lenR > lenL:  Keep extending right.
683                          * (No check for whether the minimum match length has
684                          * been underrun is needed, provided that such lengths
685                          * are marked as 0.)  */
686                 }
687         }
688
689 out:
690         for (u32 i = 0; i < num_matches / 2; i++)
691                 swap(matches[i], matches[num_matches - 1 - i]);
692         return num_matches;
693 }
694
695 static void
696 lz_lsa_skip_positions(struct lz_mf *_mf, u32 n)
697 {
698         struct lz_lsa *mf = (struct lz_lsa *)_mf;
699         do {
700                 lz_lsa_update_salink(mf->ISA[mf->base.cur_window_pos++], mf->salink);
701         } while (--n);
702 }
703
704 static void
705 lz_lsa_destroy(struct lz_mf *_mf)
706 {
707         struct lz_lsa *mf = (struct lz_lsa *)_mf;
708
709         FREE(mf->SA);
710         FREE(mf->salink);
711 }
712
713 const struct lz_mf_ops lz_linked_suffix_array_ops = {
714         .params_valid      = lz_lsa_params_valid,
715         .get_needed_memory = lz_lsa_get_needed_memory,
716         .init              = lz_lsa_init,
717         .load_window       = lz_lsa_load_window,
718         .get_matches       = lz_lsa_get_matches,
719         .skip_positions    = lz_lsa_skip_positions,
720         .destroy           = lz_lsa_destroy,
721         .struct_size       = sizeof(struct lz_lsa),
722 };