X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms-decompress.c;h=b61b0e0fb7f25df131b519631efd13e445744105;hp=f010c95c7ac2ca423c721ee03c4479d24b9b0f66;hb=06c208689d042c215bb9882232aabb0d98c01875;hpb=1fc939b7bd0b37900d974b1cd5b11df128df71f5

diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c
index f010c95c..b61b0e0f 100644
--- a/src/lzms-decompress.c
+++ b/src/lzms-decompress.c
@@ -194,7 +194,6 @@
 #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"
 
@@ -284,6 +283,8 @@ struct lzms_huffman_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;
@@ -346,23 +347,8 @@ struct lzms_decompressor {
 	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];
@@ -643,19 +629,19 @@ lzms_decode_value(struct lzms_huffman_decoder *dec)
 	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;
 }
@@ -749,17 +735,17 @@ lzms_decode_lz_match(struct lzms_decompressor *ctx)
 			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);
@@ -789,19 +775,19 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx)
 			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);
@@ -810,6 +796,7 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx)
 	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)
 {
@@ -834,9 +821,9 @@ lzms_decode_item(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);
@@ -846,25 +833,7 @@ lzms_decode_item(struct lzms_decompressor *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;
 }
 
@@ -884,11 +853,14 @@ lzms_init_range_decoder(struct lzms_range_decoder *dec,
 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;
@@ -918,9 +890,6 @@ lzms_init_decompressor(struct lzms_decompressor *ctx,
 	 * 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;
@@ -930,23 +899,29 @@ lzms_init_decompressor(struct lzms_decompressor *ctx,
 	/* 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);
 
 
@@ -972,20 +947,8 @@ lzms_init_decompressor(struct lzms_decompressor *ctx,
 		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");
 }
@@ -1078,6 +1041,9 @@ lzms_create_decompressor(size_t max_block_size,
 	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;
 }