-/*
- * lcpit_matchfinder_templates.h
- *
- * This file is included by lcpit_matchfinder.c.
- *
- * Author: Eric Biggers
- * Year: 2014, 2015
- *
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
- */
-
-/*
- * In normal mode, we can pack a buffer position and a LCP value into a 32-bit
- * number. In huge mode, we can't.
- */
-#if HUGE_MODE
-# define GET_SA_ENTRY(r) (SA[r])
-# define GET_LCP_ENTRY(r) (LCP[r])
-# define SET_LCP_ENTRY(r, val) (LCP[r] = (val))
-# define UNVISITED_TAG HUGE_UNVISITED_TAG
-#else
-# define GET_SA_ENTRY(r) (SA_and_LCP[r] & SA_and_LCP_POS_MASK)
-# define GET_LCP_ENTRY(r) (SA_and_LCP[r] >> SA_and_LCP_LCP_SHIFT)
-# define SET_LCP_ENTRY(r, val) (SA_and_LCP[r] |= (val) << SA_and_LCP_LCP_SHIFT)
-# define UNVISITED_TAG NORMAL_UNVISITED_TAG
-#endif
-
-/*
- * Build the LCP (Longest Common Prefix) array in linear time.
- *
- * LCP[r] will be the length of the longest common prefix between the suffixes
- * with positions SA[r - 1] and SA[r]. LCP[0] will be undefined.
- *
- * Algorithm taken from Kasai et al. (2001), but modified slightly:
- *
- * - For decreased memory usage and improved memory locality, pack the two
- * logically distinct SA and LCP arrays into a single array SA_and_LCP.
- *
- * - With bytes there is no realistic way to reserve a unique symbol for
- * end-of-buffer, so use explicit checks for end-of-buffer.
- *
- * - If a LCP value is less than the minimum match length, then store 0. This
- * avoids having to do comparisons against the minimum match length later.
- *
- * - If a LCP value is greater than the "nice match length", then store the
- * "nice match length". This caps the number of bits needed to store each
- * LCP value, and this caps the depth of the LCP-interval tree, without
- * usually hurting the compression ratio too much.
- *
- * References:
- *
- * Kasai et al. 2001. Linear-Time Longest-Common-Prefix Computation in
- * Suffix Arrays and Its Applications. CPM '01 Proceedings of the 12th
- * Annual Symposium on Combinatorial Pattern Matching pp. 181-192.
- */
-#if HUGE_MODE
-static void
-build_LCP_huge(u32 LCP[restrict], const u32 SA[restrict], const u32 ISA[restrict],
- const u8 T[restrict], u32 n, u32 min_lcp, u32 max_lcp)
-#else
-static void
-build_LCP_normal(u32 SA_and_LCP[restrict], const u32 ISA[restrict],
- const u8 T[restrict], u32 n, u32 min_lcp, u32 max_lcp)
-#endif
-{
- u32 h = 0;
- for (u32 i = 0; i < n; i++) {
- u32 r = ISA[i];
- if (r > 0) {
- u32 j = GET_SA_ENTRY(r - 1);
- u32 lim = min(n - i, n - j);
- while (h < lim && T[i + h] == T[j + h])
- h++;
- u32 stored_lcp = h;
- if (stored_lcp < min_lcp)
- stored_lcp = 0;
- else if (stored_lcp > max_lcp)
- stored_lcp = max_lcp;
- SET_LCP_ENTRY(r, stored_lcp);
- if (h > 0)
- h--;
- }
- }
-}
-
-/*
- * Use the suffix array accompanied with the longest-common-prefix array --- in
- * other words, the "enhanced suffix array" --- to simulate a bottom-up
- * traversal of the corresponding suffix tree, or equivalently the "lcp-interval
- * tree", as described in Abouelhoda et al. (2004).
- *
- * While doing the traversal, create a table 'intervals' that contains data for
- * each lcp-interval, specifically the lcp value of that interval, and the index
- * of the superinterval.
- *
- * Also while doing the traversal, create a table 'pos_data' that contains a
- * mapping from suffix index to the deepest lcp-interval containing it.
- *
- * The result is that we will later be able to do match-finding at a given
- * position by looking up that position in 'pos_data' to get the deepest
- * lcp-interval containing the corresponding suffix, then proceeding to the
- * superintervals. See lcpit_advance_one_byte() for more details.
- *
- * Note: We limit the depth of the lcp-interval tree by capping the lcp at
- * LCP_MAX. This can cause a sub-tree of intervals with lcp greater than
- * LCP_MAX to be collapsed into a single interval with lcp LCP_MAX. This avoids
- * degenerate cases and does not hurt match-finding very much, since if we find
- * a match of length LCP_MAX and extend it as far as possible, that's usually
- * good enough because that region of the input must already be highly
- * compressible.
- *
- * References:
- *
- * M.I. Abouelhoda, S. Kurtz, E. Ohlebusch. 2004. Replacing Suffix Trees
- * With Enhanced Suffix Arrays. Journal of Discrete Algorithms Volume 2
- * Issue 1, March 2004, pp. 53-86.
- *
- * G. Chen, S.J. Puglisi, W.F. Smyth. 2008. Lempel-Ziv Factorization
- * Using Less Time & Space. Mathematics in Computer Science June 2008,
- * Volume 1, Issue 4, pp. 605-623.
- *
- * Kasai et al. Linear-Time Longest-Common-Prefix Computation in Suffix
- * Arrays and Its Applications. 2001. CPM '01 Proceedings of the 12th
- * Annual Symposium on Combinatorial Pattern Matching pp. 181-192.
- */
-#if HUGE_MODE
-static void
-build_LCPIT_huge(const u32 SA[restrict], u32 LCP[], u64 intervals[],
- u32 pos_data[restrict], u32 n)
-#else
-static void
-build_LCPIT_normal(const u32 SA_and_LCP[restrict], u32 intervals[restrict],
- u32 pos_data[restrict], u32 n)
-#endif
-{
- u32 next_interval_idx = 0;
- u32 open_intervals[LCP_MAX + 1];
- u32 *top = open_intervals;
- u32 prev_pos = GET_SA_ENTRY(0);
-
- /* The interval with lcp=0 covers the entire array. It remains open
- * until the end. */
- *top = next_interval_idx;
- intervals[next_interval_idx] = 0;
- next_interval_idx++;
-
- for (u32 r = 1; r < n; r++) {
- u32 next_pos = GET_SA_ENTRY(r);
- u32 next_lcp = GET_LCP_ENTRY(r);
- u32 top_lcp = intervals[*top];
-
- if (next_lcp == top_lcp) {
- /* continuing the deepest open interval */
- pos_data[prev_pos] = *top;
- } else if (next_lcp > top_lcp) {
- /* opening a new interval */
- intervals[next_interval_idx] = next_lcp;
- *++top = next_interval_idx;
- pos_data[prev_pos] = next_interval_idx;
- next_interval_idx++;
- } else {
- /* closing the deepest open interval */
- pos_data[prev_pos] = *top;
- for (;;) {
- u32 closed_interval_idx = *top;
- u32 superinterval_idx = *--top;
- u32 superinterval_lcp = intervals[superinterval_idx];
-
- if (next_lcp == superinterval_lcp) {
- /* continuing the superinterval */
- intervals[closed_interval_idx] |=
- (superinterval_idx << LCP_BITS) |
- UNVISITED_TAG;
- break;
- } else if (next_lcp > superinterval_lcp) {
- /* creating a new interval that is a
- * superinterval of the one being
- * closed, but still a subinterval of
- * its superinterval */
- intervals[next_interval_idx] = next_lcp;
- *++top = next_interval_idx;
- intervals[closed_interval_idx] |=
- (next_interval_idx << LCP_BITS) |
- UNVISITED_TAG;
- next_interval_idx++;
- break;
- } else {
- /* also closing the superinterval */
- intervals[closed_interval_idx] |=
- (superinterval_idx << LCP_BITS) |
- UNVISITED_TAG;
- }
- }
- }
- prev_pos = next_pos;
- }
-
- /* close any still-open intervals */
- pos_data[prev_pos] = *top;
- while (top > open_intervals) {
- u32 closed_interval_idx = *top;
- u32 superinterval_idx = *--top;
- intervals[closed_interval_idx] |=
- (superinterval_idx << LCP_BITS) | UNVISITED_TAG;
- }
-}
-
-/*
- * Advance the LCP-interval tree matchfinder by one byte.
- *
- * If @record_matches is true, then matches are recorded in the @matches array,
- * and the return value is the number of matches found. Otherwise, @matches is
- * ignored and the return value is always 0.
- */
-static inline u32
-#if HUGE_MODE
-lcpit_advance_one_byte_huge
-#else
-lcpit_advance_one_byte_normal
-#endif
-(struct lcpit_matchfinder *mf, struct lz_match * restrict matches,
- bool record_matches)
-{
- const u32 cur_pos = mf->cur_pos++;
- u32 * const pos_data = mf->pos_data;
-#if HUGE_MODE
- u64 * const intervals = mf->intervals64;
-#else
- u32 * const intervals = mf->intervals;
-#endif
- u32 num_matches = 0;
- u32 lcp, next_lcp;
- u32 interval, next_interval;
- u32 cur_match, next_match;
-
- /* Look up the deepest lcp-interval containing the current suffix. */
- interval = pos_data[cur_pos];
-
- /* Prefetch the deepest lcp-interval containing the next suffix. */
- prefetch(&intervals[pos_data[cur_pos + 1]]);
-
- /* Since the current position is greater than any position previously
- * searched, set the "lcp interval of the next match" for this suffix to
- * 0. This is the index of the root interval, and this indicates that
- * there is no next match. */
- pos_data[cur_pos] = 0;
-
- /* Ascend the lcp-interval tree until we reach an lcp-interval that has
- * already been visited. */
-
- while (intervals[interval] & UNVISITED_TAG) {
-
- /* Visiting this lcp-interval for the first time. Therefore,
- * there are no matches with length equal to the lcp of this
- * lcp-interval. */
-
- /* Extract the LCP and superinterval reference. */
-
- lcp = intervals[interval] & LCP_MASK;
-
- /* If the LCP is shorter than the minimum length of matches to
- * be produced, we're done, since the LCP will only ever get
- * shorter from here. This also prevents ascending above the
- * root of the lcp-interval tree, since the root is guaranteed
- * to be a 0-interval. */
- if (lcp == 0)
- return 0;
-
- next_interval = (intervals[interval] & ~UNVISITED_TAG) >> LCP_BITS;
-
- /* Set the position of the most-recently-seen suffix within this
- * lcp-interval. Since this is the first visitation of this
- * lcp-interval, this is simply the current suffix.
- *
- * Note that this overwrites the superinterval reference which
- * was previously included in this lcp-interval data slot.
- * Further visitations of this lcp-interval will detect that it
- * is already visited and will follow the chain of
- * most-recently-seen suffixes rather than ascend the tree
- * directly. */
- intervals[interval] = (cur_pos << LCP_BITS) | lcp;
-
- /* Ascend to the superinterval of this lcp-interval. */
- interval = next_interval;
- }
-
- /* We've already visited the current lcp-interval. */
-
- /* Extract the LCP of this lcp-interval. */
- lcp = intervals[interval] & LCP_MASK;
-
- /* Extract the current match for this lcp-interval. This usually is the
- * most-recently-seen suffix within this lcp-interval, but it may be
- * outdated. */
- cur_match = intervals[interval] >> LCP_BITS;
-
- for (;;) {
- /* If the LCP is shorter than the minimum length of matches to
- * be produced, we're done, since the LCP will only ever get
- * shorter from here. This also prevents ascending above the
- * root of the lcp-interval tree, since the root is guaranteed
- * to be a 0-interval. */
- if (lcp == 0)
- break;
-
- /* Advance the current match until the lcp of the *next* match
- * is lower than the current lcp. When this is true we know
- * that the current match is up to date (lowest offset /
- * greatest position for that lcp). */
-
- next_match = cur_match;
- do {
- next_interval = pos_data[next_match];
- next_lcp = intervals[next_interval] & LCP_MASK;
- cur_match = next_match;
- next_match = intervals[next_interval] >> LCP_BITS;
- } while (next_lcp >= lcp);
-
- /* Link the current position into the match chain, discarding
- * any skipped matches. */
- intervals[interval] = (cur_pos << LCP_BITS) | lcp;
- pos_data[cur_match] = interval;
-
- if (record_matches) {
- /* Record the match. */
- matches[num_matches].length = lcp;
- matches[num_matches].offset = cur_pos - cur_match;
- num_matches++;
- }
-
- /* Advance to the next match. */
- interval = next_interval;
- lcp = next_lcp;
- cur_match = next_match;
- }
- return num_matches;
-}
-
-#undef GET_SA_ENTRY
-#undef GET_LCP_ENTRY
-#undef SET_LCP_ENTRY
-#undef UNVISITED_TAG