X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flz_sarray.c;h=3d8484e41b4bf741cefcc4604499e332e3b55121;hb=bb7fd0c1abe5459aeccf95009b9f365f80ab6c74;hp=b880f9cc45f1195cc7559e8985ac7271604b22cf;hpb=41f15b937564a3ae58f199c27e8290a1b1a40856;p=wimlib diff --git a/src/lz_sarray.c b/src/lz_sarray.c index b880f9cc..3d8484e4 100644 --- a/src/lz_sarray.c +++ b/src/lz_sarray.c @@ -5,7 +5,7 @@ */ /* - * 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 @@ -40,6 +40,9 @@ #include "divsufsort/divsufsort.h" #include +#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. * @@ -51,17 +54,17 @@ * 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; @@ -69,13 +72,13 @@ verify_suffix_array(const input_idx_t SA[restrict], /* 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)); @@ -90,14 +93,14 @@ verify_suffix_array(const input_idx_t SA[restrict], * 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 i; + lz_sarray_pos_t r; - for (i = 0; i < n; i++) - ISA[SA[i]] = i; + for (r = 0; r < n; r++) + ISA[SA[r]] = r; } @@ -111,13 +114,13 @@ compute_inverse_suffix_array(input_idx_t ISA[restrict], * 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++) { @@ -141,19 +144,19 @@ compute_lcp_array(input_idx_t LCP[restrict], * 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)); @@ -180,41 +183,111 @@ verify_lcp_array(input_idx_t LCP[restrict], * * 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; } } @@ -224,16 +297,17 @@ init_salink(struct salink link[restrict], * 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; } @@ -241,27 +315,27 @@ verify_salink(const struct salink link[], 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; } @@ -269,21 +343,20 @@ verify_salink(const struct salink link[], 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; } } @@ -301,24 +374,17 @@ verify_salink(const struct salink link[], * 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 @@ -353,12 +419,16 @@ verify_salink(const struct salink link[], */ 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; @@ -366,21 +436,48 @@ lz_sarray_init(struct lz_sarray *mf, 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; } /* @@ -397,28 +494,24 @@ lz_sarray_get_needed_memory(input_idx_t max_window_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); @@ -434,7 +527,8 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n) * 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. */ @@ -443,8 +537,10 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n) 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;