X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms_decompress.c;h=f1ee951e7a7aab586cbe28cb16d912926ffc9e83;hb=94fd0e32a64292c4e40b98fe542f4be78112e3c9;hp=d5d51417352b2ff5b81a8da2fdaaa27ca6e886ed;hpb=723d5dbc1705200082f640453f19233a386bc655;p=wimlib

diff --git a/src/lzms_decompress.c b/src/lzms_decompress.c
index d5d51417..f1ee951e 100644
--- a/src/lzms_decompress.c
+++ b/src/lzms_decompress.c
@@ -463,18 +463,22 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
 	/* Load the probability entry corresponding to the current state.  */
 	prob_entry = &probs[*state_p];
 
+	/* Update the state early.  We'll still need to OR the state with 1
+	 * later if the decoded bit is a 1.  */
+	*state_p = (*state_p << 1) & (num_states - 1);
+
+	/* Get the probability (out of LZMS_PROBABILITY_DENOMINATOR) that the
+	 * next bit is 0.  */
+	prob = lzms_get_probability(prob_entry);
+
 	/* Normalize if needed.  */
-	if (rd->range <= 0xffff) {
+	if (!(rd->range & 0xFFFF0000)) {
 		rd->range <<= 16;
 		rd->code <<= 16;
 		if (likely(rd->next != rd->end))
 			rd->code |= le16_to_cpu(*rd->next++);
 	}
 
-	/* Get the probability (out of LZMS_PROBABILITY_DENOMINATOR) that the
-	 * next bit is 0.  */
-	prob = lzms_get_probability(prob_entry);
-
 	/* Based on the probability, calculate the bound between the 0-bit
 	 * region and the 1-bit region of the range.  */
 	bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;
@@ -484,7 +488,6 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
 		rd->range = bound;
 
 		/* Update the state and probability entry based on the decoded bit.  */
-		*state_p = ((*state_p << 1) | 0) & (num_states - 1);
 		lzms_update_probability_entry(prob_entry, 0);
 		return 0;
 	} else {
@@ -493,8 +496,8 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
 		rd->code -= bound;
 
 		/* Update the state and probability entry based on the decoded bit.  */
-		*state_p = ((*state_p << 1) | 1) & (num_states - 1);
 		lzms_update_probability_entry(prob_entry, 1);
+		*state_p |= 1;
 		return 1;
 	}
 }
@@ -724,10 +727,14 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 	/* LRU queues for match sources  */
 	u32 recent_lz_offsets[LZMS_NUM_LZ_REPS + 1];
 	u64 recent_delta_pairs[LZMS_NUM_DELTA_REPS + 1];
-	u32 pending_lz_offset = 0;
-	u64 pending_delta_pair = 0;
-	const u8 *lz_offset_still_pending;
-	const u8 *delta_pair_still_pending;
+
+	/* Previous item type: 0 = literal, 1 = LZ match, 2 = delta match.
+	 * This is used to handle delayed updates of the LRU queues.  Instead of
+	 * actually delaying the updates, we can check when decoding each rep
+	 * match whether a delayed update needs to be taken into account, and if
+	 * so get the match source from slot 'rep_idx + 1' instead of from slot
+	 * 'rep_idx'.  */
+	unsigned prev_item_type = 0;
 
 	/* States and probability entries for item type disambiguation  */
 	u32 main_state = 0;
@@ -772,6 +779,7 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 		{
 			/* Literal  */
 			*out_next++ = lzms_decode_literal(d, &is);
+			prev_item_type = 0;
 
 		} else if (!lzms_decode_bit(&rd, &match_state,
 					    LZMS_NUM_MATCH_PROBS,
@@ -782,55 +790,42 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 			u32 offset;
 			u32 length;
 
+			STATIC_ASSERT(LZMS_NUM_LZ_REPS == 3);
+
 			if (!lzms_decode_bit(&rd, &lz_state,
 					     LZMS_NUM_LZ_PROBS, d->probs.lz))
 			{
 				/* Explicit offset  */
 				offset = lzms_decode_lz_offset(d, &is);
+
+				recent_lz_offsets[3] = recent_lz_offsets[2];
+				recent_lz_offsets[2] = recent_lz_offsets[1];
+				recent_lz_offsets[1] = recent_lz_offsets[0];
 			} else {
 				/* Repeat offset  */
 
-				if (pending_lz_offset != 0 &&
-				    out_next != lz_offset_still_pending)
-				{
-					BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
-					recent_lz_offsets[3] = recent_lz_offsets[2];
-					recent_lz_offsets[2] = recent_lz_offsets[1];
-					recent_lz_offsets[1] = recent_lz_offsets[0];
-					recent_lz_offsets[0] = pending_lz_offset;
-					pending_lz_offset = 0;
-				}
-
-				BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
 				if (!lzms_decode_bit(&rd, &lz_rep_states[0],
 						     LZMS_NUM_LZ_REP_PROBS,
 						     d->probs.lz_rep[0]))
 				{
-					offset = recent_lz_offsets[0];
-					recent_lz_offsets[0] = recent_lz_offsets[1];
-					recent_lz_offsets[1] = recent_lz_offsets[2];
-					recent_lz_offsets[2] = recent_lz_offsets[3];
+					offset = recent_lz_offsets[0 + (prev_item_type & 1)];
+					recent_lz_offsets[0 + (prev_item_type & 1)] = recent_lz_offsets[0];
 				} else if (!lzms_decode_bit(&rd, &lz_rep_states[1],
 							    LZMS_NUM_LZ_REP_PROBS,
 							    d->probs.lz_rep[1]))
 				{
-					offset = recent_lz_offsets[1];
-					recent_lz_offsets[1] = recent_lz_offsets[2];
-					recent_lz_offsets[2] = recent_lz_offsets[3];
+					offset = recent_lz_offsets[1 + (prev_item_type & 1)];
+					recent_lz_offsets[1 + (prev_item_type & 1)] = recent_lz_offsets[1];
+					recent_lz_offsets[1] = recent_lz_offsets[0];
 				} else {
-					offset = recent_lz_offsets[2];
-					recent_lz_offsets[2] = recent_lz_offsets[3];
+					offset = recent_lz_offsets[2 + (prev_item_type & 1)];
+					recent_lz_offsets[2 + (prev_item_type & 1)] = recent_lz_offsets[2];
+					recent_lz_offsets[2] = recent_lz_offsets[1];
+					recent_lz_offsets[1] = recent_lz_offsets[0];
 				}
 			}
-
-			if (pending_lz_offset != 0) {
-				BUILD_BUG_ON(LZMS_NUM_LZ_REPS != 3);
-				recent_lz_offsets[3] = recent_lz_offsets[2];
-				recent_lz_offsets[2] = recent_lz_offsets[1];
-				recent_lz_offsets[1] = recent_lz_offsets[0];
-				recent_lz_offsets[0] = pending_lz_offset;
-			}
-			pending_lz_offset = offset;
+			recent_lz_offsets[0] = offset;
+			prev_item_type = 1;
 
 			length = lzms_decode_length(d, &is);
 
@@ -841,8 +836,6 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 
 			lz_copy(out_next, length, offset, out_end, LZMS_MIN_MATCH_LENGTH);
 			out_next += length;
-
-			lz_offset_still_pending = out_next;
 		} else {
 			/* Delta match  */
 
@@ -854,6 +847,9 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 			u32 offset;
 			const u8 *matchptr;
 			u32 length;
+			u64 pair;
+
+			STATIC_ASSERT(LZMS_NUM_DELTA_REPS == 3);
 
 			if (!lzms_decode_bit(&rd, &delta_state,
 					     LZMS_NUM_DELTA_PROBS,
@@ -862,53 +858,37 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 				/* Explicit offset  */
 				power = lzms_decode_delta_power(d, &is);
 				raw_offset = lzms_decode_delta_offset(d, &is);
-			} else {
-				/* Repeat offset  */
-				u64 val;
-
-				if (pending_delta_pair != 0 &&
-				    out_next != delta_pair_still_pending)
-				{
-					BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
-					recent_delta_pairs[3] = recent_delta_pairs[2];
-					recent_delta_pairs[2] = recent_delta_pairs[1];
-					recent_delta_pairs[1] = recent_delta_pairs[0];
-					recent_delta_pairs[0] = pending_delta_pair;
-					pending_delta_pair = 0;
-				}
 
-				BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
+				pair = ((u64)power << 32) | raw_offset;
+				recent_delta_pairs[3] = recent_delta_pairs[2];
+				recent_delta_pairs[2] = recent_delta_pairs[1];
+				recent_delta_pairs[1] = recent_delta_pairs[0];
+			} else {
 				if (!lzms_decode_bit(&rd, &delta_rep_states[0],
 						     LZMS_NUM_DELTA_REP_PROBS,
 						     d->probs.delta_rep[0]))
 				{
-					val = recent_delta_pairs[0];
-					recent_delta_pairs[0] = recent_delta_pairs[1];
-					recent_delta_pairs[1] = recent_delta_pairs[2];
-					recent_delta_pairs[2] = recent_delta_pairs[3];
+					pair = recent_delta_pairs[0 + (prev_item_type >> 1)];
+					recent_delta_pairs[0 + (prev_item_type >> 1)] = recent_delta_pairs[0];
 				} else if (!lzms_decode_bit(&rd, &delta_rep_states[1],
 							    LZMS_NUM_DELTA_REP_PROBS,
 							    d->probs.delta_rep[1]))
 				{
-					val = recent_delta_pairs[1];
-					recent_delta_pairs[1] = recent_delta_pairs[2];
-					recent_delta_pairs[2] = recent_delta_pairs[3];
+					pair = recent_delta_pairs[1 + (prev_item_type >> 1)];
+					recent_delta_pairs[1 + (prev_item_type >> 1)] = recent_delta_pairs[1];
+					recent_delta_pairs[1] = recent_delta_pairs[0];
 				} else {
-					val = recent_delta_pairs[2];
-					recent_delta_pairs[2] = recent_delta_pairs[3];
+					pair = recent_delta_pairs[2 + (prev_item_type >> 1)];
+					recent_delta_pairs[2 + (prev_item_type >> 1)] = recent_delta_pairs[2];
+					recent_delta_pairs[2] = recent_delta_pairs[1];
+					recent_delta_pairs[1] = recent_delta_pairs[0];
 				}
-				power = val >> 32;
-				raw_offset = (u32)val;
-			}
 
-			if (pending_delta_pair != 0) {
-				BUILD_BUG_ON(LZMS_NUM_DELTA_REPS != 3);
-				recent_delta_pairs[3] = recent_delta_pairs[2];
-				recent_delta_pairs[2] = recent_delta_pairs[1];
-				recent_delta_pairs[1] = recent_delta_pairs[0];
-				recent_delta_pairs[0] = pending_delta_pair;
+				power = pair >> 32;
+				raw_offset = (u32)pair;
 			}
-			pending_delta_pair = raw_offset | ((u64)power << 32);
+			recent_delta_pairs[0] = pair;
+			prev_item_type = 2;
 
 			length = lzms_decode_length(d, &is);
 
@@ -938,8 +918,6 @@ lzms_decompress(const void * const restrict in, const size_t in_nbytes,
 				out_next++;
 				matchptr++;
 			} while (--length);
-
-			delta_pair_still_pending = out_next;
 		}
 	}