/*
* lzms-decompress.c
- *
- * A decompressor for the LZMS compression format.
*/
/*
- * Copyright (C) 2013 Eric Biggers
- *
- * This file is part of wimlib, a library for working with WIM files.
+ * Copyright (C) 2013, 2014 Eric Biggers
*
- * 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.
+ * 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 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/.
*/
/*
* is a container format from which the locations and sizes (both compressed and
* uncompressed) of the constituent blocks can be determined.
*
- * A LZMS-compressed block must be read in 16-bit little endian units from both
+ * An LZMS-compressed block must be read in 16-bit little endian units from both
* directions. One logical bitstream starts at the front of the block and
* proceeds forwards. Another logical bitstream starts at the end of the block
* and proceeds backwards. Bits read from the forwards bitstream constitute
* offset is 1, regardless of match length.
*
* For LZ matches, up to 3 repeat offsets are allowed, similar to some other
- * LZ-based formats such as LZX and LZMA. They must updated in a LRU fashion,
- * except for a quirk: updates to the queue must be delayed by one LZMS item,
- * except for the removal of a repeat match. As a result, 4 entries are
- * actually needed in the queue, even though it is only possible to decode
- * references to the first 3 at any given time. The queue must be initialized
- * to the offsets {1, 2, 3, 4}.
+ * LZ-based formats such as LZX and LZMA. They must updated in an LRU fashion,
+ * except for a quirk: inserting anything to the front of the queue must be
+ * delayed by one LZMS item. The reason for this is presumably that there is
+ * almost no reason to code the same match offset twice in a row, since you
+ * might as well have coded a longer match at that offset. For this same
+ * reason, it also is a requirement that when an offset in the queue is used,
+ * that offset is removed from the queue immediately (and made pending for
+ * front-insertion after the following decoded item), and everything to the
+ * right is shifted left one queue slot. This creates a need for an "overflow"
+ * fourth entry in the queue, even though it is only possible to decode
+ * references to the first 3 entries at any given time. The queue must be
+ * initialized to the offsets {1, 2, 3, 4}.
*
* Repeat delta matches are handled similarly, but for them there are two queues
* updated in lock-step: one for powers and one for raw offsets. The power
* 1024 symbols have been decoded with it.
*
* - The LZ offset code, used for decoding the offsets of standard LZ77
- * matches. Each symbol represents a position slot, which corresponds to a
+ * matches. Each symbol represents an offset slot, which corresponds to a
* base value and some number of extra bits which must be read and added to
* the base value to reconstitute the full offset. The number of symbols in
- * this code is the number of position slots needed to represent all possible
+ * this code is the number of offset slots needed to represent all possible
* offsets in the uncompressed block. This code must be rebuilt whenever
* 1024 symbols have been decoded with it.
*
* symbols have been decoded with it.
*
* - The delta offset code, used for decoding the offsets of delta matches.
- * Each symbol corresponds to a position slot, which corresponds to a base
+ * Each symbol corresponds to an offset slot, which corresponds to a base
* value and some number of extra bits which must be read and added to the
* base value to reconstitute the full offset. The number of symbols in this
* code is equal to the number of symbols in the LZ offset code. This code
* have equal frequency. Following that, each code must be rebuilt whenever a
* certain number of symbols has been decoded with it.
*
- * In general, multiple valid Huffman codes can be constructed from a set of
- * symbol frequencies. Like other compression formats such as XPRESS, LZX, and
- * DEFLATE, the LZMS format solves this ambiguity by requiring that all Huffman
- * codes be constructed in canonical form. This form requires that same-length
- * codewords be lexicographically ordered the same way as the corresponding
- * symbols and that all shorter codewords lexicographically precede longer
- * codewords.
+ * Like other compression formats such as XPRESS, LZX, and DEFLATE, the LZMS
+ * format requires that all Huffman codes be constructed in canonical form.
+ * This form requires that same-length codewords be lexicographically ordered
+ * the same way as the corresponding symbols and that all shorter codewords
+ * lexicographically precede longer codewords. Such a code can be constructed
+ * directly from codeword lengths, although in LZMS this is not actually
+ * necessary because the codes are built using adaptive symbol frequencies.
+ *
+ * Even with the canonical code restriction, the same frequencies can be used to
+ * construct multiple valid Huffman codes. Therefore, the decompressor needs to
+ * construct the right one. Specifically, the LZMS format requires that the
+ * Huffman code be constructed as if the well-known priority queue algorithm is
+ * used and frequency ties are always broken in favor of leaf nodes. See
+ * make_canonical_huffman_code() in compress_common.c for more information.
*
- * Codewords in all the LZMS Huffman codes are limited to 15 bits. If the
- * canonical code for a given set of symbol frequencies has any codewords longer
- * than 15 bits, then all frequencies must be divided by 2, rounding up, and the
- * code construction must be attempted again.
+ * Codewords in LZMS are guaranteed to not exceed 15 bits. The format otherwise
+ * places no restrictions on codeword length. Therefore, the Huffman code
+ * construction algorithm that a correct LZMS decompressor uses need not
+ * implement length-limited code construction. But if it does (e.g. by virtue
+ * of being shared among multiple compression algorithms), the details of how it
+ * does so are unimportant, provided that the maximum codeword length parameter
+ * is set to at least 15 bits.
*
- * A LZMS-compressed block seemingly cannot have a compressed size greater than
+ * An LZMS-compressed block seemingly cannot have a compressed size greater than
* or equal to the uncompressed size. In such cases the block must be stored
* uncompressed.
*
# include "config.h"
#endif
-#include "wimlib.h"
#include "wimlib/compress_common.h"
#include "wimlib/decompressor_ops.h"
#include "wimlib/decompress_common.h"
#include "wimlib/util.h"
#include <limits.h>
-#include <pthread.h>
#define LZMS_DECODE_TABLE_BITS 10
* at a time, this needs to be 64 bits rather than 32 bits. */
u64 bitbuf;
- /* Number of bits in @bitbuf that are are used. */
+ /* Number of bits in @bitbuf that are used. */
unsigned num_filled_bits;
/* Pointer to the one past the next little-endian 16-bit integer in the
size_t num_le16_remaining;
};
-/* Probability entry for use by the range decoder when in a specific state. */
-struct lzms_probability_entry {
-
- /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
- * have been decoded using this probability entry. This is a cached
- * value because it can be computed as LZMS_PROBABILITY_MAX minus the
- * Hamming weight of the low-order LZMS_PROBABILITY_MAX bits of
- * @recent_bits. */
- u32 num_recent_zero_bits;
-
- /* The most recent LZMS_PROBABILITY_MAX bits that have been decoded
- * using this probability entry. The size of this variable, in bits,
- * must be at least LZMS_PROBABILITY_MAX. */
- u64 recent_bits;
-};
-
/* Structure used for range decoding. This wraps around `struct
* lzms_range_decoder_raw' to use and maintain probability entries. */
struct lzms_range_decoder {
* read using this decoder. */
const u32 *slot_base_tab;
+ const u8 *extra_bits_tab;
+
/* Number of symbols that have been read using this code far. Reset to
* 0 whenever the code is rebuilt. */
u32 num_syms_read;
u8 lens[LZMS_MAX_NUM_SYMS];
/* The codeword of each symbol in the Huffman code. */
- u16 codewords[LZMS_MAX_NUM_SYMS];
+ u32 codewords[LZMS_MAX_NUM_SYMS];
/* A table for quickly decoding symbols encoded using the Huffman code.
*/
struct lzms_huffman_decoder delta_power_decoder;
struct lzms_huffman_decoder delta_offset_decoder;
- /* LRU (least-recently-used) queue of LZ match offsets. */
- u64 recent_lz_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
-
- /* LRU (least-recently-used) queue of delta match powers. */
- u32 recent_delta_powers[LZMS_NUM_RECENT_OFFSETS + 1];
-
- /* LRU (least-recently-used) queue of delta match offsets. */
- u32 recent_delta_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
-
- /* These variables are used to delay updates to the LRU queues by one
- * decoded item. */
- u32 prev_lz_offset;
- u32 prev_delta_power;
- u32 prev_delta_offset;
- u32 upcoming_lz_offset;
- u32 upcoming_delta_power;
- u32 upcoming_delta_offset;
+ /* LRU (least-recently-used) queues for match information. */
+ struct lzms_lru_queues lru;
- /* Used for postprocessing */
+ /* Used for postprocessing. */
s32 last_target_usages[65536];
};
-/* A table that maps position slots to their base values. These are constants
- * computed at runtime by lzms_compute_slot_bases(). */
-static u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
-
-/* A table that maps length slots to their base values. These are constants
- * computed at runtime by lzms_compute_slot_bases(). */
-static u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
-
-static void
-lzms_decode_delta_rle_slot_bases(u32 slot_bases[],
- const u8 delta_run_lens[], size_t num_run_lens)
-{
- u32 delta = 1;
- u32 base = 0;
- size_t slot = 0;
- for (size_t i = 0; i < num_run_lens; i++) {
- u8 run_len = delta_run_lens[i];
- while (run_len--) {
- base += delta;
- slot_bases[slot++] = base;
- }
- delta <<= 1;
- }
-}
-
-/* Initialize the global position and length slot tables. */
-static void
-lzms_compute_slot_bases(void)
-{
- /* If an explicit formula that maps LZMS position and length slots to
- * slot bases exists, then it could be used here. But until one is
- * found, the following code fills in the slots using the observation
- * that the increase from one slot base to the next is an increasing
- * power of 2. Therefore, run-length encoding of the delta of adjacent
- * entries can be used. */
- static const u8 position_slot_delta_run_lens[] = {
- 9, 0, 9, 7, 10, 15, 15, 20,
- 20, 30, 33, 40, 42, 45, 60, 73,
- 80, 85, 95, 105, 6,
- };
-
- static const u8 length_slot_delta_run_lens[] = {
- 27, 4, 6, 4, 5, 2, 1, 1,
- 1, 1, 1, 0, 0, 0, 0, 0,
- 1,
- };
-
- lzms_decode_delta_rle_slot_bases(lzms_position_slot_base,
- position_slot_delta_run_lens,
- ARRAY_LEN(position_slot_delta_run_lens));
-
- lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS] = 0x7fffffff;
-
- lzms_decode_delta_rle_slot_bases(lzms_length_slot_base,
- length_slot_delta_run_lens,
- ARRAY_LEN(length_slot_delta_run_lens));
-
- lzms_length_slot_base[LZMS_NUM_LEN_SYMS] = 0x400108ab;
-}
-
-/* Initialize the global position length slot tables if not done so already. */
-static void
-lzms_init_slot_bases(void)
-{
- static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
- static bool already_computed = false;
-
- if (unlikely(!already_computed)) {
- pthread_mutex_lock(&mutex);
- if (!already_computed) {
- lzms_compute_slot_bases();
- already_computed = true;
- }
- pthread_mutex_unlock(&mutex);
- }
-}
-
-/* Return the position slot for the specified offset. */
-static u32
-lzms_get_position_slot_raw(u32 offset)
-{
- u32 position_slot = 0;
- while (lzms_position_slot_base[position_slot + 1] <= offset)
- position_slot++;
- return position_slot;
-}
-
/* Initialize the input bitstream @is to read forwards from the specified
* compressed data buffer @in that is @in_limit 16-bit integers long. */
static void
/* Load the probability entry corresponding to the current state. */
prob_entry = &dec->prob_entries[dec->state];
- /* Treat the number of zero bits in the most recently decoded
- * LZMS_PROBABILITY_MAX bits with this probability entry as the chance,
- * out of LZMS_PROBABILITY_MAX, that the next bit will be a 0. However,
- * don't allow 0% or 100% probabilities. */
- prob = prob_entry->num_recent_zero_bits;
- if (prob == LZMS_PROBABILITY_MAX)
- prob = LZMS_PROBABILITY_MAX - 1;
- else if (prob == 0)
- prob = 1;
+ /* Get the probability that the next bit is 0. */
+ prob = lzms_get_probability(prob_entry);
/* Decode the next bit. */
bit = lzms_range_decoder_raw_decode_bit(dec->rd, prob);
- /* Update the state based on the newly decoded bit. */
+ /* Update the state and probability entry based on the decoded bit. */
dec->state = (((dec->state << 1) | bit) & dec->mask);
-
- /* Update the recent bits, including the cached count of 0's. */
- BUILD_BUG_ON(LZMS_PROBABILITY_MAX > sizeof(prob_entry->recent_bits) * 8);
- if (bit == 0) {
- if (prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1))) {
- /* Replacing 1 bit with 0 bit; increment the zero count.
- */
- prob_entry->num_recent_zero_bits++;
- }
- } else {
- if (!(prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1)))) {
- /* Replacing 0 bit with 1 bit; decrement the zero count.
- */
- prob_entry->num_recent_zero_bits--;
- }
- }
- prob_entry->recent_bits = (prob_entry->recent_bits << 1) | bit;
+ lzms_update_probability_entry(prob_entry, bit);
/* Return the decoded bit. */
return bit;
static void
lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec)
{
- int ret;
/* XXX: This implementation makes use of code already implemented for
* the XPRESS and LZX compression formats. However, since for the
dec->num_syms);
make_canonical_huffman_code(dec->num_syms, LZMS_MAX_CODEWORD_LEN,
dec->sym_freqs, dec->lens, dec->codewords);
- ret = make_huffman_decode_table(dec->decode_table, dec->num_syms,
- LZMS_DECODE_TABLE_BITS, dec->lens,
- LZMS_MAX_CODEWORD_LEN);
+#if defined(ENABLE_LZMS_DEBUG)
+ int ret =
+#endif
+ make_huffman_decode_table(dec->decode_table, dec->num_syms,
+ LZMS_DECODE_TABLE_BITS, dec->lens,
+ LZMS_MAX_CODEWORD_LEN);
LZMS_ASSERT(ret == 0);
}
/* Decode and return the next Huffman-encoded symbol from the LZMS-compressed
* block using the specified Huffman decoder. */
static u32
-lzms_decode_huffman_symbol(struct lzms_huffman_decoder *dec)
+lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec)
{
- const u8 *lens = dec->lens;
const u16 *decode_table = dec->decode_table;
struct lzms_input_bitstream *is = dec->is;
+ u16 entry;
+ u16 key_bits;
+ u16 sym;
/* The Huffman codes used in LZMS are adaptive and must be rebuilt
* whenever a certain number of symbols have been read. Each such
dec->num_syms_read = 0;
}
- /* In the following Huffman decoding implementation, the first
- * LZMS_DECODE_TABLE_BITS of the input are used as an offset into a
- * decode table. The entry will either provide the decoded symbol
- * directly, or else a "real" Huffman binary tree will be searched to
- * decode the symbol. */
-
+ /* XXX: Copied from read_huffsym() (decompress_common.h), since this
+ * uses a different input bitstream type. Should unify the
+ * implementations. */
lzms_input_bitstream_ensure_bits(is, LZMS_MAX_CODEWORD_LEN);
- u16 key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS);
- u16 sym = decode_table[key_bits];
-
- if (sym < dec->num_syms) {
- /* Fast case: The decode table directly provided the symbol. */
- lzms_input_bitstream_remove_bits(is, lens[sym]);
+ /* Index the decode table by the next table_bits bits of the input. */
+ key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS);
+ entry = decode_table[key_bits];
+ if (likely(entry < 0xC000)) {
+ /* Fast case: The decode table directly provided the symbol and
+ * codeword length. The low 11 bits are the symbol, and the
+ * high 5 bits are the codeword length. */
+ lzms_input_bitstream_remove_bits(is, entry >> 11);
+ sym = entry & 0x7FF;
} else {
- /* Slow case: The symbol took too many bits to include directly
- * in the decode table, so search for it in a binary tree at the
- * end of the decode table. */
+ /* Slow case: The codeword for the symbol is longer than
+ * table_bits, so the symbol does not have an entry directly in
+ * the first (1 << table_bits) entries of the decode table.
+ * Traverse the appropriate binary tree bit-by-bit in order to
+ * decode the symbol. */
lzms_input_bitstream_remove_bits(is, LZMS_DECODE_TABLE_BITS);
do {
- key_bits = sym + lzms_input_bitstream_pop_bits(is, 1);
- } while ((sym = decode_table[key_bits]) >= dec->num_syms);
+ key_bits = (entry & 0x3FFF) + lzms_input_bitstream_pop_bits(is, 1);
+ } while ((entry = decode_table[key_bits]) >= 0xC000);
+ sym = entry;
}
/* Tally and return the decoded symbol. */
unsigned num_extra_bits;
u32 extra_bits;
- /* Read the slot (position slot, length slot, etc.), which is encoded as
- * a Huffman symbol. */
- slot = lzms_decode_huffman_symbol(dec);
-
LZMS_ASSERT(dec->slot_base_tab != NULL);
+ LZMS_ASSERT(dec->extra_bits_tab != NULL);
+
+ /* Read the slot (offset slot, length slot, etc.), which is encoded as a
+ * Huffman symbol. */
+ slot = lzms_huffman_decode_symbol(dec);
/* Get the number of extra bits needed to represent the range of values
* that share the slot. */
- num_extra_bits = bsr32(dec->slot_base_tab[slot + 1] -
- dec->slot_base_tab[slot]);
+ num_extra_bits = dec->extra_bits_tab[slot];
- /* Read the number of extra bits and add them to the slot to form the
- * final decoded value. */
+ /* Read the number of extra bits and add them to the slot base to form
+ * the final decoded value. */
extra_bits = lzms_input_bitstream_read_bits(dec->is, num_extra_bits);
return dec->slot_base_tab[slot] + extra_bits;
}
lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset)
{
u8 *out_next;
- u8 *matchptr;
if (length > ctx->out_end - ctx->out_next) {
LZMS_DEBUG("Match overrun!");
}
out_next = ctx->out_next;
- matchptr = out_next - offset;
- while (length--)
- *out_next++ = *matchptr++;
- ctx->out_next = out_next;
+ lz_copy(out_next, length, offset, ctx->out_end);
+ ctx->out_next = out_next + length;
+
return 0;
}
if (!lzms_range_decode_bit(&ctx->lz_repeat_match_range_decoders[i]))
break;
- offset = ctx->recent_lz_offsets[i];
+ offset = ctx->lru.lz.recent_offsets[i];
for (; i < LZMS_NUM_RECENT_OFFSETS; i++)
- ctx->recent_lz_offsets[i] = ctx->recent_lz_offsets[i + 1];
+ ctx->lru.lz.recent_offsets[i] = ctx->lru.lz.recent_offsets[i + 1];
}
/* Decode match length, which is always given explicitly (there is no
* LRU queue for repeat lengths). */
length = lzms_decode_value(&ctx->length_decoder);
- ctx->upcoming_lz_offset = offset;
+ ctx->lru.lz.upcoming_offset = offset;
LZMS_DEBUG("Decoded %s LZ match: length=%u, offset=%u",
(bit ? "repeat" : "explicit"), length, offset);
bit = lzms_range_decode_bit(&ctx->delta_match_range_decoder);
if (bit == 0) {
- power = lzms_decode_huffman_symbol(&ctx->delta_power_decoder);
+ power = lzms_huffman_decode_symbol(&ctx->delta_power_decoder);
raw_offset = lzms_decode_value(&ctx->delta_offset_decoder);
} else {
int i;
if (!lzms_range_decode_bit(&ctx->delta_repeat_match_range_decoders[i]))
break;
- power = ctx->recent_delta_powers[i];
- raw_offset = ctx->recent_delta_offsets[i];
+ power = ctx->lru.delta.recent_powers[i];
+ raw_offset = ctx->lru.delta.recent_offsets[i];
for (; i < LZMS_NUM_RECENT_OFFSETS; i++) {
- ctx->recent_delta_powers[i] = ctx->recent_delta_powers[i + 1];
- ctx->recent_delta_offsets[i] = ctx->recent_delta_offsets[i + 1];
+ ctx->lru.delta.recent_powers[i] = ctx->lru.delta.recent_powers[i + 1];
+ ctx->lru.delta.recent_offsets[i] = ctx->lru.delta.recent_offsets[i + 1];
}
}
length = lzms_decode_value(&ctx->length_decoder);
- ctx->upcoming_delta_power = power;
- ctx->upcoming_delta_offset = raw_offset;
+ ctx->lru.delta.upcoming_power = power;
+ ctx->lru.delta.upcoming_offset = raw_offset;
LZMS_DEBUG("Decoded %s delta match: length=%u, power=%u, raw_offset=%u",
(bit ? "repeat" : "explicit"), length, power, raw_offset);
return lzms_copy_delta_match(ctx, length, power, raw_offset);
}
+/* Decode an LZ or delta match. */
static int
lzms_decode_match(struct lzms_decompressor *ctx)
{
static int
lzms_decode_literal(struct lzms_decompressor *ctx)
{
- u8 literal = lzms_decode_huffman_symbol(&ctx->literal_decoder);
+ u8 literal = lzms_huffman_decode_symbol(&ctx->literal_decoder);
LZMS_DEBUG("Decoded literal: 0x%02x", literal);
return lzms_copy_literal(ctx, literal);
}
{
int ret;
- ctx->upcoming_delta_offset = 0;
- ctx->upcoming_lz_offset = 0;
- ctx->upcoming_delta_power = 0;
+ ctx->lru.lz.upcoming_offset = 0;
+ ctx->lru.delta.upcoming_power = 0;
+ ctx->lru.delta.upcoming_offset = 0;
if (lzms_range_decode_bit(&ctx->main_range_decoder))
ret = lzms_decode_match(ctx);
if (ret)
return ret;
- /* Update LRU queues */
- if (ctx->prev_lz_offset != 0) {
- for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--)
- ctx->recent_lz_offsets[i + 1] = ctx->recent_lz_offsets[i];
- ctx->recent_lz_offsets[0] = ctx->prev_lz_offset;
- }
-
- if (ctx->prev_delta_offset != 0) {
- for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) {
- ctx->recent_delta_powers[i + 1] = ctx->recent_delta_powers[i];
- ctx->recent_delta_offsets[i + 1] = ctx->recent_delta_offsets[i];
- }
- ctx->recent_delta_powers[0] = ctx->prev_delta_power;
- ctx->recent_delta_offsets[0] = ctx->prev_delta_offset;
- }
-
- ctx->prev_lz_offset = ctx->upcoming_lz_offset;
- ctx->prev_delta_offset = ctx->upcoming_delta_offset;
- ctx->prev_delta_power = ctx->upcoming_delta_power;
+ lzms_update_lru_queues(&ctx->lru);
return 0;
}
static void
lzms_init_huffman_decoder(struct lzms_huffman_decoder *dec,
struct lzms_input_bitstream *is,
- const u32 *slot_base_tab, unsigned num_syms,
+ const u32 *slot_base_tab,
+ const u8 *extra_bits_tab,
+ unsigned num_syms,
unsigned rebuild_freq)
{
dec->is = is;
dec->slot_base_tab = slot_base_tab;
+ dec->extra_bits_tab = extra_bits_tab;
dec->num_syms = num_syms;
dec->num_syms_read = rebuild_freq;
dec->rebuild_freq = rebuild_freq;
const void *cdata, unsigned clen,
void *ubuf, unsigned ulen)
{
- unsigned num_position_slots;
+ unsigned num_offset_slots;
LZMS_DEBUG("Initializing decompressor (clen=%u, ulen=%u)", clen, ulen);
* backwards) */
lzms_input_bitstream_init(&ctx->is, cdata, clen / 2);
- /* Initialize position and length slot bases if not done already. */
- lzms_init_slot_bases();
-
- /* Calculate the number of position slots needed for this compressed
+ /* Calculate the number of offset slots needed for this compressed
* block. */
- num_position_slots = lzms_get_position_slot_raw(ulen - 1) + 1;
+ num_offset_slots = lzms_get_offset_slot(ulen - 1) + 1;
- LZMS_DEBUG("Using %u position slots", num_position_slots);
+ LZMS_DEBUG("Using %u offset slots", num_offset_slots);
/* Initialize Huffman decoders for each alphabet used in the compressed
* representation. */
lzms_init_huffman_decoder(&ctx->literal_decoder, &ctx->is,
- NULL, LZMS_NUM_LITERAL_SYMS,
+ NULL, NULL, LZMS_NUM_LITERAL_SYMS,
LZMS_LITERAL_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is,
- lzms_position_slot_base, num_position_slots,
+ lzms_offset_slot_base,
+ lzms_extra_offset_bits,
+ num_offset_slots,
LZMS_LZ_OFFSET_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->length_decoder, &ctx->is,
- lzms_length_slot_base, LZMS_NUM_LEN_SYMS,
+ lzms_length_slot_base,
+ lzms_extra_length_bits,
+ LZMS_NUM_LEN_SYMS,
LZMS_LENGTH_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is,
- lzms_position_slot_base, num_position_slots,
+ lzms_offset_slot_base,
+ lzms_extra_offset_bits,
+ num_offset_slots,
LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->delta_power_decoder, &ctx->is,
- NULL, LZMS_NUM_DELTA_POWER_SYMS,
+ NULL, NULL, LZMS_NUM_DELTA_POWER_SYMS,
LZMS_DELTA_POWER_CODE_REBUILD_FREQ);
lzms_init_range_decoder(&ctx->delta_repeat_match_range_decoders[i],
&ctx->rd, LZMS_NUM_DELTA_REPEAT_MATCH_STATES);
- /* Initialize the LRU queue for recent match offsets. */
- for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++)
- ctx->recent_lz_offsets[i] = i + 1;
-
- for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) {
- ctx->recent_delta_powers[i] = 0;
- ctx->recent_delta_offsets[i] = i + 1;
- }
- ctx->prev_lz_offset = 0;
- ctx->prev_delta_offset = 0;
- ctx->prev_delta_power = 0;
- ctx->upcoming_lz_offset = 0;
- ctx->upcoming_delta_offset = 0;
- ctx->upcoming_delta_power = 0;
+ /* Initialize LRU match information. */
+ lzms_init_lru_queues(&ctx->lru);
LZMS_DEBUG("Decompressor successfully initialized");
}
return 0;
}
-static s32
-lzms_try_x86_translation(u8 *ubuf, s32 i, s32 num_op_bytes,
- s32 *closest_target_usage_p, s32 last_target_usages[],
- s32 max_trans_offset)
-{
- u16 pos;
-
- if (i - *closest_target_usage_p <= max_trans_offset) {
- LZMS_DEBUG("Performed x86 translation at position %d "
- "(opcode 0x%02x)", i, ubuf[i]);
- le32 *p32 = (le32*)&ubuf[i + num_op_bytes];
- u32 n = le32_to_cpu(*p32);
- *p32 = cpu_to_le32(n - i);
- }
-
- pos = i + le16_to_cpu(*(const le16*)&ubuf[i + num_op_bytes]);
-
- i += num_op_bytes + sizeof(le32) - 1;
-
- if (i - last_target_usages[pos] <= LZMS_X86_MAX_GOOD_TARGET_OFFSET)
- *closest_target_usage_p = i;
-
- last_target_usages[pos] = i;
-
- return i + 1;
-}
-
-static s32
-lzms_process_x86_translation(u8 *ubuf, s32 i, s32 *closest_target_usage_p,
- s32 last_target_usages[])
-{
- /* Switch on first byte of the opcode, assuming it is really an x86
- * instruction. */
- switch (ubuf[i]) {
- case 0x48:
- if (ubuf[i + 1] == 0x8b) {
- if (ubuf[i + 2] == 0x5 || ubuf[i + 2] == 0xd) {
- /* Load relative (x86_64) */
- return lzms_try_x86_translation(ubuf, i, 3,
- closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET);
- }
- } else if (ubuf[i + 1] == 0x8d) {
- if ((ubuf[i + 2] & 0x7) == 0x5) {
- /* Load effective address relative (x86_64) */
- return lzms_try_x86_translation(ubuf, i, 3,
- closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET);
- }
- }
- break;
-
- case 0x4c:
- if (ubuf[i + 1] == 0x8d) {
- if ((ubuf[i + 2] & 0x7) == 0x5) {
- /* Load effective address relative (x86_64) */
- return lzms_try_x86_translation(ubuf, i, 3,
- closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET);
- }
- }
- break;
-
- case 0xe8:
- /* Call relative */
- return lzms_try_x86_translation(ubuf, i, 1, closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET / 2);
-
- case 0xe9:
- /* Jump relative */
- return i + 5;
-
- case 0xf0:
- if (ubuf[i + 1] == 0x83 && ubuf[i + 2] == 0x05) {
- /* Lock add relative */
- return lzms_try_x86_translation(ubuf, i, 3,
- closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET);
- }
- break;
-
- case 0xff:
- if (ubuf[i + 1] == 0x15) {
- /* Call indirect */
- return lzms_try_x86_translation(ubuf, i, 2,
- closest_target_usage_p,
- last_target_usages,
- LZMS_X86_MAX_TRANSLATION_OFFSET);
- }
- break;
- }
- return i + 1;
-}
-
-/* Postprocess the uncompressed data by undoing the translation of relative
- * addresses embedded in x86 instructions into absolute addresses.
- *
- * There does not appear to be any way to check to see if this postprocessing
- * actually needs to be done (or to plug in alternate filters, like in LZMA),
- * and the corresponding preprocessing seems to be done unconditionally. */
-static void
-lzms_postprocess_data(u8 *ubuf, s32 ulen, s32 *last_target_usages)
-{
- /* Offset (from beginning of buffer) of the most recent reference to a
- * seemingly valid target address. */
- s32 closest_target_usage = -LZMS_X86_MAX_TRANSLATION_OFFSET - 1;
-
- /* Initialize the last_target_usages array. Each entry will contain the
- * offset (from beginning of buffer) of the most recently used target
- * address beginning with two bytes equal to the array index. */
- for (s32 i = 0; i < 65536; i++)
- last_target_usages[i] = -LZMS_X86_MAX_GOOD_TARGET_OFFSET - 1;
-
- /* Check each byte in the buffer for an x86 opcode for which a
- * translation may be possible. No translations are done on any
- * instructions starting in the last 11 bytes of the buffer. */
- for (s32 i = 0; i < ulen - 11; )
- i = lzms_process_x86_translation(ubuf, i, &closest_target_usage,
- last_target_usages);
-}
-
static int
lzms_decompress(const void *compressed_data, size_t compressed_size,
void *uncompressed_data, size_t uncompressed_size, void *_ctx)
return -1;
}
- /* A LZMS-compressed data block should be evenly divisible into 16-bit
+ /* An LZMS-compressed data block should be evenly divisible into 16-bit
* integers. */
if (compressed_size % 2 != 0) {
LZMS_DEBUG("Compressed size not divisible by 2 (got %zu)",
}
/* Handle the trivial case where nothing needs to be decompressed.
- * (Necessary because a window of size 0 does not have a valid position
+ * (Necessary because a window of size 0 does not have a valid offset
* slot.) */
if (uncompressed_size == 0)
return 0;
- /* The x86 post-processor requires that the uncompressed length fit into
- * a signed 32-bit integer. Also, the position slot table cannot be
- * searched for a position of INT32_MAX or greater. */
- if (uncompressed_size >= INT32_MAX) {
- LZMS_DEBUG("Uncompressed length too large "
- "(got %u, expected < INT32_MAX)", ulen);
- return -1;
- }
-
/* Decode the literals and matches. */
if (lzms_decode_items(compressed_data, compressed_size,
uncompressed_data, uncompressed_size, ctx))
return -1;
/* Postprocess the data. */
- lzms_postprocess_data(uncompressed_data, uncompressed_size,
- ctx->last_target_usages);
+ lzms_x86_filter(uncompressed_data, uncompressed_size,
+ ctx->last_target_usages, true);
LZMS_DEBUG("Decompression successful.");
return 0;
{
struct lzms_decompressor *ctx = _ctx;
- FREE(ctx);
+ ALIGNED_FREE(ctx);
}
static int
-lzms_create_decompressor(size_t max_block_size,
- const struct wimlib_decompressor_params_header *params,
- void **ctx_ret)
+lzms_create_decompressor(size_t max_block_size, void **ctx_ret)
{
struct lzms_decompressor *ctx;
- ctx = MALLOC(sizeof(struct lzms_decompressor));
+ /* The x86 post-processor requires that the uncompressed length fit into
+ * a signed 32-bit integer. Also, the offset slot table cannot be
+ * searched for an offset of INT32_MAX or greater. */
+ if (max_block_size >= INT32_MAX)
+ return WIMLIB_ERR_INVALID_PARAM;
+
+ ctx = ALIGNED_MALLOC(sizeof(struct lzms_decompressor),
+ DECODE_TABLE_ALIGNMENT);
if (ctx == NULL)
return WIMLIB_ERR_NOMEM;
+ /* Initialize offset and length slot data if not done already. */
+ lzms_init_slots();
+
*ctx_ret = ctx;
return 0;
}
git://wimlib.net / wimlib / blobdiff