--- /dev/null
+/*
+ * bt_matchfinder.h
+ *
+ * Copyright (c) 2014 Eric Biggers. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include "wimlib/lz_extend.h"
+#include "wimlib/lz_hash3.h"
+#include "wimlib/matchfinder_common.h"
+#include "wimlib/unaligned.h"
+
+#ifndef BT_MATCHFINDER_HASH_ORDER
+# if MATCHFINDER_WINDOW_ORDER < 14
+# define BT_MATCHFINDER_HASH_ORDER 14
+# else
+# define BT_MATCHFINDER_HASH_ORDER 15
+# endif
+#endif
+
+#define BT_MATCHFINDER_HASH_LENGTH (1UL << BT_MATCHFINDER_HASH_ORDER)
+
+#define BT_MATCHFINDER_TOTAL_LENGTH \
+ (BT_MATCHFINDER_HASH_LENGTH + (2UL * MATCHFINDER_WINDOW_SIZE))
+
+struct bt_matchfinder {
+ union {
+ pos_t mf_data[BT_MATCHFINDER_TOTAL_LENGTH];
+ struct {
+ pos_t hash_tab[BT_MATCHFINDER_HASH_LENGTH];
+ pos_t child_tab[2UL * MATCHFINDER_WINDOW_SIZE];
+ };
+ };
+} _aligned_attribute(MATCHFINDER_ALIGNMENT);
+
+static inline void
+bt_matchfinder_init(struct bt_matchfinder *mf)
+{
+ matchfinder_init(mf->hash_tab, BT_MATCHFINDER_HASH_LENGTH);
+}
+
+#if MATCHFINDER_IS_SLIDING
+static inline void
+bt_matchfinder_slide_window(struct bt_matchfinder *mf)
+{
+ matchfinder_rebase(mf->mf_data, BT_MATCHFINDER_TOTAL_LENGTH);
+}
+#endif
+
+static inline unsigned
+bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf,
+ const u8 * const in_base,
+ const u8 * const in_next,
+ const unsigned min_len,
+ const unsigned max_len,
+ const unsigned nice_len,
+ const unsigned max_search_depth,
+ unsigned long *prev_hash,
+ struct lz_match * const restrict matches)
+{
+ struct lz_match *lz_matchptr = matches;
+ unsigned depth_remaining = max_search_depth;
+ unsigned hash;
+ pos_t cur_match;
+ const u8 *matchptr;
+ unsigned best_len;
+ pos_t *pending_lt_ptr, *pending_gt_ptr;
+ unsigned best_lt_len, best_gt_len;
+ unsigned len;
+ pos_t *children;
+
+ if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES + 1))
+ return 0;
+
+ hash = *prev_hash;
+ *prev_hash = lz_hash(in_next + 1, BT_MATCHFINDER_HASH_ORDER);
+ prefetch(&mf->hash_tab[*prev_hash]);
+ cur_match = mf->hash_tab[hash];
+ mf->hash_tab[hash] = in_next - in_base;
+
+ best_len = min_len - 1;
+ pending_lt_ptr = &mf->child_tab[(in_next - in_base) << 1];
+ pending_gt_ptr = &mf->child_tab[((in_next - in_base) << 1) + 1];
+ best_lt_len = 0;
+ best_gt_len = 0;
+ for (;;) {
+ if (!matchfinder_match_in_window(cur_match,
+ in_base, in_next) ||
+ !depth_remaining--)
+ {
+ *pending_lt_ptr = MATCHFINDER_INITVAL;
+ *pending_gt_ptr = MATCHFINDER_INITVAL;
+ return lz_matchptr - matches;
+ }
+
+ matchptr = &in_base[cur_match];
+ len = min(best_lt_len, best_gt_len);
+
+ children = &mf->child_tab[(unsigned long)
+ matchfinder_slot_for_match(cur_match) << 1];
+
+ if (matchptr[len] == in_next[len]) {
+
+ len = lz_extend(in_next, matchptr, len + 1, max_len);
+
+ if (len > best_len) {
+ best_len = len;
+
+ lz_matchptr->length = len;
+ lz_matchptr->offset = in_next - matchptr;
+ lz_matchptr++;
+
+ if (len >= nice_len) {
+ *pending_lt_ptr = children[0];
+ *pending_gt_ptr = children[1];
+ return lz_matchptr - matches;
+ }
+ }
+ }
+
+ if (matchptr[len] < in_next[len]) {
+ *pending_lt_ptr = cur_match;
+ pending_lt_ptr = &children[1];
+ cur_match = *pending_lt_ptr;
+ best_lt_len = len;
+ } else {
+ *pending_gt_ptr = cur_match;
+ pending_gt_ptr = &children[0];
+ cur_match = *pending_gt_ptr;
+ best_gt_len = len;
+ }
+ }
+}
+
+static inline void
+bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf,
+ const u8 * const in_base,
+ const u8 * const in_next,
+ const u8 * const in_end,
+ const unsigned nice_len,
+ const unsigned max_search_depth,
+ unsigned long *prev_hash)
+{
+ unsigned depth_remaining = max_search_depth;
+ unsigned hash;
+ pos_t cur_match;
+ const u8 *matchptr;
+ pos_t *pending_lt_ptr, *pending_gt_ptr;
+ unsigned best_lt_len, best_gt_len;
+ unsigned len;
+ pos_t *children;
+
+ if (unlikely(in_end - in_next < LZ_HASH_REQUIRED_NBYTES + 1))
+ return;
+
+ hash = *prev_hash;
+ *prev_hash = lz_hash(in_next + 1, BT_MATCHFINDER_HASH_ORDER);
+ prefetch(&mf->hash_tab[*prev_hash]);
+ cur_match = mf->hash_tab[hash];
+ mf->hash_tab[hash] = in_next - in_base;
+
+ depth_remaining = max_search_depth;
+ pending_lt_ptr = &mf->child_tab[(in_next - in_base) << 1];
+ pending_gt_ptr = &mf->child_tab[((in_next - in_base) << 1) + 1];
+ best_lt_len = 0;
+ best_gt_len = 0;
+ for (;;) {
+ if (!matchfinder_match_in_window(cur_match,
+ in_base, in_next) ||
+ !depth_remaining--)
+ {
+ *pending_lt_ptr = MATCHFINDER_INITVAL;
+ *pending_gt_ptr = MATCHFINDER_INITVAL;
+ return;
+ }
+
+ matchptr = &in_base[cur_match];
+ len = min(best_lt_len, best_gt_len);
+
+ children = &mf->child_tab[(unsigned long)
+ matchfinder_slot_for_match(cur_match) << 1];
+
+ if (matchptr[len] == in_next[len]) {
+ len = lz_extend(in_next, matchptr, len + 1, nice_len);
+ if (len == nice_len) {
+ *pending_lt_ptr = children[0];
+ *pending_gt_ptr = children[1];
+ return;
+ }
+ }
+
+ if (matchptr[len] < in_next[len]) {
+ *pending_lt_ptr = cur_match;
+ pending_lt_ptr = &children[1];
+ cur_match = *pending_lt_ptr;
+ best_lt_len = len;
+ } else {
+ *pending_gt_ptr = cur_match;
+ pending_gt_ptr = &children[0];
+ cur_match = *pending_gt_ptr;
+ best_gt_len = len;
+ }
+ }
+}
git://wimlib.net / wimlib / blobdiff