+/*
+ * lz_sarray.h
+ *
+ * Suffix array match-finder for LZ (Lempel-Ziv) compression.
+ */
+
+/*
+ * Copyright (C) 2013 Eric Biggers
+ *
+ * This file is part of wimlib, a library for working with WIM files.
+ *
+ * wimlib is free software; you can redistribute it and/or modify it under the
+ * terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 3 of the License, or (at your option)
+ * any later version.
+ *
+ * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ * A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ */
+
+#ifndef _WIMLIB_LZ_SARRAY_H
+#define _WIMLIB_LZ_SARRAY_H
+
+#include "wimlib/compiler.h"
+#include "wimlib/lz.h"
+#include "wimlib/types.h"
+
+struct salink;
+
+/* Suffix array LZ (Lempel-Ziv) match-finder. */
+struct lz_sarray {
+ /* Allocated window size for the match-finder. */
+ input_idx_t max_window_size;
+
+ /* Minimum match length to return. */
+ input_idx_t min_match_len;
+
+ /* Maximum match length to return. */
+ input_idx_t max_match_len;
+
+ /* Maximum matches to consider at each position (max search depth). */
+ u32 max_matches_to_consider;
+
+ /* Maximum number of matches to return at each position. */
+ u32 max_matches_to_return;
+
+ /* Current position in the window */
+ input_idx_t cur_pos;
+
+ /* Current window size. */
+ input_idx_t window_size;
+
+ /* Suffix array for window.
+ * This is a mapping from suffix rank to suffix position. */
+ input_idx_t *SA;
+
+ /* Inverse suffix array for window.
+ * This is a mapping from suffix position to suffix rank.
+ * If 0 <= r < window_size, then ISA[SA[r]] == r. */
+ input_idx_t *ISA;
+
+ /* Longest common prefix array corresponding to the suffix array SA.
+ * LCP[i] is the length of the longest common prefix between the
+ * suffixes with positions SA[i - 1] and SA[i]. LCP[0] is undefined.
+ */
+ input_idx_t *LCP;
+
+ /* Suffix array links.
+ *
+ * During a linear scan of the input string to find matches, this array
+ * used to keep track of which rank suffixes in the suffix array appear
+ * before the current position. Instead of searching in the original
+ * suffix array, scans for matches at a given position traverse a linked
+ * list containing only suffixes that appear before that position. */
+ struct salink *salink;
+};
+
+/* Suffix array link */
+struct salink {
+ /* Rank of highest ranked suffix that has rank lower than the suffix
+ * corresponding to this structure and either has a lower position
+ * (initially) or has a position lower than the highest position at
+ * which matches have been searched for so far, or -1 if there is no
+ * such suffix. */
+ input_idx_t prev;
+
+ /* Rank of lowest ranked suffix that has rank greater than the suffix
+ * corresponding to this structure and either has a lower position
+ * (intially) or has a position lower than the highest position at which
+ * matches have been searched for so far, or -1 if there is no such
+ * suffix. */
+ input_idx_t next;
+
+ /* Length of longest common prefix between the suffix corresponding to
+ * this structure and the suffix with rank @prev, or 0 if @prev is -1.
+ */
+ input_idx_t lcpprev;
+
+ /* Length of longest common prefix between the suffix corresponding to
+ * this structure and the suffix with rank @next, or 0 if @next is -1.
+ */
+ input_idx_t lcpnext;
+};
+
+extern bool
+lz_sarray_init(struct lz_sarray *mf,
+ input_idx_t max_window_size,
+ input_idx_t min_match_len,
+ input_idx_t max_match_len,
+ u32 max_matches_to_consider,
+ u32 max_matches_to_return);
+
+extern void
+lz_sarray_destroy(struct lz_sarray *mf);
+
+extern void
+lz_sarray_load_window(struct lz_sarray *mf, const u8 window[],
+ input_idx_t window_size);
+
+static inline input_idx_t
+lz_sarray_get_pos(const struct lz_sarray *mf)
+{
+ return mf->cur_pos;
+}
+
+/* Advance the suffix array match-finder to the next position. */
+static _always_inline_attribute void
+lz_sarray_update_salink(const input_idx_t i,
+ const input_idx_t SA[const restrict],
+ const input_idx_t ISA[const restrict],
+ struct salink link[const restrict])
+{
+ /* r = Rank of the suffix at the current position. */
+ const input_idx_t r = ISA[i];
+
+ /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the
+ * current suffix AND has a LOWER position, or -1 if none exists. */
+ const input_idx_t next = link[r].next;
+
+ /* prev = rank of HIGHEST ranked suffix that is ranked LOWER than the
+ * current suffix AND has a LOWER position, or -1 if none exists. */
+ const input_idx_t prev = link[r].prev;
+
+ /* Link the suffix at the current position into the linked list that
+ * contains all suffixes in the suffix array that are appear at or
+ * before the current position, sorted by rank.
+ *
+ * Save the values of all fields we overwrite so that rollback is
+ * possible. */
+ if (next != ~(input_idx_t)0) {
+
+ link[next].prev = r;
+ link[next].lcpprev = link[r].lcpnext;
+ }
+
+ if (prev != ~(input_idx_t)0) {
+
+ link[prev].next = r;
+ link[prev].lcpnext = link[r].lcpprev;
+ }
+}
+
+/* Skip the current position in the suffix array match-finder. */
+static _always_inline_attribute void
+lz_sarray_skip_position(struct lz_sarray *mf)
+{
+ LZ_ASSERT(mf->cur_pos < mf->window_size);
+ lz_sarray_update_salink(mf->cur_pos++, mf->SA, mf->ISA, mf->salink);
+}
+
+typedef input_idx_t lz_sarray_cost_t;
+#define LZ_SARRAY_INFINITE_COST (~(lz_sarray_cost_t)0)
+
+/*
+ * Use the suffix array match-finder to retrieve a list of LZ matches at the
+ * current position.
+ *
+ * Returns the number of matches written into @matches. The matches are
+ * returned in decreasing order by length, and each will be of unique length
+ * between the minimum and maximum match lengths passed to lz_sarray_init(). Up
+ * to @max_matches_to_return (passed to lz_sarray_init()) matches will be
+ * returned.
+ *
+ * @eval_match_cost is a function for evaluating the cost of a match when
+ * deciding which ones to return. It is only used for comparing matches of the
+ * same length. It needs to be fast, and need not be exact; an implementation
+ * might simply rank matches by their offset, for example, although
+ * implementations may choose to take into account additional information such
+ * as repeat offsets.
+ */
+static _always_inline_attribute u32
+lz_sarray_get_matches(struct lz_sarray *mf,
+ struct raw_match matches[],
+ lz_sarray_cost_t (*eval_match_cost)
+ (input_idx_t length,
+ input_idx_t offset,
+ const void *ctx),
+ const void *eval_match_cost_ctx)
+{
+ LZ_ASSERT(mf->cur_pos < mf->window_size);
+ const input_idx_t i = mf->cur_pos++;
+
+ const input_idx_t * const restrict SA = mf->SA;
+ const input_idx_t * const restrict ISA = mf->ISA;
+ struct salink * const restrict link = mf->salink;
+ const input_idx_t min_match_len = mf->min_match_len;
+ const u32 max_matches_to_consider = mf->max_matches_to_consider;
+ const u32 max_matches_to_return = mf->max_matches_to_return;
+
+ /* r = Rank of the suffix at the current position. */
+ const input_idx_t r = ISA[i];
+
+ /* Prepare for searching the current position. */
+ lz_sarray_update_salink(i, SA, ISA, link);
+
+ /* L = rank of next suffix to the left;
+ * R = rank of next suffix to the right;
+ * lenL = length of match between current position and the suffix with rank L;
+ * lenR = length of match between current position and the suffix with rank R.
+ *
+ * This is left and right relative to the rank of the current suffix.
+ * Since the suffixes in the suffix array are sorted, the longest
+ * matches are immediately to the left and right (using the linked list
+ * to ignore all suffixes that occur later in the window). The match
+ * length decreases the farther left and right we go. We shall keep the
+ * length on both sides in sync in order to choose the lowest-cost match
+ * of each length.
+ */
+ input_idx_t L = link[r].prev;
+ input_idx_t R = link[r].next;
+ input_idx_t lenL = link[r].lcpprev;
+ input_idx_t lenR = link[r].lcpnext;
+
+ /* nmatches = number of matches found so far. */
+ u32 nmatches = 0;
+
+ /* best_cost = cost of lowest-cost match found so far.
+ *
+ * We keep track of this so that we can ignore shorter matches that do
+ * not have lower costs than a longer matches already found.
+ */
+ lz_sarray_cost_t best_cost = LZ_SARRAY_INFINITE_COST;
+
+ /* count_remaining = maximum number of possible matches remaining to be
+ * considered. */
+ u32 count_remaining = max_matches_to_consider;
+
+ /* pending = match currently being considered for a specific length. */
+ struct raw_match pending;
+ lz_sarray_cost_t pending_cost;
+
+ while (lenL >= min_match_len || lenR >= min_match_len)
+ {
+ pending.len = lenL;
+ pending_cost = LZ_SARRAY_INFINITE_COST;
+ lz_sarray_cost_t cost;
+
+ /* Extend left. */
+ if (lenL >= min_match_len && lenL >= lenR) {
+ for (;;) {
+
+ if (--count_remaining == 0)
+ goto out_save_pending;
+
+ input_idx_t offset = i - SA[L];
+
+ /* Save match if it has smaller cost. */
+ cost = (*eval_match_cost)(lenL, offset,
+ eval_match_cost_ctx);
+ if (cost < pending_cost) {
+ pending.offset = offset;
+ pending_cost = cost;
+ }
+
+ if (link[L].lcpprev < lenL) {
+ /* Match length decreased. */
+
+ lenL = link[L].lcpprev;
+
+ /* Save the pending match unless the
+ * right side still may have matches of
+ * this length to be scanned, or if a
+ * previous (longer) match had lower
+ * cost. */
+ if (pending.len > lenR) {
+ if (pending_cost < best_cost) {
+ best_cost = pending_cost;
+ matches[nmatches++] = pending;
+ if (nmatches == max_matches_to_return)
+ return nmatches;
+ }
+ pending.len = lenL;
+ pending_cost = LZ_SARRAY_INFINITE_COST;
+ }
+ if (lenL < min_match_len || lenL < lenR)
+ break;
+ }
+ L = link[L].prev;
+ }
+ }
+
+ pending.len = lenR;
+
+ /* Extend right. */
+ if (lenR >= min_match_len && lenR > lenL) {
+ for (;;) {
+
+ if (--count_remaining == 0)
+ goto out_save_pending;
+
+ input_idx_t offset = i - SA[R];
+
+ /* Save match if it has smaller cost. */
+ cost = (*eval_match_cost)(lenR,
+ offset,
+ eval_match_cost_ctx);
+ if (cost < pending_cost) {
+ pending.offset = offset;
+ pending_cost = cost;
+ }
+
+ if (link[R].lcpnext < lenR) {
+ /* Match length decreased. */
+
+ lenR = link[R].lcpnext;
+
+ /* Save the pending match unless a
+ * previous (longer) match had lower
+ * cost. */
+ if (pending_cost < best_cost) {
+ matches[nmatches++] = pending;
+ best_cost = pending_cost;
+ if (nmatches == max_matches_to_return)
+ return nmatches;
+ }
+
+ if (lenR < min_match_len || lenR <= lenL)
+ break;
+
+ pending.len = lenR;
+ pending_cost = LZ_SARRAY_INFINITE_COST;
+ }
+ R = link[R].next;
+ }
+ }
+ }
+ goto out;
+
+out_save_pending:
+ if (pending_cost != LZ_SARRAY_INFINITE_COST)
+ matches[nmatches++] = pending;
+
+out:
+ return nmatches;
+}
+
+#endif /* _WIMLIB_LZ_SARRAY_H */
git://wimlib.net / wimlib / commitdiff