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