Split prefetch() into prefetchr() and prefetchw()
[wimlib] / src / lcpit_matchfinder.c
1 /*
2  * lcpit_matchfinder.c
3  *
4  * A match-finder for Lempel-Ziv compression based on bottom-up construction and
5  * traversal of the Longest Common Prefix (LCP) interval tree.
6  *
7  * Author:      Eric Biggers
8  * Year:        2014, 2015
9  *
10  * The author dedicates this file to the public domain.
11  * You can do whatever you want with this file.
12  */
13
14 #ifdef HAVE_CONFIG_H
15 #  include "config.h"
16 #endif
17
18 #include <limits.h>
19
20 #include "wimlib/divsufsort.h"
21 #include "wimlib/lcpit_matchfinder.h"
22 #include "wimlib/util.h"
23
24 #define LCP_BITS                6
25 #define LCP_MAX                 (((u32)1 << LCP_BITS) - 1)
26 #define LCP_SHIFT               (32 - LCP_BITS)
27 #define LCP_MASK                (LCP_MAX << LCP_SHIFT)
28 #define POS_MASK                (((u32)1 << (32 - LCP_BITS)) - 1)
29 #define MAX_NORMAL_BUFSIZE      (POS_MASK + 1)
30
31 #define HUGE_LCP_BITS           7
32 #define HUGE_LCP_MAX            (((u32)1 << HUGE_LCP_BITS) - 1)
33 #define HUGE_LCP_SHIFT          (64 - HUGE_LCP_BITS)
34 #define HUGE_LCP_MASK           ((u64)HUGE_LCP_MAX << HUGE_LCP_SHIFT)
35 #define HUGE_POS_MASK           0xFFFFFFFF
36 #define MAX_HUGE_BUFSIZE        ((u64)HUGE_POS_MASK + 1)
37 #define HUGE_UNVISITED_TAG      0x100000000
38
39 #define PREFETCH_SAFETY         5
40
41 /*
42  * Build the LCP (Longest Common Prefix) array in linear time.
43  *
44  * LCP[r] will be the length of the longest common prefix between the suffixes
45  * with positions SA[r - 1] and SA[r].  LCP[0] will be undefined.
46  *
47  * Algorithm taken from Kasai et al. (2001), but modified slightly:
48  *
49  *  - With bytes there is no realistic way to reserve a unique symbol for
50  *    end-of-buffer, so use explicit checks for end-of-buffer.
51  *
52  *  - For decreased memory usage and improved memory locality, pack the two
53  *    logically distinct SA and LCP arrays into a single array SA_and_LCP.
54  *
55  *  - Since SA_and_LCP is accessed randomly, improve the cache behavior by
56  *    reading several entries ahead in ISA and prefetching the upcoming
57  *    SA_and_LCP entry.
58  *
59  *  - If an LCP value is less than the minimum match length, then store 0.  This
60  *    avoids having to do comparisons against the minimum match length later.
61  *
62  *  - If an LCP value is greater than the "nice match length", then store the
63  *    "nice match length".  This caps the number of bits needed to store each
64  *    LCP value, and this caps the depth of the LCP-interval tree, without
65  *    usually hurting the compression ratio too much.
66  *
67  * References:
68  *
69  *      Kasai et al.  2001.  Linear-Time Longest-Common-Prefix Computation in
70  *      Suffix Arrays and Its Applications.  CPM '01 Proceedings of the 12th
71  *      Annual Symposium on Combinatorial Pattern Matching pp. 181-192.
72  */
73 static void
74 build_LCP(u32 SA_and_LCP[restrict], const u32 ISA[restrict],
75           const u8 T[restrict], const u32 n,
76           const u32 min_lcp, const u32 max_lcp)
77 {
78         u32 h = 0;
79         for (u32 i = 0; i < n; i++) {
80                 const u32 r = ISA[i];
81                 prefetchw(&SA_and_LCP[ISA[i + PREFETCH_SAFETY]]);
82                 if (r > 0) {
83                         const u32 j = SA_and_LCP[r - 1] & POS_MASK;
84                         const u32 lim = min(n - i, n - j);
85                         while (h < lim && T[i + h] == T[j + h])
86                                 h++;
87                         u32 stored_lcp = h;
88                         if (stored_lcp < min_lcp)
89                                 stored_lcp = 0;
90                         else if (stored_lcp > max_lcp)
91                                 stored_lcp = max_lcp;
92                         SA_and_LCP[r] |= stored_lcp << LCP_SHIFT;
93                         if (h > 0)
94                                 h--;
95                 }
96         }
97 }
98
99 /*
100  * Use the suffix array accompanied with the longest-common-prefix array ---
101  * which in combination can be called the "enhanced suffix array" --- to
102  * simulate a bottom-up traversal of the corresponding suffix tree, or
103  * equivalently the lcp-interval tree.  Do so in suffix rank order, but save the
104  * superinterval references needed for later bottom-up traversal of the tree in
105  * suffix position order.
106  *
107  * To enumerate the lcp-intervals, this algorithm scans the suffix array and its
108  * corresponding LCP array linearly.  While doing so, it maintains a stack of
109  * lcp-intervals that are currently open, meaning that their left boundaries
110  * have been seen but their right boundaries have not.  The bottom of the stack
111  * is the interval which covers the entire suffix array (this has lcp=0), and
112  * the top of the stack is the deepest interval that is currently open (this has
113  * the greatest lcp of any interval on the stack).  When this algorithm opens an
114  * lcp-interval, it assigns it a unique index in intervals[] and pushes it onto
115  * the stack.  When this algorithm closes an interval, it pops it from the stack
116  * and sets the intervals[] entry of that interval to the index and lcp of that
117  * interval's superinterval, which is the new top of the stack.
118  *
119  * This algorithm also set pos_data[pos] for each suffix position 'pos' to the
120  * index and lcp of the deepest lcp-interval containing it.  Alternatively, we
121  * can interpret each suffix as being associated with a singleton lcp-interval,
122  * or leaf of the suffix tree.  With this interpretation, an entry in pos_data[]
123  * is the superinterval reference for one of these singleton lcp-intervals and
124  * therefore is not fundamentally different from an entry in intervals[].
125  *
126  * To reduce memory usage, this algorithm re-uses the suffix array's memory to
127  * store the generated intervals[] array.  This is possible because SA and LCP
128  * are accessed linearly, and no more than one interval is generated per suffix.
129  *
130  * The techniques used in this algorithm are described in various published
131  * papers.  The generation of lcp-intervals from the suffix array (SA) and the
132  * longest-common-prefix array (LCP) is given as Algorithm BottomUpTraverse in
133  * Kasai et al. (2001) and Algorithm 4.1 ("Computation of lcp-intervals") in
134  * Abouelhoda et al. (2004).  Both these papers note the equivalence between
135  * lcp-intervals (including the singleton lcp-interval for each suffix) and
136  * nodes of the suffix tree.  Abouelhoda et al. (2004) furthermore applies
137  * bottom-up traversal of the lcp-interval tree to Lempel-Ziv factorization, as
138  * does Chen at al. (2008).  Algorithm CPS1b of Chen et al. (2008) dynamically
139  * re-uses the suffix array during bottom-up traversal of the lcp-interval tree.
140  *
141  * References:
142  *
143  *      Kasai et al. Linear-Time Longest-Common-Prefix Computation in Suffix
144  *      Arrays and Its Applications.  2001.  CPM '01 Proceedings of the 12th
145  *      Annual Symposium on Combinatorial Pattern Matching pp. 181-192.
146  *
147  *      M.I. Abouelhoda, S. Kurtz, E. Ohlebusch.  2004.  Replacing Suffix Trees
148  *      With Enhanced Suffix Arrays.  Journal of Discrete Algorithms Volume 2
149  *      Issue 1, March 2004, pp. 53-86.
150  *
151  *      G. Chen, S.J. Puglisi, W.F. Smyth.  2008.  Lempel-Ziv Factorization
152  *      Using Less Time & Space.  Mathematics in Computer Science June 2008,
153  *      Volume 1, Issue 4, pp. 605-623.
154  */
155 static void
156 build_LCPIT(u32 intervals[restrict], u32 pos_data[restrict], const u32 n)
157 {
158         u32 * const SA_and_LCP = intervals;
159         u32 next_interval_idx;
160         u32 open_intervals[LCP_MAX + 1];
161         u32 *top = open_intervals;
162         u32 prev_pos = SA_and_LCP[0] & POS_MASK;
163
164         *top = 0;
165         intervals[0] = 0;
166         next_interval_idx = 1;
167
168         for (u32 r = 1; r < n; r++) {
169                 const u32 next_pos = SA_and_LCP[r] & POS_MASK;
170                 const u32 next_lcp = SA_and_LCP[r] & LCP_MASK;
171                 const u32 top_lcp = *top & LCP_MASK;
172
173                 prefetchw(&pos_data[SA_and_LCP[r + PREFETCH_SAFETY] & POS_MASK]);
174
175                 if (next_lcp == top_lcp) {
176                         /* Continuing the deepest open interval  */
177                         pos_data[prev_pos] = *top;
178                 } else if (next_lcp > top_lcp) {
179                         /* Opening a new interval  */
180                         *++top = next_lcp | next_interval_idx++;
181                         pos_data[prev_pos] = *top;
182                 } else {
183                         /* Closing the deepest open interval  */
184                         pos_data[prev_pos] = *top;
185                         for (;;) {
186                                 const u32 closed_interval_idx = *top-- & POS_MASK;
187                                 const u32 superinterval_lcp = *top & LCP_MASK;
188
189                                 if (next_lcp == superinterval_lcp) {
190                                         /* Continuing the superinterval */
191                                         intervals[closed_interval_idx] = *top;
192                                         break;
193                                 } else if (next_lcp > superinterval_lcp) {
194                                         /* Creating a new interval that is a
195                                          * superinterval of the one being
196                                          * closed, but still a subinterval of
197                                          * its superinterval  */
198                                         *++top = next_lcp | next_interval_idx++;
199                                         intervals[closed_interval_idx] = *top;
200                                         break;
201                                 } else {
202                                         /* Also closing the superinterval  */
203                                         intervals[closed_interval_idx] = *top;
204                                 }
205                         }
206                 }
207                 prev_pos = next_pos;
208         }
209
210         /* Close any still-open intervals.  */
211         pos_data[prev_pos] = *top;
212         for (; top > open_intervals; top--)
213                 intervals[*top & POS_MASK] = *(top - 1);
214 }
215
216 /*
217  * Advance the LCP-interval tree matchfinder by one byte.
218  *
219  * If @record_matches is true, then matches are written to the @matches array
220  * sorted by strictly decreasing length and strictly decreasing offset, and the
221  * return value is the number of matches found.  Otherwise, @matches is ignored
222  * and the return value is always 0.
223  *
224  * How this algorithm works:
225  *
226  * 'cur_pos' is the position of the current suffix, which is the suffix being
227  * matched against.  'cur_pos' starts at 0 and is incremented each time this
228  * function is called.  This function finds each suffix with position less than
229  * 'cur_pos' that shares a prefix with the current suffix, but for each distinct
230  * prefix length it finds only the suffix with the greatest position (i.e. the
231  * most recently seen in the linear traversal by position).  This function
232  * accomplishes this using the lcp-interval tree data structure that was built
233  * by build_LCPIT() and is updated dynamically by this function.
234  *
235  * The first step is to read 'pos_data[cur_pos]', which gives the index and lcp
236  * value of the deepest lcp-interval containing the current suffix --- or,
237  * equivalently, the parent of the conceptual singleton lcp-interval that
238  * contains the current suffix.
239  *
240  * The second step is to ascend the lcp-interval tree until reaching an interval
241  * that has not yet been visited, and link the intervals to the current suffix
242  * along the way.   An lcp-interval has been visited if and only if it has been
243  * linked to a suffix.  Initially, no lcp-intervals are linked to suffixes.
244  *
245  * The third step is to continue ascending the lcp-interval tree, but indirectly
246  * through suffix links rather than through the original superinterval
247  * references, and continuing to form links with the current suffix along the
248  * way.  Each suffix visited during this step, except in a special case to
249  * handle outdated suffixes, is a match which can be written to matches[].  Each
250  * intervals[] entry contains the position of the next suffix to visit, which we
251  * shall call 'match_pos'; this is the most recently seen suffix that belongs to
252  * that lcp-interval.  'pos_data[match_pos]' then contains the lcp and interval
253  * index of the next lcp-interval that should be visited.
254  *
255  * We can view these arrays as describing a new set of links that gets overlaid
256  * on top of the original superinterval references of the lcp-interval tree.
257  * Each such link can connect a node of the lcp-interval tree to an ancestor
258  * more than one generation removed.
259  *
260  * For each one-byte advance, the current position becomes the most recently
261  * seen suffix for a continuous sequence of lcp-intervals from a leaf interval
262  * to the root interval.  Conceptually, this algorithm needs to update all these
263  * nodes to link to 'cur_pos', and then update 'pos_data[cur_pos]' to a "null"
264  * link.  But actually, if some of these nodes have the same most recently seen
265  * suffix, then this algorithm just visits the pos_data[] entry for that suffix
266  * and skips over all these nodes in one step.  Updating the extra nodes is
267  * accomplished by creating a redirection from the previous suffix to the
268  * current suffix.
269  *
270  * Using this shortcutting scheme, it's possible for a suffix to become out of
271  * date, which means that it is no longer the most recently seen suffix for the
272  * lcp-interval under consideration.  This case is detected by noticing when the
273  * next lcp-interval link actually points deeper in the tree, and it is worked
274  * around by just continuing until we get to a link that actually takes us
275  * higher in the tree.  This can be described as a lazy-update scheme.
276  */
277 static inline u32
278 lcpit_advance_one_byte(const u32 cur_pos,
279                        u32 pos_data[restrict],
280                        u32 intervals[restrict],
281                        struct lz_match matches[restrict],
282                        const bool record_matches)
283 {
284         u32 ref;
285         u32 super_ref;
286         u32 match_pos;
287         struct lz_match *matchptr;
288
289         /* Get the deepest lcp-interval containing the current suffix. */
290         ref = pos_data[cur_pos];
291
292         /* Prefetch the deepest lcp-interval containing the *next* suffix. */
293         prefetchw(&intervals[pos_data[cur_pos + 1] & POS_MASK]);
294
295         /* There is no "next suffix" after the current one.  */
296         pos_data[cur_pos] = 0;
297
298         /* Ascend until we reach a visited interval, the root, or a child of the
299          * root.  Link unvisited intervals to the current suffix as we go.  */
300         while ((super_ref = intervals[ref & POS_MASK]) & LCP_MASK) {
301                 intervals[ref & POS_MASK] = cur_pos;
302                 ref = super_ref;
303         }
304
305         if (super_ref == 0) {
306                 /* In this case, the current interval may be any of:
307                  * (1) the root;
308                  * (2) an unvisited child of the root;
309                  * (3) an interval last visited by suffix 0
310                  *
311                  * We could avoid the ambiguity with (3) by using an lcp
312                  * placeholder value other than 0 to represent "visited", but
313                  * it's fastest to use 0.  So we just don't allow matches with
314                  * position 0.  */
315
316                 if (ref != 0)  /* Not the root?  */
317                         intervals[ref & POS_MASK] = cur_pos;
318                 return 0;
319         }
320
321         /* Ascend indirectly via pos_data[] links.  */
322         match_pos = super_ref;
323         matchptr = matches;
324         for (;;) {
325                 while ((super_ref = pos_data[match_pos]) > ref)
326                         match_pos = intervals[super_ref & POS_MASK];
327                 intervals[ref & POS_MASK] = cur_pos;
328                 pos_data[match_pos] = ref;
329                 if (record_matches) {
330                         matchptr->length = ref >> LCP_SHIFT;
331                         matchptr->offset = cur_pos - match_pos;
332                         matchptr++;
333                 }
334                 if (super_ref == 0)
335                         break;
336                 ref = super_ref;
337                 match_pos = intervals[ref & POS_MASK];
338         }
339         return matchptr - matches;
340 }
341
342 /* Expand SA from 32 bits to 64 bits.  */
343 static void
344 expand_SA(void *p, u32 n)
345 {
346         typedef u32 _may_alias_attribute aliased_u32_t;
347         typedef u64 _may_alias_attribute aliased_u64_t;
348
349         aliased_u32_t *SA = p;
350         aliased_u64_t *SA64 = p;
351
352         u32 r = n - 1;
353         do {
354                 SA64[r] = SA[r];
355         } while (r--);
356 }
357
358 /* Like build_LCP(), but for buffers larger than MAX_NORMAL_BUFSIZE.  */
359 static void
360 build_LCP_huge(u64 SA_and_LCP64[restrict], const u32 ISA[restrict],
361                const u8 T[restrict], const u32 n,
362                const u32 min_lcp, const u32 max_lcp)
363 {
364         u32 h = 0;
365         for (u32 i = 0; i < n; i++) {
366                 const u32 r = ISA[i];
367                 prefetchw(&SA_and_LCP64[ISA[i + PREFETCH_SAFETY]]);
368                 if (r > 0) {
369                         const u32 j = SA_and_LCP64[r - 1] & HUGE_POS_MASK;
370                         const u32 lim = min(n - i, n - j);
371                         while (h < lim && T[i + h] == T[j + h])
372                                 h++;
373                         u32 stored_lcp = h;
374                         if (stored_lcp < min_lcp)
375                                 stored_lcp = 0;
376                         else if (stored_lcp > max_lcp)
377                                 stored_lcp = max_lcp;
378                         SA_and_LCP64[r] |= (u64)stored_lcp << HUGE_LCP_SHIFT;
379                         if (h > 0)
380                                 h--;
381                 }
382         }
383 }
384
385 /*
386  * Like build_LCPIT(), but for buffers larger than MAX_NORMAL_BUFSIZE.
387  *
388  * This "huge" version is also slightly different in that the lcp value stored
389  * in each intervals[] entry is the lcp value for that interval, not its
390  * superinterval.  This lcp value stays put in intervals[] and doesn't get moved
391  * to pos_data[] during lcpit_advance_one_byte_huge().  One consequence of this
392  * is that we have to use a special flag to distinguish visited from unvisited
393  * intervals.  But overall, this scheme keeps the memory usage at 12n instead of
394  * 16n.  (The non-huge version is 8n.)
395  */
396 static void
397 build_LCPIT_huge(u64 intervals64[restrict], u32 pos_data[restrict], const u32 n)
398 {
399         u64 * const SA_and_LCP64 = intervals64;
400         u32 next_interval_idx;
401         u32 open_intervals[HUGE_LCP_MAX + 1];
402         u32 *top = open_intervals;
403         u32 prev_pos = SA_and_LCP64[0] & HUGE_POS_MASK;
404
405         *top = 0;
406         intervals64[0] = 0;
407         next_interval_idx = 1;
408
409         for (u32 r = 1; r < n; r++) {
410                 const u32 next_pos = SA_and_LCP64[r] & HUGE_POS_MASK;
411                 const u64 next_lcp = SA_and_LCP64[r] & HUGE_LCP_MASK;
412                 const u64 top_lcp = intervals64[*top];
413
414                 prefetchw(&pos_data[SA_and_LCP64[r + PREFETCH_SAFETY] & HUGE_POS_MASK]);
415
416                 if (next_lcp == top_lcp) {
417                         /* Continuing the deepest open interval  */
418                         pos_data[prev_pos] = *top;
419                 } else if (next_lcp > top_lcp) {
420                         /* Opening a new interval  */
421                         intervals64[next_interval_idx] = next_lcp;
422                         pos_data[prev_pos] = next_interval_idx;
423                         *++top = next_interval_idx++;
424                 } else {
425                         /* Closing the deepest open interval  */
426                         pos_data[prev_pos] = *top;
427                         for (;;) {
428                                 const u32 closed_interval_idx = *top--;
429                                 const u64 superinterval_lcp = intervals64[*top];
430
431                                 if (next_lcp == superinterval_lcp) {
432                                         /* Continuing the superinterval */
433                                         intervals64[closed_interval_idx] |=
434                                                 HUGE_UNVISITED_TAG | *top;
435                                         break;
436                                 } else if (next_lcp > superinterval_lcp) {
437                                         /* Creating a new interval that is a
438                                          * superinterval of the one being
439                                          * closed, but still a subinterval of
440                                          * its superinterval  */
441                                         intervals64[next_interval_idx] = next_lcp;
442                                         intervals64[closed_interval_idx] |=
443                                                 HUGE_UNVISITED_TAG | next_interval_idx;
444                                         *++top = next_interval_idx++;
445                                         break;
446                                 } else {
447                                         /* Also closing the superinterval  */
448                                         intervals64[closed_interval_idx] |=
449                                                 HUGE_UNVISITED_TAG | *top;
450                                 }
451                         }
452                 }
453                 prev_pos = next_pos;
454         }
455
456         /* Close any still-open intervals.  */
457         pos_data[prev_pos] = *top;
458         for (; top > open_intervals; top--)
459                 intervals64[*top] |= HUGE_UNVISITED_TAG | *(top - 1);
460 }
461
462 /* Like lcpit_advance_one_byte(), but for buffers larger than
463  * MAX_NORMAL_BUFSIZE.  */
464 static inline u32
465 lcpit_advance_one_byte_huge(const u32 cur_pos,
466                             u32 pos_data[restrict],
467                             u64 intervals64[restrict],
468                             struct lz_match matches[restrict],
469                             const bool record_matches)
470 {
471         u32 interval_idx;
472         u32 next_interval_idx;
473         u64 cur;
474         u64 next;
475         u32 match_pos;
476         struct lz_match *matchptr;
477
478         interval_idx = pos_data[cur_pos];
479         prefetchw(&pos_data[intervals64[pos_data[cur_pos + 1]] & HUGE_POS_MASK]);
480         prefetchw(&intervals64[pos_data[cur_pos + 2]]);
481         pos_data[cur_pos] = 0;
482
483         while ((next = intervals64[interval_idx]) & HUGE_UNVISITED_TAG) {
484                 intervals64[interval_idx] = (next & HUGE_LCP_MASK) | cur_pos;
485                 interval_idx = next & HUGE_POS_MASK;
486         }
487
488         matchptr = matches;
489         while (next & HUGE_LCP_MASK) {
490                 cur = next;
491                 do {
492                         match_pos = next & HUGE_POS_MASK;
493                         next_interval_idx = pos_data[match_pos];
494                         next = intervals64[next_interval_idx];
495                 } while (next > cur);
496                 intervals64[interval_idx] = (cur & HUGE_LCP_MASK) | cur_pos;
497                 pos_data[match_pos] = interval_idx;
498                 if (record_matches) {
499                         matchptr->length = cur >> HUGE_LCP_SHIFT;
500                         matchptr->offset = cur_pos - match_pos;
501                         matchptr++;
502                 }
503                 interval_idx = next_interval_idx;
504         }
505         return matchptr - matches;
506 }
507
508 static inline u64
509 get_pos_data_size(size_t max_bufsize)
510 {
511         return (u64)max((u64)max_bufsize + PREFETCH_SAFETY,
512                         DIVSUFSORT_TMP_LEN) * sizeof(u32);
513 }
514
515 static inline u64
516 get_intervals_size(size_t max_bufsize)
517 {
518         return ((u64)max_bufsize + PREFETCH_SAFETY) *
519                 (max_bufsize <= MAX_NORMAL_BUFSIZE ? sizeof(u32) : sizeof(u64));
520 }
521
522 /*
523  * Calculate the number of bytes of memory needed for the LCP-interval tree
524  * matchfinder.
525  *
526  * @max_bufsize - maximum buffer size to support
527  *
528  * Returns the number of bytes required.
529  */
530 u64
531 lcpit_matchfinder_get_needed_memory(size_t max_bufsize)
532 {
533         return get_pos_data_size(max_bufsize) + get_intervals_size(max_bufsize);
534 }
535
536 /*
537  * Initialize the LCP-interval tree matchfinder.
538  *
539  * @mf - the matchfinder structure to initialize
540  * @max_bufsize - maximum buffer size to support
541  * @min_match_len - minimum match length in bytes
542  * @nice_match_len - only consider this many bytes of each match
543  *
544  * Returns true if successfully initialized; false if out of memory.
545  */
546 bool
547 lcpit_matchfinder_init(struct lcpit_matchfinder *mf, size_t max_bufsize,
548                        u32 min_match_len, u32 nice_match_len)
549 {
550         if (lcpit_matchfinder_get_needed_memory(max_bufsize) > SIZE_MAX)
551                 return false;
552         if (max_bufsize > MAX_HUGE_BUFSIZE - PREFETCH_SAFETY)
553                 return false;
554
555         mf->pos_data = MALLOC(get_pos_data_size(max_bufsize));
556         mf->intervals = MALLOC(get_intervals_size(max_bufsize));
557         if (!mf->pos_data || !mf->intervals) {
558                 lcpit_matchfinder_destroy(mf);
559                 return false;
560         }
561
562         mf->min_match_len = min_match_len;
563         mf->nice_match_len = min(nice_match_len,
564                                  (max_bufsize <= MAX_NORMAL_BUFSIZE) ?
565                                  LCP_MAX : HUGE_LCP_MAX);
566         return true;
567 }
568
569 /*
570  * Build the suffix array SA for the specified byte array T of length n.
571  *
572  * The suffix array is a sorted array of the byte array's suffixes, represented
573  * by indices into the byte array.  It can equivalently be viewed as a mapping
574  * from suffix rank to suffix position.
575  *
576  * To build the suffix array, we use libdivsufsort, which uses an
577  * induced-sorting-based algorithm.  In practice, this seems to be the fastest
578  * suffix array construction algorithm currently available.
579  *
580  * References:
581  *
582  *      Y. Mori.  libdivsufsort, a lightweight suffix-sorting library.
583  *      https://code.google.com/p/libdivsufsort/.
584  *
585  *      G. Nong, S. Zhang, and W.H. Chan.  2009.  Linear Suffix Array
586  *      Construction by Almost Pure Induced-Sorting.  Data Compression
587  *      Conference, 2009.  DCC '09.  pp. 193 - 202.
588  *
589  *      S.J. Puglisi, W.F. Smyth, and A. Turpin.  2007.  A Taxonomy of Suffix
590  *      Array Construction Algorithms.  ACM Computing Surveys (CSUR) Volume 39
591  *      Issue 2, 2007 Article No. 4.
592  */
593 static void
594 build_SA(u32 SA[], const u8 T[], u32 n, u32 *tmp)
595 {
596         /* Note: divsufsort() requires a fixed amount of temporary space.  The
597          * implementation of divsufsort() has been modified from the original to
598          * use the provided temporary space instead of allocating its own, since
599          * we don't want to have to deal with malloc() failures here.  */
600         divsufsort(T, SA, n, tmp);
601 }
602
603 /*
604  * Build the inverse suffix array ISA from the suffix array SA.
605  *
606  * Whereas the suffix array is a mapping from suffix rank to suffix position,
607  * the inverse suffix array is a mapping from suffix position to suffix rank.
608  */
609 static void
610 build_ISA(u32 ISA[restrict], const u32 SA[restrict], u32 n)
611 {
612         for (u32 r = 0; r < n; r++)
613                 ISA[SA[r]] = r;
614 }
615
616 /*
617  * Prepare the LCP-interval tree matchfinder for a new input buffer.
618  *
619  * @mf - the initialized matchfinder structure
620  * @T - the input buffer
621  * @n - size of the input buffer in bytes.  This must be nonzero and can be at
622  *      most the max_bufsize with which lcpit_matchfinder_init() was called.
623  */
624 void
625 lcpit_matchfinder_load_buffer(struct lcpit_matchfinder *mf, const u8 *T, u32 n)
626 {
627         /* intervals[] temporarily stores SA and LCP packed together.
628          * pos_data[] temporarily stores ISA.
629          * pos_data[] is also used as the temporary space for divsufsort().  */
630
631         build_SA(mf->intervals, T, n, mf->pos_data);
632         build_ISA(mf->pos_data, mf->intervals, n);
633         if (n <= MAX_NORMAL_BUFSIZE) {
634                 for (u32 i = 0; i < PREFETCH_SAFETY; i++) {
635                         mf->intervals[n + i] = 0;
636                         mf->pos_data[n + i] = 0;
637                 }
638                 build_LCP(mf->intervals, mf->pos_data, T, n,
639                           mf->min_match_len, mf->nice_match_len);
640                 build_LCPIT(mf->intervals, mf->pos_data, n);
641                 mf->huge_mode = false;
642         } else {
643                 for (u32 i = 0; i < PREFETCH_SAFETY; i++) {
644                         mf->intervals64[n + i] = 0;
645                         mf->pos_data[n + i] = 0;
646                 }
647                 expand_SA(mf->intervals, n);
648                 build_LCP_huge(mf->intervals64, mf->pos_data, T, n,
649                                mf->min_match_len, mf->nice_match_len);
650                 build_LCPIT_huge(mf->intervals64, mf->pos_data, n);
651                 mf->huge_mode = true;
652         }
653         mf->cur_pos = 0; /* starting at beginning of input buffer  */
654 }
655
656 /*
657  * Retrieve a list of matches with the next position.
658  *
659  * The matches will be recorded in the @matches array, ordered by strictly
660  * decreasing length and strictly decreasing offset.
661  *
662  * The return value is the number of matches found and written to @matches.
663  * This can be any value in [0, nice_match_len - min_match_len + 1].
664  */
665 u32
666 lcpit_matchfinder_get_matches(struct lcpit_matchfinder *mf,
667                               struct lz_match *matches)
668 {
669         if (mf->huge_mode)
670                 return lcpit_advance_one_byte_huge(mf->cur_pos++, mf->pos_data,
671                                                    mf->intervals64, matches, true);
672         else
673                 return lcpit_advance_one_byte(mf->cur_pos++, mf->pos_data,
674                                               mf->intervals, matches, true);
675 }
676
677 /*
678  * Skip the next @count bytes (don't search for matches at them).  @count is
679  * assumed to be > 0.
680  */
681 void
682 lcpit_matchfinder_skip_bytes(struct lcpit_matchfinder *mf, u32 count)
683 {
684         if (mf->huge_mode) {
685                 do {
686                         lcpit_advance_one_byte_huge(mf->cur_pos++, mf->pos_data,
687                                                     mf->intervals64, NULL, false);
688                 } while (--count);
689         } else {
690                 do {
691                         lcpit_advance_one_byte(mf->cur_pos++, mf->pos_data,
692                                                mf->intervals, NULL, false);
693                 } while (--count);
694         }
695 }
696
697 /*
698  * Destroy an LCP-interval tree matchfinder that was previously initialized with
699  * lcpit_matchfinder_init().
700  */
701 void
702 lcpit_matchfinder_destroy(struct lcpit_matchfinder *mf)
703 {
704         FREE(mf->pos_data);
705         FREE(mf->intervals);
706 }