*/
/*
- * Copyright (C) 2013 Eric Biggers
+ * Copyright (C) 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/.
*/
/*
*
* 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 an 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}.
+ * 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
#include "wimlib/decompress_common.h"
#include "wimlib/error.h"
#include "wimlib/lzms.h"
+#include "wimlib/unaligned.h"
#include "wimlib/util.h"
#include <limits.h>
if (unlikely(is->num_le16_remaining == 0))
return -1;
- next = le16_to_cpu(*--is->in);
+ next = get_unaligned_u16_le(--is->in);
is->num_le16_remaining--;
is->bitbuf |= next << (sizeof(is->bitbuf) * 8 - is->num_filled_bits - 16);
const le16 *in, size_t in_limit)
{
rd->range = 0xffffffff;
- rd->code = ((u32)le16_to_cpu(in[0]) << 16) |
- ((u32)le16_to_cpu(in[1]) << 0);
+ rd->code = ((u32)get_unaligned_u16_le(&in[0]) << 16) |
+ ((u32)get_unaligned_u16_le(&in[1]) << 0);
rd->in = in + 2;
rd->num_le16_remaining = in_limit - 2;
}
rd->range <<= 16;
if (unlikely(rd->num_le16_remaining == 0))
return -1;
- rd->code = (rd->code << 16) | le16_to_cpu(*rd->in++);
+ rd->code = (rd->code << 16) | get_unaligned_u16_le(rd->in++);
rd->num_le16_remaining--;
}
return 0;
/* 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;
LZMS_ASSERT(dec->slot_base_tab != NULL);
LZMS_ASSERT(dec->extra_bits_tab != NULL);
- /* Read the slot (position slot, length slot, etc.), which is encoded as
- * a Huffman symbol. */
+ /* 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
out_next = ctx->out_next;
- lz_copy(out_next, length, offset, ctx->out_end);
+ lz_copy(out_next, length, offset, ctx->out_end, 1);
ctx->out_next = out_next + length;
return 0;
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);
- /* 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(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_LITERAL_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is,
- lzms_position_slot_base,
- lzms_extra_position_bits,
- 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_CODE_REBUILD_FREQ);
lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is,
- lzms_position_slot_base,
- lzms_extra_position_bits,
- 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,
}
/* 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 %zu, expected < INT32_MAX)",
- uncompressed_size);
- return -1;
- }
-
/* Decode the literals and matches. */
if (lzms_decode_items(compressed_data, compressed_size,
uncompressed_data, uncompressed_size, 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;
+ /* 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 position and length slot data if not done already. */
+ /* Initialize offset and length slot data if not done already. */
lzms_init_slots();
*ctx_ret = ctx;