- u32 next_interval;
- u32 incomplete_intervals[lcp_limit + 1];
- u32 *cur_interval;
- u32 prev_pos;
-
- /* As we determine lcp-intervals, we assign each one an entry in
- * 'intervals', overwriting LCP in the process. Each such entry will
- * contain the index in 'intervals' of the superinterval, along with the
- * longest common prefix length that the suffixes in that interval
- * share.
- *
- * Note: since we don't need its memory for anything, we don't overwrite
- * the suffix array, even though this could potentially be done since
- * it's not actually used during match-finding. */
-
- /* Process rank 0 as special case. This creates the lcp-interval
- * containing every suffix in the window. */
- prev_pos = SA[0];
- intervals[0] = 0;
- pos_data[prev_pos] = 0;
- cur_interval = incomplete_intervals;
- *cur_interval = 0;
- next_interval = 1;
-
- /* Iterate through each suffix array rank. */
- for (u32 r = 1; r < n; r++) {
-
- /* Get the longest common prefix (lcp) between the suffixes with
- * ranks r and r - 1. But cap it to the lcp limit. */
- const u32 lcp = min(LCP[r], lcp_limit);
-
- /* Convert rank => position using the suffix array. */
- const u32 pos = SA[r];
-
- /* cur_interval points to the index of the deepest (highest lcp
- * value) incomplete lcp-interval. */
-
- /*
- * There are three cases:
- *
- * (1) The lcp stayed the same as the previous value. Place the
- * current suffix in cur_interval. (This placement is
- * tentative, because if LCP increases at the next rank, this
- * suffix could still be placed in the resulting new LCP
- * interval instead.) cur_interval remains unchanged.
- *
- * (2) The lcp increased from the previous value. This signals
- * the beginning of a new lcp-interval. Create it and push it
- * onto the stack of incomplete intervals. But since lcp is
- * defined in terms of the longest prefix between this suffix
- * and the *previous* ranked suffix, the new lcp-interval
- * actually should have begun at the *previous* ranked suffix.
- * Therefore, we need to set both pos_data[pos] and
- * pos_data[prev_pos] to refer to the new interval.
- *
- * (3) The lcp decreased from the previous value. This signals
- * the termination of at least one lcp-interval. Pop the stack,
- * finalizing the lcp-intervals, until the current lcp is at
- * least as large as the lcp associated with cur_interval.
- * Then, if the current lcp is equal to the lcp associated with
- * cur_interval, place the current suffix in cur_interval,
- * similar to case (1). Else, create a new lcp-interval,
- * similar to case (2).
- */
-
- if (lcp == (intervals[*cur_interval] & LZ_LCPIT_LCP_MASK)) {
-
- /* Case (1) */
-
- pos_data[pos] = *cur_interval;
-
- } else if (lcp > (intervals[*cur_interval] & LZ_LCPIT_LCP_MASK)) {