/*
* xpress-compress.c
*
- * A compressor that produces output compatible with the XPRESS (Huffman
- * version) compression format.
+ * A compressor for the XPRESS compression format (Huffman variant).
*/
/*
* Copyright (C) 2012, 2013, 2014 Eric Biggers
*
- * This file is part of wimlib, a library for working with WIM files.
+ * This file is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU Lesser General Public License as published by the Free
+ * Software Foundation; either version 3 of the License, or (at your option) any
+ * later version.
*
- * wimlib is free software; you can redistribute it and/or modify it under the
- * terms of the GNU General Public License as published by the Free
- * Software Foundation; either version 3 of the License, or (at your option)
- * any later version.
- *
- * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
- * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
- * A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * This file is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
* details.
*
- * You should have received a copy of the GNU General Public License
- * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this file; if not, see http://www.gnu.org/licenses/.
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
-#include "wimlib/compressor_ops.h"
+/*
+ * The maximum buffer size, in bytes, that can be compressed. An XPRESS
+ * compressor instance must be created with a 'max_bufsize' less than or equal
+ * to this value.
+ */
+#define XPRESS_MAX_BUFSIZE 65536
+
+/*
+ * Define to 1 to enable the near-optimal parsing algorithm at high compression
+ * levels. The near-optimal parsing algorithm produces a compression ratio
+ * significantly better than the greedy and lazy algorithms. However, it is
+ * much slower.
+ */
+#define SUPPORT_NEAR_OPTIMAL_PARSING 1
+
+/*
+ * The lowest compression level at which near-optimal parsing is enabled.
+ */
+#define MIN_LEVEL_FOR_NEAR_OPTIMAL 60
+
+/*
+ * The window order for the matchfinder. This must be the base 2 logarithm of
+ * the maximum buffer size.
+ */
+#define MATCHFINDER_WINDOW_ORDER 16
+
+/*
+ * Although XPRESS can potentially use a sliding window, it isn't well suited
+ * for large buffers of data because there is no way to reset the Huffman code.
+ * Therefore, we only allow buffers in which there is no restriction on match
+ * offsets (no sliding window). This simplifies the code and allows some
+ * optimizations.
+ */
+#define MATCHFINDER_IS_SLIDING 0
+
+#include <string.h>
+
+#include "wimlib/bitops.h"
#include "wimlib/compress_common.h"
+#include "wimlib/compressor_ops.h"
+#include "wimlib/endianness.h"
#include "wimlib/error.h"
-#include "wimlib/lz_mf.h"
+#include "wimlib/hc_matchfinder.h"
+#include "wimlib/unaligned.h"
#include "wimlib/util.h"
#include "wimlib/xpress.h"
-#include <string.h>
+#if SUPPORT_NEAR_OPTIMAL_PARSING
-#define XPRESS_CACHE_PER_POS 8
-#define XPRESS_OPTIM_ARRAY_LENGTH 4096
+/*
+ * CACHE_RESERVE_PER_POS is the number of lz_match structures to reserve in the
+ * match cache for each byte position. This value should be high enough so that
+ * virtually the time, all matches found in the input buffer can fit in the
+ * match cache. However, fallback behavior on cache overflow is still required.
+ */
+#define CACHE_RESERVE_PER_POS 8
-struct xpress_compressor;
-struct xpress_item;
-struct xpress_mc_pos_data;
+/*
+ * We use a binary-tree based matchfinder for optimal parsing because it can
+ * find more matches in the same number of steps compared to hash-chain based
+ * matchfinders. In addition, since we need to find matches at almost every
+ * position, there isn't much penalty for keeping the sequences sorted in the
+ * binary trees.
+ */
+#include "wimlib/bt_matchfinder.h"
-struct xpress_compressor_params {
+struct xpress_optimum_node;
- /* Only used when choose_items_func == xpress_choose_items_near_optimal */
- u32 num_optim_passes;
+#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
- /* Given the data to compress (c->cur_window, c->cur_window_size),
- * 'choose_items_func' fills in c->chosen_items with the intermediate
- * representation of the match/literal sequence to output. Also fills
- * in c->codewords and c->lens to provide the Huffman code with which
- * these items should be output.
- *
- * Returns the number of items written to c->chosen_items. This can be
- * at most c->cur_window_size. (The worst case is all literals, no
- * matches.) */
- u32 (*choose_items_func)(struct xpress_compressor *c);
-
- /* Match-finding algorithm and parameters */
- enum lz_mf_algo mf_algo;
- u32 max_search_depth;
- u32 nice_match_length;
-};
+struct xpress_item;
-/* XPRESS compressor state. */
+/* The main XPRESS compressor structure */
struct xpress_compressor {
- /* Parameters determined based on the compression level. */
- struct xpress_compressor_params params;
-
- /* Lempel-Ziv match-finder */
- struct lz_mf *mf;
-
- /* Optimal parsing data */
- unsigned (*get_matches_func)(struct xpress_compressor *,
- const struct lz_match **);
- void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
- const u8 *cur_window_ptr;
- struct lz_match *cached_matches;
- struct lz_match *cache_ptr;
- struct lz_match *cache_limit;
- struct xpress_mc_pos_data *optimum;
- unsigned optimum_cur_idx;
- unsigned optimum_end_idx;
- u8 costs[XPRESS_NUM_SYMBOLS];
-
- /* The selected sequence of matches/literals */
- struct xpress_item *chosen_items;
-
- /* Data currently being compressed */
- const u8 *cur_window;
- u32 cur_window_size;
-
- /* Symbol frequency counters */
+ /* Pointer to the compress() implementation chosen at allocation time */
+ size_t (*impl)(struct xpress_compressor *,
+ const void *, size_t, void *, size_t);
+
+ /* Symbol frequency counters for the Huffman code */
u32 freqs[XPRESS_NUM_SYMBOLS];
- /* The current Huffman code */
+ /* The Huffman codewords and their lengths */
u32 codewords[XPRESS_NUM_SYMBOLS];
u8 lens[XPRESS_NUM_SYMBOLS];
-};
-/* Match-chooser position data.
- * See corresponding declaration in lzx-compress.c for more information. */
-struct xpress_mc_pos_data {
- u32 cost;
-#define MC_INFINITE_COST ((u32)~0UL)
+ /* The "nice" match length: if a match of this length is found, then
+ * choose it immediately without further consideration. */
+ unsigned nice_match_length;
+
+ /* The maximum search depth: consider at most this many potential
+ * matches at each position. */
+ unsigned max_search_depth;
union {
+ /* Data for greedy or lazy parsing */
struct {
- u32 link;
- u32 match_offset;
- } prev;
+ struct hc_matchfinder hc_mf;
+ struct xpress_item *chosen_items;
+ u8 nonoptimal_end[0];
+ };
+
+ #if SUPPORT_NEAR_OPTIMAL_PARSING
+ /* Data for near-optimal parsing */
struct {
- u32 link;
- u32 match_offset;
- } next;
+ struct bt_matchfinder bt_mf;
+ struct xpress_optimum_node *optimum_nodes;
+ struct lz_match *match_cache;
+ struct lz_match *cache_overflow_mark;
+ unsigned num_optim_passes;
+ u32 costs[XPRESS_NUM_SYMBOLS];
+ u8 optimal_end[0];
+ };
+ #endif
};
};
-/* Intermediate XPRESS match/literal representation. */
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+
+/*
+ * This structure represents a byte position in the input buffer and a node in
+ * the graph of possible match/literal choices.
+ *
+ * Logically, each incoming edge to this node is labeled with a literal or a
+ * match that can be taken to reach this position from an earlier position; and
+ * each outgoing edge from this node is labeled with a literal or a match that
+ * can be taken to advance from this position to a later position.
+ *
+ * But these "edges" are actually stored elsewhere (in 'match_cache'). Here we
+ * associate with each node just two pieces of information:
+ *
+ * 'cost_to_end' is the minimum cost to reach the end of the buffer from
+ * this position.
+ *
+ * 'item' represents the literal or match that must be chosen from here to
+ * reach the end of the buffer with the minimum cost. Equivalently, this
+ * can be interpreted as the label of the outgoing edge on the minimum cost
+ * path to the "end of buffer" node from this node.
+ */
+struct xpress_optimum_node {
+
+ u32 cost_to_end;
+
+ /*
+ * Notes on the match/literal representation used here:
+ *
+ * The low bits of 'item' are the length: 1 if the item is a
+ * literal, or the match length if the item is a match.
+ *
+ * The high bits of 'item' are the actual literal byte if the item
+ * is a literal, or the match offset if the item is a match.
+ */
+#define OPTIMUM_OFFSET_SHIFT 16
+#define OPTIMUM_LEN_MASK (((u32)1 << OPTIMUM_OFFSET_SHIFT) - 1)
+ u32 item;
+};
+
+#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
+
+/* An intermediate representation of an XPRESS match or literal */
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 byte. */
+ /*
+ * Bits 0 - 8: Symbol
+ * Bits 9 - 24: Length - XPRESS_MIN_MATCH_LEN
+ * Bits 25 - 28: Number of extra offset bits
+ * Bits 29+ : Extra offset bits
+ *
+ * Unfortunately, gcc generates worse code if we use real bitfields here.
+ */
+ u64 data;
};
-/* Output an XPRESS match. */
-static void
-xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
- const u32 codewords[], const u8 lens[])
-{
- unsigned len_hdr = min(match.adjusted_len, 0xf);
- unsigned offset_bsr = bsr32(match.offset);
- unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
-
- /* Huffman symbol */
- bitstream_put_bits(ostream, codewords[sym], lens[sym]);
-
- /* If length >= 18, one extra length byte.
- * If length >= 273, three (total) extra length bytes. */
- if (match.adjusted_len >= 0xf) {
- u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
- bitstream_put_byte(ostream, byte1);
- if (byte1 == 0xff) {
- bitstream_put_byte(ostream, match.adjusted_len & 0xff);
- bitstream_put_byte(ostream, match.adjusted_len >> 8);
- }
- }
+/*
+ * Structure to keep track of the current state of sending compressed data to
+ * the output buffer.
+ *
+ * The XPRESS bitstream is encoded as a sequence of little endian 16-bit coding
+ * units interwoven with literal bytes.
+ */
+struct xpress_output_bitstream {
- /* Offset bits */
- bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
-}
+ /* Bits that haven't yet been written to the output buffer. */
+ u32 bitbuf;
-/* Output a sequence of XPRESS matches and literals. */
+ /* Number of bits currently held in @bitbuf. */
+ u32 bitcount;
+
+ /* Pointer to the start of the output buffer. */
+ u8 *start;
+
+ /* Pointer to the location in the ouput buffer at which to write the
+ * next 16 bits. */
+ u8 *next_bits;
+
+ /* Pointer to the location in the output buffer at which to write the
+ * next 16 bits, after @next_bits. */
+ u8 *next_bits2;
+
+ /* Pointer to the location in the output buffer at which to write the
+ * next literal byte. */
+ u8 *next_byte;
+
+ /* Pointer to the end of the output buffer. */
+ u8 *end;
+};
+
+/* Reset the symbol frequencies for the XPRESS Huffman code. */
static void
-xpress_write_items(struct output_bitstream *ostream,
- const struct xpress_item items[], u32 num_items,
- const u32 codewords[], const u8 lens[])
+xpress_reset_symbol_frequencies(struct xpress_compressor *c)
{
- for (u32 i = 0; i < num_items; i++) {
- if (items[i].offset) {
- /* Match */
- xpress_write_match(items[i], ostream, codewords, lens);
- } else {
- /* Literal */
- unsigned lit = items[i].adjusted_len;
- bitstream_put_bits(ostream, codewords[lit], lens[lit]);
- }
- }
- /* End-of-data symbol (required for MS compatibility) */
- bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
+ memset(c->freqs, 0, sizeof(c->freqs));
}
-/* Make the Huffman code for XPRESS.
+/*
+ * Make the Huffman code for XPRESS.
*
- * Takes as input c->freqs and produces as output c->lens and c->codewords. */
+ * Input: c->freqs
+ * Output: c->lens and c->codewords
+ */
static void
xpress_make_huffman_code(struct xpress_compressor *c)
{
c->freqs, c->lens, c->codewords);
}
-/* Account for the Huffman symbol that would be produced by outputting the
- * specified literal. Returns the intermediate representation of the literal.
+/*
+ * Initialize the output bitstream.
+ *
+ * @os
+ * The output bitstream structure to initialize.
+ * @buffer
+ * The output buffer.
+ * @size
+ * Size of @buffer, in bytes. Must be at least 4.
*/
-static inline struct xpress_item
-xpress_tally_literal(u8 lit, u32 freqs[])
-{
- freqs[lit]++;
- return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
-}
-
-/* Account for the Huffman symbol that would be produced by outputting the
- * specified match. Returns the intermediate representation of the match. */
-static inline struct xpress_item
-xpress_tally_match(u32 len, u32 offset, u32 freqs[])
-{
- u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
- unsigned len_hdr = min(adjusted_len, 0xf);
- unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
-
- freqs[sym]++;
- return (struct xpress_item) { .offset = offset,
- .adjusted_len = adjusted_len };
-}
-
-static unsigned
-xpress_get_matches_fillcache(struct xpress_compressor *c,
- const struct lz_match **matches_ret)
+static void
+xpress_init_output(struct xpress_output_bitstream *os, void *buffer, size_t size)
{
- struct lz_match *cache_ptr;
- struct lz_match *matches;
- unsigned num_matches;
-
- cache_ptr = c->cache_ptr;
- matches = cache_ptr + 1;
- if (likely(cache_ptr <= c->cache_limit)) {
- num_matches = lz_mf_get_matches(c->mf, matches);
- cache_ptr->len = num_matches;
- c->cache_ptr = matches + num_matches;
- } else {
- num_matches = 0;
- }
- c->cur_window_ptr++;
- *matches_ret = matches;
- return num_matches;
+ os->bitbuf = 0;
+ os->bitcount = 0;
+ os->start = buffer;
+ os->next_bits = os->start;
+ os->next_bits2 = os->start + 2;
+ os->next_byte = os->start + 4;
+ os->end = os->start + size;
}
-static unsigned
-xpress_get_matches_usecache(struct xpress_compressor *c,
- const struct lz_match **matches_ret)
+/*
+ * Write some bits to the output bitstream.
+ *
+ * The bits are given by the low-order @num_bits bits of @bits. Higher-order
+ * bits in @bits cannot be set. At most 16 bits can be written at once.
+ *
+ * If the output buffer space is exhausted, then the bits will be ignored, and
+ * xpress_flush_output() will return 0 when it gets called.
+ */
+static inline void
+xpress_write_bits(struct xpress_output_bitstream *os,
+ const u32 bits, const unsigned num_bits)
{
- struct lz_match *cache_ptr;
- struct lz_match *matches;
- unsigned num_matches;
-
- cache_ptr = c->cache_ptr;
- matches = cache_ptr + 1;
- if (likely(cache_ptr <= c->cache_limit)) {
- num_matches = cache_ptr->len;
- c->cache_ptr = matches + num_matches;
- } else {
- num_matches = 0;
+ /* This code is optimized for XPRESS, which never needs to write more
+ * than 16 bits at once. */
+
+ os->bitcount += num_bits;
+ os->bitbuf = (os->bitbuf << num_bits) | bits;
+
+ if (os->bitcount > 16) {
+ os->bitcount -= 16;
+ if (os->end - os->next_byte >= 2) {
+ put_unaligned_u16_le(os->bitbuf >> os->bitcount, os->next_bits);
+ os->next_bits = os->next_bits2;
+ os->next_bits2 = os->next_byte;
+ os->next_byte += 2;
+ }
}
- c->cur_window_ptr++;
- *matches_ret = matches;
- return num_matches;
}
-static unsigned
-xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
- const struct lz_match **matches_ret)
+/*
+ * Interweave a literal byte into the output bitstream.
+ */
+static inline void
+xpress_write_byte(struct xpress_output_bitstream *os, u8 byte)
{
- struct lz_match *cache_ptr;
- struct lz_match *matches;
- unsigned num_matches;
-
- cache_ptr = c->cache_ptr;
- matches = cache_ptr + 1;
- num_matches = cache_ptr->len;
- c->cache_ptr = matches + num_matches;
- c->cur_window_ptr++;
- *matches_ret = matches;
- return num_matches;
+ if (os->next_byte < os->end)
+ *os->next_byte++ = byte;
}
-static unsigned
-xpress_get_matches_noncaching(struct xpress_compressor *c,
- const struct lz_match **matches_ret)
+/*
+ * Interweave two literal bytes into the output bitstream.
+ */
+static inline void
+xpress_write_u16(struct xpress_output_bitstream *os, u16 v)
{
- c->cur_window_ptr++;
- *matches_ret = c->cached_matches;
- return lz_mf_get_matches(c->mf, c->cached_matches);
+ if (os->end - os->next_byte >= 2) {
+ put_unaligned_u16_le(v, os->next_byte);
+ os->next_byte += 2;
+ }
}
/*
- * Find matches at the next position in the window.
- *
- * Returns the number of matches found and sets *matches_ret to point to the
- * matches array. The matches will be sorted by strictly increasing length and
- * offset.
+ * Flush the last coding unit to the output buffer if needed. Return the total
+ * number of bytes written to the output buffer, or 0 if an overflow occurred.
*/
-static inline unsigned
-xpress_get_matches(struct xpress_compressor *c,
- const struct lz_match **matches_ret)
+static size_t
+xpress_flush_output(struct xpress_output_bitstream *os)
{
- return (*c->get_matches_func)(c, matches_ret);
-}
+ if (os->end - os->next_byte < 2)
+ return 0;
-static void
-xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
-{
- struct lz_match *cache_ptr;
-
- c->cur_window_ptr += n;
- cache_ptr = c->cache_ptr;
- lz_mf_skip_positions(c->mf, n);
- if (likely(cache_ptr <= c->cache_limit)) {
- do {
- cache_ptr->len = 0;
- cache_ptr += 1;
- } while (--n && likely(cache_ptr <= c->cache_limit));
- }
- c->cache_ptr = cache_ptr;
+ put_unaligned_u16_le(os->bitbuf << (16 - os->bitcount), os->next_bits);
+ put_unaligned_u16_le(0, os->next_bits2);
+
+ return os->next_byte - os->start;
}
-static void
-xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
+static inline void
+xpress_write_extra_length_bytes(struct xpress_output_bitstream *os,
+ unsigned adjusted_len)
{
- struct lz_match *cache_ptr;
-
- c->cur_window_ptr += n;
- cache_ptr = c->cache_ptr;
- if (likely(cache_ptr <= c->cache_limit)) {
- do {
- cache_ptr += 1 + cache_ptr->len;
- } while (--n && likely(cache_ptr <= c->cache_limit));
+ /* If length >= 18, output one extra length byte.
+ * If length >= 273, output three (total) extra length bytes. */
+ if (adjusted_len >= 0xF) {
+ u8 byte1 = min(adjusted_len - 0xF, 0xFF);
+ xpress_write_byte(os, byte1);
+ if (byte1 == 0xFF)
+ xpress_write_u16(os, adjusted_len);
}
- c->cache_ptr = cache_ptr;
}
-static void
-xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
+/* Output a match or literal. */
+static inline void
+xpress_write_item(struct xpress_item item, struct xpress_output_bitstream *os,
+ const u32 codewords[], const u8 lens[])
{
- struct lz_match *cache_ptr;
+ u64 data = item.data;
+ unsigned symbol = data & 0x1FF;
- c->cur_window_ptr += n;
- cache_ptr = c->cache_ptr;
- do {
- cache_ptr += 1 + cache_ptr->len;
- } while (--n);
- c->cache_ptr = cache_ptr;
+ xpress_write_bits(os, codewords[symbol], lens[symbol]);
+
+ if (symbol >= XPRESS_NUM_CHARS) {
+ /* Match, not a literal */
+ xpress_write_extra_length_bytes(os, (data >> 9) & 0xFFFF);
+ xpress_write_bits(os, data >> 29, (data >> 25) & 0xF);
+ }
}
+/* Output a sequence of XPRESS matches and literals. */
static void
-xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
+xpress_write_items(struct xpress_output_bitstream *os,
+ const struct xpress_item items[], size_t num_items,
+ const u32 codewords[], const u8 lens[])
{
- c->cur_window_ptr += n;
- lz_mf_skip_positions(c->mf, n);
+ for (size_t i = 0; i < num_items; i++)
+ xpress_write_item(items[i], os, codewords, lens);
}
-/*
- * Skip the specified number of positions in the window (don't search for
- * matches at them).
- */
-static inline void
-xpress_skip_bytes(struct xpress_compressor *c, u32 n)
-{
- return (*c->skip_bytes_func)(c, n);
-}
+#if SUPPORT_NEAR_OPTIMAL_PARSING
/*
- * Returns the cost, in bits, required to output the literal from the previous
- * window position (the position at which matches were last searched).
+ * Follow the minimum cost path in the graph of possible match/literal choices
+ * and write out the matches/literals using the specified Huffman code.
+ *
+ * Note: this is slightly duplicated with xpress_write_items(). However, we
+ * don't want to waste time translating between intermediate match/literal
+ * representations.
*/
-static inline u32
-xpress_prev_literal_cost(const struct xpress_compressor *c)
+static void
+xpress_write_item_list(struct xpress_output_bitstream *os,
+ struct xpress_optimum_node *optimum_nodes,
+ size_t count, const u32 codewords[], const u8 lens[])
{
- return c->costs[*(c->cur_window_ptr - 1)];
+ struct xpress_optimum_node *cur_optimum_ptr = optimum_nodes;
+ struct xpress_optimum_node *end_optimum_ptr = optimum_nodes + count;
+ do {
+ unsigned length = cur_optimum_ptr->item & OPTIMUM_LEN_MASK;
+ unsigned offset = cur_optimum_ptr->item >> OPTIMUM_OFFSET_SHIFT;
+
+ if (length == 1) {
+ /* Literal */
+ unsigned literal = offset;
+
+ xpress_write_bits(os, codewords[literal], lens[literal]);
+ } else {
+ /* Match */
+ unsigned adjusted_len;
+ unsigned offset_high_bit;
+ unsigned len_hdr;
+ unsigned sym;
+
+ adjusted_len = length - XPRESS_MIN_MATCH_LEN;
+ offset_high_bit = fls32(offset);
+ len_hdr = min(0xF, adjusted_len);
+ sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
+
+ xpress_write_bits(os, codewords[sym], lens[sym]);
+ xpress_write_extra_length_bytes(os, adjusted_len);
+ xpress_write_bits(os, offset - (1U << offset_high_bit),
+ offset_high_bit);
+ }
+ cur_optimum_ptr += length;
+ } while (cur_optimum_ptr != end_optimum_ptr);
}
+#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
/*
- * Reverse the linked list of near-optimal matches so that they can be returned
- * in forwards order.
+ * Output the XPRESS-compressed data, given the sequence of match/literal
+ * "items" that was chosen to represent the input data.
*
- * Returns the first match in the list.
+ * If @near_optimal is %false, then the items are taken from the array
+ * c->chosen_items[0...count].
+ *
+ * If @near_optimal is %true, then the items are taken from the minimum cost
+ * path stored in c->optimum_nodes[0...count].
*/
-static struct lz_match
-xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
+static size_t
+xpress_write(struct xpress_compressor *c, void *out, size_t out_nbytes_avail,
+ size_t count, bool near_optimal)
{
- unsigned prev_link, saved_prev_link;
- u32 prev_match_offset, saved_prev_match_offset;
+ u8 *cptr;
+ struct xpress_output_bitstream os;
+ size_t out_size;
- c->optimum_end_idx = cur_pos;
+ /* Account for the end-of-data symbol and make the Huffman code. */
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
- saved_prev_link = c->optimum[cur_pos].prev.link;
- saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
+ /* Output the Huffman code as a series of 512 4-bit lengths. */
+ cptr = out;
+ for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
+ *cptr++ = (c->lens[i + 1] << 4) | c->lens[i];
- do {
- prev_link = saved_prev_link;
- prev_match_offset = saved_prev_match_offset;
+ xpress_init_output(&os, cptr, out_nbytes_avail - XPRESS_NUM_SYMBOLS / 2);
- saved_prev_link = c->optimum[prev_link].prev.link;
- saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
+ /* Output the Huffman-encoded items. */
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+ if (near_optimal) {
+ xpress_write_item_list(&os, c->optimum_nodes, count,
+ c->codewords, c->lens);
- c->optimum[prev_link].next.link = cur_pos;
- c->optimum[prev_link].next.match_offset = prev_match_offset;
+ } else
+#endif
+ {
+ xpress_write_items(&os, c->chosen_items, count,
+ c->codewords, c->lens);
+ }
- cur_pos = prev_link;
- } while (cur_pos != 0);
+ /* Write the end-of-data symbol (needed for MS compatibility) */
+ xpress_write_bits(&os, c->codewords[XPRESS_END_OF_DATA],
+ c->lens[XPRESS_END_OF_DATA]);
- c->optimum_cur_idx = c->optimum[0].next.link;
+ /* Flush any pending data. Then return the compressed size if the
+ * compressed data fit in the output buffer, or 0 if it did not. */
+ out_size = xpress_flush_output(&os);
+ if (out_size == 0)
+ return 0;
- return (struct lz_match)
- { .len = c->optimum_cur_idx,
- .offset = c->optimum[0].next.match_offset,
- };
+ return out_size + XPRESS_NUM_SYMBOLS / 2;
}
-/*
- * Near-optimal parsing.
- *
- * This does a forward lowest-cost path search. The search is terminated when a
- * sufficiently long match is found, when the search reaches a position with no
- * alternatives, or when the temporary 'optimum' array fills up. After
- * termination of the search, matches/literals will be returned one by one by
- * successive calls to this function. Once all the matches/literals are used
- * up, the next call to this function will begin a new search.
- */
-static struct lz_match
-xpress_choose_near_optimal_item(struct xpress_compressor *c)
+/* Tally the Huffman symbol for a literal and return the intermediate
+ * representation of that literal. */
+static inline struct xpress_item
+xpress_record_literal(struct xpress_compressor *c, unsigned literal)
{
- const struct lz_match *matches;
- unsigned num_matches;
- struct lz_match match;
- unsigned cur_pos;
- unsigned end_pos;
- struct xpress_mc_pos_data * const optimum = c->optimum;
-
- if (c->optimum_cur_idx != c->optimum_end_idx) {
- /* Return previously computed match or literal. */
- match.len = optimum[c->optimum_cur_idx].next.link -
- c->optimum_cur_idx;
- match.offset = optimum[c->optimum_cur_idx].next.match_offset;
-
- c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
- return match;
- }
-
- c->optimum_cur_idx = 0;
- c->optimum_end_idx = 0;
-
- num_matches = xpress_get_matches(c, &matches);
-
- if (num_matches == 0)
- return (struct lz_match) {};
+ c->freqs[literal]++;
- if (matches[num_matches - 1].len >= c->params.nice_match_length) {
- /* Take the long match immediately. */
- xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
- return matches[num_matches - 1];
- }
+ return (struct xpress_item) {
+ .data = literal,
+ };
+}
- /* Consider coding a literal. */
- optimum[1].cost = xpress_prev_literal_cost(c);
- optimum[1].prev.link = 0;
+/* Tally the Huffman symbol for a match and return the intermediate
+ * representation of that match. */
+static inline struct xpress_item
+xpress_record_match(struct xpress_compressor *c, unsigned length, unsigned offset)
+{
+ unsigned adjusted_len = length - XPRESS_MIN_MATCH_LEN;
+ unsigned len_hdr = min(adjusted_len, 0xF);
+ unsigned offset_high_bit = fls32(offset);
+ unsigned sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
+
+ c->freqs[sym]++;
+
+ return (struct xpress_item) {
+ .data = (u64)sym |
+ ((u64)adjusted_len << 9) |
+ ((u64)offset_high_bit << 25) |
+ ((u64)(offset ^ (1U << offset_high_bit)) << 29),
+ };
+}
- optimum[2].cost = MC_INFINITE_COST;
+/*
+ * This is the "greedy" XPRESS compressor. It always chooses the longest match.
+ * (Exception: as a heuristic, we pass up length 3 matches that have large
+ * offsets.)
+ */
+static size_t
+xpress_compress_greedy(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
+{
+ const u8 * const in_base = in;
+ const u8 * in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ unsigned len_3_too_far;
- {
- /* Consider coding a match. Cost evaluation is hand-inlined so
- * that we can do some performance hacks. */
+ if (in_nbytes <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
- unsigned i = 0;
- unsigned len = 3;
- struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
+ hc_matchfinder_init(&c->hc_mf);
- if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
- do {
- u32 offset = matches[i].offset;
- u32 offset_bsr = bsr32(offset);
- unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
- unsigned sym = XPRESS_NUM_CHARS +
- ((offset_bsr << 4) | len_hdr);
- do {
- optimum_ptr->prev.link = 0;
- optimum_ptr->prev.match_offset = offset;
- optimum_ptr->cost = offset_bsr + c->costs[sym];
- sym++;
- optimum_ptr++;
- } while (++len <= matches[i].len);
- } while (++i != num_matches);
+ do {
+ unsigned length;
+ unsigned offset;
+
+ length = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN - 1,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &offset);
+ if (length >= XPRESS_MIN_MATCH_LEN &&
+ !(length == XPRESS_MIN_MATCH_LEN && offset >= len_3_too_far))
+ {
+ /* Match found */
+ *next_chosen_item++ =
+ xpress_record_match(c, length, offset);
+ in_next += 1;
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ length - 1);
+ in_next += length - 1;
} else {
- do {
- u32 offset = matches[i].offset;
- u32 offset_bsr = bsr32(offset);
- do {
- u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
- unsigned len_hdr = min(adjusted_len, 0xf);
- unsigned sym = XPRESS_NUM_CHARS +
- ((offset_bsr << 4) | len_hdr);
- u32 cost = offset_bsr + c->costs[sym];
- if (adjusted_len >= 0xf) {
- cost += 8;
- if (adjusted_len - 0xf >= 0xff)
- cost += 16;
- }
-
- optimum_ptr->prev.link = 0;
- optimum_ptr->prev.match_offset = offset;
- optimum_ptr->cost = cost;
- optimum_ptr++;
- } while (++len <= matches[i].len);
- } while (++i != num_matches);
+ /* No match found */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *in_next);
+ in_next += 1;
}
- }
-
- end_pos = matches[num_matches - 1].len;
- cur_pos = 1;
- do {
- u32 cost;
- u32 longest_len;
+ } while (in_next != in_end);
- num_matches = xpress_get_matches(c, &matches);
+ return xpress_write(c, out, out_nbytes_avail,
+ next_chosen_item - c->chosen_items, false);
+}
- if (num_matches) {
- longest_len = matches[num_matches - 1].len;
- if (longest_len >= c->params.nice_match_length) {
- /* Take the long match immediately. */
- match = xpress_match_chooser_reverse_list(c, cur_pos);
+/*
+ * This is the "lazy" XPRESS compressor. Before choosing a match, it checks to
+ * see if there's a longer match at the next position. If yes, it outputs a
+ * literal and continues to the next position. If no, it outputs the match.
+ */
+static size_t
+xpress_compress_lazy(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
+{
+ const u8 * const in_base = in;
+ const u8 * in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ unsigned len_3_too_far;
- optimum[cur_pos].next.match_offset =
- matches[num_matches - 1].offset;
- optimum[cur_pos].next.link = cur_pos + longest_len;
- c->optimum_end_idx = cur_pos + longest_len;
+ if (in_nbytes <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
- xpress_skip_bytes(c, longest_len - 1);
+ hc_matchfinder_init(&c->hc_mf);
- return match;
- }
- } else {
- longest_len = 1;
+ do {
+ unsigned cur_len;
+ unsigned cur_offset;
+ unsigned next_len;
+ unsigned next_offset;
+
+ /* Find the longest match at the current position. */
+ cur_len = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN - 1,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &cur_offset);
+ in_next += 1;
+
+ if (cur_len < XPRESS_MIN_MATCH_LEN ||
+ (cur_len == XPRESS_MIN_MATCH_LEN &&
+ cur_offset >= len_3_too_far))
+ {
+ /* No match found. Choose a literal. */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *(in_next - 1));
+ continue;
}
- while (end_pos < cur_pos + longest_len)
- optimum[++end_pos].cost = MC_INFINITE_COST;
+ have_cur_match:
+ /* We have a match at the current position. */
- /* Consider coding a literal. */
- cost = optimum[cur_pos].cost + xpress_prev_literal_cost(c);
- if (cost < optimum[cur_pos + 1].cost) {
- optimum[cur_pos + 1].cost = cost;
- optimum[cur_pos + 1].prev.link = cur_pos;
- }
+ /* If the current match is very long, choose it immediately. */
+ if (cur_len >= c->nice_match_length) {
- if (num_matches) {
- /* Consider coding a match. Cost evaluation is
- * hand-inlined so that we can do some performance
- * hacks. */
- unsigned i = 0;
- unsigned len = 3;
- struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
- u32 cur_cost = optimum[cur_pos].cost;
-
- if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
- do {
- u32 offset = matches[i].offset;
- u32 offset_bsr = bsr32(offset);
- unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
- unsigned sym = XPRESS_NUM_CHARS +
- ((offset_bsr << 4) | len_hdr);
-
- u32 base_cost = cur_cost + offset_bsr;
- do {
- cost = base_cost + c->costs[sym];
- if (cost < optimum_ptr->cost) {
- optimum_ptr->prev.link = cur_pos;
- optimum_ptr->prev.match_offset = offset;
- optimum_ptr->cost = cost;
- }
- sym++;
- optimum_ptr++;
- } while (++len <= matches[i].len);
- } while (++i != num_matches);
- } else {
- do {
- u32 offset = matches[i].offset;
- u32 offset_bsr = bsr32(offset);
-
- u32 base_cost = cur_cost + offset_bsr;
- do {
- u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
- unsigned len_hdr = min(adjusted_len, 0xf);
- unsigned sym = XPRESS_NUM_CHARS +
- ((offset_bsr << 4) | len_hdr);
-
- cost = base_cost + c->costs[sym];
- if (adjusted_len >= 0xf) {
- cost += 8;
- if (adjusted_len - 0xf >= 0xff)
- cost += 16;
- }
-
- if (cost < optimum_ptr->cost) {
- optimum_ptr->prev.link = cur_pos;
- optimum_ptr->prev.match_offset = offset;
- optimum_ptr->cost = cost;
- }
- optimum_ptr++;
- } while (++len <= matches[i].len);
- } while (++i != num_matches);
- }
- }
+ *next_chosen_item++ =
+ xpress_record_match(c, cur_len, cur_offset);
- cur_pos++;
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ cur_len - 1);
+ in_next += cur_len - 1;
+ continue;
+ }
- } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
+ /*
+ * Try to find a match at the next position.
+ *
+ * Note: since we already have a match at the *current*
+ * position, we use only half the 'max_search_depth' when
+ * checking the *next* position. This is a useful trade-off
+ * because it's more worthwhile to use a greater search depth on
+ * the initial match than on the next match (since a lot of the
+ * time, that next match won't even be used).
+ *
+ * Note: it's possible to structure the code such that there's
+ * only one call to longest_match(), which handles both the
+ * "find the initial match" and "try to find a longer match"
+ * cases. However, it is faster to have two call sites, with
+ * longest_match() inlined at each.
+ */
+ next_len = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ cur_len,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth / 2,
+ &next_offset);
+ in_next += 1;
+
+ if (next_len > cur_len) {
+ /* Found a longer match at the next position, so output
+ * a literal. */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *(in_next - 2));
+ cur_len = next_len;
+ cur_offset = next_offset;
+ goto have_cur_match;
+ } else {
+ /* Didn't find a longer match at the next position, so
+ * output the current match. */
+ *next_chosen_item++ =
+ xpress_record_match(c, cur_len, cur_offset);
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ cur_len - 2);
+ in_next += cur_len - 2;
+ continue;
+ }
+ } while (in_next != in_end);
- return xpress_match_chooser_reverse_list(c, cur_pos);
+ return xpress_write(c, out, out_nbytes_avail,
+ next_chosen_item - c->chosen_items, false);
}
-/* Set default XPRESS Huffman symbol costs to kick-start the iterative
- * optimization algorithm. */
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+
+/*
+ * Set Huffman symbol costs for the first optimization pass.
+ *
+ * It works well to assume that each Huffman symbol is equally probable. This
+ * results in each symbol being assigned a cost of -log2(1.0/num_syms) where
+ * 'num_syms' is the number of symbols in the alphabet.
+ */
static void
-xpress_set_default_costs(u8 costs[])
+xpress_set_default_costs(struct xpress_compressor *c)
{
- unsigned i;
-
- for (i = 0; i < XPRESS_NUM_CHARS; i++)
- costs[i] = 8;
-
- for (; i < XPRESS_NUM_SYMBOLS; i++)
- costs[i] = 10;
+ for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
+ c->costs[i] = 9;
}
-/* Copy the Huffman codeword lengths array @lens to the Huffman symbol costs
- * array @costs, but also assign a default cost to each 0-length (unused)
- * codeword. */
+/* Update the cost model based on the codeword lengths @c->lens. */
static void
-xpress_set_costs(u8 costs[], const u8 lens[])
+xpress_update_costs(struct xpress_compressor *c)
{
for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
- costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
+ c->costs[i] = c->lens[i] ? c->lens[i] : XPRESS_MAX_CODEWORD_LEN;
}
-/* Near-optimal parsing */
-static u32
-xpress_choose_items_near_optimal(struct xpress_compressor *c)
+/*
+ * Follow the minimum cost path in the graph of possible match/literal choices
+ * and compute the frequencies of the Huffman symbols that are needed to output
+ * those matches and literals.
+ */
+static void
+xpress_tally_item_list(struct xpress_compressor *c,
+ struct xpress_optimum_node *end_optimum_ptr)
{
- u32 num_passes_remaining = c->params.num_optim_passes;
- const u8 *window_ptr;
- const u8 *window_end;
- struct xpress_item *next_chosen_item;
- struct lz_match raw_item;
- struct xpress_item xpress_item;
-
- xpress_set_default_costs(c->costs);
- c->optimum_cur_idx = 0;
- c->optimum_end_idx = 0;
-
- if (c->params.num_optim_passes > 1) {
- c->get_matches_func = xpress_get_matches_fillcache;
- c->skip_bytes_func = xpress_skip_bytes_fillcache;
- } else {
- c->get_matches_func = xpress_get_matches_noncaching;
- c->skip_bytes_func = xpress_skip_bytes_noncaching;
- }
+ struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes;
- lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
-
- while (--num_passes_remaining) {
- c->cur_window_ptr = c->cur_window;
- window_ptr = c->cur_window;
- window_end = window_ptr + c->cur_window_size;
- c->cache_ptr = c->cached_matches;
- memset(c->freqs, 0, sizeof(c->freqs));
-
- while (window_ptr != window_end) {
- raw_item = xpress_choose_near_optimal_item(c);
- if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
- xpress_tally_match(raw_item.len,
- raw_item.offset, c->freqs);
- window_ptr += raw_item.len;
- } else {
- xpress_tally_literal(*window_ptr, c->freqs);
- window_ptr += 1;
- }
- }
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
- xpress_set_costs(c->costs, c->lens);
- if (c->cache_ptr <= c->cache_limit) {
- c->get_matches_func = xpress_get_matches_usecache_nocheck;
- c->skip_bytes_func = xpress_skip_bytes_usecache_nocheck;
- } else {
- c->get_matches_func = xpress_get_matches_usecache;
- c->skip_bytes_func = xpress_skip_bytes_usecache;
- }
- }
+ do {
+ unsigned length = cur_optimum_ptr->item & OPTIMUM_LEN_MASK;
+ unsigned offset = cur_optimum_ptr->item >> OPTIMUM_OFFSET_SHIFT;
- c->cur_window_ptr = c->cur_window;
- window_ptr = c->cur_window;
- window_end = window_ptr + c->cur_window_size;
- c->cache_ptr = c->cached_matches;
- memset(c->freqs, 0, sizeof(c->freqs));
- next_chosen_item = c->chosen_items;
-
- u32 unseen_cost = 9;
- while (window_ptr != window_end) {
- raw_item = xpress_choose_near_optimal_item(c);
- if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
- xpress_item = xpress_tally_match(raw_item.len,
- raw_item.offset,
- c->freqs);
- window_ptr += raw_item.len;
+ if (length == 1) {
+ /* Literal */
+ unsigned literal = offset;
+
+ c->freqs[literal]++;
} else {
- xpress_item = xpress_tally_literal(*window_ptr,
- c->freqs);
- window_ptr += 1;
- }
- *next_chosen_item++ = xpress_item;
+ /* Match */
+ unsigned adjusted_len;
+ unsigned offset_high_bit;
+ unsigned len_hdr;
+ unsigned sym;
- /* When doing one-pass near-optimal parsing, rebuild the Huffman
- * code occasionally. */
- if (unlikely((next_chosen_item - c->chosen_items) % 2048 == 0) &&
- c->cur_window_size >= 16384 &&
- c->params.num_optim_passes == 1)
- {
- xpress_make_huffman_code(c);
- for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
- c->costs[i] = c->lens[i] ? c->lens[i] : unseen_cost;
- if (unseen_cost < 15)
- unseen_cost++;
+ adjusted_len = length - XPRESS_MIN_MATCH_LEN;
+ offset_high_bit = fls32(offset);
+ len_hdr = min(0xF, adjusted_len);
+ sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
+
+ c->freqs[sym]++;
}
- }
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
- return next_chosen_item - c->chosen_items;
+ cur_optimum_ptr += length;
+ } while (cur_optimum_ptr != end_optimum_ptr);
}
-/* Lazy parsing */
-static u32
-xpress_choose_items_lazy(struct xpress_compressor *c)
+/*
+ * Find a new minimum cost path through the graph of possible match/literal
+ * choices. We find the minimum cost path from 'c->optimum_nodes[0]', which
+ * represents the node at the beginning of the input buffer, to
+ * 'c->optimum_nodes[in_nbytes]', which represents the node at the end of the
+ * input buffer. Edge costs are evaluated using the cost model 'c->costs'.
+ *
+ * The algorithm works backward, starting at 'c->optimum_nodes[in_nbytes]' and
+ * proceeding backwards one position at a time. At each position, the minimum
+ * cost to reach 'c->optimum_nodes[in_nbytes]' from that position is computed
+ * and the match/literal choice is saved.
+ */
+static void
+xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
+ struct lz_match *end_cache_ptr)
{
- struct lz_mf *mf;
- u32 len_3_too_far;
- const u8 *window_ptr;
- const u8 *window_end;
- u32 num_matches;
- struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
- struct xpress_item *next_chosen_item;
- struct lz_match prev_match;
+ struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes + in_nbytes;
+ struct lz_match *cache_ptr = end_cache_ptr;
- mf = c->mf;
-
- lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
-
- if (c->cur_window_size <= 8192)
- len_3_too_far = 2048;
- else
- len_3_too_far = 4096;
-
- memset(c->freqs, 0, sizeof(c->freqs));
+ cur_optimum_ptr->cost_to_end = 0;
+ do {
+ unsigned literal;
+ u32 best_item;
+ u32 best_cost_to_end;
+ unsigned num_matches;
+ struct lz_match *match;
+ unsigned len;
- window_ptr = c->cur_window;
- window_end = c->cur_window + c->cur_window_size;
- next_chosen_item = c->chosen_items;
+ cur_optimum_ptr--;
+ cache_ptr--;
- for (;;) {
+ literal = cache_ptr->offset;
- /* Don't have match at previous position */
+ /* Consider coding a literal. */
+ best_item = ((u32)literal << OPTIMUM_OFFSET_SHIFT) | 1;
+ best_cost_to_end = c->costs[literal] +
+ (cur_optimum_ptr + 1)->cost_to_end;
- num_matches = lz_mf_get_matches(mf, matches);
- window_ptr++;
+ num_matches = cache_ptr->length;
- if (num_matches == 0 ||
- (matches[num_matches - 1].len == 3 &&
- matches[num_matches - 1].offset >= len_3_too_far))
- {
- /* No matches found => output literal */
- *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 1),
- c->freqs);
- if (window_ptr == window_end)
- break;
+ if (num_matches == 0) {
+ /* No matches; the only choice is the literal. */
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
continue;
}
- prev_match = matches[num_matches - 1];
-
- have_prev_match:
- /* Have match at previous position */
-
- if (prev_match.len >= c->params.nice_match_length) {
- /* Very long match found => output immediately */
- *next_chosen_item++ = xpress_tally_match(prev_match.len,
- prev_match.offset,
- c->freqs);
- lz_mf_skip_positions(mf, prev_match.len - 1);
- window_ptr += prev_match.len - 1;
- if (window_ptr == window_end)
- break;
- continue;
- }
+ /*
+ * Consider each match length from the minimum
+ * (XPRESS_MIN_MATCH_LEN) to the length of the longest match
+ * found at this position. For each length, consider only the
+ * smallest offset for which that length is available. Although
+ * this is not guaranteed to be optimal due to the possibility
+ * of a larger offset costing less than a smaller offset to
+ * code, this is a very useful heuristic.
+ */
+ match = cache_ptr - num_matches;
+ len = XPRESS_MIN_MATCH_LEN;
+ if (cache_ptr[-1].length < 0xF + XPRESS_MIN_MATCH_LEN) {
+ /* All lengths are small. Optimize accordingly. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
- num_matches = lz_mf_get_matches(mf, matches);
- window_ptr++;
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ len_hdr = len - XPRESS_MIN_MATCH_LEN;
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
+ } else {
+ /* Some lengths are big. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
- if (num_matches == 0 ||
- (matches[num_matches - 1].len <= prev_match.len))
- {
- /* Next match is not longer => output previous match */
- *next_chosen_item++ = xpress_tally_match(prev_match.len,
- prev_match.offset,
- c->freqs);
- lz_mf_skip_positions(mf, prev_match.len - 2);
- window_ptr += prev_match.len - 2;
- if (window_ptr == window_end)
- break;
- continue;
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned adjusted_len;
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ adjusted_len = len - XPRESS_MIN_MATCH_LEN;
+ len_hdr = min(adjusted_len, 0xF);
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (adjusted_len >= 0xF) {
+ cost_to_end += 8;
+ if (adjusted_len - 0xF >= 0xFF)
+ cost_to_end += 16;
+ }
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
}
-
- /* Next match is longer => output literal */
-
- *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 2),
- c->freqs);
-
- prev_match = matches[num_matches - 1];
-
- goto have_prev_match;
- }
-
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
- return next_chosen_item - c->chosen_items;
+ cache_ptr -= num_matches;
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
+ } while (cur_optimum_ptr != c->optimum_nodes);
}
-/* Greedy parsing */
-static u32
-xpress_choose_items_greedy(struct xpress_compressor *c)
+/*
+ * This routine finds matches at each position in the buffer in[0...in_nbytes].
+ * The matches are cached in the array c->match_cache, and the return value is a
+ * pointer past the last slot in this array that was filled.
+ */
+static struct lz_match *
+xpress_find_matches(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes)
{
- struct lz_mf *mf;
- u32 len_3_too_far;
- const u8 *window_ptr;
- const u8 *window_end;
- struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
- u32 num_matches;
- struct xpress_item *next_chosen_item;
-
- mf = c->mf;
-
- lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
+ const u8 * const in_base = in;
+ const u8 *in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct lz_match *cache_ptr = c->match_cache;
+ unsigned long prev_hash = 0;
- if (c->cur_window_size <= 8192)
- len_3_too_far = 2048;
- else
- len_3_too_far = 4096;
-
- memset(c->freqs, 0, sizeof(c->freqs));
-
- window_ptr = c->cur_window;
- window_end = c->cur_window + c->cur_window_size;
- next_chosen_item = c->chosen_items;
+ bt_matchfinder_init(&c->bt_mf);
do {
- /* Get longest match at the current position. */
- num_matches = lz_mf_get_matches(mf, matches);
+ unsigned num_matches;
- if (num_matches == 0 ||
- (matches[num_matches - 1].len == 3 &&
- matches[num_matches - 1].offset >= len_3_too_far))
- {
- *next_chosen_item++ = xpress_tally_literal(*window_ptr, c->freqs);
- window_ptr += 1;
- } else {
- u32 len = matches[num_matches - 1].len;
- u32 offset = matches[num_matches - 1].offset;
+ /* If we've found so many matches that the cache might overflow
+ * if we keep finding more, then stop finding matches. This
+ * case is very unlikely. */
+ if (unlikely(cache_ptr >= c->cache_overflow_mark)) {
+ do {
+ cache_ptr->length = 0;
+ cache_ptr->offset = *in_next++;
+ cache_ptr++;
+ } while (in_next != in_end);
+ return cache_ptr;
+ }
+
+ /* Find matches with the current position using the binary tree
+ * matchfinder and save them in the next available slots in
+ * the match cache. */
+ num_matches =
+ bt_matchfinder_get_matches(&c->bt_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &prev_hash,
+ cache_ptr);
+ cache_ptr += num_matches;
+ cache_ptr->length = num_matches;
+ cache_ptr->offset = *in_next;
+ in_next++;
+ cache_ptr++;
- *next_chosen_item++ = xpress_tally_match(len, offset, c->freqs);
- lz_mf_skip_positions(mf, len - 1);
- window_ptr += len;
+ if (num_matches) {
+ /*
+ * If there was a very long match found, then don't
+ * cache any matches for the bytes covered by that
+ * match. This avoids degenerate behavior when
+ * compressing highly redundant data, where the number
+ * of matches can be very large.
+ *
+ * This heuristic doesn't actually hurt the compression
+ * ratio very much. If there's a long match, then the
+ * data must be highly compressible, so it doesn't
+ * matter as much what we do.
+ */
+ unsigned best_len = cache_ptr[-2].length;
+ if (best_len >= c->nice_match_length) {
+ --best_len;
+ do {
+ bt_matchfinder_skip_position(&c->bt_mf,
+ in_base,
+ in_next,
+ in_end,
+ min(in_end - in_next,
+ c->nice_match_length),
+ c->max_search_depth,
+ &prev_hash);
+
+ cache_ptr->length = 0;
+ cache_ptr->offset = *in_next++;
+ cache_ptr++;
+ } while (--best_len);
+ }
}
- } while (window_ptr != window_end);
+ } while (in_next != in_end);
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
- return next_chosen_item - c->chosen_items;
+ return cache_ptr;
}
-/* Huffman-only parsing */
-static u32
-xpress_choose_items_huffonly(struct xpress_compressor *c)
+/*
+ * This is the "near-optimal" XPRESS compressor. It computes a compressed
+ * representation of the input buffer by executing a minimum cost path search
+ * over the graph of possible match/literal choices, assuming a certain cost for
+ * each Huffman symbol. The result is usually close to optimal, but it is *not*
+ * guaranteed to be optimal because of (a) heuristic restrictions in which
+ * matches are considered, and (b) symbol costs are unknown until those symbols
+ * have already been chosen --- so iterative optimization must be used, and the
+ * algorithm might converge on a local optimum rather than a global optimum.
+ */
+static size_t
+xpress_compress_near_optimal(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
{
- const u8 *window_ptr;
- const u8 *window_end;
- struct xpress_item *next_chosen_item;
-
- memset(c->freqs, 0, sizeof(c->freqs));
+ struct lz_match *end_cache_ptr;
+ unsigned num_passes_remaining = c->num_optim_passes;
- window_ptr = c->cur_window;
- window_end = c->cur_window + c->cur_window_size;
- next_chosen_item = c->chosen_items;
+ /* Run the input buffer through the matchfinder and save the results. */
+ end_cache_ptr = xpress_find_matches(c, in, in_nbytes);
+ /* The first optimization pass uses a default cost model. Each
+ * additional optimization pass uses a cost model derived from the
+ * Huffman code computed in the previous pass. */
+ xpress_set_default_costs(c);
do {
- *next_chosen_item++ = xpress_tally_literal(*window_ptr++, c->freqs);
- } while (window_ptr != window_end);
-
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
- return next_chosen_item - c->chosen_items;
-}
-
-/* Given the specified compression level and maximum window size, build the
- * parameters to use for XPRESS compression. */
-static void
-xpress_build_params(unsigned int compression_level, u32 max_window_size,
- struct xpress_compressor_params *xpress_params)
-{
- memset(xpress_params, 0, sizeof(*xpress_params));
-
- if (compression_level == 1) {
-
- /* Huffman only (no Lempel-Ziv matches) */
- xpress_params->mf_algo = LZ_MF_NULL;
- xpress_params->choose_items_func = xpress_choose_items_huffonly;
-
- } else if (compression_level < 30) {
-
- /* Greedy parsing */
- xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
- xpress_params->choose_items_func = xpress_choose_items_greedy;
- xpress_params->nice_match_length = compression_level;
- xpress_params->max_search_depth = compression_level / 2;
-
- } else if (compression_level < 60) {
-
- /* Lazy parsing */
- xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
- xpress_params->choose_items_func = xpress_choose_items_lazy;
- xpress_params->nice_match_length = compression_level;
- xpress_params->max_search_depth = compression_level / 2;
-
- } else {
-
- /* Near-optimal parsing */
- xpress_params->choose_items_func = xpress_choose_items_near_optimal;
- if (max_window_size >= 32768)
- xpress_params->mf_algo = LZ_MF_BINARY_TREES;
- else
- xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
- xpress_params->num_optim_passes = compression_level / 40;
- xpress_params->nice_match_length = min(compression_level / 2,
- XPRESS_MAX_MATCH_LEN);
- xpress_params->max_search_depth = min(compression_level,
- XPRESS_MAX_MATCH_LEN);
- }
-}
-
-/* Given the specified XPRESS parameters and maximum window size, build the
- * parameters to use for match-finding. */
-static void
-xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
- u32 max_window_size, struct lz_mf_params *mf_params)
-{
- memset(mf_params, 0, sizeof(*mf_params));
-
- mf_params->algorithm = xpress_params->mf_algo;
- mf_params->max_window_size = max_window_size;
- mf_params->min_match_len = XPRESS_MIN_MATCH_LEN;
- mf_params->max_match_len = XPRESS_MAX_MATCH_LEN;
- mf_params->max_search_depth = xpress_params->max_search_depth;
- mf_params->nice_match_len = xpress_params->nice_match_length;
-}
+ xpress_find_min_cost_path(c, in_nbytes, end_cache_ptr);
+ xpress_tally_item_list(c, c->optimum_nodes + in_nbytes);
+ if (num_passes_remaining > 1) {
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ xpress_update_costs(c);
+ xpress_reset_symbol_frequencies(c);
+ }
+ } while (--num_passes_remaining);
-static inline bool
-xpress_window_size_valid(size_t window_size)
-{
- return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
+ return xpress_write(c, out, out_nbytes_avail, in_nbytes, true);
}
-static void
-xpress_free_compressor(void *_c);
+#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
static u64
-xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
+xpress_get_needed_memory(size_t max_bufsize, unsigned compression_level)
{
- u64 size = 0;
- struct xpress_compressor_params params;
+ size_t size = 0;
- if (!xpress_window_size_valid(max_window_size))
+ if (max_bufsize > XPRESS_MAX_BUFSIZE)
return 0;
- xpress_build_params(compression_level, max_window_size, ¶ms);
-
- size += sizeof(struct xpress_compressor);
-
- size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
-
- if (params.choose_items_func == xpress_choose_items_near_optimal) {
- size += (XPRESS_OPTIM_ARRAY_LENGTH + params.nice_match_length) *
- sizeof(struct xpress_mc_pos_data);
- if (params.num_optim_passes > 1) {
- size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
- params.max_search_depth + 1);
- size += cache_len * sizeof(struct lz_match);
- } else {
- size += params.max_search_depth * sizeof(struct lz_match);
- }
+ if (compression_level < MIN_LEVEL_FOR_NEAR_OPTIMAL ||
+ !SUPPORT_NEAR_OPTIMAL_PARSING) {
+ size += offsetof(struct xpress_compressor, nonoptimal_end);
+ size += max_bufsize * sizeof(struct xpress_item);
}
-
- size += max_window_size * sizeof(struct xpress_item);
-
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+ else {
+ size += offsetof(struct xpress_compressor, optimal_end);
+ size += (max_bufsize + 1) * sizeof(struct xpress_optimum_node);
+ size += ((max_bufsize * CACHE_RESERVE_PER_POS) +
+ XPRESS_MAX_MATCH_LEN + max_bufsize) *
+ sizeof(struct lz_match);
+ }
+#endif
return size;
}
static int
-xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
+xpress_create_compressor(size_t max_bufsize, unsigned compression_level,
void **c_ret)
{
struct xpress_compressor *c;
- struct xpress_compressor_params params;
- struct lz_mf_params mf_params;
- if (!xpress_window_size_valid(max_window_size))
+ if (max_bufsize > XPRESS_MAX_BUFSIZE)
return WIMLIB_ERR_INVALID_PARAM;
- xpress_build_params(compression_level, max_window_size, ¶ms);
- xpress_build_mf_params(¶ms, max_window_size, &mf_params);
-
- c = CALLOC(1, sizeof(struct xpress_compressor));
- if (!c)
- goto oom;
-
- c->params = params;
-
- c->mf = lz_mf_alloc(&mf_params);
- if (!c->mf)
- goto oom;
-
- if (params.choose_items_func == xpress_choose_items_near_optimal) {
- c->optimum = MALLOC((XPRESS_OPTIM_ARRAY_LENGTH +
- params.nice_match_length) *
- sizeof(struct xpress_mc_pos_data));
- if (!c->optimum)
- goto oom;
- if (params.num_optim_passes > 1) {
- size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
- params.max_search_depth + 1);
- c->cached_matches = MALLOC(cache_len * sizeof(struct lz_match));
- if (!c->cached_matches)
- goto oom;
- c->cache_limit = c->cached_matches + cache_len -
- (params.max_search_depth + 1);
- } else {
- c->cached_matches = MALLOC(params.max_search_depth *
- sizeof(struct lz_match));
- if (!c->cached_matches)
- goto oom;
+ if (compression_level < 30) {
+ c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
+ nonoptimal_end),
+ MATCHFINDER_ALIGNMENT);
+ if (!c)
+ return WIMLIB_ERR_NOMEM;
+ c->impl = xpress_compress_greedy;
+ c->max_search_depth = (compression_level * 24) / 16;
+ c->nice_match_length = (compression_level * 48) / 16;
+ c->chosen_items = MALLOC(max_bufsize * sizeof(struct xpress_item));
+ if (!c->chosen_items) {
+ ALIGNED_FREE(c);
+ return WIMLIB_ERR_NOMEM;
+ }
+ } else if (compression_level < MIN_LEVEL_FOR_NEAR_OPTIMAL ||
+ !SUPPORT_NEAR_OPTIMAL_PARSING)
+ {
+ c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
+ nonoptimal_end),
+ MATCHFINDER_ALIGNMENT);
+ if (!c)
+ return WIMLIB_ERR_NOMEM;
+
+ c->impl = xpress_compress_lazy;
+ c->max_search_depth = (compression_level * 24) / 32;
+ c->nice_match_length = (compression_level * 48) / 32;
+ c->chosen_items = MALLOC(max_bufsize * sizeof(struct xpress_item));
+ if (!c->chosen_items) {
+ ALIGNED_FREE(c);
+ return WIMLIB_ERR_NOMEM;
}
}
-
- c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
- if (!c->chosen_items)
- goto oom;
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+ else {
+ c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
+ optimal_end),
+ MATCHFINDER_ALIGNMENT);
+ if (!c)
+ return WIMLIB_ERR_NOMEM;
+ c->impl = xpress_compress_near_optimal;
+ c->max_search_depth = (compression_level * 32) / 100;
+ c->nice_match_length = (compression_level * 50) / 100;
+ c->num_optim_passes = compression_level / 40;
+
+ c->optimum_nodes = MALLOC((max_bufsize + 1) *
+ sizeof(struct xpress_optimum_node));
+ c->match_cache = MALLOC(((max_bufsize * CACHE_RESERVE_PER_POS) +
+ XPRESS_MAX_MATCH_LEN + max_bufsize) *
+ sizeof(struct lz_match));
+ if (!c->optimum_nodes || !c->match_cache) {
+ FREE(c->optimum_nodes);
+ FREE(c->match_cache);
+ ALIGNED_FREE(c);
+ return WIMLIB_ERR_NOMEM;
+ }
+ c->cache_overflow_mark =
+ &c->match_cache[max_bufsize * CACHE_RESERVE_PER_POS];
+ }
+#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
*c_ret = c;
return 0;
-
-oom:
- xpress_free_compressor(c);
- return WIMLIB_ERR_NOMEM;
}
static size_t
-xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
- void *compressed_data, size_t compressed_size_avail, void *_c)
+xpress_compress(const void *in, size_t in_nbytes,
+ void *out, size_t out_nbytes_avail, void *_c)
{
struct xpress_compressor *c = _c;
- u32 num_chosen_items;
- u8 *cptr;
- struct output_bitstream ostream;
- u32 compressed_size;
- /* 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 (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
+ if (out_nbytes_avail <= XPRESS_NUM_SYMBOLS / 2 + 4)
return 0;
- /* Determine match/literal sequence to divide the data into. */
- c->cur_window = uncompressed_data;
- c->cur_window_size = uncompressed_size;
- num_chosen_items = (*c->params.choose_items_func)(c);
-
- /* Output the Huffman code as a series of 512 4-bit lengths. */
- cptr = compressed_data;
- for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
- *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4);
-
- /* Output the encoded matches/literals. */
- init_output_bitstream(&ostream, cptr,
- compressed_size_avail - XPRESS_NUM_SYMBOLS / 2 - 1);
- xpress_write_items(&ostream, c->chosen_items, num_chosen_items,
- c->codewords, c->lens);
-
- /* 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;
+ xpress_reset_symbol_frequencies(c);
- /* Return the length of the compressed data. */
- return compressed_size + XPRESS_NUM_SYMBOLS / 2;
+ return (*c->impl)(c, in, in_nbytes, out, out_nbytes_avail);
}
static void
struct xpress_compressor *c = _c;
if (c) {
- lz_mf_free(c->mf);
- FREE(c->cached_matches);
- FREE(c->optimum);
- FREE(c->chosen_items);
- FREE(c);
+ #if SUPPORT_NEAR_OPTIMAL_PARSING
+ if (c->impl == xpress_compress_near_optimal) {
+ FREE(c->optimum_nodes);
+ FREE(c->match_cache);
+ } else
+ #endif
+ FREE(c->chosen_items);
+ ALIGNED_FREE(c);
}
}
git://wimlib.net / wimlib / blobdiff