X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Fbt_matchfinder.h;h=189c5a1571037cffe7f7ecead61a02275b9a66e6;hp=78ecdd751c20dd62c5787d52d8a81dda81d35ffb;hb=80c2fe3e6463cfd0eca5bead23a08731b6db9576;hpb=917100f2f08773e5b6c7a479a095b499fab848b8

diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h
index 78ecdd75..189c5a15 100644
--- a/include/wimlib/bt_matchfinder.h
+++ b/include/wimlib/bt_matchfinder.h
@@ -48,9 +48,14 @@
 #ifndef _BT_MATCHFINDER_H
 #define _BT_MATCHFINDER_H
 
+#ifndef MATCHFINDER_MAX_WINDOW_ORDER
+#  error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!"
+#endif
+
+#include <string.h>
+
 #include "wimlib/lz_extend.h"
 #include "wimlib/lz_hash.h"
-#include "wimlib/matchfinder_common.h"
 
 #if MATCHFINDER_MAX_WINDOW_ORDER < 13
 #  define BT_MATCHFINDER_HASH_ORDER 14
@@ -60,26 +65,40 @@
 #  define BT_MATCHFINDER_HASH_ORDER 16
 #endif
 
-#define BT_MATCHFINDER_HASH_LENGTH	(1UL << BT_MATCHFINDER_HASH_ORDER)
+#if MATCHFINDER_MAX_WINDOW_ORDER <= 16
+typedef u16 pos_t;
+#else
+typedef u32 pos_t;
+#endif
+
+/* Representation of a match found by the bt_matchfinder  */
+struct lz_match {
+
+	/* The number of bytes matched.  */
+	pos_t length;
+
+	/* The offset back from the current position that was matched.  */
+	pos_t offset;
+};
 
 struct bt_matchfinder {
-	pos_t hash_tab[BT_MATCHFINDER_HASH_LENGTH];
+	pos_t hash_tab[1UL << BT_MATCHFINDER_HASH_ORDER];
 	pos_t child_tab[];
-} _aligned_attribute(MATCHFINDER_ALIGNMENT);
+};
 
 /* Return the number of bytes that must be allocated for a 'bt_matchfinder' that
  * can work with buffers up to the specified size.  */
 static inline size_t
 bt_matchfinder_size(size_t max_bufsize)
 {
-	return sizeof(pos_t) * (BT_MATCHFINDER_HASH_LENGTH + (2 * max_bufsize));
+	return sizeof(struct bt_matchfinder) + (2 * max_bufsize * sizeof(pos_t));
 }
 
 /* Prepare the matchfinder for a new input buffer.  */
 static inline void
 bt_matchfinder_init(struct bt_matchfinder *mf)
 {
-	matchfinder_init(mf->hash_tab, BT_MATCHFINDER_HASH_LENGTH);
+	memset(mf, 0, sizeof(*mf));
 }
 
 static inline u32
@@ -169,7 +188,7 @@ bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
 	unsigned len;
 	unsigned best_len = min_len - 1;
 
-	if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES + 1)) {
+	if (unlikely(max_len < LZ_HASH3_REQUIRED_NBYTES + 1)) {
 		*best_len_ret = best_len;
 		return lz_matchptr;
 	}
@@ -178,7 +197,7 @@ bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
 	*next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
 	cur_node = mf->hash_tab[hash];
 	mf->hash_tab[hash] = in_next - in_begin;
-	prefetch(&mf->hash_tab[*next_hash]);
+	prefetchw(&mf->hash_tab[*next_hash]);
 
 	pending_lt_ptr = bt_left_child(mf, in_next - in_begin);
 	pending_gt_ptr = bt_right_child(mf, in_next - in_begin);
@@ -186,9 +205,9 @@ bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
 	best_gt_len = 0;
 	len = 0;
 
-	if (!matchfinder_node_valid(cur_node)) {
-		*pending_lt_ptr = MATCHFINDER_NULL;
-		*pending_gt_ptr = MATCHFINDER_NULL;
+	if (!cur_node) {
+		*pending_lt_ptr = 0;
+		*pending_gt_ptr = 0;
 		*best_len_ret = best_len;
 		return lz_matchptr;
 	}
@@ -228,9 +247,9 @@ bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
 				len = best_lt_len;
 		}
 
-		if (!matchfinder_node_valid(cur_node) || !--depth_remaining) {
-			*pending_lt_ptr = MATCHFINDER_NULL;
-			*pending_gt_ptr = MATCHFINDER_NULL;
+		if (!cur_node || !--depth_remaining) {
+			*pending_lt_ptr = 0;
+			*pending_gt_ptr = 0;
 			*best_len_ret = best_len;
 			return lz_matchptr;
 		}
@@ -278,14 +297,14 @@ bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf,
 	unsigned best_lt_len, best_gt_len;
 	unsigned len;
 
-	if (unlikely(in_end - in_next < LZ_HASH_REQUIRED_NBYTES + 1))
+	if (unlikely(in_end - in_next < LZ_HASH3_REQUIRED_NBYTES + 1))
 		return;
 
 	hash = *next_hash;
 	*next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
 	cur_node = mf->hash_tab[hash];
 	mf->hash_tab[hash] = in_next - in_begin;
-	prefetch(&mf->hash_tab[*next_hash]);
+	prefetchw(&mf->hash_tab[*next_hash]);
 
 	depth_remaining = max_search_depth;
 	pending_lt_ptr = bt_left_child(mf, in_next - in_begin);
@@ -294,9 +313,9 @@ bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf,
 	best_gt_len = 0;
 	len = 0;
 
-	if (!matchfinder_node_valid(cur_node)) {
-		*pending_lt_ptr = MATCHFINDER_NULL;
-		*pending_gt_ptr = MATCHFINDER_NULL;
+	if (!cur_node) {
+		*pending_lt_ptr = 0;
+		*pending_gt_ptr = 0;
 		return;
 	}
 
@@ -328,9 +347,9 @@ bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf,
 				len = best_lt_len;
 		}
 
-		if (!matchfinder_node_valid(cur_node) || !--depth_remaining) {
-			*pending_lt_ptr = MATCHFINDER_NULL;
-			*pending_gt_ptr = MATCHFINDER_NULL;
+		if (!cur_node || !--depth_remaining) {
+			*pending_lt_ptr = 0;
+			*pending_gt_ptr = 0;
 			return;
 		}
 	}