--- /dev/null
+/*
+ * lcpit_matchfinder.h
+ *
+ * A match-finder for Lempel-Ziv compression based on bottom-up construction and
+ * traversal of the Longest Common Prefix (LCP) interval tree.
+ *
+ * Author: Eric Biggers
+ * Year: 2014, 2015
+ *
+ * The author dedicates this file to the public domain.
+ * You can do whatever you want with this file.
+ */
+
+#include <limits.h>
+#include <string.h>
+
+#include "wimlib/divsufsort.h"
+#include "wimlib/lcpit_matchfinder.h"
+#include "wimlib/util.h"
+
+#define LCP_BITS 6
+#define LCP_MASK ((1 << LCP_BITS) - 1)
+#define LCP_MAX LCP_MASK
+#define NORMAL_UNVISITED_TAG ((u32)1 << 31)
+#define MAX_NORMAL_BUFSIZE ((u32)1 << (31 - LCP_BITS))
+#define HUGE_UNVISITED_TAG ((u64)1 << 63)
+#define SA_and_LCP_LCP_SHIFT (32 - LCP_BITS)
+#define SA_and_LCP_POS_MASK (((u32)1 << SA_and_LCP_LCP_SHIFT) - 1)
+
+/*
+ * Include the template header to define the functions build_LCP(),
+ * build_LCPIT(), and lcpit_advance_one_byte(). There are "normal" and "huge"
+ * versions of each function. The normal versions assume that a buffer position
+ * and LCP value can be packed into a 32-bit integer, whereas the huge versions
+ * assume that 64 bits is needed.
+ *
+ * Both versions cap LCP values to 6 bits. This limits the depth of the
+ * lcp-interval tree without hurting the compression ratio too much. Matches of
+ * length 63 are sufficiently long that the compression ratio doesn't change
+ * significantly if we choose one such match over another.
+ */
+#define HUGE_MODE 1
+#include "lcpit_matchfinder_templates.h"
+#undef HUGE_MODE
+
+#define HUGE_MODE 0
+#include "lcpit_matchfinder_templates.h"
+#undef HUGE_MODE
+
+/*
+ * Calculate the number of bytes of memory needed for the LCP-interval tree
+ * matchfinder.
+ *
+ * @max_bufsize - maximum buffer size to support
+ *
+ * Returns the number of bytes required.
+ */
+u64
+lcpit_matchfinder_get_needed_memory(size_t max_bufsize)
+{
+ u64 size = 0;
+
+ /* pos_data (+1 is for prefetch) */
+ size += ((u64)max_bufsize + 1) * sizeof(u32);
+
+ /* intervals or intervals64 */
+ size += max((u64)max_bufsize, DIVSUFSORT_TMP_LEN) *
+ (max_bufsize <= MAX_NORMAL_BUFSIZE ? sizeof(u32) : sizeof(u64));
+
+ /* SA */
+ size += (u64)max_bufsize * sizeof(u32);
+
+ return size;
+}
+
+/*
+ * Initialize the LCP-interval tree matchfinder.
+ *
+ * @mf - the matchfinder structure to initialize
+ * @max_bufsize - maximum buffer size to support
+ * @min_match_len - minimum match length in bytes
+ * @nice_match_len - only consider this many bytes of each match
+ *
+ * Returns true if successfully initialized; false if out of memory.
+ */
+bool
+lcpit_matchfinder_init(struct lcpit_matchfinder *mf, size_t max_bufsize,
+ u32 min_match_len, u32 nice_match_len)
+{
+ if (lcpit_matchfinder_get_needed_memory(max_bufsize) > SIZE_MAX)
+ return false;
+
+ mf->pos_data = MALLOC((max_bufsize + 1) * sizeof(u32));
+ mf->intervals = MALLOC(max((u64)max_bufsize, DIVSUFSORT_TMP_LEN) *
+ (max_bufsize <= MAX_NORMAL_BUFSIZE ?
+ sizeof(u32) : sizeof(u64)));
+ mf->SA = MALLOC(max_bufsize * sizeof(u32));
+
+ if (!mf->pos_data || !mf->intervals || !mf->SA) {
+ lcpit_matchfinder_destroy(mf);
+ return false;
+ }
+
+ mf->min_match_len = min_match_len;
+ mf->nice_match_len = min(nice_match_len, LCP_MAX);
+ return true;
+}
+
+/*
+ * Build the suffix array SA for the specified byte array T of length n.
+ *
+ * The suffix array is a sorted array of the byte array's suffixes, represented
+ * by indices into the byte array. It can equivalently be viewed as a mapping
+ * from suffix rank to suffix position.
+ *
+ * To build the suffix array, we use libdivsufsort, which uses an
+ * induced-sorting-based algorithm. In practice, this seems to be the fastest
+ * suffix array construction algorithm currently available.
+ *
+ * References:
+ *
+ * Y. Mori. libdivsufsort, a lightweight suffix-sorting library.
+ * https://code.google.com/p/libdivsufsort/.
+ *
+ * G. Nong, S. Zhang, and W.H. Chan. 2009. Linear Suffix Array
+ * Construction by Almost Pure Induced-Sorting. Data Compression
+ * Conference, 2009. DCC '09. pp. 193 - 202.
+ *
+ * S.J. Puglisi, W.F. Smyth, and A. Turpin. 2007. A Taxonomy of Suffix
+ * Array Construction Algorithms. ACM Computing Surveys (CSUR) Volume 39
+ * Issue 2, 2007 Article No. 4.
+ */
+static void
+build_SA(u32 SA[], const u8 T[], u32 n, u32 *tmp)
+{
+ /* Note: divsufsort() needs temporary space --- one array with 256
+ * spaces and one array with 65536 spaces. The implementation of
+ * divsufsort() has been modified from the original to use the provided
+ * temporary space instead of allocating its own, since we don't want to
+ * have to deal with malloc() failures here. */
+ divsufsort(T, SA, n, tmp);
+}
+
+/*
+ * Build the inverse suffix array ISA from the suffix array SA.
+ *
+ * Whereas the suffix array is a mapping from suffix rank to suffix position,
+ * the inverse suffix array is a mapping from suffix position to suffix rank.
+ */
+static void
+build_ISA(u32 ISA[restrict], const u32 SA[restrict], u32 n)
+{
+ for (u32 r = 0; r < n; r++)
+ ISA[SA[r]] = r;
+}
+
+/*
+ * Prepare the LCP-interval tree matchfinder for a new input buffer.
+ *
+ * @mf - the initialized matchfinder structure
+ * @T - the input buffer
+ * @n - size of the input buffer in bytes. This may be at most the max_bufsize
+ * with which lcpit_matchfinder_init() was called.
+ */
+void
+lcpit_matchfinder_load_buffer(struct lcpit_matchfinder *mf, const u8 *T, u32 n)
+{
+ if (n == 0)
+ return;
+
+ build_SA(mf->SA, T, n, mf->intervals);
+ build_ISA(mf->pos_data, mf->SA, n);
+ if (n <= MAX_NORMAL_BUFSIZE) {
+ /* "Normal" sized buffer */
+
+ /* Build LCP, packing it into ->SA */
+ build_LCP_normal(mf->SA, mf->pos_data, T, n,
+ mf->min_match_len, mf->nice_match_len);
+ /* Prepare ->intervals and ->pos_data */
+ build_LCPIT_normal(mf->SA, mf->intervals, mf->pos_data, n);
+ mf->huge_mode = false;
+ } else {
+ /* "Huge" sized buffer */
+
+ /* Build LCP in the second half of ->intervals64. It may be
+ * partially overwritten in build_LCPIT_huge(), but this is okay
+ * since each LCP entry is guaranteed to be consumed before it
+ * can possibly be overwritten. */
+ build_LCP_huge(mf->intervals + n, mf->SA, mf->pos_data, T, n,
+ mf->min_match_len, mf->nice_match_len);
+ /* Prepare ->intervals64 and ->pos_data */
+ build_LCPIT_huge(mf->SA, mf->intervals + n, mf->intervals64,
+ mf->pos_data, n);
+ mf->huge_mode = true;
+ }
+ mf->cur_pos = 0; /* starting at beginning of input buffer */
+ mf->pos_data[n] = 0; /* safety entry for prefetch() overrun */
+}
+
+/*
+ * Retrieve a list of matches with the next position.
+ *
+ * The matches will be recorded in the @matches array, ordered by strictly
+ * decreasing length and strictly decreasing offset.
+ *
+ * The return value is the number of matches found and written to @matches.
+ * This can be any value in [0, nice_match_len - min_match_len + 1].
+ *
+ * If the caller attempts to advance beyond the end of the input buffer, the
+ * behavior is undefined.
+ */
+u32
+lcpit_matchfinder_get_matches(struct lcpit_matchfinder *mf,
+ struct lz_match *matches)
+{
+ if (mf->huge_mode)
+ return lcpit_advance_one_byte_huge(mf, matches, true);
+ else
+ return lcpit_advance_one_byte_normal(mf, matches, true);
+}
+
+/*
+ * Skip the next @count bytes (don't search for matches at them). @count is
+ * assumed to be > 0.
+ *
+ * If the caller attempts to advance beyond the end of the input buffer, the
+ * behavior is undefined.
+ */
+void
+lcpit_matchfinder_skip_bytes(struct lcpit_matchfinder *mf, u32 count)
+{
+ if (mf->huge_mode) {
+ do {
+ lcpit_advance_one_byte_huge(mf, NULL, false);
+ } while (--count);
+ } else {
+ do {
+ lcpit_advance_one_byte_normal(mf, NULL, false);
+ } while (--count);
+ }
+}
+
+/*
+ * Destroy an LCP-interval tree matchfinder that was previously initialized with
+ * lcpit_matchfinder_init().
+ *
+ * If the struct has been zeroed out, this has no effect.
+ */
+void
+lcpit_matchfinder_destroy(struct lcpit_matchfinder *mf)
+{
+ FREE(mf->pos_data);
+ FREE(mf->intervals);
+ FREE(mf->SA);
+ memset(mf, 0, sizeof(*mf));
+}
git://wimlib.net / wimlib / blobdiff