Get rid of matchfinder_common.h and manual memsets
[wimlib] / include / wimlib / bt_matchfinder.h
index 75858a33ebe6157f592bce6274fed700362332e5..189c5a1571037cffe7f7ecead61a02275b9a66e6 100644 (file)
 /*
  * 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 <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
+#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 */