#ifndef _BT_MATCHFINDER_H
#define _BT_MATCHFINDER_H
+#ifndef MATCHFINDER_MAX_WINDOW_ORDER
+# error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!"
+#endif
+
+#include <string.h>
+
#include "wimlib/lz_extend.h"
#include "wimlib/lz_hash.h"
-#include "wimlib/matchfinder_common.h"
#if MATCHFINDER_MAX_WINDOW_ORDER < 13
# define BT_MATCHFINDER_HASH_ORDER 14
# define BT_MATCHFINDER_HASH_ORDER 16
#endif
-#define BT_MATCHFINDER_HASH_LENGTH (1UL << BT_MATCHFINDER_HASH_ORDER)
+#if MATCHFINDER_MAX_WINDOW_ORDER <= 16
+typedef u16 pos_t;
+#else
+typedef u32 pos_t;
+#endif
+
+/* Representation of a match found by the bt_matchfinder */
+struct lz_match {
+
+ /* The number of bytes matched. */
+ pos_t length;
+
+ /* The offset back from the current position that was matched. */
+ pos_t offset;
+};
struct bt_matchfinder {
- pos_t hash_tab[BT_MATCHFINDER_HASH_LENGTH];
+ pos_t hash_tab[1UL << BT_MATCHFINDER_HASH_ORDER];
pos_t child_tab[];
-} _aligned_attribute(MATCHFINDER_ALIGNMENT);
+};
/* Return the number of bytes that must be allocated for a 'bt_matchfinder' that
* can work with buffers up to the specified size. */
static inline size_t
bt_matchfinder_size(size_t max_bufsize)
{
- return sizeof(pos_t) * (BT_MATCHFINDER_HASH_LENGTH + (2 * max_bufsize));
+ return sizeof(struct bt_matchfinder) + (2 * max_bufsize * sizeof(pos_t));
}
/* Prepare the matchfinder for a new input buffer. */
static inline void
bt_matchfinder_init(struct bt_matchfinder *mf)
{
- matchfinder_init(mf->hash_tab, BT_MATCHFINDER_HASH_LENGTH);
+ memset(mf, 0, sizeof(*mf));
}
static inline u32
* The maximum permissible match length at this position.
* @nice_len
* Stop searching if a match of at least this length is found.
+ * Must be <= @max_len.
* @max_search_depth
- * Limit on the number of potential matches to consider.
+ * 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
unsigned len;
unsigned best_len = min_len - 1;
- if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES + 1)) {
+ if (unlikely(max_len < LZ_HASH3_REQUIRED_NBYTES + 1)) {
*best_len_ret = best_len;
return lz_matchptr;
}
*next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
cur_node = mf->hash_tab[hash];
mf->hash_tab[hash] = in_next - in_begin;
- prefetch(&mf->hash_tab[*next_hash]);
+ prefetchw(&mf->hash_tab[*next_hash]);
pending_lt_ptr = bt_left_child(mf, in_next - in_begin);
pending_gt_ptr = bt_right_child(mf, in_next - in_begin);
best_gt_len = 0;
len = 0;
- if (!matchfinder_node_valid(cur_node)) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
+ if (!cur_node) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
*best_len_ret = best_len;
return lz_matchptr;
}
len = best_lt_len;
}
- if (!matchfinder_node_valid(cur_node) || !--depth_remaining) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
+ if (!cur_node || !--depth_remaining) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
*best_len_ret = best_len;
return lz_matchptr;
}
unsigned best_lt_len, best_gt_len;
unsigned len;
- if (unlikely(in_end - in_next < LZ_HASH_REQUIRED_NBYTES + 1))
+ if (unlikely(in_end - in_next < LZ_HASH3_REQUIRED_NBYTES + 1))
return;
hash = *next_hash;
*next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
cur_node = mf->hash_tab[hash];
mf->hash_tab[hash] = in_next - in_begin;
- prefetch(&mf->hash_tab[*next_hash]);
+ prefetchw(&mf->hash_tab[*next_hash]);
depth_remaining = max_search_depth;
pending_lt_ptr = bt_left_child(mf, in_next - in_begin);
best_gt_len = 0;
len = 0;
- if (!matchfinder_node_valid(cur_node)) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
+ if (!cur_node) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
return;
}
len = best_lt_len;
}
- if (!matchfinder_node_valid(cur_node) || !--depth_remaining) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
+ if (!cur_node || !--depth_remaining) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
return;
}
}