+++ /dev/null
-/*
- * xpress-compress.c
- *
- * A compressor for the XPRESS compression format (Huffman variant).
- */
-
-/*
- * Copyright (C) 2012, 2013, 2014 Eric Biggers
- *
- * 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.
- *
- * 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 Lesser General Public License
- * along with this file; if not, see http://www.gnu.org/licenses/.
- */
-
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
-
-/*
- * 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/hc_matchfinder.h"
-#include "wimlib/unaligned.h"
-#include "wimlib/util.h"
-#include "wimlib/xpress.h"
-
-#if SUPPORT_NEAR_OPTIMAL_PARSING
-
-/*
- * 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
-
-/*
- * 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_optimum_node;
-
-#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
-
-struct xpress_item;
-
-/* The main XPRESS compressor structure */
-struct xpress_compressor {
-
- /* 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 Huffman codewords and their lengths */
- u32 codewords[XPRESS_NUM_SYMBOLS];
- u8 lens[XPRESS_NUM_SYMBOLS];
-
- /* 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 {
- 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 {
- 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
- };
-};
-
-#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 {
- /*
- * 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;
-};
-
-/*
- * 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 {
-
- /* Bits that haven't yet been written to the output buffer. */
- u32 bitbuf;
-
- /* 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_reset_symbol_frequencies(struct xpress_compressor *c)
-{
- memset(c->freqs, 0, sizeof(c->freqs));
-}
-
-/*
- * Make the Huffman code for XPRESS.
- *
- * Input: c->freqs
- * Output: c->lens and c->codewords
- */
-static void
-xpress_make_huffman_code(struct xpress_compressor *c)
-{
- make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
- c->freqs, c->lens, c->codewords);
-}
-
-/*
- * 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 void
-xpress_init_output(struct xpress_output_bitstream *os, void *buffer, size_t size)
-{
- 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;
-}
-
-/*
- * 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)
-{
- /* 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;
- }
- }
-}
-
-/*
- * Interweave a literal byte into the output bitstream.
- */
-static inline void
-xpress_write_byte(struct xpress_output_bitstream *os, u8 byte)
-{
- if (os->next_byte < os->end)
- *os->next_byte++ = byte;
-}
-
-/*
- * Interweave two literal bytes into the output bitstream.
- */
-static inline void
-xpress_write_u16(struct xpress_output_bitstream *os, u16 v)
-{
- if (os->end - os->next_byte >= 2) {
- put_unaligned_u16_le(v, os->next_byte);
- os->next_byte += 2;
- }
-}
-
-/*
- * 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 size_t
-xpress_flush_output(struct xpress_output_bitstream *os)
-{
- if (os->end - os->next_byte < 2)
- return 0;
-
- 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 inline void
-xpress_write_extra_length_bytes(struct xpress_output_bitstream *os,
- unsigned adjusted_len)
-{
- /* 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);
- }
-}
-
-/* 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[])
-{
- u64 data = item.data;
- unsigned symbol = data & 0x1FF;
-
- 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_write_items(struct xpress_output_bitstream *os,
- const struct xpress_item items[], size_t num_items,
- const u32 codewords[], const u8 lens[])
-{
- for (size_t i = 0; i < num_items; i++)
- xpress_write_item(items[i], os, codewords, lens);
-}
-
-#if SUPPORT_NEAR_OPTIMAL_PARSING
-
-/*
- * 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 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[])
-{
- 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 */
-
-/*
- * Output the XPRESS-compressed data, given the sequence of match/literal
- * "items" that was chosen to represent the input data.
- *
- * 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 size_t
-xpress_write(struct xpress_compressor *c, void *out, size_t out_nbytes_avail,
- size_t count, bool near_optimal)
-{
- u8 *cptr;
- struct xpress_output_bitstream os;
- size_t out_size;
-
- /* Account for the end-of-data symbol and make the Huffman code. */
- c->freqs[XPRESS_END_OF_DATA]++;
- xpress_make_huffman_code(c);
-
- /* 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];
-
- xpress_init_output(&os, cptr, out_nbytes_avail - XPRESS_NUM_SYMBOLS / 2);
-
- /* 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);
-
- } else
-#endif
- {
- xpress_write_items(&os, c->chosen_items, count,
- c->codewords, c->lens);
- }
-
- /* 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]);
-
- /* 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 out_size + XPRESS_NUM_SYMBOLS / 2;
-}
-
-/* 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)
-{
- c->freqs[literal]++;
-
- return (struct xpress_item) {
- .data = literal,
- };
-}
-
-/* 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),
- };
-}
-
-/*
- * 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;
-
- if (in_nbytes <= 8192)
- len_3_too_far = 2048;
- else
- len_3_too_far = 4096;
-
- hc_matchfinder_init(&c->hc_mf);
-
- 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 {
- /* No match found */
- *next_chosen_item++ =
- xpress_record_literal(c, *in_next);
- in_next += 1;
- }
- } while (in_next != in_end);
-
- return xpress_write(c, out, out_nbytes_avail,
- next_chosen_item - c->chosen_items, false);
-}
-
-/*
- * 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;
-
- if (in_nbytes <= 8192)
- len_3_too_far = 2048;
- else
- len_3_too_far = 4096;
-
- hc_matchfinder_init(&c->hc_mf);
-
- 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;
- }
-
- have_cur_match:
- /* We have a match at the current position. */
-
- /* If the current match is very long, choose it immediately. */
- if (cur_len >= c->nice_match_length) {
-
- *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 - 1);
- in_next += cur_len - 1;
- continue;
- }
-
- /*
- * 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_write(c, out, out_nbytes_avail,
- next_chosen_item - c->chosen_items, false);
-}
-
-#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(struct xpress_compressor *c)
-{
- for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
- c->costs[i] = 9;
-}
-
-/* Update the cost model based on the codeword lengths @c->lens. */
-static void
-xpress_update_costs(struct xpress_compressor *c)
-{
- for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
- c->costs[i] = c->lens[i] ? c->lens[i] : XPRESS_MAX_CODEWORD_LEN;
-}
-
-/*
- * 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)
-{
- struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes;
-
- 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;
-
- c->freqs[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);
-
- c->freqs[sym]++;
- }
- cur_optimum_ptr += length;
- } while (cur_optimum_ptr != end_optimum_ptr);
-}
-
-/*
- * 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 xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes + in_nbytes;
- struct lz_match *cache_ptr = end_cache_ptr;
-
- 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;
-
- cur_optimum_ptr--;
- cache_ptr--;
-
- literal = cache_ptr->offset;
-
- /* 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 = cache_ptr->length;
-
- 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;
- }
-
- /*
- * 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;
-
- 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;
-
- 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);
- }
- 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);
-}
-
-/*
- * 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)
-{
- 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;
-
- bt_matchfinder_init(&c->bt_mf);
-
- do {
- unsigned num_matches;
-
- /* 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++;
-
- 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 (in_next != in_end);
-
- return cache_ptr;
-}
-
-/*
- * 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)
-{
- struct lz_match *end_cache_ptr;
- unsigned num_passes_remaining = c->num_optim_passes;
-
- /* 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 {
- 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);
-
- return xpress_write(c, out, out_nbytes_avail, in_nbytes, true);
-}
-
-#endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
-
-static u64
-xpress_get_needed_memory(size_t max_bufsize, unsigned compression_level)
-{
- size_t size = 0;
-
- if (max_bufsize > XPRESS_MAX_BUFSIZE)
- return 0;
-
- 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);
- }
-#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_bufsize, unsigned compression_level,
- void **c_ret)
-{
- struct xpress_compressor *c;
-
- if (max_bufsize > XPRESS_MAX_BUFSIZE)
- return WIMLIB_ERR_INVALID_PARAM;
-
- 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;
- }
- }
-#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;
-}
-
-static size_t
-xpress_compress(const void *in, size_t in_nbytes,
- void *out, size_t out_nbytes_avail, void *_c)
-{
- struct xpress_compressor *c = _c;
-
- if (out_nbytes_avail <= XPRESS_NUM_SYMBOLS / 2 + 4)
- return 0;
-
- xpress_reset_symbol_frequencies(c);
-
- return (*c->impl)(c, in, in_nbytes, out, out_nbytes_avail);
-}
-
-static void
-xpress_free_compressor(void *_c)
-{
- struct xpress_compressor *c = _c;
-
- if (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);
- }
-}
-
-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