bt_matchfinder: remove unnecessary max_len parameter to skip routine

[wimlib] / include / wimlib / bt_matchfinder.h

diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h
index 3d295cd91fe8e50afb1c5479ce9d62a9c9c5dd6a..39a2778b7d20971a37913d981c8e02085ca4cc4f 100644 (file)
--- a/include/wimlib/bt_matchfinder.h
+++ b/include/wimlib/bt_matchfinder.h
@@ -1,11 +1,21 @@
 /*
- * bt_matchfinder.h
+ * bt_matchfinder.h - Lempel-Ziv matchfinding with a hash table of binary trees
  *
- * Author:     Eric Biggers
- * Year:       2014, 2015
+ * The following copying information applies to this specific source code file:
  *
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
+ *
+ * To the extent possible under law, the author(s) have dedicated all copyright
+ * and related and neighboring rights to this software to the public domain
+ * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
+ * Dedication (the "CC0").
+ *
+ * This software is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
+ *
+ * You should have received a copy of the CC0 along with this software; if not
+ * see <http://creativecommons.org/publicdomain/zero/1.0/>.
  *
  * ----------------------------------------------------------------------------
  *
@@ -52,6 +62,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 +94,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  */
@@ -152,7 +163,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;
@@ -185,15 +201,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];
@@ -217,8 +244,7 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
                matchptr = &in_begin[cur_node];
 
                if (matchptr[len] == in_next[len]) {
-                       len = lz_extend(in_next, matchptr, len + 1,
-                                       (record_matches ? max_len : nice_len));
+                       len = lz_extend(in_next, matchptr, len + 1, max_len);
                        if (!record_matches || len > best_len) {
                                if (record_matches) {
                                        best_len = len;
@@ -330,7 +356,6 @@ static inline void
 TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,
                                        const u8 *in_begin,
                                        ptrdiff_t cur_pos,
-                                       u32 max_len,
                                        u32 nice_len,
                                        u32 max_search_depth,
                                        u32 next_hashes[static 2])
@@ -339,7 +364,7 @@ TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,
        TEMPLATED(bt_matchfinder_advance_one_byte)(mf,
                                                   in_begin,
                                                   cur_pos,
-                                                  max_len,
+                                                  nice_len,
                                                   nice_len,
                                                   max_search_depth,
                                                   next_hashes,