*/
/*
- * Copyright (c) 2013 Eric Biggers. All rights reserved.
+ * Copyright (c) 2013, 2014 Eric Biggers. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
#include "divsufsort/divsufsort.h"
#include <string.h>
+#define DIVSUFSORT_TMP1_SIZE (256 * sizeof(saidx_t)) /* bucket_A */
+#define DIVSUFSORT_TMP2_SIZE (256 * 256 * sizeof(saidx_t)) /* bucket_B */
+
/* If ENABLE_LZ_DEBUG is defined, verify that the suffix array satisfies its
* definition.
*
* WARNING: this is for debug use only as it does not necessarily run in linear
* time!!! */
static void
-verify_suffix_array(const input_idx_t SA[restrict],
+verify_suffix_array(const lz_sarray_pos_t SA[restrict],
const u8 T[restrict],
bool found[restrict],
- input_idx_t n)
+ lz_sarray_pos_t n)
{
#ifdef ENABLE_LZ_DEBUG
/* Ensure the SA contains exactly one of each i in [0, n - 1]. */
- for (input_idx_t i = 0; i < n; i++)
+ for (lz_sarray_pos_t i = 0; i < n; i++)
found[i] = false;
- for (input_idx_t r = 0; r < n; r++) {
- input_idx_t i = SA[r];
+ for (lz_sarray_pos_t r = 0; r < n; r++) {
+ lz_sarray_pos_t i = SA[r];
LZ_ASSERT(i < n);
LZ_ASSERT(!found[i]);
found[i] = true;
/* Ensure the suffix with rank r is lexicographically lesser than the
* suffix with rank (r + 1) for all r in [0, n - 2]. */
- for (input_idx_t r = 0; r < n - 1; r++) {
+ for (lz_sarray_pos_t r = 0; r < n - 1; r++) {
- input_idx_t i1 = SA[r];
- input_idx_t i2 = SA[r + 1];
+ lz_sarray_pos_t i1 = SA[r];
+ lz_sarray_pos_t i2 = SA[r + 1];
- input_idx_t n1 = n - i1;
- input_idx_t n2 = n - i2;
+ lz_sarray_pos_t n1 = n - i1;
+ lz_sarray_pos_t n2 = n - i2;
int res = memcmp(&T[i1], &T[i2], min(n1, n2));
LZ_ASSERT(res < 0 || (res == 0 && n1 < n2));
* the inverse suffix array is a mapping from suffix position to suffix rank.
*/
static void
-compute_inverse_suffix_array(input_idx_t ISA[restrict],
- const input_idx_t SA[restrict],
- input_idx_t n)
+compute_inverse_suffix_array(lz_sarray_pos_t ISA[restrict],
+ const lz_sarray_pos_t SA[restrict],
+ lz_sarray_pos_t n)
{
- input_idx_t r;
+ lz_sarray_pos_t r;
for (r = 0; r < n; r++)
ISA[SA[r]] = r;
* take into account that with bytes in the real world, there is no unique
* symbol at the end of the string. */
static void
-compute_lcp_array(input_idx_t LCP[restrict],
- const input_idx_t SA[restrict],
- const input_idx_t ISA[restrict],
+compute_lcp_array(lz_sarray_pos_t LCP[restrict],
+ const lz_sarray_pos_t SA[restrict],
+ const lz_sarray_pos_t ISA[restrict],
const u8 T[restrict],
- input_idx_t n)
+ lz_sarray_pos_t n)
{
- input_idx_t h, i, r, j, lim;
+ lz_sarray_pos_t h, i, r, j, lim;
h = 0;
for (i = 0; i < n; i++) {
* WARNING: this is for debug use only as it does not necessarily run in linear
* time!!! */
static void
-verify_lcp_array(input_idx_t LCP[restrict],
- const input_idx_t SA[restrict],
+verify_lcp_array(lz_sarray_pos_t LCP[restrict],
+ const lz_sarray_pos_t SA[restrict],
const u8 T[restrict],
- input_idx_t n)
+ lz_sarray_pos_t n)
{
#ifdef ENABLE_LZ_DEBUG
- for (input_idx_t r = 0; r < n - 1; r++) {
- input_idx_t i1 = SA[r];
- input_idx_t i2 = SA[r + 1];
- input_idx_t lcp = LCP[r + 1];
+ for (lz_sarray_pos_t r = 0; r < n - 1; r++) {
+ lz_sarray_pos_t i1 = SA[r];
+ lz_sarray_pos_t i2 = SA[r + 1];
+ lz_sarray_pos_t lcp = LCP[r + 1];
- input_idx_t n1 = n - i1;
- input_idx_t n2 = n - i2;
+ lz_sarray_pos_t n1 = n - i1;
+ lz_sarray_pos_t n2 = n - i2;
LZ_ASSERT(lcp <= min(n1, n2));
*
* Note: We cap the lcpprev and lcpnext values to the maximum match length so
* that the match-finder need not worry about it later, in the inner loop.
+ *
+ * Note: the LCP array is one of the inputs to this function, but it is used as
+ * temporary space and therefore will be invalidated.
*/
static void
init_salink(struct salink link[restrict],
- const input_idx_t LCP[restrict],
- const input_idx_t SA[restrict],
+ lz_sarray_pos_t LCP[restrict],
+ const lz_sarray_pos_t SA[restrict],
const u8 T[restrict],
- input_idx_t n,
- input_idx_t max_match_len)
+ lz_sarray_pos_t n,
+ lz_sarray_len_t min_match_len,
+ lz_sarray_len_t max_match_len)
{
- /* Compute salink.next and salink.lcpnext. */
- link[n - 1].next = ~(input_idx_t)0;
- link[n - 1].lcpnext = 0;
- for (input_idx_t r = n - 2; r != ~(input_idx_t)0; r--) {
- input_idx_t t = r + 1;
- input_idx_t l = LCP[t];
- while (t != ~(input_idx_t)0 && SA[t] > SA[r]) {
- l = min(l, link[t].lcpnext);
- t = link[t].next;
+ /* Calculate salink.dist_to_next and salink.lcpnext.
+ *
+ * Pass 1 calculates, for each suffix rank, the corresponding
+ * "next_initial" value which is the smallest larger rank that
+ * corresponds to a suffix starting earlier in the string. It also
+ * calculates "lcpnext_initial", which is the longest common prefix with
+ * that suffix, although to eliminate checks in lz_sarray_get_matches(),
+ * "lcpnext_initial" is set to 0 if it's less than the minimum match
+ * length or set to the maximum match length if it's greater than the
+ * maximum match length.
+ *
+ * Pass 2 translates each absolute "next_initial", a 4-byte value, into
+ * a relative "dist_to_next", a 1-byte value. This is done to save
+ * memory. In the case that the exact relative distance cannot be
+ * encoded in 1 byte, it is capped to 255. This is valid as long as
+ * lz_sarray_get_matches() validates each position before using it.
+ * Note that "lcpnext" need not be updated in this case because it will
+ * not be used until the actual next rank has been found anyway.
+ */
+ link[n - 1].next_initial = LZ_SARRAY_POS_MAX;
+ link[n - 1].lcpnext_initial = 0;
+ for (lz_sarray_pos_t r = n - 2; r != LZ_SARRAY_POS_MAX; r--) {
+ lz_sarray_pos_t t = r + 1;
+ lz_sarray_pos_t l = LCP[t];
+ while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) {
+ l = min(l, link[t].lcpnext_initial);
+ t = link[t].next_initial;
}
- link[r].next = t;
- link[r].lcpnext = min(l, max_match_len);
+ link[r].next_initial = t;
+
+ if (l < min_match_len)
+ l = 0;
+ else if (l > max_match_len)
+ l = max_match_len;
+ link[r].lcpnext_initial = l;
+ }
+ for (lz_sarray_pos_t r = 0; r < n; r++) {
+ lz_sarray_pos_t next;
+ lz_sarray_len_t l;
+ lz_sarray_delta_t dist_to_next;
+
+ next = link[r].next_initial;
+ l = link[r].lcpnext_initial;
+
+ if (next == LZ_SARRAY_POS_MAX)
+ dist_to_next = 0;
+ else if (next - r <= LZ_SARRAY_DELTA_MAX)
+ dist_to_next = next - r;
+ else
+ dist_to_next = LZ_SARRAY_DELTA_MAX;
+
+ link[r].lcpnext = l;
+ link[r].dist_to_next = dist_to_next;
}
- /* Compute salink.prev and salink.lcpprev. */
- link[0].prev = ~(input_idx_t)0;
+ /* Calculate salink.dist_to_prev and salink.lcpprev.
+ *
+ * This is analgous to dist_to_next and lcpnext as described above, but
+ * in the other direction. That is, here we're interested in, for each
+ * rank, the largest smaller rank that corresponds to a suffix starting
+ * earlier in the string.
+ *
+ * To save memory we don't have a "prev_initial" field, but rather store
+ * those values in the LCP array. */
+ LCP[0] = LZ_SARRAY_POS_MAX;
link[0].lcpprev = 0;
- for (input_idx_t r = 1; r < n; r++) {
- input_idx_t t = r - 1;
- input_idx_t l = LCP[r];
- while (t != ~(input_idx_t)0 && SA[t] > SA[r]) {
+ for (lz_sarray_pos_t r = 1; r < n; r++) {
+ lz_sarray_pos_t t = r - 1;
+ lz_sarray_pos_t l = LCP[r];
+ while (t != LZ_SARRAY_POS_MAX && SA[t] > SA[r]) {
l = min(l, link[t].lcpprev);
- t = link[t].prev;
+ t = LCP[t];
}
- link[r].prev = t;
- link[r].lcpprev = min(l, max_match_len);
+ LCP[r] = t;
+
+ if (l < min_match_len)
+ l = 0;
+ else if (l > max_match_len)
+ l = max_match_len;
+
+ link[r].lcpprev = l;
+ }
+ for (lz_sarray_pos_t r = 0; r < n; r++) {
+
+ lz_sarray_pos_t prev = LCP[r];
+
+ if (prev == LZ_SARRAY_POS_MAX)
+ link[r].dist_to_prev = 0;
+ else if (r - prev <= LZ_SARRAY_DELTA_MAX)
+ link[r].dist_to_prev = r - prev;
+ else
+ link[r].dist_to_prev = LZ_SARRAY_DELTA_MAX;
}
}
* time!!! */
static void
verify_salink(const struct salink link[],
- const input_idx_t SA[],
+ const lz_sarray_pos_t SA[],
const u8 T[],
- input_idx_t n,
- input_idx_t max_match_len)
+ lz_sarray_pos_t n,
+ lz_sarray_len_t min_match_len,
+ lz_sarray_len_t max_match_len)
{
#ifdef ENABLE_LZ_DEBUG
- for (input_idx_t r = 0; r < n; r++) {
- for (input_idx_t prev = r; ; ) {
+ for (lz_sarray_pos_t r = 0; r < n; r++) {
+ for (lz_sarray_pos_t prev = r; ; ) {
if (prev == 0) {
- LZ_ASSERT(link[r].prev == ~(input_idx_t)0);
+ LZ_ASSERT(link[r].dist_to_prev == 0);
LZ_ASSERT(link[r].lcpprev == 0);
break;
}
prev--;
if (SA[prev] < SA[r]) {
- LZ_ASSERT(link[r].prev == prev);
- LZ_ASSERT(link[r].lcpprev <= n - SA[prev]);
- LZ_ASSERT(link[r].lcpprev <= n - SA[r]);
- LZ_ASSERT(link[r].lcpprev <= max_match_len);
- LZ_ASSERT(0 == memcmp(&T[SA[prev]],
- &T[SA[r]],
- link[r].lcpprev));
- if (link[r].lcpprev < n - SA[prev] &&
- link[r].lcpprev < n - SA[r] &&
- link[r].lcpprev < max_match_len)
- {
- LZ_ASSERT(T[SA[prev] + link[r].lcpprev] !=
- T[SA[r] + link[r].lcpprev]);
- }
+ LZ_ASSERT(link[r].dist_to_prev == min(r - prev, LZ_SARRAY_DELTA_MAX));
+
+ lz_sarray_pos_t lcpprev;
+ for (lcpprev = 0;
+ lcpprev < min(n - SA[prev], n - SA[r]) &&
+ T[SA[prev] + lcpprev] == T[SA[r] + lcpprev];
+ lcpprev++)
+ ;
+ if (lcpprev < min_match_len)
+ lcpprev = 0;
+ else if (lcpprev > max_match_len)
+ lcpprev = max_match_len;
+
+ LZ_ASSERT(lcpprev == link[r].lcpprev);
break;
}
}
- for (input_idx_t next = r; ; ) {
+ for (lz_sarray_pos_t next = r; ; ) {
if (next == n - 1) {
- LZ_ASSERT(link[r].next == ~(input_idx_t)0);
+ LZ_ASSERT(link[r].dist_to_next == 0);
LZ_ASSERT(link[r].lcpnext == 0);
break;
}
next++;
if (SA[next] < SA[r]) {
- LZ_ASSERT(link[r].next == next);
- LZ_ASSERT(link[r].lcpnext <= n - SA[next]);
- LZ_ASSERT(link[r].lcpnext <= n - SA[r]);
- LZ_ASSERT(link[r].lcpnext <= max_match_len);
- LZ_ASSERT(0 == memcmp(&T[SA[next]],
- &T[SA[r]],
- link[r].lcpnext));
- if (link[r].lcpnext < n - SA[next] &&
- link[r].lcpnext < n - SA[r] &&
- link[r].lcpnext < max_match_len)
- {
- LZ_ASSERT(T[SA[next] + link[r].lcpnext] !=
- T[SA[r] + link[r].lcpnext]);
-
- }
+ LZ_ASSERT(link[r].dist_to_next == min(next - r, LZ_SARRAY_DELTA_MAX));
+
+ lz_sarray_pos_t lcpnext;
+ for (lcpnext = 0;
+ lcpnext < min(n - SA[next], n - SA[r]) &&
+ T[SA[next] + lcpnext] == T[SA[r] + lcpnext];
+ lcpnext++)
+ ;
+ if (lcpnext < min_match_len)
+ lcpnext = 0;
+ else if (lcpnext > max_match_len)
+ lcpnext = max_match_len;
+
+ LZ_ASSERT(lcpnext == link[r].lcpnext);
break;
}
}
* any memory that may have been allocated.
*
* @max_window_size
- * The maximum window size to support.
- *
- * In the current implementation, the memory needed will be
- * (6 * sizeof(input_idx_t) * @max_window_size) bytes.
- * For (sizeof(input_idx_t) == 4) that's 24 times the window size.
+ * The maximum window size to support. This must be greater than 0.
*
- * Memory is saved by saving neither the original window nor the LCP
- * (Longest Common Prefix) array; otherwise 29 times the window size would
- * be required. (In practice the compressor will likely keep the original
- * window around anyway, although based on this property of the
- * match-finder it theoretically it could overwrite it with the compressed
- * data.)
+ * The amount of needed memory will depend on this value; see
+ * lz_sarray_get_needed_memory() for details.
*
* @min_match_len
- * The minimum length of each match to be found.
+ * The minimum length of each match to be found. Must be greater than 0.
*
* @max_match_len
- * The maximum length of each match to be found.
+ * The maximum length of each match to be found. Must be greater than or
+ * equal to @min_match_len.
*
* @max_matches_to_consider
* The maximum number of matches to consider at each position. This should
*/
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,
+ lz_sarray_pos_t max_window_size,
+ lz_sarray_len_t min_match_len,
+ lz_sarray_len_t max_match_len,
u32 max_matches_to_consider,
u32 max_matches_to_return)
{
+ LZ_ASSERT(min_match_len > 0);
+ LZ_ASSERT(max_window_size > 0);
+ LZ_ASSERT(max_match_len >= min_match_len);
+
mf->max_window_size = max_window_size;
mf->min_match_len = min_match_len;
mf->max_match_len = max_match_len;
mf->max_matches_to_return = max_matches_to_return;
/* SA and ISA will share the same storage block. */
- mf->SA = MALLOC(2 * max_window_size * sizeof(mf->SA[0]));
+ if ((u64)2 * max_window_size * sizeof(mf->SA[0]) !=
+ 2 * max_window_size * sizeof(mf->SA[0]))
+ return false;
+ mf->SA = MALLOC(max_window_size * sizeof(mf->SA[0]) +
+ max(DIVSUFSORT_TMP1_SIZE,
+ max_window_size * sizeof(mf->SA[0])));
if (mf->SA == NULL)
return false;
- mf->salink = MALLOC(max_window_size * sizeof(mf->salink[0]));
+ if ((u64)max_window_size * sizeof(mf->salink[0]) !=
+ max_window_size * sizeof(mf->salink[0]))
+ return false;
+ mf->salink = MALLOC(max(DIVSUFSORT_TMP2_SIZE,
+ max_window_size * sizeof(mf->salink[0])));
if (mf->salink == NULL)
return false;
return true;
}
+/*
+ * Return the number of bytes of memory that lz_sarray_init() would allocate for
+ * the specified maximum window size.
+ *
+ * This should be (14 * @max_window_size) unless the type definitions have been
+ * changed.
+ */
u64
-lz_sarray_get_needed_memory(input_idx_t max_window_size)
+lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size)
{
- return (u64)6 * sizeof(input_idx_t) * max_window_size;
+ u64 size = 0;
+
+ /* SA and ISA: 8 bytes per position */
+ size += (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0]) +
+ max(DIVSUFSORT_TMP1_SIZE,
+ (u64)max_window_size * sizeof(((struct lz_sarray*)0)->SA[0]));
+
+ /* salink: 6 bytes per position */
+ size += max(DIVSUFSORT_TMP2_SIZE,
+ (u64)max_window_size * sizeof(((struct lz_sarray*)0)->salink[0]));
+
+ return size;
}
/*
* This function runs in linear time (relative to @n).
*/
void
-lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n)
+lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], lz_sarray_pos_t n)
{
- input_idx_t *ISA, *LCP;
+ lz_sarray_pos_t *ISA, *LCP;
LZ_ASSERT(n > 0 && n <= mf->max_window_size);
/* Compute SA (Suffix Array).
*
* divsufsort() needs temporary space --- one array with 256 spaces and
- * one array with 65536 spaces. The implementation has been modified
- * from the original to use the provided temporary space instead of
- * allocating its own.
+ * 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.
*
* We also check at build-time that divsufsort() uses the same integer
* size expected by this code. Unfortunately, divsufsort breaks if
* 'sa_idx_t' is defined to be a 16-bit integer; however, that would
* limit blocks to only 65536 bytes anyway. */
- LZ_ASSERT(mf->max_window_size * sizeof(mf->SA[0])
- >= 256 * sizeof(saidx_t));
- LZ_ASSERT(mf->max_window_size * sizeof(mf->salink[0])
- >= 256 * 256 * sizeof(saidx_t));
- BUILD_BUG_ON(sizeof(input_idx_t) != sizeof(saidx_t));
+ BUILD_BUG_ON(sizeof(lz_sarray_pos_t) != sizeof(saidx_t));
divsufsort(T, mf->SA, n, (saidx_t*)&mf->SA[n], (saidx_t*)mf->salink);
* end. This is probably worth it because computing the ISA from the SA
* is very fast, and since this match-finder is memory-hungry we'd like
* to save as much memory as possible. */
- ISA = (input_idx_t*)mf->salink;
+ BUILD_BUG_ON(sizeof(mf->salink[0]) < sizeof(mf->ISA[0]));
+ ISA = (lz_sarray_pos_t*)mf->salink;
compute_inverse_suffix_array(ISA, mf->SA, n);
/* Compute LCP (Longest Common Prefix) array. */
verify_lcp_array(LCP, mf->SA, T, n);
/* Initialize suffix array links. */
- init_salink(mf->salink, LCP, mf->SA, T, n, mf->max_match_len);
- verify_salink(mf->salink, mf->SA, T, n, mf->max_match_len);
+ init_salink(mf->salink, LCP, mf->SA, T, n,
+ mf->min_match_len, mf->max_match_len);
+ verify_salink(mf->salink, mf->SA, T, n,
+ mf->min_match_len, mf->max_match_len);
/* Compute ISA (Inverse Suffix Array) in its final position. */
ISA = mf->SA + n;
git://wimlib.net / wimlib / blobdiff