X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fxpress-compress.c;h=46f683f1895c0517ad953c340b918b79b6c1b1a3;hp=548c32cbc8a9cd5d1f56e7d011668eb5a65d3858;hb=386f6bd95d4579f4d54afdf40c602b85a6f19245;hpb=720db87557918105b17b51b03f264ddb9b89d2b9 diff --git a/src/xpress-compress.c b/src/xpress-compress.c index 548c32cb..46f683f1 100644 --- a/src/xpress-compress.c +++ b/src/xpress-compress.c @@ -7,7 +7,7 @@ */ /* - * Copyright (C) 2012, 2013 Eric Biggers + * Copyright (C) 2012, 2013, 2014 Eric Biggers * * This file is part of wimlib, a library for working with WIM files. * @@ -25,113 +25,128 @@ * along with wimlib; if not, see http://www.gnu.org/licenses/. */ -#include "xpress.h" -#include "compress.h" -#include +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "wimlib.h" +#include "wimlib/assert.h" +#include "wimlib/compressor_ops.h" +#include "wimlib/compress_common.h" +#include "wimlib/error.h" +#include "wimlib/lz_hash.h" +#include "wimlib/util.h" +#include "wimlib/xpress.h" + #include +struct xpress_record_ctx { + u32 freqs[XPRESS_NUM_SYMBOLS]; + struct xpress_item *chosen_items; +}; + +struct xpress_compressor { + u8 *window; + u32 max_window_size; + struct xpress_item *chosen_items; + u32 *prev_tab; + u32 codewords[XPRESS_NUM_SYMBOLS]; + u8 lens[XPRESS_NUM_SYMBOLS]; + struct xpress_record_ctx record_ctx; +}; + +/* Intermediate XPRESS match/literal representation. */ +struct xpress_item { + u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */ + u16 offset; /* Match offset */ + /* For literals, offset == 0 and adjusted_len is the literal. */ +}; + /* * Writes @match, which is a match given in the intermediate representation for * XPRESS matches, to the output stream @ostream. * * @codewords and @lens provide the Huffman code that is being used. */ -static int -xpress_write_match(struct output_bitstream *ostream, u32 match, - const u16 codewords[], const u8 lens[]) +static void +xpress_write_match(struct xpress_item match, + struct output_bitstream *restrict ostream, + const u32 codewords[restrict], + const u8 lens[restrict]) { - u32 adjusted_match_len = match & 0xffff; - u32 match_offset = match >> 16; - u32 len_hdr = min(adjusted_match_len, 0xf); - u32 offset_bsr = bsr32(match_offset); - u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS; - int ret; - - ret = bitstream_put_bits(ostream, codewords[sym], lens[sym]); - if (ret != 0) - return ret; - - if (adjusted_match_len >= 0xf) { - u8 byte1 = min(adjusted_match_len - 0xf, 0xff); - ret = bitstream_put_byte(ostream, byte1); - if (ret != 0) - return ret; + u8 len_hdr = min(match.adjusted_len, 0xf); + u8 offset_bsr = bsr32(match.offset); + unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr); + + bitstream_put_bits(ostream, codewords[sym], lens[sym]); + + if (match.adjusted_len >= 0xf) { + u8 byte1 = min(match.adjusted_len - 0xf, 0xff); + bitstream_put_byte(ostream, byte1); if (byte1 == 0xff) { - ret = bitstream_put_two_bytes(ostream, adjusted_match_len); - if (ret != 0) - return ret; + bitstream_put_byte(ostream, match.adjusted_len & 0xff); + bitstream_put_byte(ostream, match.adjusted_len >> 8); } } - return bitstream_put_bits(ostream, - match_offset ^ (1 << offset_bsr), offset_bsr); + bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr); } -static int -xpress_write_compressed_literals(struct output_bitstream *ostream, - const u32 match_tab[], - unsigned num_matches, - const u16 codewords[], - const u8 lens[]) +static void +xpress_write_items(struct output_bitstream *ostream, + const struct xpress_item items[restrict], + u32 num_items, + const u32 codewords[restrict], + const u8 lens[restrict]) { - for (unsigned i = 0; i < num_matches; i++) { - int ret; - u32 match = match_tab[i]; - - if (match >= XPRESS_NUM_CHARS) /* match */ - ret = xpress_write_match(ostream, match, codewords, - lens); - else /* literal byte */ - ret = bitstream_put_bits(ostream, codewords[match], - lens[match]); - if (ret != 0) - return ret; + for (u32 i = 0; i < num_items; i++) { + if (items[i].offset) { + /* Match */ + xpress_write_match(items[i], ostream, codewords, lens); + } else { + /* Literal */ + u8 lit = items[i].adjusted_len; + bitstream_put_bits(ostream, codewords[lit], lens[lit]); + } } - return bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], - lens[XPRESS_END_OF_DATA]); + bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]); } -static u32 -xpress_record_literal(u8 literal, void *__freq_tab) +static void +xpress_record_literal(u8 lit, void *_ctx) { - freq_t *freq_tab = __freq_tab; - freq_tab[literal]++; - return literal; + struct xpress_record_ctx *ctx = _ctx; + ctx->freqs[lit]++; + *(ctx->chosen_items++) = + (struct xpress_item) { .offset = 0, .adjusted_len = lit }; } -static u32 -xpress_record_match(unsigned match_offset, unsigned match_len, - void *freq_tab, void *ignore) +static void +xpress_record_match(unsigned len, unsigned offset, void *_ctx) { - wimlib_assert(match_len >= XPRESS_MIN_MATCH && - match_len <= XPRESS_MAX_MATCH); - wimlib_assert(match_offset >= XPRESS_MIN_OFFSET && - match_offset <= XPRESS_MAX_OFFSET); + struct xpress_record_ctx *ctx = _ctx; - /* - * The intermediate representation of XPRESS matches is as follows: - * - * bits description - * ---- ----------------------------------------------------------- - * - * 16-31 match offset (XPRESS_MIN_OFFSET < x < XPRESS_MAX_OFFSET) - * - * 0-15 adjusted match length (0 <= x <= XPRESS_MAX_MATCH - XPRESS_MIN_MATCH) - * - * Literals are simply represented as themselves and can be - * distinguished from matches by the fact that only literals will have - * the upper three bytes completely clear. */ - - u32 adjusted_match_len = match_len - XPRESS_MIN_MATCH; - u32 len_hdr = min(adjusted_match_len, 0xf); - u32 offset_bsr = bsr32(match_offset); - u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS; - ((freq_t*)freq_tab)[sym]++; - return adjusted_match_len | (match_offset << 16); + XPRESS_ASSERT(len >= XPRESS_MIN_MATCH_LEN); + XPRESS_ASSERT(len <= XPRESS_MAX_MATCH_LEN); + XPRESS_ASSERT(offset >= XPRESS_MIN_OFFSET); + XPRESS_ASSERT(offset <= XPRESS_MAX_OFFSET); + + unsigned adjusted_len = len - XPRESS_MIN_MATCH_LEN; + unsigned len_hdr = min(adjusted_len, 0xf); + unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr); + + XPRESS_ASSERT(sym >= XPRESS_NUM_CHARS); + XPRESS_ASSERT(sym < XPRESS_NUM_SYMBOLS); + + ctx->freqs[sym]++; + *(ctx->chosen_items++) = + (struct xpress_item) { .offset = offset, + .adjusted_len = adjusted_len }; } static const struct lz_params xpress_lz_params = { - .min_match = XPRESS_MIN_MATCH, - .max_match = XPRESS_MAX_MATCH, + .min_match = XPRESS_MIN_MATCH_LEN, + .max_match = XPRESS_MAX_MATCH_LEN, + .max_offset = XPRESS_MAX_OFFSET, .good_match = 16, .nice_match = 32, .max_chain_len = 16, @@ -139,124 +154,181 @@ static const struct lz_params xpress_lz_params = { .too_far = 4096, }; -/* - * Performs XPRESS compression on a block of data. - * - * Please see the documentation for the 'compress_func_t' type in write.c for - * the exact behavior of this function and how to call it. - */ -unsigned -xpress_compress(const void *__uncompressed_data, unsigned uncompressed_len, - void *__compressed_data) +static size_t +xpress_compress(const void *uncompressed_data, size_t uncompressed_size, + void *compressed_data, size_t compressed_size_avail, void *_c) { - const u8 *uncompressed_data = __uncompressed_data; - u8 *compressed_data = __compressed_data; + struct xpress_compressor *c = _c; + u8 *cptr = compressed_data; struct output_bitstream ostream; - u32 match_tab[uncompressed_len]; - freq_t freq_tab[XPRESS_NUM_SYMBOLS]; - u16 codewords[XPRESS_NUM_SYMBOLS]; - u8 lens[XPRESS_NUM_SYMBOLS]; - unsigned num_matches; - unsigned compressed_len; - unsigned i; - int ret; + u32 num_chosen_items; + u32 i; + size_t compressed_size; - wimlib_assert(uncompressed_len <= 32768); - - /* XPRESS requires 256 bytes of overhead for the Huffman tables, so it's - * impossible cannot compress 256 bytes or less of data to less than the + /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's + * impossible to compress 256 bytes or less of data to less than the * input size. * * +1 to take into account that the buffer for compressed data is 1 byte * smaller than the buffer for uncompressed data. * * +4 to take into account that init_output_bitstream() requires at - * least 4 bytes of data. */ - if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4) + * least 4 bytes of data. */ + if (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 1 + 4) return 0; - ZERO_ARRAY(freq_tab); - num_matches = lz_analyze_block(uncompressed_data, uncompressed_len, - match_tab, xpress_record_match, - xpress_record_literal, freq_tab, - NULL, freq_tab, - &xpress_lz_params); + /* Copy the data to a temporary buffer, but only to avoid + * inconsequential accesses of uninitialized memory in + * lz_analyze_block(). */ + memcpy(c->window, uncompressed_data, uncompressed_size); + memset(c->window + uncompressed_size, 0, 8); + + /* Determine match/literal sequence to divide the data into. */ + memset(c->record_ctx.freqs, 0, sizeof(c->record_ctx.freqs)); + c->record_ctx.chosen_items = c->chosen_items; + lz_analyze_block(c->window, + uncompressed_size, + xpress_record_match, + xpress_record_literal, + &c->record_ctx, + &xpress_lz_params, + c->prev_tab); - freq_tab[XPRESS_END_OF_DATA]++; + num_chosen_items = (c->record_ctx.chosen_items - c->chosen_items); + /* Account for end of data symbol. */ + c->record_ctx.freqs[XPRESS_END_OF_DATA]++; + + /* Build the Huffman code. */ make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN, - freq_tab, lens, codewords); + c->record_ctx.freqs, c->lens, c->codewords); - /* IMPORTANT NOTE: - * - * It's tempting to output the 512 Huffman codeword lengths using the - * bitstream_put_bits() function. However, this is NOT correct because - * bitstream_put_bits() will output 2 bytes at a time in little-endian - * order, which is the order that is needed for the compressed literals. - * However, the bytes in the lengths table are in order, so they need to - * be written one at a time without using bitstream_put_bits(). - * - * Because of this, init_output_bitstream() is not called until after - * the lengths table is output. - */ + /* Output the Huffman code as a series of 512 4-bit lengths. */ for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2) - *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4); + *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4); - init_output_bitstream(&ostream, compressed_data, - uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1); + /* Output the encoded matches/literals. */ + init_output_bitstream(&ostream, cptr, + compressed_size_avail - XPRESS_NUM_SYMBOLS / 2 - 1); - ret = xpress_write_compressed_literals(&ostream, match_tab, - num_matches, codewords, lens); - if (ret) - return 0; + xpress_write_items(&ostream, c->chosen_items, num_chosen_items, + c->codewords, c->lens); - /* Flush any bits that are buffered. */ - ret = flush_output_bitstream(&ostream); - if (ret) + /* Flush any pending data and get the length of the compressed data. */ + compressed_size = flush_output_bitstream(&ostream); + if (compressed_size == (u32)~0UL) return 0; - /* Assert that there are no output bytes between the ostream.output - * pointer and the ostream.next_bit_output pointer. This can only - * happen if bytes had been written at the ostream.output pointer before - * the last bit word was written to the stream. But, this does not - * occur since xpress_write_match() always finishes by writing some bits - * (a Huffman symbol), and the bitstream was just flushed. */ - wimlib_assert(ostream.output - ostream.next_bit_output == 2); - - /* The length of the compressed data is supposed to be the value of the - * ostream.output pointer before flushing, which is now the - * output.next_bit_output pointer after flushing. - * - * There will be an extra 2 bytes at the ostream.bit_output pointer, - * which is zeroed out. (These 2 bytes may be either the last bytes in - * the compressed data, in which case they are actually unnecessary, or - * they may precede a number of bytes embedded into the bitstream.) */ - if (ostream.bit_output > - (const u8*)__compressed_data + uncompressed_len - 3) - return 0; - *(u16*)ostream.bit_output = cpu_to_le16(0); - compressed_len = ostream.next_bit_output - (const u8*)__compressed_data; - - wimlib_assert(compressed_len <= uncompressed_len - 1); - -#ifdef ENABLE_VERIFY_COMPRESSION - /* Verify that we really get the same thing back when decompressing. */ - u8 buf[uncompressed_len]; - ret = xpress_decompress(__compressed_data, compressed_len, buf, - uncompressed_len); - if (ret) { - ERROR("xpress_compress(): Failed to decompress data we " - "compressed"); - abort(); - } - for (i = 0; i < uncompressed_len; i++) { - if (buf[i] != uncompressed_data[i]) { - ERROR("xpress_compress(): Data we compressed didn't " - "decompress to the original data (difference at " - "byte %u of %u)", i + 1, uncompressed_len); - abort(); + compressed_size += XPRESS_NUM_SYMBOLS / 2; + +#if defined(ENABLE_XPRESS_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION) + /* Verify that we really get the same thing back when decompressing. */ + { + struct wimlib_decompressor *decompressor; + + if (0 == wimlib_create_decompressor(WIMLIB_COMPRESSION_TYPE_XPRESS, + c->max_window_size, + NULL, + &decompressor)) + { + int ret; + ret = wimlib_decompress(compressed_data, + compressed_size, + c->window, + uncompressed_size, + decompressor); + wimlib_free_decompressor(decompressor); + + if (ret) { + ERROR("Failed to decompress data we " + "compressed using XPRESS algorithm"); + wimlib_assert(0); + return 0; + } + if (memcmp(uncompressed_data, c->window, + uncompressed_size)) + { + ERROR("Data we compressed using XPRESS algorithm " + "didn't decompress to original"); + wimlib_assert(0); + return 0; + } + } else { + WARNING("Failed to create decompressor for " + "data verification!"); } } #endif - return compressed_len; + + return compressed_size; +} + +static void +xpress_free_compressor(void *_c) +{ + struct xpress_compressor *c = _c; + + if (c) { + FREE(c->window); + FREE(c->chosen_items); + FREE(c->prev_tab); + FREE(c); + } } + +static int +xpress_create_compressor(size_t max_window_size, + const struct wimlib_compressor_params_header *params, + void **c_ret) +{ + struct xpress_compressor *c; + + if (max_window_size == 0 || max_window_size > (1U << 26)) + return WIMLIB_ERR_INVALID_PARAM; + + c = CALLOC(1, sizeof(struct xpress_compressor)); + if (c == NULL) + goto oom; + + c->window = MALLOC(max_window_size + 8); + if (c->window == NULL) + goto oom; + + c->max_window_size = max_window_size; + + c->chosen_items = MALLOC(max_window_size * sizeof(c->chosen_items[0])); + if (c->chosen_items == NULL) + goto oom; + + c->prev_tab = MALLOC(max_window_size * sizeof(c->prev_tab[0])); + if (c->prev_tab == NULL) + goto oom; + + *c_ret = c; + return 0; + +oom: + xpress_free_compressor(c); + return WIMLIB_ERR_NOMEM; +} + +static u64 +xpress_get_needed_memory(size_t max_window_size, + const struct wimlib_compressor_params_header *params) +{ + u64 size = 0; + + size += sizeof(struct xpress_compressor); + size += max_window_size + 8; + size += max_window_size * sizeof(((struct xpress_compressor*)0)->chosen_items[0]); + size += max_window_size * sizeof(((struct xpress_compressor*)0)->prev_tab[0]); + + return size; +} + +const struct compressor_ops xpress_compressor_ops = { + .get_needed_memory = xpress_get_needed_memory, + .create_compressor = xpress_create_compressor, + .compress = xpress_compress, + .free_compressor = xpress_free_compressor, +};