/*
- * 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/>.
*
* ----------------------------------------------------------------------------
*
#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. */
#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 */
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;
}
#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];
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;
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])
TEMPLATED(bt_matchfinder_advance_one_byte)(mf,
in_begin,
cur_pos,
- max_len,
+ nice_len,
nice_len,
max_search_depth,
next_hashes,