*/
/*
- * 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.
*
#include "wimlib.h"
#include "wimlib/assert.h"
-#include "wimlib/compress.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 <stdlib.h>
#include <string.h>
+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 *restrict ostream,
- u32 match,
- const u16 codewords[restrict],
+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)
- return ret;
-
- if (adjusted_match_len >= 0xf) {
- u8 byte1 = min(adjusted_match_len - 0xf, 0xff);
- ret = bitstream_put_byte(ostream, byte1);
- if (ret)
- 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)
- 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[restrict],
- unsigned num_matches,
- const u16 codewords[restrict],
- const u8 lens[restrict])
+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)
- 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,
.too_far = 4096,
};
-/* Documented in wimlib.h */
-WIMLIBAPI unsigned
-wimlib_xpress_compress(const void * restrict _uncompressed_data,
- unsigned uncompressed_len,
- void * restrict _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)
{
- 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;
- u8 uncompressed_data[uncompressed_len + 8];
-
- memcpy(uncompressed_data, _uncompressed_data, uncompressed_len);
- memset(uncompressed_data + uncompressed_len, 0, 8);
-
- wimlib_assert(uncompressed_len <= 32768);
+ u32 num_chosen_items;
+ u32 i;
+ size_t compressed_size;
- /* 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);
- freq_tab[XPRESS_END_OF_DATA]++;
+ /* 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);
+ 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;
-
- /* Flush any bits that are buffered. */
- ret = flush_output_bitstream(&ostream);
- if (ret)
- return 0;
+ xpress_write_items(&ostream, c->chosen_items, num_chosen_items,
+ c->codewords, c->lens);
- /* 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)
+ /* 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;
- *(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);
+ compressed_size += XPRESS_NUM_SYMBOLS / 2;
-#ifdef ENABLE_VERIFY_COMPRESSION
- /* Verify that we really get the same thing back when decompressing. */
+#if defined(ENABLE_XPRESS_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
+ /* Verify that we really get the same thing back when decompressing. */
{
- u8 buf[uncompressed_len];
- ret = wimlib_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();
+ 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,
+};
git://wimlib.net / wimlib / blobdiff