X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Fbt_matchfinder.h;h=189c5a1571037cffe7f7ecead61a02275b9a66e6;hp=75858a33ebe6157f592bce6274fed700362332e5;hb=80c2fe3e6463cfd0eca5bead23a08731b6db9576;hpb=1bba32f7f1068eaa0e8de77b8afa99af68bcb44d diff --git a/include/wimlib/bt_matchfinder.h b/include/wimlib/bt_matchfinder.h index 75858a33..189c5a15 100644 --- a/include/wimlib/bt_matchfinder.h +++ b/include/wimlib/bt_matchfinder.h @@ -1,228 +1,358 @@ /* * 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 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 +#ifndef _BT_MATCHFINDER_H +#define _BT_MATCHFINDER_H + +#ifndef MATCHFINDER_MAX_WINDOW_ORDER +# error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!" +#endif + +#include #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 +#include "wimlib/lz_hash.h" + +#if MATCHFINDER_MAX_WINDOW_ORDER < 13 +# define BT_MATCHFINDER_HASH_ORDER 14 +#elif MATCHFINDER_MAX_WINDOW_ORDER < 15 +# define BT_MATCHFINDER_HASH_ORDER 15 +#else +# define BT_MATCHFINDER_HASH_ORDER 16 +#endif + +#if MATCHFINDER_MAX_WINDOW_ORDER <= 16 +typedef u16 pos_t; +#else +typedef u32 pos_t; #endif -#define BT_MATCHFINDER_HASH_LENGTH (1UL << BT_MATCHFINDER_HASH_ORDER) +/* Representation of a match found by the bt_matchfinder */ +struct lz_match { + + /* The number of bytes matched. */ + pos_t length; -#define BT_MATCHFINDER_TOTAL_LENGTH \ - (BT_MATCHFINDER_HASH_LENGTH + (2UL * MATCHFINDER_WINDOW_SIZE)) + /* The offset back from the current position that was matched. */ + pos_t offset; +}; 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); + pos_t hash_tab[1UL << BT_MATCHFINDER_HASH_ORDER]; + 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 +bt_matchfinder_size(size_t 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)); } -#if MATCHFINDER_IS_SLIDING -static inline void -bt_matchfinder_slide_window(struct bt_matchfinder *mf) +static inline u32 +bt_matchfinder_hash_3_bytes(const u8 *in_next) { - matchfinder_rebase(mf->mf_data, BT_MATCHFINDER_TOTAL_LENGTH); + return lz_hash_3_bytes(in_next, BT_MATCHFINDER_HASH_ORDER); +} + +static inline pos_t * +bt_child(struct bt_matchfinder *mf, pos_t node, int offset) +{ + if (MATCHFINDER_MAX_WINDOW_ORDER < sizeof(pos_t) * 8) { + /* no cast needed */ + return &mf->child_tab[(node << 1) + offset]; + } else { + return &mf->child_tab[((size_t)node << 1) + offset]; + } +} + +static inline pos_t * +bt_left_child(struct bt_matchfinder *mf, pos_t node) +{ + return bt_child(mf, node, 0); } -#endif -static inline unsigned +static inline pos_t * +bt_right_child(struct bt_matchfinder *mf, pos_t node) +{ + return bt_child(mf, node, 1); +} + +/* + * Retrieve a list of matches with the current position. + * + * @mf + * The matchfinder structure. + * @in_begin + * Pointer to the beginning of the input buffer. + * @in_next + * Pointer to the next byte in the input buffer to process. This is the + * pointer to the sequence being matched against. + * @min_len + * Only record matches that are at least this long. + * @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 + * The length of the longest match found is written here. (This is + * actually 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 strictly + * increasing offset. The maximum number of matches that may be found is + * 'min(nice_len, max_len) - 3 + 1'. + * + * 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 * bt_matchfinder_get_matches(struct bt_matchfinder * const restrict mf, - const u8 * const in_base, + const u8 * const in_begin, 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) + u32 * restrict next_hash, + unsigned * restrict best_len_ret, + struct lz_match * restrict lz_matchptr) { - struct lz_match *lz_matchptr = matches; unsigned depth_remaining = max_search_depth; - unsigned hash; - pos_t cur_match; + u32 hash; + pos_t cur_node; 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; + unsigned best_len = min_len - 1; - if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES + 1)) - return 0; + if (unlikely(max_len < LZ_HASH3_REQUIRED_NBYTES + 1)) { + *best_len_ret = best_len; + return lz_matchptr; + } - 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; + 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; + prefetchw(&mf->hash_tab[*next_hash]); - 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]; + pending_lt_ptr = bt_left_child(mf, in_next - in_begin); + pending_gt_ptr = bt_right_child(mf, in_next - in_begin); 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; - } + len = 0; - matchptr = &in_base[cur_match]; - len = min(best_lt_len, best_gt_len); + if (!cur_node) { + *pending_lt_ptr = 0; + *pending_gt_ptr = 0; + *best_len_ret = best_len; + return lz_matchptr; + } - 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, 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; + *pending_lt_ptr = *bt_left_child(mf, cur_node); + *pending_gt_ptr = *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 = 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 = 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; } } } +/* + * Advance the matchfinder, but don't record any matches. + * + * @mf + * The matchfinder structure. + * @in_begin + * Pointer to the beginning of the input buffer. + * @in_next + * Pointer to the next byte in the input buffer to process. + * @in_end + * Pointer to the end of the input buffer. + * @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 bt_matchfinder_skip_position(struct bt_matchfinder * const restrict mf, - const u8 * const in_base, + const u8 * const in_begin, const u8 * const in_next, const u8 * const in_end, const unsigned nice_len, const unsigned max_search_depth, - unsigned long *prev_hash) + u32 * restrict next_hash) { unsigned depth_remaining = max_search_depth; - unsigned hash; - pos_t cur_match; + u32 hash; + pos_t cur_node; 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)) + if (unlikely(in_end - in_next < LZ_HASH3_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; + 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; + prefetchw(&mf->hash_tab[*next_hash]); 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]; + pending_lt_ptr = bt_left_child(mf, in_next - in_begin); + pending_gt_ptr = bt_right_child(mf, in_next - in_begin); 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; - } + len = 0; - matchptr = &in_base[cur_match]; - len = min(best_lt_len, best_gt_len); + if (!cur_node) { + *pending_lt_ptr = 0; + *pending_gt_ptr = 0; + return; + } - 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]; + *pending_lt_ptr = *bt_left_child(mf, cur_node); + *pending_gt_ptr = *bt_right_child(mf, cur_node); return; } } 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 = 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 = 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; + return; } } } + +#endif /* _BT_MATCHFINDER_H */