X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Fbt_matchfinder.h;h=e1a8295c40473ab7c8e73015dc0f0cd4670956a4;hp=c7f2ba8eaebd9c039d9d7441724d598de2dd6541;hb=ddb3738241c6bb94189f852b420ea849071c97e6;hpb=c9be4d389724d00cec9f5e444efb965a449d2ba8;ds=sidebyside

diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h
index c7f2ba8e..e1a8295c 100644
--- a/include/wimlib/bt_matchfinder.h
+++ b/include/wimlib/bt_matchfinder.h
@@ -52,6 +52,7 @@
 #include "wimlib/lz_hash.h"
 
 #define BT_MATCHFINDER_HASH3_ORDER 15
+#define BT_MATCHFINDER_HASH3_WAYS  2
 #define BT_MATCHFINDER_HASH4_ORDER 16
 
 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name.  */
@@ -83,7 +84,7 @@ struct TEMPLATED(bt_matchfinder) {
 #endif
 
 	/* The hash table for finding length 3 matches  */
-	mf_pos_t hash3_tab[1UL << BT_MATCHFINDER_HASH3_ORDER];
+	mf_pos_t hash3_tab[1UL << BT_MATCHFINDER_HASH3_ORDER][BT_MATCHFINDER_HASH3_WAYS];
 
 	/* The hash table which contains the roots of the binary trees for
 	 * finding length 4+ matches  */
@@ -123,6 +124,11 @@ TEMPLATED(bt_right_child)(struct TEMPLATED(bt_matchfinder) *mf, u32 node)
 	return &mf->child_tab[(node << 1) + 1];
 }
 
+/* The minimum permissible value of 'max_len' for bt_matchfinder_get_matches()
+ * and bt_matchfinder_skip_position().  There must be sufficiently many bytes
+ * remaining to load a 32-bit integer from the *next* position.  */
+#define BT_MATCHFINDER_REQUIRED_NBYTES	5
+
 /* Advance the binary tree matchfinder by one byte, optionally recording
  * matches.  @record_matches should be a compile-time constant.  */
 static inline struct lz_match *
@@ -147,7 +153,12 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
 	u16 seq2;
 	u32 hash2;
 #endif
+	STATIC_ASSERT(BT_MATCHFINDER_HASH3_WAYS >= 1 &&
+		      BT_MATCHFINDER_HASH3_WAYS <= 2);
 	u32 cur_node;
+#if BT_MATCHFINDER_HASH3_WAYS >= 2
+	u32 cur_node_2;
+#endif
 	const u8 *matchptr;
 	mf_pos_t *pending_lt_ptr, *pending_gt_ptr;
 	u32 best_lt_len, best_gt_len;
@@ -180,15 +191,26 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
 	}
 #endif
 
-	cur_node = mf->hash3_tab[hash3];
-	mf->hash3_tab[hash3] = cur_pos;
-	if (record_matches &&
-	    load_u24_unaligned(in_next) == load_u24_unaligned(&in_begin[cur_node]) &&
-	    likely(in_next != in_begin))
-	{
-		lz_matchptr->length = 3;
-		lz_matchptr->offset = in_next - &in_begin[cur_node];
-		lz_matchptr++;
+	cur_node = mf->hash3_tab[hash3][0];
+	mf->hash3_tab[hash3][0] = cur_pos;
+#if BT_MATCHFINDER_HASH3_WAYS >= 2
+	cur_node_2 = mf->hash3_tab[hash3][1];
+	mf->hash3_tab[hash3][1] = cur_node;
+#endif
+	if (record_matches && likely(in_next != in_begin)) {
+		u32 seq3 = load_u24_unaligned(in_next);
+		if (seq3 == load_u24_unaligned(&in_begin[cur_node])) {
+			lz_matchptr->length = 3;
+			lz_matchptr->offset = in_next - &in_begin[cur_node];
+			lz_matchptr++;
+		}
+	#if BT_MATCHFINDER_HASH3_WAYS >= 2
+		else if (seq3 == load_u24_unaligned(&in_begin[cur_node_2])) {
+			lz_matchptr->length = 3;
+			lz_matchptr->offset = in_next - &in_begin[cur_node_2];
+			lz_matchptr++;
+		}
+	#endif
 	}
 
 	cur_node = mf->hash4_tab[hash4];
@@ -266,7 +288,8 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
  *	The current position in the input buffer (the position of the sequence
  *	being matched against).
  * @max_len
- *	The maximum permissible match length at this position.  Must be >= 5.
+ *	The maximum permissible match length at this position.  Must be >=
+ *	BT_MATCHFINDER_REQUIRED_NBYTES.
  * @nice_len
  *	Stop searching if a match of at least this length is found.
  *	Must be <= @max_len.