From 67e3a69b10498376108c15e5c48b8bb2fc8623e7 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Thu, 9 Jan 2014 15:04:11 -0600 Subject: [PATCH] lz_sarray: Use 16-bit length This saves 4 bytes of memory per position and only decreases the compression ratio on very repetitive files (with matches of length > 65535), and even then only slightly. Performance is not significantly affected but may be slightly improved due to better use of cache. --- NEWS | 4 +- include/wimlib/lz_sarray.h | 113 +++++++++++++------------ src/lz_sarray.c | 164 ++++++++++++++++++++----------------- src/lzms-compress.c | 7 +- 4 files changed, 161 insertions(+), 127 deletions(-) diff --git a/NEWS b/NEWS index 8dae65d6..e9d946ae 100644 --- a/NEWS +++ b/NEWS @@ -1,8 +1,6 @@ Only the most important changes more recent than version 0.6 are noted here. Version 1.6.1: - This release is minor bug-fixes only: - Stored files with size exactly 4 GiB (4,294,967,296 bytes) are now decompressed correctly. @@ -12,6 +10,8 @@ Version 1.6.1: Fixed a potential stack overflow when extracting solid archives (packed streams) containing more than about 100000 files. + Memory usage for LZMS and LZX compression has been decreased slightly. + Version 1.6.0: Support for extracting and updating the new version 3584 WIMs has been added. These WIMs typically pack many streams ("files") together into a diff --git a/include/wimlib/lz_sarray.h b/include/wimlib/lz_sarray.h index 76e6a084..6e06e42b 100644 --- a/include/wimlib/lz_sarray.h +++ b/include/wimlib/lz_sarray.h @@ -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 @@ -35,12 +35,26 @@ #define _WIMLIB_LZ_SARRAY_H #include "wimlib/compiler.h" /* must define '_always_inline_attribute' */ -#include "wimlib/lz.h" /* must define 'struct raw_match', 'input_idx_t', - and LZ_ASSERT(). */ -#include "wimlib/types.h" /* must define 'bool', 'u8', 'u32' */ +#include "wimlib/lz.h" /* must define 'struct raw_match' and LZ_ASSERT() */ +#include "wimlib/types.h" /* must define 'bool', 'u8', 'u16, and 'u32' */ struct salink; +/* Position type --- must be an unsigned type large enough to hold the length of + * longest window for which the suffix array match-finder will be used. */ +typedef u32 lz_sarray_pos_t; + +/* Length type --- must be an unsigned type large enough to hold the maximum + * match length. */ +typedef u16 lz_sarray_len_t; + +/* Cost type, for the user-provided match cost evaluation function. */ +typedef lz_sarray_pos_t lz_sarray_cost_t; + +#define LZ_SARRAY_LEN_MAX ((lz_sarray_len_t)~0UL) +#define LZ_SARRAY_POS_MAX ((lz_sarray_pos_t)~0UL) +#define LZ_SARRAY_INFINITE_COST ((lz_sarray_cost_t)~0UL) + /* State of the suffix array LZ (Lempel-Ziv) match-finder. * * This is defined here for benefit of the inlined code. It's not intended for @@ -54,13 +68,13 @@ struct lz_sarray { * sufficient to find matches. This number is the maximum length of * those arrays, or also the maximum window (block) size that can be * passed to lz_sarray_load_window(). */ - input_idx_t max_window_size; + lz_sarray_pos_t max_window_size; - /* Minimum match length to return. */ - input_idx_t min_match_len; + /* Minimum length of matches to return. */ + lz_sarray_len_t min_match_len; - /* Maximum match length to return. */ - input_idx_t max_match_len; + /* Maximum length of matches to return. */ + lz_sarray_len_t max_match_len; /* Maximum matches to consider at each position (max search depth). */ u32 max_matches_to_consider; @@ -69,19 +83,19 @@ struct lz_sarray { u32 max_matches_to_return; /* Current position in the window. */ - input_idx_t cur_pos; + lz_sarray_pos_t cur_pos; /* Current window size. */ - input_idx_t window_size; + lz_sarray_pos_t window_size; /* Suffix array for the current window. * This is a mapping from suffix rank to suffix position. */ - input_idx_t *SA; + lz_sarray_pos_t *SA; /* Inverse suffix array for the current 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; + lz_sarray_pos_t *ISA; /* Suffix array links. * @@ -99,36 +113,36 @@ 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 ~(input_idx_t)0 if + * which matches have been searched for so far, or LZ_SARRAY_POS_MAX if * there is no such suffix. * * Think of this as a pointer to the closest position in the suffix * array to the left that corresponds to a suffix that begins at a * position in the current dictionary (i.e. before the current position * in the window). */ - input_idx_t prev; + lz_sarray_pos_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 ~(input_idx_t)0 if there is - * no such suffix. + * matches have been searched for so far, or LZ_SARRAY_POS_MAX if there + * is no such suffix. * Think of this as a pointer to the closest position in the suffix * array to the right that corresponds to a suffix that begins at a * position in the current dictionary (i.e. before the current position * in the window). */ - input_idx_t next; + lz_sarray_pos_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 - * ~(input_idx_t)0. */ - input_idx_t lcpprev; + * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */ + lz_sarray_len_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 - * ~(input_idx_t)0. */ - input_idx_t lcpnext; + * LZ_SARRAY_POS_MAX. Capped to the maximum match length. */ + lz_sarray_len_t lcpnext; }; /*-----------------------------------*/ @@ -137,26 +151,26 @@ struct salink { 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, + 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); extern u64 -lz_sarray_get_needed_memory(input_idx_t max_window_size); +lz_sarray_get_needed_memory(lz_sarray_pos_t max_window_size); extern void lz_sarray_destroy(struct lz_sarray *mf); extern 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); /*-------------------*/ /* Inline functions */ /*-------------------*/ -static _always_inline_attribute input_idx_t +static _always_inline_attribute lz_sarray_pos_t lz_sarray_get_pos(const struct lz_sarray *mf) { return mf->cur_pos; @@ -164,27 +178,27 @@ lz_sarray_get_pos(const struct lz_sarray *mf) /* Advance the suffix array match-finder to the next position. */ static _always_inline_attribute void -lz_sarray_update_salink(const input_idx_t r, struct salink link[]) +lz_sarray_update_salink(const lz_sarray_pos_t r, struct salink link[]) { /* next = rank of LOWEST ranked suffix that is ranked HIGHER than the - * current suffix AND has a LOWER position, or ~(input_idx_t)0 if none + * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none * exists. */ - const input_idx_t next = link[r].next; + const lz_sarray_pos_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 ~(input_idx_t)0 if none + * current suffix AND has a LOWER position, or LZ_SARRAY_POS_MAX if none * exists. */ - const input_idx_t prev = link[r].prev; + const lz_sarray_pos_t prev = link[r].prev; /* Link the suffix at the current position into the linked list that * contains all suffixes referenced by the suffix array that appear at * or before the current position, sorted by rank. */ - if (next != ~(input_idx_t)0) { + if (next != LZ_SARRAY_POS_MAX) { link[next].prev = r; link[next].lcpprev = link[r].lcpnext; } - if (prev != ~(input_idx_t)0) { + if (prev != LZ_SARRAY_POS_MAX) { link[prev].next = r; link[prev].lcpnext = link[r].lcpprev; } @@ -198,9 +212,6 @@ lz_sarray_skip_position(struct lz_sarray *mf) lz_sarray_update_salink(mf->ISA[mf->cur_pos++], 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 matches at the * current position. @@ -221,23 +232,23 @@ 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, + (lz_sarray_pos_t length, + lz_sarray_pos_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 lz_sarray_pos_t i = mf->cur_pos++; - const input_idx_t * const restrict SA = mf->SA; - const input_idx_t * const restrict ISA = mf->ISA; + const lz_sarray_pos_t * const restrict SA = mf->SA; + const lz_sarray_pos_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 lz_sarray_pos_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]; + const lz_sarray_pos_t r = ISA[i]; /* Prepare for searching the current position. */ lz_sarray_update_salink(r, link); @@ -255,10 +266,10 @@ lz_sarray_get_matches(struct lz_sarray *mf, * 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; + lz_sarray_pos_t L = link[r].prev; + lz_sarray_pos_t R = link[r].next; + lz_sarray_pos_t lenL = link[r].lcpprev; + lz_sarray_pos_t lenR = link[r].lcpnext; /* nmatches = number of matches found so far. */ u32 nmatches = 0; @@ -290,7 +301,7 @@ lz_sarray_get_matches(struct lz_sarray *mf, if (--count_remaining == 0) goto out_save_pending; - input_idx_t offset = i - SA[L]; + lz_sarray_pos_t offset = i - SA[L]; /* Save match if it has smaller cost. */ cost = (*eval_match_cost)(lenL, offset, @@ -336,7 +347,7 @@ lz_sarray_get_matches(struct lz_sarray *mf, if (--count_remaining == 0) goto out_save_pending; - input_idx_t offset = i - SA[R]; + lz_sarray_pos_t offset = i - SA[R]; /* Save match if it has smaller cost. */ cost = (*eval_match_cost)(lenR, diff --git a/src/lz_sarray.c b/src/lz_sarray.c index 881c3c6c..5e0fa7fa 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 @@ -51,17 +51,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 +69,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,11 +90,11 @@ 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 r; + lz_sarray_pos_t r; for (r = 0; r < n; r++) ISA[SA[r]] = r; @@ -111,13 +111,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 +141,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)); @@ -183,19 +183,19 @@ verify_lcp_array(input_idx_t LCP[restrict], */ static void init_salink(struct salink link[restrict], - const input_idx_t LCP[restrict], - const input_idx_t SA[restrict], + const 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 max_match_len) { /* Compute salink.next and salink.lcpnext. */ - link[n - 1].next = ~(input_idx_t)0; + link[n - 1].next = LZ_SARRAY_POS_MAX; 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]) { + 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); t = link[t].next; } @@ -204,12 +204,12 @@ init_salink(struct salink link[restrict], } /* Compute salink.prev and salink.lcpprev. */ - link[0].prev = ~(input_idx_t)0; + link[0].prev = 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; } @@ -224,16 +224,16 @@ 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 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].prev == LZ_SARRAY_POS_MAX); LZ_ASSERT(link[r].lcpprev == 0); break; } @@ -259,9 +259,9 @@ verify_salink(const struct salink link[], } } - 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].next == LZ_SARRAY_POS_MAX); LZ_ASSERT(link[r].lcpnext == 0); break; } @@ -301,24 +301,17 @@ verify_salink(const struct salink link[], * any memory that may have been allocated. * * @max_window_size - * The maximum window size to support. + * The maximum window size to support. This must be greater than 0. * - * 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. - * - * 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 +346,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,10 +363,16 @@ 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. */ + if ((u64)2 * max_window_size * sizeof(mf->SA[0]) != + 2 * max_window_size * sizeof(mf->SA[0])) + return false; mf->SA = MALLOC(2 * max_window_size * sizeof(mf->SA[0])); if (mf->SA == NULL) return false; + if ((u64)max_window_size * sizeof(mf->salink[0]) != + max_window_size * sizeof(mf->salink[0])) + return false; mf->salink = MALLOC(max_window_size * sizeof(mf->salink[0])); if (mf->salink == NULL) return false; @@ -377,10 +380,25 @@ lz_sarray_init(struct lz_sarray *mf, return true; } +/* + * Return the number of bytes of memory that lz_sarray_init() would allocate for + * the specified maximum window size. + * + * This should be (20 * @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 * 2 * sizeof(((struct lz_sarray*)0)->SA[0]); + + /* salink: 12 bytes per position */ + size += (u64)max_window_size * sizeof(((struct lz_sarray*)0)->salink[0]); + + return size; } /* @@ -397,9 +415,9 @@ 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); @@ -418,7 +436,7 @@ lz_sarray_load_window(struct lz_sarray *mf, const u8 T[], input_idx_t n) >= 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 +452,7 @@ 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; + ISA = (lz_sarray_pos_t*)mf->salink; compute_inverse_suffix_array(ISA, mf->SA, n); /* Compute LCP (Longest Common Prefix) array. */ diff --git a/src/lzms-compress.c b/src/lzms-compress.c index 6f17f5db..2f87fd43 100644 --- a/src/lzms-compress.c +++ b/src/lzms-compress.c @@ -1179,6 +1179,9 @@ static const struct wimlib_lzms_compressor_params lzms_default = { .optim_array_length = 1024, }; +static bool +lzms_params_valid(const struct wimlib_compressor_params_header *); + static const struct wimlib_lzms_compressor_params * lzms_get_params(const struct wimlib_compressor_params_header *_params) { @@ -1188,6 +1191,8 @@ lzms_get_params(const struct wimlib_compressor_params_header *_params) if (params == NULL) params = &lzms_default; + LZMS_ASSERT(lzms_params_valid(¶ms->hdr)); + return params; } @@ -1221,7 +1226,7 @@ lzms_create_compressor(size_t max_block_size, if (!lz_sarray_init(&ctx->lz_sarray, max_block_size, params->min_match_length, - params->max_match_length, + min(params->max_match_length, LZ_SARRAY_LEN_MAX), params->max_search_depth, params->max_matches_per_pos)) goto oom; -- 2.43.0