bt_matchfinder: use 4-byte hashing for trees

diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h
index 1a94497845cd0a4d34380c8d7f69ba812f7e08a2..c7f2ba8eaebd9c039d9d7441724d598de2dd6541 100644 (file)
--- a/include/wimlib/bt_matchfinder.h
+++ b/include/wimlib/bt_matchfinder.h
@@ -12,14 +12,14 @@
  * This is a Binary Trees (bt) based matchfinder.
  *
  * The main data structure is a hash table where each hash bucket contains a
  * This is a Binary Trees (bt) based matchfinder.
  *
  * The main data structure is a hash table where each hash bucket contains a

- * binary tree of sequences whose first 3 bytes share the same hash code.  Each
+ * binary tree of sequences whose first 4 bytes share the same hash code.  Each

  * sequence is identified by its starting position in the input buffer.  Each
  * binary tree is always sorted such that each left child represents a sequence
  * lexicographically lesser than its parent and each right child represents a
  * sequence lexicographically greater than its parent.
  *
  * The algorithm processes the input buffer sequentially.  At each byte
  * sequence is identified by its starting position in the input buffer.  Each
  * binary tree is always sorted such that each left child represents a sequence
  * lexicographically lesser than its parent and each right child represents a
  * sequence lexicographically greater than its parent.
  *
  * The algorithm processes the input buffer sequentially.  At each byte

- * position, the hash code of the first 3 bytes of the sequence beginning at
+ * position, the hash code of the first 4 bytes of the sequence beginning at

  * that position (the sequence being matched against) is computed.  This
  * identifies the hash bucket to use for that position.  Then, a new binary tree
  * node is created to represent the current sequence.  Then, in a single tree
  * that position (the sequence being matched against) is computed.  This
  * identifies the hash bucket to use for that position.  Then, a new binary tree
  * node is created to represent the current sequence.  Then, in a single tree


@@ -51,7 +51,8 @@
 #include "wimlib/lz_extend.h"
 #include "wimlib/lz_hash.h"
 
 #include "wimlib/lz_extend.h"
 #include "wimlib/lz_hash.h"
 

-#define BT_MATCHFINDER_HASH3_ORDER 16
+#define BT_MATCHFINDER_HASH3_ORDER 15
+#define BT_MATCHFINDER_HASH4_ORDER 16

 
 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name.  */
 #undef TEMPLATED
 
 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name.  */
 #undef TEMPLATED


@@ -81,10 +82,13 @@ struct TEMPLATED(bt_matchfinder) {
        mf_pos_t hash2_tab[1UL << BT_MATCHFINDER_HASH2_ORDER];
 #endif
 
        mf_pos_t hash2_tab[1UL << BT_MATCHFINDER_HASH2_ORDER];
 #endif
 

-       /* The hash table which contains the roots of the binary trees for
-        * finding length 3 matches  */
+       /* 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];
 

+       /* The hash table which contains the roots of the binary trees for
+        * finding length 4+ matches  */
+       mf_pos_t hash4_tab[1UL << BT_MATCHFINDER_HASH4_ORDER];
+

        /* The child node references for the binary trees.  The left and right
         * children of the node for the sequence with position 'pos' are
         * 'child_tab[pos * 2]' and 'child_tab[pos * 2 + 1]', respectively.  */
        /* The child node references for the binary trees.  The left and right
         * children of the node for the sequence with position 'pos' are
         * 'child_tab[pos * 2]' and 'child_tab[pos * 2 + 1]', respectively.  */


@@ -128,28 +132,38 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
                                           const u32 max_len,
                                           const u32 nice_len,
                                           const u32 max_search_depth,
                                           const u32 max_len,
                                           const u32 nice_len,
                                           const u32 max_search_depth,

-                                          u32 * const restrict next_hash,
+                                          u32 next_hashes[const restrict static 2],

                                           u32 * const restrict best_len_ret,
                                           struct lz_match * restrict lz_matchptr,
                                           const bool record_matches)
 {
        const u8 *in_next = in_begin + cur_pos;
        u32 depth_remaining = max_search_depth;
                                           u32 * const restrict best_len_ret,
                                           struct lz_match * restrict lz_matchptr,
                                           const bool record_matches)
 {
        const u8 *in_next = in_begin + cur_pos;
        u32 depth_remaining = max_search_depth;

+       u32 next_seq4;
+       u32 next_seq3;
+       u32 hash3;
+       u32 hash4;

 #ifdef BT_MATCHFINDER_HASH2_ORDER
        u16 seq2;
        u32 hash2;
 #endif
 #ifdef BT_MATCHFINDER_HASH2_ORDER
        u16 seq2;
        u32 hash2;
 #endif

-       u32 hash3;

        u32 cur_node;
        const u8 *matchptr;
        mf_pos_t *pending_lt_ptr, *pending_gt_ptr;
        u32 best_lt_len, best_gt_len;
        u32 len;
        u32 cur_node;
        const u8 *matchptr;
        mf_pos_t *pending_lt_ptr, *pending_gt_ptr;
        u32 best_lt_len, best_gt_len;
        u32 len;

-       u32 best_len = 2;
+       u32 best_len = 3;
+
+       next_seq4 = load_u32_unaligned(in_next + 1);
+       next_seq3 = loaded_u32_to_u24(next_seq4);
+
+       hash3 = next_hashes[0];
+       hash4 = next_hashes[1];

 
 

-       hash3 = *next_hash;
-       *next_hash = lz_hash(load_u24_unaligned(in_next + 1), BT_MATCHFINDER_HASH3_ORDER);
-       prefetchw(&mf->hash3_tab[*next_hash]);
+       next_hashes[0] = lz_hash(next_seq3, BT_MATCHFINDER_HASH3_ORDER);
+       next_hashes[1] = lz_hash(next_seq4, BT_MATCHFINDER_HASH4_ORDER);
+       prefetchw(&mf->hash3_tab[next_hashes[0]]);
+       prefetchw(&mf->hash4_tab[next_hashes[1]]);

 
 #ifdef BT_MATCHFINDER_HASH2_ORDER
        seq2 = load_u16_unaligned(in_next);
 
 #ifdef BT_MATCHFINDER_HASH2_ORDER
        seq2 = load_u16_unaligned(in_next);


@@ -168,6 +182,17 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
 
        cur_node = mf->hash3_tab[hash3];
        mf->hash3_tab[hash3] = cur_pos;
 
        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->hash4_tab[hash4];
+       mf->hash4_tab[hash4] = cur_pos;

 
        pending_lt_ptr = TEMPLATED(bt_left_child)(mf, cur_pos);
        pending_gt_ptr = TEMPLATED(bt_right_child)(mf, cur_pos);
 
        pending_lt_ptr = TEMPLATED(bt_left_child)(mf, cur_pos);
        pending_gt_ptr = TEMPLATED(bt_right_child)(mf, cur_pos);


@@ -247,22 +272,21 @@ TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * co
  *     Must be <= @max_len.
  * @max_search_depth
  *     Limit on the number of potential matches to consider.  Must be >= 1.
  *     Must be <= @max_len.
  * @max_search_depth
  *     Limit on the number of potential matches to consider.  Must be >= 1.

- * @next_hash
- *     Pointer to the hash code for the current sequence, which was computed
- *     one position in advance so that the binary tree root could be
- *     prefetched.  This is an input/output parameter.
+ * @next_hashes
+ *     The precomputed hash codes for the sequence beginning at @in_next.
+ *     These will be used and then updated with the precomputed hashcodes for
+ *     the sequence beginning at @in_next + 1.

  * @best_len_ret
  * @best_len_ret

- *     If a match of length >= 3 was found, then the length of the longest such
- *     match is written here; otherwise 2 is written here.  (Note: this is
+ *     If a match of length >= 4 was found, then the length of the longest such
+ *     match is written here; otherwise 3 is written here.  (Note: this is

  *     redundant with the 'struct lz_match' array, but this is easier for the
  *     compiler to optimize when inlined and the caller immediately does a
  *     check against 'best_len'.)
  * @lz_matchptr
  *     An array in which this function will record the matches.  The recorded
  *     redundant with the 'struct lz_match' array, but this is easier for the
  *     compiler to optimize when inlined and the caller immediately does a
  *     check against 'best_len'.)
  * @lz_matchptr
  *     An array in which this function will record the matches.  The recorded

- *     matches will be sorted by strictly increasing length and increasing
- *     offset.  The maximum number of matches that may be found is
- *     'min(nice_len, max_len) - 2 + 1', or one less if length 2 matches are
- *     disabled.
+ *     matches will be sorted by strictly increasing length and (non-strictly)
+ *     increasing offset.  The maximum number of matches that may be found is
+ *     'nice_len - 1', or one less if length 2 matches are disabled.

  *
  * The return value is a pointer to the next available slot in the @lz_matchptr
  * array.  (If no matches were found, this will be the same as @lz_matchptr.)
  *
  * The return value is a pointer to the next available slot in the @lz_matchptr
  * array.  (If no matches were found, this will be the same as @lz_matchptr.)


@@ -274,7 +298,7 @@ TEMPLATED(bt_matchfinder_get_matches)(struct TEMPLATED(bt_matchfinder) *mf,
                                      u32 max_len,
                                      u32 nice_len,
                                      u32 max_search_depth,
                                      u32 max_len,
                                      u32 nice_len,
                                      u32 max_search_depth,

-                                     u32 *next_hash,
+                                     u32 next_hashes[static 2],

                                      u32 *best_len_ret,
                                      struct lz_match *lz_matchptr)
 {
                                      u32 *best_len_ret,
                                      struct lz_match *lz_matchptr)
 {


@@ -284,7 +308,7 @@ TEMPLATED(bt_matchfinder_get_matches)(struct TEMPLATED(bt_matchfinder) *mf,
                                                          max_len,
                                                          nice_len,
                                                          max_search_depth,
                                                          max_len,
                                                          nice_len,
                                                          max_search_depth,

-                                                         next_hash,
+                                                         next_hashes,

                                                          best_len_ret,
                                                          lz_matchptr,
                                                          true);
                                                          best_len_ret,
                                                          lz_matchptr,
                                                          true);


@@ -293,26 +317,8 @@ TEMPLATED(bt_matchfinder_get_matches)(struct TEMPLATED(bt_matchfinder) *mf,
 /*
  * Advance the matchfinder, but don't record any matches.
  *
 /*
  * Advance the matchfinder, but don't record any matches.
  *

- * @mf
- *     The matchfinder structure.
- * @in_begin
- *     Pointer to the beginning of the input buffer.
- * @cur_pos
- *     The current position in the input buffer.
- * @max_len
- *     The maximum permissible match length at this position.  Must be >= 5.
- * @nice_len
- *     Stop searching if a match of at least this length is found.
- * @max_search_depth
- *     Limit on the number of potential matches to consider.
- * @next_hash
- *     Pointer to the hash code for the current sequence, which was computed
- *     one position in advance so that the binary tree root could be
- *     prefetched.  This is an input/output parameter.
- *
- * Note: this is very similar to bt_matchfinder_get_matches() because both
- * functions must do hashing and tree re-rooting.  This version just doesn't
- * actually record any matches.
+ * This is very similar to bt_matchfinder_get_matches() because both functions
+ * must do hashing and tree re-rooting.

  */
 static inline void
 TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,
  */
 static inline void
 TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,


@@ -321,7 +327,7 @@ TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,
                                        u32 max_len,
                                        u32 nice_len,
                                        u32 max_search_depth,
                                        u32 max_len,
                                        u32 nice_len,
                                        u32 max_search_depth,

-                                       u32 *next_hash)
+                                       u32 next_hashes[static 2])

 {
        u32 best_len;
        TEMPLATED(bt_matchfinder_advance_one_byte)(mf,
 {
        u32 best_len;
        TEMPLATED(bt_matchfinder_advance_one_byte)(mf,


@@ -330,7 +336,7 @@ TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) *mf,
                                                   max_len,
                                                   nice_len,
                                                   max_search_depth,
                                                   max_len,
                                                   nice_len,
                                                   max_search_depth,

-                                                  next_hash,
+                                                  next_hashes,

                                                   &best_len,
                                                   NULL,
                                                   false);
                                                   &best_len,
                                                   NULL,
                                                   false);

diff --git a/src/lzx_compress.c b/src/lzx_compress.c
index d36f8aaa380ae747723f8e0f475862464af5145b..36e27dbed6c2ecdda17b4206e3d8a75c0b299ceb 100644 (file)
--- a/src/lzx_compress.c
+++ b/src/lzx_compress.c
@@ -1781,7 +1781,7 @@ lzx_compress_near_optimal(struct lzx_compressor *c,
        const u8 * const in_end  = in_begin + c->in_nbytes;
        u32 max_len = LZX_MAX_MATCH_LEN;
        u32 nice_len = min(c->nice_match_length, max_len);
        const u8 * const in_end  = in_begin + c->in_nbytes;
        u32 max_len = LZX_MAX_MATCH_LEN;
        u32 nice_len = min(c->nice_match_length, max_len);

-       u32 next_hash = 0;
+       u32 next_hashes[2] = {};

        struct lzx_lru_queue queue;
 
        CALL_BT_MF(is_16_bit, c, bt_matchfinder_init);
        struct lzx_lru_queue queue;
 
        CALL_BT_MF(is_16_bit, c, bt_matchfinder_init);


@@ -1819,7 +1819,7 @@ lzx_compress_near_optimal(struct lzx_compressor *c,
                                                 max_len,
                                                 nice_len,
                                                 c->max_search_depth,
                                                 max_len,
                                                 nice_len,
                                                 c->max_search_depth,

-                                                &next_hash,
+                                                next_hashes,

                                                 &best_len,
                                                 cache_ptr + 1);
                        in_next++;
                                                 &best_len,
                                                 cache_ptr + 1);
                        in_next++;


@@ -1857,7 +1857,7 @@ lzx_compress_near_optimal(struct lzx_compressor *c,
                                                   max_len,
                                                   nice_len,
                                                   c->max_search_depth,
                                                   max_len,
                                                   nice_len,
                                                   c->max_search_depth,

-                                                  &next_hash);
+                                                  next_hashes);

                                        in_next++;
                                        cache_ptr->length = 0;
                                        cache_ptr++;
                                        in_next++;
                                        cache_ptr->length = 0;
                                        cache_ptr++;

diff --git a/src/xpress_compress.c b/src/xpress_compress.c
index ba7a9af7272ecb3510d6a6ab04e7fec0319dd3cd..776de7cdc4c33032f82a75d7d4333f041df36217 100644 (file)
--- a/src/xpress_compress.c
+++ b/src/xpress_compress.c
@@ -907,7 +907,7 @@ xpress_find_matches(struct xpress_compressor * restrict c,
        const u8 * const in_begin = in;
        const u8 *in_next = in_begin;
        struct lz_match *cache_ptr = c->match_cache;
        const u8 * const in_begin = in;
        const u8 *in_next = in_begin;
        struct lz_match *cache_ptr = c->match_cache;

-       u32 next_hash = 0;
+       u32 next_hashes[2] = {};

        u32 max_len = in_nbytes;
        u32 nice_len = min(max_len, c->nice_match_length);
 
        u32 max_len = in_nbytes;
        u32 nice_len = min(max_len, c->nice_match_length);
 


@@ -935,7 +935,7 @@ xpress_find_matches(struct xpress_compressor * restrict c,
                                                   max_len,
                                                   nice_len,
                                                   c->max_search_depth,
                                                   max_len,
                                                   nice_len,
                                                   c->max_search_depth,

-                                                  &next_hash,
+                                                  next_hashes,

                                                   &best_len,
                                                   cache_ptr);
                cache_ptr->length = cache_ptr - matches;
                                                   &best_len,
                                                   cache_ptr);
                cache_ptr->length = cache_ptr - matches;


@@ -965,7 +965,7 @@ xpress_find_matches(struct xpress_compressor * restrict c,
                                                             max_len,
                                                             nice_len,
                                                             c->max_search_depth,
                                                             max_len,
                                                             nice_len,
                                                             c->max_search_depth,

-                                                            &next_hash);
+                                                            next_hashes);

                                cache_ptr->length = 0;
                                cache_ptr->offset = *in_next++;
                                cache_ptr++;
                                cache_ptr->length = 0;
                                cache_ptr->offset = *in_next++;
                                cache_ptr++;