From c9be4d389724d00cec9f5e444efb965a449d2ba8 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sat, 19 Sep 2015 13:56:14 -0500 Subject: [PATCH] bt_matchfinder: use 4-byte hashing for trees --- include/wimlib/bt_matchfinder.h | 96 +++++++++++++++++---------------- src/lzx_compress.c | 6 +-- src/xpress_compress.c | 6 +-- 3 files changed, 57 insertions(+), 51 deletions(-) diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h index 1a944978..c7f2ba8e 100644 --- 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 - * 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 - * 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 @@ -51,7 +51,8 @@ #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 @@ -81,10 +82,13 @@ struct TEMPLATED(bt_matchfinder) { 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]; + /* 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. */ @@ -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, - 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 next_seq4; + u32 next_seq3; + u32 hash3; + u32 hash4; #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 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); @@ -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; + 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); @@ -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. - * @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 - * 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 - * 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.) @@ -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 *next_hash, + u32 next_hashes[static 2], 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, - next_hash, + next_hashes, 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. * - * @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, @@ -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 *next_hash) + u32 next_hashes[static 2]) { 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, - next_hash, + next_hashes, &best_len, NULL, false); diff --git a/src/lzx_compress.c b/src/lzx_compress.c index d36f8aaa..36e27dbe 100644 --- 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); - u32 next_hash = 0; + u32 next_hashes[2] = {}; 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, - &next_hash, + next_hashes, &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, - &next_hash); + next_hashes); in_next++; cache_ptr->length = 0; cache_ptr++; diff --git a/src/xpress_compress.c b/src/xpress_compress.c index ba7a9af7..776de7cd 100644 --- 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; - u32 next_hash = 0; + u32 next_hashes[2] = {}; 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, - &next_hash, + next_hashes, &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, - &next_hash); + next_hashes); cache_ptr->length = 0; cache_ptr->offset = *in_next++; cache_ptr++; -- 2.43.0