X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzx-compress.c;h=c72fd460c84d47a4612fde0214499acad1d17f5c;hp=c7c18b6090d7ab6e890cfc9df4c03e42a917ac82;hb=69bf8e6b27c11c8dfb0e9794ea43c3b8af72ee38;hpb=01e2459ae40d90bc1ab1b39829d4ef6686a213a0 diff --git a/src/lzx-compress.c b/src/lzx-compress.c index c7c18b60..c72fd460 100644 --- a/src/lzx-compress.c +++ b/src/lzx-compress.c @@ -42,7 +42,8 @@ * and certain other details are quite similar, such as the method for storing * Huffman codes. However, some of the main differences are: * - * - LZX preprocesses the data before attempting to compress it. + * - LZX preprocesses the data to attempt to make x86 machine code slightly more + * compressible before attempting to compress it further. * - LZX uses a "main" alphabet which combines literals and matches, with the * match symbols containing a "length header" (giving all or part of the match * length) and a "position slot" (giving, roughly speaking, the order of @@ -51,7 +52,8 @@ * dynamic Huffman blocks ("aligned offset" and "verbatim"). * - LZX has a minimum match length of 2 rather than 3. * - In LZX, match offsets 0 through 2 actually represent entries in an LRU - * queue of match offsets. + * queue of match offsets. This is very useful for certain types of files, + * such as binary files that have repeating records. * * Algorithms * ========== @@ -66,34 +68,39 @@ * * The "slow" algorithm to generate LZX-compressed data is roughly as follows: * - * 1. Preprocess the input data to translate the targets of x86 call instructions - * to absolute offsets. + * 1. Preprocess the input data to translate the targets of x86 call + * instructions to absolute offsets. * - * 2. Build the suffix array and inverse suffix array for the input data. + * 2. Build the suffix array and inverse suffix array for the input data. The + * suffix array contains the indices of all suffixes of the input data, + * sorted lexcographically by the corresponding suffixes. The "position" of + * a suffix is the index of that suffix in the original string, whereas the + * "rank" of a suffix is the index at which that suffix's position is found + * in the suffix array. * * 3. Build the longest common prefix array corresponding to the suffix array. * - * 4. For each suffix rank, find the highest lower suffix rank that has a - * lower position, the lowest higher suffix rank that has a lower position, - * and the length of the common prefix shared between each. (Position = - * index of suffix in original string, rank = index of suffix in suffix - * array.) This information is later used to link suffix ranks into a - * doubly-linked list for searching the suffix array. + * 4. For each suffix, find the highest lower ranked suffix that has a lower + * position, the lowest higher ranked suffix that has a lower position, and + * the length of the common prefix shared between each. This information is + * later used to link suffix ranks into a doubly-linked list for searching + * the suffix array. * * 5. Set a default cost model for matches/literals. * - * 6. Determine the lowest cost sequence of LZ77 matches ((offset, length) pairs) - * and literal bytes to divide the input into. Raw match-finding is done by - * searching the suffix array using a linked list to avoid considering any - * suffixes that start after the current position. Each run of the - * match-finder returns the lowest-cost longest match as well as any shorter - * matches that have even lower costs. Each such run also adds the suffix - * rank of the current position into the linked list being used to search the - * suffix array. Parsing, or match-choosing, is solved as a minimum-cost - * path problem using a forward "optimal parsing" algorithm based on the - * Deflate encoder from 7-Zip. This algorithm moves forward calculating the - * minimum cost to reach each byte until either a very long match is found or - * until a position is found at which no matches start or overlap. + * 6. Determine the lowest cost sequence of LZ77 matches ((offset, length) + * pairs) and literal bytes to divide the input into. Raw match-finding is + * done by searching the suffix array using a linked list to avoid + * considering any suffixes that start after the current position. Each run + * of the match-finder returns the approximate lowest-cost longest match as + * well as any shorter matches that have even lower approximate costs. Each + * such run also adds the suffix rank of the current position into the linked + * list being used to search the suffix array. Parsing, or match-choosing, + * is solved as a minimum-cost path problem using a forward "optimal parsing" + * algorithm based on the Deflate encoder from 7-Zip. This algorithm moves + * forward calculating the minimum cost to reach each byte until either a + * very long match is found or until a position is found at which no matches + * start or overlap. * * 7. Build the Huffman codes needed to output the matches/literals. * @@ -104,20 +111,24 @@ * 9. Output the resulting block using the match/literal sequences and the * Huffman codes that were computed for the block. * + * Note: the algorithm does not yet attempt to split the input into multiple LZX + * blocks, instead using a series of blocks of LZX_DIV_BLOCK_SIZE bytes. + * * Fast algorithm * -------------- * * The fast algorithm (and the only one available in wimlib v1.5.1 and earlier) * spends much less time on the main bottlenecks of the compression process --- - * that is the match finding, match choosing, and block splitting. Matches are - * found and chosen with hash chains using a greedy parse with one position of - * look-ahead. No block splitting is done; only compressing the full input into - * an aligned offset block is considered. + * that is, the match finding and match choosing. Matches are found and chosen + * with hash chains using a greedy parse with one position of look-ahead. No + * block splitting is done; only compressing the full input into an aligned + * offset block is considered. * * API * === * - * The old API (retained for backward compatibility) consists of just one function: + * The old API (retained for backward compatibility) consists of just one + * function: * * wimlib_lzx_compress() * @@ -128,20 +139,24 @@ * wimlib_lzx_alloc_context() * wimlib_lzx_compress2() * wimlib_lzx_free_context() + * wimlib_lzx_set_default_params() * * Both wimlib_lzx_compress() and wimlib_lzx_compress2() are designed to - * compress an in-memory buffer of up to 32768 bytes. There is no sliding - * window. This is suitable for the WIM format, which uses fixed-size chunks - * that are seemingly always 32768 bytes. If needed, the compressor potentially - * could be extended to support a larger and/or sliding window. + * compress an in-memory buffer of up to the window size, which can be any power + * of two between 2^15 and 2^21 inclusively. However, by default, the WIM + * format uses 2^15, and this is seemingly the only value that is compatible + * with WIMGAPI. In any case, the window is not a true "sliding window" since + * no data is ever "slid out" of the window. This is needed for the WIM format, + * which is designed such that chunks may be randomly accessed. * * Both wimlib_lzx_compress() and wimlib_lzx_compress2() return 0 if the data * could not be compressed to less than the size of the uncompressed data. * Again, this is suitable for the WIM format, which stores such data chunks * uncompressed. * - * The functions in this API are exported from the library, although this is - * only in case other programs happen to have uses for it other than WIM + * The functions in this LZX compression API are exported from the library, + * although with the possible exception of wimlib_lzx_set_default_params(), this + * is only in case other programs happen to have uses for it other than WIM * reading/writing as already handled through the rest of the library. * * Acknowledgments @@ -150,7 +165,8 @@ * Acknowledgments to several open-source projects and research papers that made * it possible to implement this code: * - * - divsufsort (author: Yuta Mori), for the suffix array construction code. + * - divsufsort (author: Yuta Mori), for the suffix array construction code, + * located in a separate directory (divsufsort/). * * - "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its * Applications" (Kasai et al. 2001), for the LCP array computation. @@ -162,7 +178,7 @@ * (match-choosing). * * - zlib (author: Jean-loup Gailly and Mark Adler), for the hash table - * match-finding algorithm. + * match-finding algorithm (used in lz77.c). * * - lzx-compress (author: Matthew T. Russotto), on which some parts of this * code were originally based. @@ -174,6 +190,7 @@ #include "wimlib.h" #include "wimlib/compress.h" +#include "wimlib/endianness.h" #include "wimlib/error.h" #include "wimlib/lzx.h" #include "wimlib/util.h" @@ -182,32 +199,23 @@ #include #ifdef ENABLE_LZX_DEBUG -# include +# include "wimlib/decompress.h" #endif #include "divsufsort/divsufsort.h" -typedef freq_t input_idx_t; -typedef u32 sym_cost_t; typedef u32 block_cost_t; -#define INFINITE_SYM_COST ((sym_cost_t)~0U) #define INFINITE_BLOCK_COST ((block_cost_t)~0U) #define LZX_OPTIM_ARRAY_SIZE 4096 -/* Currently, this constant can't simply be changed because the code currently - * uses a static number of position slots (and may make other assumptions as - * well). */ -#define LZX_MAX_WINDOW_SIZE 32768 - -/* This may be WIM-specific */ -#define LZX_DEFAULT_BLOCK_SIZE 32768 +#define LZX_DIV_BLOCK_SIZE 32768 #define LZX_MAX_CACHE_PER_POS 10 /* Codewords for the LZX main, length, and aligned offset Huffman codes */ struct lzx_codewords { - u16 main[LZX_MAINCODE_NUM_SYMBOLS]; + u16 main[LZX_MAINCODE_MAX_NUM_SYMBOLS]; u16 len[LZX_LENCODE_NUM_SYMBOLS]; u16 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; }; @@ -218,7 +226,7 @@ struct lzx_codewords { * A 0 length means the codeword has zero frequency. */ struct lzx_lens { - u8 main[LZX_MAINCODE_NUM_SYMBOLS]; + u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS]; u8 len[LZX_LENCODE_NUM_SYMBOLS]; u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; }; @@ -229,9 +237,9 @@ struct lzx_lens { * --- generally a high cost, since even if it gets used in the next iteration, * it probably will not be used very times. */ struct lzx_costs { - sym_cost_t main[LZX_MAINCODE_NUM_SYMBOLS]; - sym_cost_t len[LZX_LENCODE_NUM_SYMBOLS]; - sym_cost_t aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; + u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS]; + u8 len[LZX_LENCODE_NUM_SYMBOLS]; + u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; }; /* The LZX main, length, and aligned offset Huffman codes */ @@ -242,9 +250,9 @@ struct lzx_codes { /* Tables for tallying symbol frequencies in the three LZX alphabets */ struct lzx_freqs { - freq_t main[LZX_MAINCODE_NUM_SYMBOLS]; - freq_t len[LZX_LENCODE_NUM_SYMBOLS]; - freq_t aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; + input_idx_t main[LZX_MAINCODE_MAX_NUM_SYMBOLS]; + input_idx_t len[LZX_LENCODE_NUM_SYMBOLS]; + input_idx_t aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS]; }; /* LZX intermediate match/literal format */ @@ -258,7 +266,7 @@ struct lzx_match { * * 8-24 position footer. This is the offset of the real formatted * offset from the position base. This can be at most 17 bits - * (since lzx_extra_bits[LZX_NUM_POSITION_SLOTS - 1] is 17). + * (since lzx_extra_bits[LZX_MAX_POSITION_SLOTS - 1] is 17). * * 0-7 length of match, minus 2. This can be at most * (LZX_MAX_MATCH_LEN - 2) == 255, so it will fit in 8 bits. */ @@ -385,20 +393,27 @@ struct lzx_compressor { * 0xe8 byte preprocessing is done directly on the data here before * further compression. * - * Note that this compressor does *not* use a sliding window!!!! It's - * not needed in the WIM format, since every chunk is compressed + * Note that this compressor does *not* use a real sliding window!!!! + * It's not needed in the WIM format, since every chunk is compressed * independently. This is by design, to allow random access to the * chunks. * * We reserve a few extra bytes to potentially allow reading off the end * of the array in the match-finding code for optimization purposes. */ - u8 window[LZX_MAX_WINDOW_SIZE + 12]; + u8 *window; /* Number of bytes of data to be compressed, which is the number of * bytes of data in @window that are actually valid. */ input_idx_t window_size; + /* Allocated size of the @window. */ + input_idx_t max_window_size; + + /* Number of symbols in the main alphabet (depends on the + * @max_window_size since it determines the maximum allowed offset). */ + unsigned num_main_syms; + /* The current match offset LRU queue. */ struct lzx_lru_queue queue; @@ -406,10 +421,6 @@ struct lzx_compressor { * block. */ struct lzx_match *chosen_matches; - struct raw_match *cached_matches; - unsigned cached_matches_pos; - bool matches_cached; - /* Information about the LZX blocks the preprocessed input was divided * into. */ struct lzx_block_spec *block_specs; @@ -424,29 +435,28 @@ struct lzx_compressor { * codewords. */ struct lzx_codes zero_codes; - /* Slow algorithm only: The current cost model. */ + /* The current cost model. */ struct lzx_costs costs; - /* Slow algorithm only: Suffix array for window. - * This is a mapping from suffix rank to suffix position. - * - * Suffix rank means the index of the suffix in the sorted list of - * suffixes, whereas suffix position means the index in the string at - * which the suffix starts. - */ + /* Fast algorithm only: Array of hash table links. */ + input_idx_t *prev_tab; + + /* Suffix array for window. + * This is a mapping from suffix rank to suffix position. */ input_idx_t *SA; - /* Slow algorithm only: Inverse suffix array for window. + /* Inverse suffix array for window. * This is a mapping from suffix position to suffix rank. - * In other words, if 0 <= r < window_size, then ISA[SA[r]] == r. */ + * If 0 <= r < window_size, then ISA[SA[r]] == r. */ input_idx_t *ISA; - /* Slow algorithm only: Longest Common Prefix array. LCP[i] is the - * number of initial bytes that the suffixes at positions SA[i - 1] and - * SA[i] share. LCP[0] is undefined. */ + /* 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; - /* Slow algorithm only: Suffix array links. + /* 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 @@ -455,17 +465,22 @@ struct lzx_compressor { * list containing only suffixes that appear before that position. */ struct salink *salink; - /* Slow algorithm only: Position in window of next match to return. - * This cannot simply be modified, as the match-finder must still be - * synchronized on the same position. To seek forwards or backwards, - * use lzx_lz_skip_bytes() or lzx_lz_rewind_matchfinder(), respectively. - */ + /* Position in window of next match to return. */ input_idx_t match_window_pos; - /* Slow algorithm only: The match-finder shall ensure the length of - * matches does not exceed this position in the input. */ + /* The match-finder shall ensure the length of matches does not exceed + * this position in the input. */ input_idx_t match_window_end; + /* Matches found by the match-finder are cached in the following array + * to achieve a slight speedup when the same matches are needed on + * subsequent passes. This is suboptimal because different matches may + * be preferred with different cost models, but seems to be a worthwhile + * speedup. */ + struct raw_match *cached_matches; + unsigned cached_matches_pos; + bool matches_cached; + /* Slow algorithm only: Temporary space used for match-choosing * algorithm. * @@ -485,49 +500,10 @@ struct lzx_compressor { u32 optimum_end_idx; }; -/* Returns the LZX position slot that corresponds to a given formatted offset. - * - * Logically, this returns the smallest i such that - * formatted_offset >= lzx_position_base[i]. - * - * The actual implementation below takes advantage of the regularity of the - * numbers in the lzx_position_base array to calculate the slot directly from - * the formatted offset without actually looking at the array. - */ -static _always_inline_attribute unsigned -lzx_get_position_slot_raw(unsigned formatted_offset) -{ -#if 0 - /* - * Slots 36-49 (formatted_offset >= 262144) can be found by - * (formatted_offset/131072) + 34 == (formatted_offset >> 17) + 34; - * however, this check for formatted_offset >= 262144 is commented out - * because WIM chunks cannot be that large. - */ - if (formatted_offset >= 262144) { - return (formatted_offset >> 17) + 34; - } else -#endif - { - /* Note: this part here only works if: - * - * 2 <= formatted_offset < 655360 - * - * It is < 655360 because the frequency of the position bases - * increases starting at the 655360 entry, and it is >= 2 - * because the below calculation fails if the most significant - * bit is lower than the 2's place. */ - LZX_ASSERT(2 <= formatted_offset && formatted_offset < 655360); - unsigned mssb_idx = bsr32(formatted_offset); - return (mssb_idx << 1) | - ((formatted_offset >> (mssb_idx - 1)) & 1); - } -} - - /* Returns the LZX position slot that corresponds to a given match offset, - * taking into account the recent offset queue (and optionally updating it). */ -static _always_inline_attribute unsigned + * taking into account the recent offset queue and updating it if the offset is + * found in it. */ +static unsigned lzx_get_position_slot(unsigned offset, struct lzx_lru_queue *queue) { unsigned position_slot; @@ -542,9 +518,9 @@ lzx_get_position_slot(unsigned offset, struct lzx_lru_queue *queue) * LRU queue because repeat matches are simply * swapped to the front. */ swap(queue->R[0], queue->R[i]); - /* For recent offsets, the position slot is simply the - * index of the entry in the queue. */ + /* The resulting position slot is simply the first index + * at which the offset was found in the queue. */ return i; } } @@ -566,9 +542,10 @@ lzx_get_position_slot(unsigned offset, struct lzx_lru_queue *queue) * a set of tables that map symbols to codewords and codeword lengths. */ static void lzx_make_huffman_codes(const struct lzx_freqs *freqs, - struct lzx_codes *codes) + struct lzx_codes *codes, + unsigned num_main_syms) { - make_canonical_huffman_code(LZX_MAINCODE_NUM_SYMBOLS, + make_canonical_huffman_code(num_main_syms, LZX_MAX_MAIN_CODEWORD_LEN, freqs->main, codes->lens.main, @@ -633,7 +610,7 @@ lzx_write_match(struct output_bitstream *out, int block_type, } /* Combine the position slot with the length header into a single symbol - * that will be encoded with the main tree. + * that will be encoded with the main code. * * The actual main symbol is offset by LZX_NUM_CHARS because values * under LZX_NUM_CHARS are used to indicate a literal byte rather than a @@ -655,7 +632,7 @@ lzx_write_match(struct output_bitstream *out, int block_type, /* For aligned offset blocks with at least 3 extra bits, output the * verbatim bits literally, then the aligned bits encoded using the - * aligned offset tree. Otherwise, only the verbatim bits need to be + * aligned offset code. Otherwise, only the verbatim bits need to be * output. */ if ((block_type == LZX_BLOCKTYPE_ALIGNED) && (num_extra_bits >= 3)) { @@ -678,7 +655,7 @@ static unsigned lzx_build_precode(const u8 lens[restrict], const u8 prev_lens[restrict], const unsigned num_syms, - freq_t precode_freqs[restrict LZX_PRECODE_NUM_SYMBOLS], + input_idx_t precode_freqs[restrict LZX_PRECODE_NUM_SYMBOLS], u8 output_syms[restrict num_syms], u8 precode_lens[restrict LZX_PRECODE_NUM_SYMBOLS], u16 precode_codewords[restrict LZX_PRECODE_NUM_SYMBOLS], @@ -694,7 +671,7 @@ lzx_build_precode(const u8 lens[restrict], * literally. * * output_syms[] will be filled in with the length symbols that will be - * output, including RLE codes, not yet encoded using the pre-tree. + * output, including RLE codes, not yet encoded using the precode. * * cur_run_len keeps track of how many code word lengths are in the * current run of identical lengths. */ @@ -760,7 +737,7 @@ lzx_build_precode(const u8 lens[restrict], * * The extra length symbol is encoded as a difference * from the length of the codeword for the first symbol - * in the run in the previous tree. + * in the run in the previous code. * */ while (cur_run_len >= 4) { unsigned additional_bits; @@ -783,7 +760,7 @@ lzx_build_precode(const u8 lens[restrict], /* Any remaining lengths in the run are outputted without RLE, * as a difference from the length of that codeword in the - * previous tree. */ + * previous code. */ while (cur_run_len > 0) { signed char delta; @@ -837,7 +814,7 @@ lzx_write_compressed_code(struct output_bitstream *out, const u8 prev_lens[restrict], unsigned num_syms) { - freq_t precode_freqs[LZX_PRECODE_NUM_SYMBOLS]; + input_idx_t precode_freqs[LZX_PRECODE_NUM_SYMBOLS]; u8 output_syms[num_syms]; u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS]; u16 precode_codewords[LZX_PRECODE_NUM_SYMBOLS]; @@ -929,12 +906,12 @@ lzx_write_matches_and_literals(struct output_bitstream *ostream, } static void -lzx_assert_codes_valid(const struct lzx_codes * codes) +lzx_assert_codes_valid(const struct lzx_codes * codes, unsigned num_main_syms) { #ifdef ENABLE_LZX_DEBUG unsigned i; - for (i = 0; i < LZX_MAINCODE_NUM_SYMBOLS; i++) + for (i = 0; i < num_main_syms; i++) LZX_ASSERT(codes->lens.main[i] <= LZX_MAX_MAIN_CODEWORD_LEN); for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++) @@ -945,10 +922,10 @@ lzx_assert_codes_valid(const struct lzx_codes * codes) const unsigned tablebits = 10; u16 decode_table[(1 << tablebits) + - (2 * max(LZX_MAINCODE_NUM_SYMBOLS, LZX_LENCODE_NUM_SYMBOLS))] + (2 * max(num_main_syms, LZX_LENCODE_NUM_SYMBOLS))] _aligned_attribute(DECODE_TABLE_ALIGNMENT); LZX_ASSERT(0 == make_huffman_decode_table(decode_table, - LZX_MAINCODE_NUM_SYMBOLS, + num_main_syms, min(tablebits, LZX_MAINCODE_TABLEBITS), codes->lens.main, LZX_MAX_MAIN_CODEWORD_LEN)); @@ -969,6 +946,8 @@ lzx_assert_codes_valid(const struct lzx_codes * codes) static void lzx_write_compressed_block(int block_type, unsigned block_size, + unsigned max_window_size, + unsigned num_main_syms, struct lzx_match * chosen_matches, unsigned num_chosen_matches, const struct lzx_codes * codes, @@ -979,27 +958,41 @@ lzx_write_compressed_block(int block_type, LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED || block_type == LZX_BLOCKTYPE_VERBATIM); - LZX_ASSERT(block_size <= LZX_MAX_WINDOW_SIZE); - LZX_ASSERT(num_chosen_matches <= LZX_MAX_WINDOW_SIZE); - lzx_assert_codes_valid(codes); + lzx_assert_codes_valid(codes, num_main_syms); /* The first three bits indicate the type of block and are one of the * LZX_BLOCKTYPE_* constants. */ - bitstream_put_bits(ostream, block_type, LZX_BLOCKTYPE_NBITS); + bitstream_put_bits(ostream, block_type, 3); - /* The next bit indicates whether the block size is the default (32768), - * indicated by a 1 bit, or whether the block size is given by the next - * 16 bits, indicated by a 0 bit. */ + /* Output the block size. + * + * The original LZX format seemed to always encode the block size in 3 + * bytes. However, the implementation in WIMGAPI, as used in WIM files, + * uses the first bit to indicate whether the block is the default size + * (32768) or a different size given explicitly by the next 16 bits. + * + * By default, this compressor uses a window size of 32768 and therefore + * follows the WIMGAPI behavior. However, this compressor also supports + * window sizes greater than 32768 bytes, which do not appear to be + * supported by WIMGAPI. In such cases, we retain the default size bit + * to mean a size of 32768 bytes but output non-default block size in 24 + * bits rather than 16. The compatibility of this behavior is unknown + * because WIMs created with chunk size greater than 32768 can seemingly + * only be opened by wimlib anyway. */ if (block_size == LZX_DEFAULT_BLOCK_SIZE) { bitstream_put_bits(ostream, 1, 1); } else { bitstream_put_bits(ostream, 0, 1); - bitstream_put_bits(ostream, block_size, LZX_BLOCKSIZE_NBITS); + + if (max_window_size >= 65536) + bitstream_put_bits(ostream, block_size >> 16, 8); + + bitstream_put_bits(ostream, block_size, 16); } /* Write out lengths of the main code. Note that the LZX specification * incorrectly states that the aligned offset code comes after the - * length code, but in fact it is the very first tree to be written + * length code, but in fact it is the very first code to be written * (before the main code). */ if (block_type == LZX_BLOCKTYPE_ALIGNED) for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) @@ -1008,23 +1001,23 @@ lzx_write_compressed_block(int block_type, LZX_DEBUG("Writing main code..."); - /* Write the pre-tree and lengths for the first LZX_NUM_CHARS symbols in + /* Write the precode and lengths for the first LZX_NUM_CHARS symbols in * the main code, which are the codewords for literal bytes. */ lzx_write_compressed_code(ostream, codes->lens.main, prev_codes->lens.main, LZX_NUM_CHARS); - /* Write the pre-tree and lengths for the rest of the main code, which + /* Write the precode and lengths for the rest of the main code, which * are the codewords for match headers. */ lzx_write_compressed_code(ostream, codes->lens.main + LZX_NUM_CHARS, prev_codes->lens.main + LZX_NUM_CHARS, - LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS); + num_main_syms - LZX_NUM_CHARS); LZX_DEBUG("Writing length code..."); - /* Write the pre-tree and lengths for the length code. */ + /* Write the precode and lengths for the length code. */ lzx_write_compressed_code(ostream, codes->lens.len, prev_codes->lens.len, @@ -1044,6 +1037,7 @@ lzx_write_compressed_block(int block_type, static void lzx_write_all_blocks(struct lzx_compressor *ctx, struct output_bitstream *ostream) { + const struct lzx_codes *prev_codes = &ctx->zero_codes; for (unsigned i = 0; i < ctx->num_blocks; i++) { const struct lzx_block_spec *spec = &ctx->block_specs[i]; @@ -1055,11 +1049,14 @@ lzx_write_all_blocks(struct lzx_compressor *ctx, struct output_bitstream *ostrea lzx_write_compressed_block(spec->block_type, spec->block_size, + ctx->max_window_size, + ctx->num_main_syms, &ctx->chosen_matches[spec->chosen_matches_start_pos], spec->num_chosen_matches, &spec->codes, prev_codes, ostream); + prev_codes = &spec->codes; } } @@ -1067,13 +1064,10 @@ lzx_write_all_blocks(struct lzx_compressor *ctx, struct output_bitstream *ostrea /* Constructs an LZX match from a literal byte and updates the main code symbol * frequencies. */ static u32 -lzx_record_literal(u8 literal, void *_freqs) +lzx_tally_literal(u8 lit, struct lzx_freqs *freqs) { - struct lzx_freqs *freqs = _freqs; - - freqs->main[literal]++; - - return (u32)literal; + freqs->main[lit]++; + return (u32)lit; } /* Constructs an LZX match from an offset and a length, and updates the LRU @@ -1081,11 +1075,9 @@ lzx_record_literal(u8 literal, void *_freqs) * alphabets. The return value is a 32-bit number that provides the match in an * intermediate representation documented below. */ static u32 -lzx_record_match(unsigned match_offset, unsigned match_len, - void *_freqs, void *_queue) +lzx_tally_match(unsigned match_len, unsigned match_offset, + struct lzx_freqs *freqs, struct lzx_lru_queue *queue) { - struct lzx_freqs *freqs = _freqs; - struct lzx_lru_queue *queue = _queue; unsigned position_slot; unsigned position_footer; u32 len_header; @@ -1134,34 +1126,46 @@ lzx_record_match(unsigned match_offset, unsigned match_len, freqs->aligned[position_footer & 7]++; /* Pack the position slot, position footer, and match length into an - * intermediate representation. - * - * bits description - * ---- ----------------------------------------------------------- - * - * 31 1 if a match, 0 if a literal. - * - * 30-25 position slot. This can be at most 50, so it will fit in 6 - * bits. - * - * 8-24 position footer. This is the offset of the real formatted - * offset from the position base. This can be at most 17 bits - * (since lzx_extra_bits[LZX_NUM_POSITION_SLOTS - 1] is 17). - * - * 0-7 length of match, offset by 2. This can be at most - * (LZX_MAX_MATCH_LEN - 2) == 255, so it will fit in 8 bits. */ - BUILD_BUG_ON(LZX_NUM_POSITION_SLOTS > 64); - LZX_ASSERT(lzx_get_num_extra_bits(LZX_NUM_POSITION_SLOTS - 1) <= 17); - BUILD_BUG_ON(LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1 > 256); + * intermediate representation. See `struct lzx_match' for details. + */ + LZX_ASSERT(LZX_MAX_POSITION_SLOTS <= 64); + LZX_ASSERT(lzx_get_num_extra_bits(LZX_MAX_POSITION_SLOTS - 1) <= 17); + LZX_ASSERT(LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1 <= 256); + + LZX_ASSERT(position_slot <= (1U << (31 - 25)) - 1); + LZX_ASSERT(position_footer <= (1U << (25 - 8)) - 1); + LZX_ASSERT(adjusted_match_len <= (1U << (8 - 0)) - 1); return 0x80000000 | (position_slot << 25) | (position_footer << 8) | (adjusted_match_len); } +struct lzx_record_ctx { + struct lzx_freqs freqs; + struct lzx_lru_queue queue; + struct lzx_match *matches; +}; + +static void +lzx_record_match(unsigned len, unsigned offset, void *_ctx) +{ + struct lzx_record_ctx *ctx = _ctx; + + (ctx->matches++)->data = lzx_tally_match(len, offset, &ctx->freqs, &ctx->queue); +} + +static void +lzx_record_literal(u8 lit, void *_ctx) +{ + struct lzx_record_ctx *ctx = _ctx; + + (ctx->matches++)->data = lzx_tally_literal(lit, &ctx->freqs); +} + /* Returns the cost, in bits, to output a literal byte using the specified cost * model. */ -static sym_cost_t +static unsigned lzx_literal_cost(u8 c, const struct lzx_costs * costs) { return costs->main[c]; @@ -1172,18 +1176,18 @@ lzx_literal_cost(u8 c, const struct lzx_costs * costs) * codes, return the approximate number of bits it will take to represent this * match in the compressed output. Take into account the match offset LRU * queue and optionally update it. */ -static sym_cost_t +static unsigned lzx_match_cost(unsigned length, unsigned offset, const struct lzx_costs *costs, struct lzx_lru_queue *queue) { unsigned position_slot; unsigned len_header, main_symbol; - sym_cost_t cost = 0; + unsigned cost = 0; position_slot = lzx_get_position_slot(offset, queue); len_header = min(length - LZX_MIN_MATCH_LEN, LZX_NUM_PRIMARY_LENS); - main_symbol = (position_slot << 3) | len_header | LZX_NUM_CHARS; + main_symbol = ((position_slot << 3) | len_header) + LZX_NUM_CHARS; /* Account for main symbol. */ cost += costs->main[main_symbol]; @@ -1205,16 +1209,19 @@ lzx_match_cost(unsigned length, unsigned offset, const struct lzx_costs *costs, } -/* Very fast heuristic cost evaluation to use in the inner loop of the - * match-finder. */ -static sym_cost_t +/* Fast heuristic cost evaluation to use in the inner loop of the match-finder. + * Unlike lzx_match_cost() which does a true cost evaluation, this simply + * prioritize matches based on their offset. */ +static block_cost_t lzx_match_cost_fast(unsigned offset, const struct lzx_lru_queue *queue) { + /* It seems well worth it to take the time to give priority to recently + * used offsets. */ for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++) if (offset == queue->R[i]) return i; - BUILD_BUG_ON(LZX_MAX_WINDOW_SIZE >= (sym_cost_t)~0U); + BUILD_BUG_ON(LZX_MAX_WINDOW_SIZE >= (block_cost_t)~0U); return offset; } @@ -1231,9 +1238,10 @@ static void lzx_set_costs(struct lzx_compressor * ctx, const struct lzx_lens * lens) { unsigned i; + unsigned num_main_syms = ctx->num_main_syms; /* Main code */ - for (i = 0; i < LZX_MAINCODE_NUM_SYMBOLS; i++) { + for (i = 0; i < num_main_syms; i++) { ctx->costs.main[i] = lens->main[i]; if (ctx->costs.main[i] == 0) ctx->costs.main[i] = ctx->params.alg_params.slow.main_nostat_cost; @@ -1291,25 +1299,6 @@ lzx_lz_update_salink(input_idx_t i, } } -/* Rewind the suffix array match-finder to the specified position. - * - * This undoes a series of updates by lzx_lz_update_salink(). */ -static void -lzx_lz_rewind_matchfinder(struct lzx_compressor *ctx, - const unsigned orig_pos) -{ - LZX_DEBUG("Rewind match-finder %u => %u", ctx->match_window_pos, orig_pos); - - if (ctx->match_window_pos == orig_pos) - return; - - LZX_ASSERT(ctx->match_window_pos > orig_pos); - LZX_ASSERT(orig_pos == 0); - ctx->matches_cached = true; - ctx->cached_matches_pos = 0; - ctx->match_window_pos = orig_pos; -} - /* * Use the suffix array match-finder to retrieve a list of LZ matches at the * current position. @@ -1338,8 +1327,8 @@ lzx_lz_get_matches(const input_idx_t i, struct raw_match matches[const restrict], const struct lzx_lru_queue * const restrict queue, const unsigned min_match_len, - const uint32_t max_matches_to_consider, - const uint32_t max_matches_to_return) + const u32 max_matches_to_consider, + const u32 max_matches_to_return) { /* r = Rank of the suffix at the current position. */ const input_idx_t r = ISA[i]; @@ -1373,21 +1362,21 @@ lzx_lz_get_matches(const input_idx_t i, * We keep track of this so that we can ignore shorter matches that do * not have lower costs than a longer matches already found. */ - sym_cost_t best_cost = INFINITE_SYM_COST; + block_cost_t best_cost = INFINITE_BLOCK_COST; /* count_remaining = maximum number of possible matches remaining to be * considered. */ - uint32_t count_remaining = max_matches_to_consider; + u32 count_remaining = max_matches_to_consider; /* pending = match currently being considered for a specific length. */ struct raw_match pending; + block_cost_t pending_cost; while (lenL >= min_match_len || lenR >= min_match_len) { pending.len = lenL; - pending.offset = (input_idx_t)~0U; - sym_cost_t pending_cost = INFINITE_SYM_COST; - sym_cost_t cost; + pending_cost = INFINITE_BLOCK_COST; + block_cost_t cost; /* Extend left. */ if (lenL >= min_match_len && lenL >= lenR) { @@ -1423,8 +1412,7 @@ lzx_lz_get_matches(const input_idx_t i, return nmatches; } pending.len = lenL; - pending.offset = (input_idx_t)~0U; - pending_cost = INFINITE_SYM_COST; + pending_cost = INFINITE_BLOCK_COST; } if (lenL < min_match_len || lenL < lenR) break; @@ -1470,8 +1458,7 @@ lzx_lz_get_matches(const input_idx_t i, break; pending.len = lenR; - pending.offset = (input_idx_t)~0U; - pending_cost = INFINITE_SYM_COST; + pending_cost = INFINITE_BLOCK_COST; } R = link[R].next; } @@ -1480,7 +1467,7 @@ lzx_lz_get_matches(const input_idx_t i, goto out; out_save_pending: - if (pending.offset != (input_idx_t)~0U) + if (pending_cost != INFINITE_BLOCK_COST) matches[nmatches++] = pending; out: @@ -1529,10 +1516,10 @@ lzx_lz_get_matches_caching(struct lzx_compressor *ctx, num_matches = matches[-1].len; } else { unsigned min_match_len = LZX_MIN_MATCH_LEN; - if (min_match_len <= 2 && !ctx->params.alg_params.slow.use_len2_matches) - min_match_len = 3; - const uint32_t max_search_depth = ctx->params.alg_params.slow.max_search_depth; - const uint32_t max_matches_per_pos = ctx->params.alg_params.slow.max_matches_per_pos; + if (!ctx->params.alg_params.slow.use_len2_matches) + min_match_len = max(min_match_len, 3); + const u32 max_search_depth = ctx->params.alg_params.slow.max_search_depth; + const u32 max_matches_per_pos = ctx->params.alg_params.slow.max_matches_per_pos; if (unlikely(max_search_depth == 0 || max_matches_per_pos == 0)) num_matches = 0; @@ -1636,8 +1623,9 @@ lzx_lz_reverse_near_optimal_match_list(struct lzx_compressor *ctx, * model rather than simply assuming that longer is better. * * Still, this is not truly an optimal parser because very long matches are - * taken immediately. This is done to avoid considering many different - * alternatives that are unlikely to significantly be better. + * taken immediately, and the raw match-finder takes some shortcuts. This is + * done to avoid considering many different alternatives that are unlikely to + * be significantly better. * * This algorithm is based on that used in 7-Zip's DEFLATE encoder. * @@ -1659,14 +1647,8 @@ lzx_lz_reverse_near_optimal_match_list(struct lzx_compressor *ctx, * ctx->optimum (internal state; leave uninitialized) * ctx->optimum_cur_idx (must set to 0 before first call) * ctx->optimum_end_idx (must set to 0 before first call) - * ctx->SA (must be built before first call) - * ctx->ISA (must be built before first call) - * ctx->salink (must be built before first call) - * ctx->match_window_pos (must initialize to position of next match to - * return; subsequent calls return subsequent - * matches) - * ctx->match_window_end (must initialize to limit of match-finding region; - * subsequent calls use the same limit) + * + * Plus any state used by the raw match-finder. * * The return value is a (length, offset) pair specifying the match or literal * chosen. For literals, the length is less than LZX_MIN_MATCH_LEN and the @@ -1832,7 +1814,7 @@ lzx_lz_get_near_optimal_match(struct lzx_compressor * ctx) * Set default symbol costs. */ static void -lzx_set_default_costs(struct lzx_costs * costs) +lzx_set_default_costs(struct lzx_costs * costs, unsigned num_main_syms) { unsigned i; @@ -1841,7 +1823,7 @@ lzx_set_default_costs(struct lzx_costs * costs) costs->main[i] = 8; /* Match header symbols */ - for (; i < LZX_MAINCODE_NUM_SYMBOLS; i++) + for (; i < num_main_syms; i++) costs->main[i] = 10; /* Length symbols */ @@ -1880,15 +1862,20 @@ lzx_choose_verbatim_or_aligned(const struct lzx_freqs * freqs, } /* Find a near-optimal sequence of matches/literals with which to output the - * specified LZX block, and set its type to that which has the minimum cost to + * specified LZX block, then set its type to that which has the minimum cost to * output. */ static void lzx_optimize_block(struct lzx_compressor *ctx, struct lzx_block_spec *spec, unsigned num_passes) { - struct lzx_lru_queue orig_queue = ctx->queue; + const struct lzx_lru_queue orig_queue = ctx->queue; struct lzx_freqs freqs; + unsigned orig_window_pos = spec->window_pos; + unsigned orig_cached_pos = ctx->cached_matches_pos; + + LZX_ASSERT(ctx->match_window_pos == spec->window_pos); + ctx->match_window_end = spec->window_pos + spec->block_size; spec->chosen_matches_start_pos = spec->window_pos; @@ -1899,7 +1886,8 @@ lzx_optimize_block(struct lzx_compressor *ctx, struct lzx_block_spec *spec, * computed from the previous pass. */ for (unsigned pass = 0; pass < num_passes; pass++) { - lzx_lz_rewind_matchfinder(ctx, spec->window_pos); + ctx->match_window_pos = orig_window_pos; + ctx->cached_matches_pos = orig_cached_pos; ctx->queue = orig_queue; spec->num_chosen_matches = 0; memset(&freqs, 0, sizeof(freqs)); @@ -1910,22 +1898,25 @@ lzx_optimize_block(struct lzx_compressor *ctx, struct lzx_block_spec *spec, raw_match = lzx_lz_get_near_optimal_match(ctx); if (raw_match.len >= LZX_MIN_MATCH_LEN) { - lzx_match.data = lzx_record_match(raw_match.offset, raw_match.len, - &freqs, &ctx->queue); + lzx_match.data = lzx_tally_match(raw_match.len, raw_match.offset, + &freqs, &ctx->queue); i += raw_match.len; } else { - lzx_match.data = lzx_record_literal(ctx->window[i], &freqs); + lzx_match.data = lzx_tally_literal(ctx->window[i], &freqs); i += 1; } ctx->chosen_matches[spec->chosen_matches_start_pos + spec->num_chosen_matches++] = lzx_match; } - lzx_make_huffman_codes(&freqs, &spec->codes); + lzx_make_huffman_codes(&freqs, &spec->codes, + ctx->num_main_syms); if (pass < num_passes - 1) lzx_set_costs(ctx, &spec->codes.lens); + ctx->matches_cached = true; } spec->block_type = lzx_choose_verbatim_or_aligned(&freqs, &spec->codes); + ctx->matches_cached = false; } static void @@ -1954,13 +1945,18 @@ lzx_lz_init_matchfinder(const u8 T[const restrict], /* Compute SA (Suffix Array). */ { - saidx_t sa[n]; /* ISA and link are used as temporary space. */ - BUILD_BUG_ON(LZX_MAX_WINDOW_SIZE * sizeof(ISA[0]) < 256 * sizeof(saidx_t)); - BUILD_BUG_ON(LZX_MAX_WINDOW_SIZE * 2 * sizeof(link[0]) < 256 * 256 * sizeof(saidx_t)); - divsufsort(T, sa, n, (saidx_t*)ISA, (saidx_t*)link); - for (input_idx_t i = 0; i < n; i++) - SA[i] = sa[i]; + BUILD_BUG_ON(LZX_MIN_WINDOW_SIZE * sizeof(ISA[0]) < 256 * sizeof(saidx_t)); + BUILD_BUG_ON(LZX_MIN_WINDOW_SIZE * 2 * sizeof(link[0]) < 256 * 256 * sizeof(saidx_t)); + + if (sizeof(input_idx_t) == sizeof(saidx_t)) { + divsufsort(T, SA, n, (saidx_t*)ISA, (saidx_t*)link); + } else { + saidx_t sa[n]; + divsufsort(T, sa, n, (saidx_t*)ISA, (saidx_t*)link); + for (input_idx_t i = 0; i < n; i++) + SA[i] = sa[i]; + } } #ifdef ENABLE_LZX_DEBUG @@ -2060,7 +2056,7 @@ lzx_lz_init_matchfinder(const u8 T[const restrict], } link[r].next = t; link[r].lcpnext = min(l, max_match_len); - LZX_ASSERT(t == (input_idx_t)~0 || l <= n - SA[t]); + LZX_ASSERT(t == (input_idx_t)~0U || l <= n - SA[t]); LZX_ASSERT(l <= n - SA[r]); LZX_ASSERT(memcmp(&T[SA[r]], &T[SA[t]], l) == 0); } @@ -2104,15 +2100,16 @@ lzx_prepare_blocks(struct lzx_compressor * ctx) ctx->match_window_pos = 0; /* Set up a default cost model. */ - lzx_set_default_costs(&ctx->costs); + lzx_set_default_costs(&ctx->costs, ctx->num_main_syms); - /* Initially assume that the entire input will be one LZX block. */ - ctx->block_specs[0].block_type = LZX_BLOCKTYPE_ALIGNED; - ctx->block_specs[0].window_pos = 0; - ctx->block_specs[0].block_size = ctx->window_size; - ctx->num_blocks = 1; + ctx->num_blocks = DIV_ROUND_UP(ctx->window_size, LZX_DIV_BLOCK_SIZE); + for (unsigned i = 0; i < ctx->num_blocks; i++) { + unsigned pos = LZX_DIV_BLOCK_SIZE * i; + ctx->block_specs[i].window_pos = pos; + ctx->block_specs[i].block_size = min(ctx->window_size - pos, LZX_DIV_BLOCK_SIZE); + } - /* Perform near-optimal LZ parsing. */ + /* Determine sequence of matches/literals to output for each block. */ lzx_optimize_blocks(ctx); } @@ -2127,9 +2124,6 @@ lzx_prepare_blocks(struct lzx_compressor * ctx) * ctx->window[] * ctx->window_size * - * Working space: - * ctx->queue - * * Output --- the block specification and the corresponding match/literal data: * * ctx->block_specs[] @@ -2139,8 +2133,7 @@ lzx_prepare_blocks(struct lzx_compressor * ctx) static void lzx_prepare_block_fast(struct lzx_compressor * ctx) { - unsigned num_matches; - struct lzx_freqs freqs; + struct lzx_record_ctx record_ctx; struct lzx_block_spec *spec; /* Parameters to hash chain LZ match finder @@ -2150,6 +2143,7 @@ lzx_prepare_block_fast(struct lzx_compressor * ctx) * aren't worth choosing when using greedy or lazy parsing. */ .min_match = 3, .max_match = LZX_MAX_MATCH_LEN, + .max_offset = LZX_MAX_WINDOW_SIZE, .good_match = LZX_MAX_MATCH_LEN, .nice_match = LZX_MAX_MATCH_LEN, .max_chain_len = LZX_MAX_MATCH_LEN, @@ -2158,29 +2152,28 @@ lzx_prepare_block_fast(struct lzx_compressor * ctx) }; /* Initialize symbol frequencies and match offset LRU queue. */ - memset(&freqs, 0, sizeof(struct lzx_freqs)); - lzx_lru_queue_init(&ctx->queue); + memset(&record_ctx.freqs, 0, sizeof(struct lzx_freqs)); + lzx_lru_queue_init(&record_ctx.queue); + record_ctx.matches = ctx->chosen_matches; /* Determine series of matches/literals to output. */ - num_matches = lz_analyze_block(ctx->window, - ctx->window_size, - (u32*)ctx->chosen_matches, - lzx_record_match, - lzx_record_literal, - &freqs, - &ctx->queue, - &freqs, - &lzx_lz_params); - + lz_analyze_block(ctx->window, + ctx->window_size, + lzx_record_match, + lzx_record_literal, + &record_ctx, + &lzx_lz_params, + ctx->prev_tab); /* Set up block specification. */ spec = &ctx->block_specs[0]; spec->block_type = LZX_BLOCKTYPE_ALIGNED; spec->window_pos = 0; spec->block_size = ctx->window_size; - spec->num_chosen_matches = num_matches; + spec->num_chosen_matches = (record_ctx.matches - ctx->chosen_matches); spec->chosen_matches_start_pos = 0; - lzx_make_huffman_codes(&freqs, &spec->codes); + lzx_make_huffman_codes(&record_ctx.freqs, &spec->codes, + ctx->num_main_syms); ctx->num_blocks = 1; } @@ -2227,20 +2220,19 @@ wimlib_lzx_compress2(const void * const restrict uncompressed_data, { struct lzx_compressor *ctx = (struct lzx_compressor*)lzx_ctx; struct output_bitstream ostream; - unsigned compressed_len; + input_idx_t compressed_len; if (uncompressed_len < 100) { LZX_DEBUG("Too small to bother compressing."); return 0; } - if (uncompressed_len > 32768) { - LZX_DEBUG("Only up to 32768 bytes of uncompressed data are supported."); + if (uncompressed_len > ctx->max_window_size) { + LZX_DEBUG("Can't compress %u bytes using window of %u bytes!", + uncompressed_len, ctx->max_window_size); return 0; } - wimlib_assert(lzx_ctx != NULL); - LZX_DEBUG("Attempting to compress %u bytes...", uncompressed_len); /* The input data must be preprocessed. To avoid changing the original @@ -2274,33 +2266,32 @@ wimlib_lzx_compress2(const void * const restrict uncompressed_data, lzx_write_all_blocks(ctx, &ostream); LZX_DEBUG("Flushing bitstream..."); - if (flush_output_bitstream(&ostream)) { - /* If the bitstream cannot be flushed, then the output space was - * exhausted. */ + compressed_len = flush_output_bitstream(&ostream); + if (compressed_len == ~(input_idx_t)0) { LZX_DEBUG("Data did not compress to less than original length!"); return 0; } - /* Compute the length of the compressed data. */ - compressed_len = ostream.bit_output - (u8*)compressed_data; - LZX_DEBUG("Done: compressed %u => %u bytes.", uncompressed_len, compressed_len); /* Verify that we really get the same thing back when decompressing. - * TODO: Disable this check by default on the slow algorithm. */ + * Although this could be disabled by default in all cases, it only + * takes around 2-3% of the running time of the slow algorithm to do the + * verification. */ if (ctx->params.algorithm == WIMLIB_LZX_ALGORITHM_SLOW #if defined(ENABLE_LZX_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION) || 1 #endif ) { - u8 buf[uncompressed_len]; - int ret; + /* The decompression buffer can be any temporary space that's no + * longer needed. */ + u8 *buf = (u8*)(ctx->SA ? ctx->SA : ctx->prev_tab); - ret = wimlib_lzx_decompress(compressed_data, compressed_len, - buf, uncompressed_len); - if (ret) { + if (wimlib_lzx_decompress2(compressed_data, compressed_len, + buf, uncompressed_len, ctx->max_window_size)) + { ERROR("Failed to decompress data we " "compressed using LZX algorithm"); wimlib_assert(0); @@ -2374,6 +2365,7 @@ lzx_params_valid(const struct wimlib_lzx_params *params) return true; } +/* API function documented in wimlib.h */ WIMLIBAPI int wimlib_lzx_set_default_params(const struct wimlib_lzx_params * params) { @@ -2390,12 +2382,16 @@ wimlib_lzx_set_default_params(const struct wimlib_lzx_params * params) /* API function documented in wimlib.h */ WIMLIBAPI int -wimlib_lzx_alloc_context(const struct wimlib_lzx_params *params, +wimlib_lzx_alloc_context(u32 window_size, + const struct wimlib_lzx_params *params, struct wimlib_lzx_context **ctx_pp) { LZX_DEBUG("Allocating LZX context..."); + if (!lzx_window_size_valid(window_size)) + return WIMLIB_ERR_INVALID_PARAM; + struct lzx_compressor *ctx; static const struct wimlib_lzx_params fast_default = { @@ -2446,7 +2442,9 @@ wimlib_lzx_alloc_context(const struct wimlib_lzx_params *params, if (ctx_pp) { ctx = *(struct lzx_compressor**)ctx_pp; - if (ctx && lzx_params_compatible(&ctx->params, params)) + if (ctx && + lzx_params_compatible(&ctx->params, params) && + ctx->max_window_size == window_size) return 0; } else { LZX_DEBUG("Check parameters only."); @@ -2455,66 +2453,62 @@ wimlib_lzx_alloc_context(const struct wimlib_lzx_params *params, LZX_DEBUG("Allocating memory."); - ctx = MALLOC(sizeof(struct lzx_compressor)); + ctx = CALLOC(1, sizeof(struct lzx_compressor)); if (ctx == NULL) goto err; - size_t block_specs_length; + ctx->num_main_syms = lzx_get_num_main_syms(window_size); + ctx->max_window_size = window_size; + ctx->window = MALLOC(window_size + 12); + if (ctx->window == NULL) + goto err; -#if 0 - if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) - block_specs_length = 1U << params->alg_params.slow.num_split_passes; - else -#endif - block_specs_length = 1U; + if (params->algorithm == WIMLIB_LZX_ALGORITHM_FAST) { + ctx->prev_tab = MALLOC(window_size * sizeof(ctx->prev_tab[0])); + if (ctx->prev_tab == NULL) + goto err; + } + + size_t block_specs_length = DIV_ROUND_UP(window_size, LZX_DIV_BLOCK_SIZE); ctx->block_specs = MALLOC(block_specs_length * sizeof(ctx->block_specs[0])); if (ctx->block_specs == NULL) - goto err_free_ctx; + goto err; if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) { - ctx->SA = MALLOC(3U * LZX_MAX_WINDOW_SIZE * sizeof(ctx->SA[0])); + ctx->SA = MALLOC(3U * window_size * sizeof(ctx->SA[0])); if (ctx->SA == NULL) - goto err_free_block_specs; - ctx->ISA = ctx->SA + LZX_MAX_WINDOW_SIZE; - ctx->LCP = ctx->ISA + LZX_MAX_WINDOW_SIZE; - ctx->salink = MALLOC(LZX_MAX_WINDOW_SIZE * sizeof(ctx->salink[0])); + goto err; + ctx->ISA = ctx->SA + window_size; + ctx->LCP = ctx->ISA + window_size; + + ctx->salink = MALLOC(window_size * sizeof(ctx->salink[0])); if (ctx->salink == NULL) - goto err_free_SA; - } else { - ctx->SA = NULL; - ctx->ISA = NULL; - ctx->LCP = NULL; - ctx->salink = NULL; + goto err; } if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) { ctx->optimum = MALLOC((LZX_OPTIM_ARRAY_SIZE + LZX_MAX_MATCH_LEN) * sizeof(ctx->optimum[0])); if (ctx->optimum == NULL) - goto err_free_salink; - } else { - ctx->optimum = NULL; + goto err; } if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) { - uint32_t cache_per_pos; + u32 cache_per_pos; cache_per_pos = params->alg_params.slow.max_matches_per_pos; if (cache_per_pos > LZX_MAX_CACHE_PER_POS) cache_per_pos = LZX_MAX_CACHE_PER_POS; - ctx->cached_matches = MALLOC(LZX_MAX_WINDOW_SIZE * (cache_per_pos + 1) * + ctx->cached_matches = MALLOC(window_size * (cache_per_pos + 1) * sizeof(ctx->cached_matches[0])); if (ctx->cached_matches == NULL) - goto err_free_optimum; - } else { - ctx->cached_matches = NULL; + goto err; } - ctx->chosen_matches = MALLOC(LZX_MAX_WINDOW_SIZE * - sizeof(ctx->chosen_matches[0])); + ctx->chosen_matches = MALLOC(window_size * sizeof(ctx->chosen_matches[0])); if (ctx->chosen_matches == NULL) - goto err_free_cached_matches; + goto err; memcpy(&ctx->params, params, sizeof(struct wimlib_lzx_params)); memset(&ctx->zero_codes, 0, sizeof(ctx->zero_codes)); @@ -2525,19 +2519,8 @@ wimlib_lzx_alloc_context(const struct wimlib_lzx_params *params, *ctx_pp = (struct wimlib_lzx_context*)ctx; return 0; -err_free_cached_matches: - FREE(ctx->cached_matches); -err_free_optimum: - FREE(ctx->optimum); -err_free_salink: - FREE(ctx->salink); -err_free_SA: - FREE(ctx->SA); -err_free_block_specs: - FREE(ctx->block_specs); -err_free_ctx: - FREE(ctx); err: + wimlib_lzx_free_context((struct wimlib_lzx_context*)ctx); LZX_DEBUG("Ran out of memory."); return WIMLIB_ERR_NOMEM; } @@ -2549,12 +2532,14 @@ wimlib_lzx_free_context(struct wimlib_lzx_context *_ctx) struct lzx_compressor *ctx = (struct lzx_compressor*)_ctx; if (ctx) { - FREE(ctx->cached_matches); FREE(ctx->chosen_matches); + FREE(ctx->cached_matches); FREE(ctx->optimum); - FREE(ctx->SA); FREE(ctx->salink); + FREE(ctx->SA); FREE(ctx->block_specs); + FREE(ctx->prev_tab); + FREE(ctx->window); FREE(ctx); } } @@ -2569,7 +2554,7 @@ wimlib_lzx_compress(const void * const restrict uncompressed_data, struct wimlib_lzx_context *ctx = NULL; unsigned compressed_len; - ret = wimlib_lzx_alloc_context(NULL, &ctx); + ret = wimlib_lzx_alloc_context(32768, NULL, &ctx); if (ret) { wimlib_assert(ret != WIMLIB_ERR_INVALID_PARAM); WARNING("Couldn't allocate LZX compression context: %"TS"",