X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Flzms.h;h=76381a416829de89773d65de795d788cd7b06b7f;hb=bf37aaad751707696439d5070eeaea8d7e9a9e14;hp=177ad548606b91daeb64fc6b85b507905fa121c8;hpb=63195f84da11e0ea9ee226edc050835862275ebb;p=wimlib

diff --git a/include/wimlib/lzms.h b/include/wimlib/lzms.h
index 177ad548..76381a41 100644
--- a/include/wimlib/lzms.h
+++ b/include/wimlib/lzms.h
@@ -8,12 +8,15 @@
 #ifdef ENABLE_LZMS_DEBUG
 #	define LZMS_DEBUG DEBUG
 #       define LZMS_ASSERT wimlib_assert
+#       include "wimlib/assert.h"
+#       include "wimlib/error.h"
 #else
 #	define LZMS_DEBUG(format, ...)
 #	define LZMS_ASSERT(...)
 #endif
 
 #define LZMS_NUM_RECENT_OFFSETS			3
+#define LZMS_MAX_INIT_RECENT_OFFSET		(LZMS_NUM_RECENT_OFFSETS + 1)
 
 #define LZMS_PROBABILITY_BITS			6
 #define LZMS_PROBABILITY_MAX			(1U << LZMS_PROBABILITY_BITS)
@@ -47,7 +50,7 @@
 
 /* Code shared between the LZMS decompressor and compressor.  */
 
-#include <wimlib/types.h>
+#include <wimlib/util.h>
 
 extern void
 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
@@ -68,28 +71,99 @@ struct lzms_probability_entry {
 	u64 recent_bits;
 };
 
+/* LRU queues for LZ matches.  */
+struct lzms_lz_lru_queues {
+
+        /* Recent LZ match offsets  */
+	u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
+
+        /* These variables are used to delay updates to the LRU queues by one
+         * decoded item.  */
+	u32 prev_offset;
+	u32 upcoming_offset;
+};
+
+/* LRU queues for delta matches.  */
+struct lzms_delta_lru_queues {
+
+        /* Recent delta match powers and offsets  */
+	u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
+	u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
+
+        /* These variables are used to delay updates to the LRU queues by one
+         * decoded item.  */
+	u32 prev_power;
+	u32 prev_offset;
+	u32 upcoming_power;
+	u32 upcoming_offset;
+};
+
+/* LRU (least-recently-used) queues for match information.  */
+struct lzms_lru_queues {
+        struct lzms_lz_lru_queues lz;
+        struct lzms_delta_lru_queues delta;
+};
+
 extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
 
+extern u8 lzms_extra_position_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+
+extern u16 lzms_order_to_position_slot_bounds[30][2];
+
 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
 
+#define LZMS_NUM_FAST_LENGTHS 1024
+extern u8 lzms_length_slot_fast[LZMS_NUM_FAST_LENGTHS];
+
+extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
+
 extern void
-lzms_init_slot_bases(void);
+lzms_init_slots(void);
 
+/* Return the slot for the specified value.  */
 extern u32
-lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
+lzms_get_slot(u32 value, const u32 slot_base_tab[], u32 num_slots);
 
 static inline u32
-lzms_get_position_slot(u32 value)
+lzms_get_position_slot(u32 position)
 {
-	return lzms_get_slot(value, lzms_position_slot_base,
-			     LZMS_MAX_NUM_OFFSET_SYMS);
+	u32 order = bsr32(position);
+	u32 l = lzms_order_to_position_slot_bounds[order][0];
+	u32 r = lzms_order_to_position_slot_bounds[order][1];
+
+	for (;;) {
+		u32 slot = (l + r) / 2;
+		if (position >= lzms_position_slot_base[slot]) {
+			if (position < lzms_position_slot_base[slot + 1])
+				return slot;
+			else
+				l = slot + 1;
+		} else {
+			r = slot - 1;
+		}
+	}
 }
 
 static inline u32
-lzms_get_length_slot(u32 value)
+lzms_get_length_slot(u32 length)
 {
-	return lzms_get_slot(value, lzms_length_slot_base,
-			     LZMS_NUM_LEN_SYMS);
+	if (likely(length < LZMS_NUM_FAST_LENGTHS))
+		return lzms_length_slot_fast[length];
+	else
+		return lzms_get_slot(length, lzms_length_slot_base,
+				     LZMS_NUM_LEN_SYMS);
 }
 
+extern void
+lzms_init_lru_queues(struct lzms_lru_queues *lru);
+
+extern void
+lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz);
+
+extern void
+lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
+
+extern void
+lzms_update_lru_queues(struct lzms_lru_queues *lru);
+
 #endif /* _WIMLIB_LZMS_H  */