/*
* bt_matchfinder.h
*
- * Copyright (c) 2014 Eric Biggers. All rights reserved.
+ * Author: Eric Biggers
+ * Year: 2014, 2015
*
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
+ * The author dedicates this file to the public domain.
+ * You can do whatever you want with this file.
*
- * 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 is a Binary Trees (bt) based matchfinder.
*
- * 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.
+ * 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
+ * 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
+ * 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
+ * traversal, the hash bucket's binary tree is searched for matches and is
+ * re-rooted at the new node.
+ *
+ * Compared to the simpler algorithm that uses linked lists instead of binary
+ * trees (see hc_matchfinder.h), the binary tree version gains more information
+ * at each node visitation. Ideally, the binary tree version will examine only
+ * 'log(n)' nodes to find the same matches that the linked list version will
+ * find by examining 'n' nodes. In addition, the binary tree version can
+ * examine fewer bytes at each node by taking advantage of the common prefixes
+ * that result from the sort order, whereas the linked list version may have to
+ * examine up to the full length of the match at each node.
+ *
+ * However, it is not always best to use the binary tree version. It requires
+ * nearly twice as much memory as the linked list version, and it takes time to
+ * keep the binary trees sorted, even at positions where the compressor does not
+ * need matches. Generally, when doing fast compression on small buffers,
+ * binary trees are the wrong approach. They are best suited for thorough
+ * compression and/or large buffers.
+ *
+ * ----------------------------------------------------------------------------
*/
-#pragma once
+
+#include <string.h>
#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
+#include "wimlib/lz_hash.h"
-#define BT_MATCHFINDER_HASH_LENGTH (1UL << BT_MATCHFINDER_HASH_ORDER)
+#define BT_MATCHFINDER_HASH3_ORDER 16
-#define BT_MATCHFINDER_TOTAL_LENGTH \
- (BT_MATCHFINDER_HASH_LENGTH + (2UL * MATCHFINDER_WINDOW_SIZE))
+/* TEMPLATED functions and structures have MF_SUFFIX appended to their name. */
+#undef TEMPLATED
+#define TEMPLATED(name) CONCAT(name, MF_SUFFIX)
-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);
+#ifndef _WIMLIB_BT_MATCHFINDER_H
+#define _WIMLIB_BT_MATCHFINDER_H
-static inline void
-bt_matchfinder_init(struct bt_matchfinder *mf)
+/* Non-templated definitions */
+
+/* Representation of a match found by the bt_matchfinder */
+struct lz_match {
+
+ /* The number of bytes matched. */
+ u32 length;
+
+ /* The offset back from the current position that was matched. */
+ u32 offset;
+};
+
+#endif /* _WIMLIB_BT_MATCHFINDER_H */
+
+struct TEMPLATED(bt_matchfinder) {
+
+ /* The hash table for finding length 2 matches, if enabled */
+#ifdef BT_MATCHFINDER_HASH2_ORDER
+ 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 */
+ mf_pos_t hash3_tab[1UL << BT_MATCHFINDER_HASH3_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. */
+ mf_pos_t child_tab[];
+};
+
+/* 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
+TEMPLATED(bt_matchfinder_size)(size_t max_bufsize)
{
- matchfinder_init(mf->hash_tab, BT_MATCHFINDER_HASH_LENGTH);
+ return sizeof(struct TEMPLATED(bt_matchfinder)) +
+ (2 * max_bufsize * sizeof(mf_pos_t));
}
-#if MATCHFINDER_IS_SLIDING
+/* Prepare the matchfinder for a new input buffer. */
static inline void
-bt_matchfinder_slide_window(struct bt_matchfinder *mf)
+TEMPLATED(bt_matchfinder_init)(struct TEMPLATED(bt_matchfinder) *mf)
{
- matchfinder_rebase(mf->mf_data, BT_MATCHFINDER_TOTAL_LENGTH);
+ memset(mf, 0, sizeof(*mf));
}
-#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)
+static inline mf_pos_t *
+TEMPLATED(bt_left_child)(struct TEMPLATED(bt_matchfinder) *mf, u32 node)
{
- 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;
- }
+ return &mf->child_tab[(node << 1) + 0];
+}
- matchptr = &in_base[cur_match];
- len = min(best_lt_len, best_gt_len);
+static inline mf_pos_t *
+TEMPLATED(bt_right_child)(struct TEMPLATED(bt_matchfinder) *mf, u32 node)
+{
+ return &mf->child_tab[(node << 1) + 1];
+}
- children = &mf->child_tab[(unsigned long)
- matchfinder_slot_for_match(cur_match) << 1];
+/* Advance the binary tree matchfinder by one byte, optionally recording
+ * matches. @record_matches should be a compile-time constant. */
+static inline struct lz_match *
+TEMPLATED(bt_matchfinder_advance_one_byte)(struct TEMPLATED(bt_matchfinder) * const restrict mf,
+ const u8 * const restrict in_begin,
+ const ptrdiff_t cur_pos,
+ const u32 max_len,
+ const u32 nice_len,
+ const u32 max_search_depth,
+ u32 * const restrict next_hash,
+ 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;
+#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;
- if (matchptr[len] == in_next[len]) {
+ if (unlikely(max_len < LZ_HASH3_REQUIRED_NBYTES + 1)) {
+ *best_len_ret = best_len;
+ return lz_matchptr;
+ }
- len = lz_extend(in_next, matchptr, len + 1, max_len);
+ hash3 = *next_hash;
+ *next_hash = lz_hash(load_u24_unaligned(in_next + 1), BT_MATCHFINDER_HASH3_ORDER);
+ prefetchw(&mf->hash3_tab[*next_hash]);
- if (len > best_len) {
- best_len = len;
+#ifdef BT_MATCHFINDER_HASH2_ORDER
+ seq2 = load_u16_unaligned(in_next);
+ hash2 = lz_hash(seq2, BT_MATCHFINDER_HASH2_ORDER);
+ cur_node = mf->hash2_tab[hash2];
+ mf->hash2_tab[hash2] = cur_pos;
+ if (record_matches &&
+ seq2 == load_u16_unaligned(&in_begin[cur_node]) &&
+ likely(in_next != in_begin))
+ {
+ lz_matchptr->length = 2;
+ lz_matchptr->offset = in_next - &in_begin[cur_node];
+ lz_matchptr++;
+ }
+#endif
- lz_matchptr->length = len;
- lz_matchptr->offset = in_next - matchptr;
- lz_matchptr++;
+ cur_node = mf->hash3_tab[hash3];
+ mf->hash3_tab[hash3] = cur_pos;
- if (len >= nice_len) {
- *pending_lt_ptr = children[0];
- *pending_gt_ptr = children[1];
- return lz_matchptr - matches;
- }
- }
- }
+ pending_lt_ptr = TEMPLATED(bt_left_child)(mf, cur_pos);
+ pending_gt_ptr = TEMPLATED(bt_right_child)(mf, cur_pos);
- 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;
- }
+ if (!cur_node) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
+ *best_len_ret = best_len;
+ return lz_matchptr;
}
-}
-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);
+ len = 0;
- children = &mf->child_tab[(unsigned long)
- matchfinder_slot_for_match(cur_match) << 1];
+ for (;;) {
+ matchptr = &in_begin[cur_node];
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;
+ len = lz_extend(in_next, matchptr, len + 1,
+ (record_matches ? max_len : nice_len));
+ if (!record_matches || len > best_len) {
+ if (record_matches) {
+ best_len = len;
+ lz_matchptr->length = len;
+ lz_matchptr->offset = in_next - matchptr;
+ lz_matchptr++;
+ }
+ if (len >= nice_len) {
+ *pending_lt_ptr = *TEMPLATED(bt_left_child)(mf, cur_node);
+ *pending_gt_ptr = *TEMPLATED(bt_right_child)(mf, cur_node);
+ *best_len_ret = best_len;
+ return lz_matchptr;
+ }
}
}
if (matchptr[len] < in_next[len]) {
- *pending_lt_ptr = cur_match;
- pending_lt_ptr = &children[1];
- cur_match = *pending_lt_ptr;
+ *pending_lt_ptr = cur_node;
+ pending_lt_ptr = TEMPLATED(bt_right_child)(mf, cur_node);
+ cur_node = *pending_lt_ptr;
best_lt_len = len;
+ if (best_gt_len < len)
+ len = best_gt_len;
} else {
- *pending_gt_ptr = cur_match;
- pending_gt_ptr = &children[0];
- cur_match = *pending_gt_ptr;
+ *pending_gt_ptr = cur_node;
+ pending_gt_ptr = TEMPLATED(bt_left_child)(mf, cur_node);
+ cur_node = *pending_gt_ptr;
best_gt_len = len;
+ if (best_lt_len < len)
+ len = best_lt_len;
+ }
+
+ if (!cur_node || !--depth_remaining) {
+ *pending_lt_ptr = 0;
+ *pending_gt_ptr = 0;
+ *best_len_ret = best_len;
+ return lz_matchptr;
}
}
}
+
+/*
+ * Retrieve a list of matches with the current position.
+ *
+ * @mf
+ * The matchfinder structure.
+ * @in_begin
+ * Pointer to the beginning of the input buffer.
+ * @cur_pos
+ * The current position in the input buffer (the position of the sequence
+ * being matched against).
+ * @max_len
+ * 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. 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.
+ * @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
+ * 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.
+ *
+ * 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.)
+ */
+static inline struct lz_match *
+TEMPLATED(bt_matchfinder_get_matches)(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_hash,
+ u32 *best_len_ret,
+ struct lz_match *lz_matchptr)
+{
+ return TEMPLATED(bt_matchfinder_advance_one_byte)(mf,
+ in_begin,
+ cur_pos,
+ max_len,
+ nice_len,
+ max_search_depth,
+ next_hash,
+ best_len_ret,
+ lz_matchptr,
+ true);
+}
+
+/*
+ * 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.
+ * @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.
+ */
+static inline void
+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_hash)
+{
+ u32 best_len;
+ TEMPLATED(bt_matchfinder_advance_one_byte)(mf,
+ in_begin,
+ cur_pos,
+ max_len,
+ nice_len,
+ max_search_depth,
+ next_hash,
+ &best_len,
+ NULL,
+ false);
+}
git://wimlib.net / wimlib / blobdiff