#include "wimlib/compress_common.h"
#include "wimlib/decompressor_ops.h"
#include "wimlib/decompress_common.h"
-#include "wimlib/error.h"
#include "wimlib/lzms.h"
#include "wimlib/util.h"
* 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;
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. */
s32 last_target_usages[65536];
unsigned num_extra_bits;
u32 extra_bits;
+ 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. */
slot = lzms_huffman_decode_symbol(dec);
- LZMS_ASSERT(dec->slot_base_tab != NULL);
-
/* 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;
}
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);
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 a LZ or delta match. */
static int
lzms_decode_match(struct lzms_decompressor *ctx)
{
{
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;
* 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
* block. */
num_position_slots = lzms_get_position_slot(ulen - 1) + 1;
/* 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_position_slot_base,
+ lzms_extra_position_bits,
+ num_position_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_position_slot_base,
+ lzms_extra_position_bits,
+ num_position_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");
}
if (ctx == NULL)
return WIMLIB_ERR_NOMEM;
+ /* Initialize position and length slot data if not done already. */
+ lzms_init_slots();
+
*ctx_ret = ctx;
return 0;
}
git://wimlib.net / wimlib / blobdiff