wimlib.net Git - wimlib/blob - include/wimlib/bt_matchfinder.h

   1 /*
   2  * bt_matchfinder.h
   3  *
   4  * Author:      Eric Biggers
   5  * Year:        2014, 2015
   6  *
   7  * The author dedicates this file to the public domain.
   8  * You can do whatever you want with this file.
   9  *
  10  * ----------------------------------------------------------------------------
  11  *
  12  * This is a Binary Trees (bt) based matchfinder.
  13  *
  14  * The data structure is a hash table where each hash bucket contains a binary
  15  * tree of sequences whose first 3 bytes share the same hash code.  Each
  16  * sequence is identified by its starting position in the input buffer.  Each
  17  * binary tree is always sorted such that each left child represents a sequence
  18  * lexicographically lesser than its parent and each right child represents a
  19  * sequence lexicographically greater than its parent.
  20  *
  21  * The algorithm processes the input buffer sequentially.  At each byte
  22  * position, the hash code of the first 3 bytes of the sequence beginning at
  23  * that position (the sequence being matched against) is computed.  This
  24  * identifies the hash bucket to use for that position.  Then, a new binary tree
  25  * node is created to represent the current sequence.  Then, in a single tree
  26  * traversal, the hash bucket's binary tree is searched for matches and is
  27  * re-rooted at the new node.
  28  *
  29  * Compared to the simpler algorithm that uses linked lists instead of binary
  30  * trees (see hc_matchfinder.h), the binary tree version gains more information
  31  * at each node visitation.  Ideally, the binary tree version will examine only
  32  * 'log(n)' nodes to find the same matches that the linked list version will
  33  * find by examining 'n' nodes.  In addition, the binary tree version can
  34  * examine fewer bytes at each node by taking advantage of the common prefixes
  35  * that result from the sort order, whereas the linked list version may have to
  36  * examine up to the full length of the match at each node.
  37  *
  38  * However, it is not always best to use the binary tree version.  It requires
  39  * nearly twice as much memory as the linked list version, and it takes time to
  40  * keep the binary trees sorted, even at positions where the compressor does not
  41  * need matches.  Generally, when doing fast compression on small buffers,
  42  * binary trees are the wrong approach.  They are best suited for thorough
  43  * compression and/or large buffers.
  44  *
  45  * ----------------------------------------------------------------------------
  46  */
  47
  48
  49 #include <string.h>
  50
  51 #include "wimlib/lz_extend.h"
  52 #include "wimlib/lz_hash.h"
  53
  54 #define BT_MATCHFINDER_HASH_ORDER 16
  55
  56 /* TEMPLATED functions and structures have MF_SUFFIX appended to their name.  */
  57 #undef TEMPLATED
  58 #define TEMPLATED(name)         CONCAT(name, MF_SUFFIX)
  59
  60 #ifndef _WIMLIB_BT_MATCHFINDER_H
  61 #define _WIMLIB_BT_MATCHFINDER_H
  62
  63 /* Non-templated definitions  */
  64
  65 /* Representation of a match found by the bt_matchfinder  */
  66 struct lz_match {
  67
  68         /* The number of bytes matched.  */
  69         u32 length;
  70
  71         /* The offset back from the current position that was matched.  */
  72         u32 offset;
  73 };
  74
  75 static inline u32
  76 bt_matchfinder_hash_3_bytes(const u8 *in_next)
  77 {
  78         return lz_hash_3_bytes(in_next, BT_MATCHFINDER_HASH_ORDER);
  79 }
  80
  81 #endif /* _WIMLIB_BT_MATCHFINDER_H */
  82
  83 struct TEMPLATED(bt_matchfinder) {
  84         pos_t hash_tab[1UL << BT_MATCHFINDER_HASH_ORDER];
  85         pos_t child_tab[];
  86 };
  87
  88 /* Return the number of bytes that must be allocated for a 'bt_matchfinder' that
  89  * can work with buffers up to the specified size.  */
  90 static inline size_t
  91 TEMPLATED(bt_matchfinder_size)(size_t max_bufsize)
  92 {
  93         return sizeof(struct TEMPLATED(bt_matchfinder)) +
  94                 (2 * max_bufsize * sizeof(pos_t));
  95 }
  96
  97 /* Prepare the matchfinder for a new input buffer.  */
  98 static inline void
  99 TEMPLATED(bt_matchfinder_init)(struct TEMPLATED(bt_matchfinder) *mf)
 100 {
 101         memset(mf, 0, sizeof(*mf));
 102 }
 103
 104 static inline pos_t *
 105 TEMPLATED(bt_child)(struct TEMPLATED(bt_matchfinder) *mf, pos_t node, int offset)
 106 {
 107         return &mf->child_tab[(node << 1) + offset];
 108 }
 109
 110 static inline pos_t *
 111 TEMPLATED(bt_left_child)(struct TEMPLATED(bt_matchfinder) *mf, pos_t node)
 112 {
 113         return TEMPLATED(bt_child)(mf, node, 0);
 114 }
 115
 116 static inline pos_t *
 117 TEMPLATED(bt_right_child)(struct TEMPLATED(bt_matchfinder) *mf, pos_t node)
 118 {
 119         return TEMPLATED(bt_child)(mf, node, 1);
 120 }
 121
 122 /*
 123  * Retrieve a list of matches with the current position.
 124  *
 125  * @mf
 126  *      The matchfinder structure.
 127  * @in_begin
 128  *      Pointer to the beginning of the input buffer.
 129  * @in_next
 130  *      Pointer to the next byte in the input buffer to process.  This is the
 131  *      pointer to the sequence being matched against.
 132  * @min_len
 133  *      Only record matches that are at least this long.
 134  * @max_len
 135  *      The maximum permissible match length at this position.
 136  * @nice_len
 137  *      Stop searching if a match of at least this length is found.
 138  *      Must be <= @max_len.
 139  * @max_search_depth
 140  *      Limit on the number of potential matches to consider.  Must be >= 1.
 141  * @next_hash
 142  *      Pointer to the hash code for the current sequence, which was computed
 143  *      one position in advance so that the binary tree root could be
 144  *      prefetched.  This is an input/output parameter.
 145  * @best_len_ret
 146  *      The length of the longest match found is written here.  (This is
 147  *      actually redundant with the 'struct lz_match' array, but this is easier
 148  *      for the compiler to optimize when inlined and the caller immediately
 149  *      does a check against 'best_len'.)
 150  * @lz_matchptr
 151  *      An array in which this function will record the matches.  The recorded
 152  *      matches will be sorted by strictly increasing length and strictly
 153  *      increasing offset.  The maximum number of matches that may be found is
 154  *      'min(nice_len, max_len) - 3 + 1'.
 155  *
 156  * The return value is a pointer to the next available slot in the @lz_matchptr
 157  * array.  (If no matches were found, this will be the same as @lz_matchptr.)
 158  */
 159 static inline struct lz_match *
 160 TEMPLATED(bt_matchfinder_get_matches)(struct TEMPLATED(bt_matchfinder) * const restrict mf,
 161                                       const u8 * const in_begin,
 162                                       const u8 * const in_next,
 163                                       const unsigned min_len,
 164                                       const unsigned max_len,
 165                                       const unsigned nice_len,
 166                                       const unsigned max_search_depth,
 167                                       u32 * restrict next_hash,
 168                                       unsigned * restrict best_len_ret,
 169                                       struct lz_match * restrict lz_matchptr)
 170 {
 171         unsigned depth_remaining = max_search_depth;
 172         u32 hash;
 173         pos_t cur_node;
 174         const u8 *matchptr;
 175         pos_t *pending_lt_ptr, *pending_gt_ptr;
 176         unsigned best_lt_len, best_gt_len;
 177         unsigned len;
 178         unsigned best_len = min_len - 1;
 179
 180         if (unlikely(max_len < LZ_HASH3_REQUIRED_NBYTES + 1)) {
 181                 *best_len_ret = best_len;
 182                 return lz_matchptr;
 183         }
 184
 185         hash = *next_hash;
 186         *next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
 187         cur_node = mf->hash_tab[hash];
 188         mf->hash_tab[hash] = in_next - in_begin;
 189         prefetchw(&mf->hash_tab[*next_hash]);
 190
 191         pending_lt_ptr = TEMPLATED(bt_left_child)(mf, in_next - in_begin);
 192         pending_gt_ptr = TEMPLATED(bt_right_child)(mf, in_next - in_begin);
 193         best_lt_len = 0;
 194         best_gt_len = 0;
 195         len = 0;
 196
 197         if (!cur_node) {
 198                 *pending_lt_ptr = 0;
 199                 *pending_gt_ptr = 0;
 200                 *best_len_ret = best_len;
 201                 return lz_matchptr;
 202         }
 203
 204         for (;;) {
 205                 matchptr = &in_begin[cur_node];
 206
 207                 if (matchptr[len] == in_next[len]) {
 208                         len = lz_extend(in_next, matchptr, len + 1, max_len);
 209                         if (len > best_len) {
 210                                 best_len = len;
 211                                 lz_matchptr->length = len;
 212                                 lz_matchptr->offset = in_next - matchptr;
 213                                 lz_matchptr++;
 214                                 if (len >= nice_len) {
 215                                         *pending_lt_ptr = *TEMPLATED(bt_left_child)(mf, cur_node);
 216                                         *pending_gt_ptr = *TEMPLATED(bt_right_child)(mf, cur_node);
 217                                         *best_len_ret = best_len;
 218                                         return lz_matchptr;
 219                                 }
 220                         }
 221                 }
 222
 223                 if (matchptr[len] < in_next[len]) {
 224                         *pending_lt_ptr = cur_node;
 225                         pending_lt_ptr = TEMPLATED(bt_right_child)(mf, cur_node);
 226                         cur_node = *pending_lt_ptr;
 227                         best_lt_len = len;
 228                         if (best_gt_len < len)
 229                                 len = best_gt_len;
 230                 } else {
 231                         *pending_gt_ptr = cur_node;
 232                         pending_gt_ptr = TEMPLATED(bt_left_child)(mf, cur_node);
 233                         cur_node = *pending_gt_ptr;
 234                         best_gt_len = len;
 235                         if (best_lt_len < len)
 236                                 len = best_lt_len;
 237                 }
 238
 239                 if (!cur_node || !--depth_remaining) {
 240                         *pending_lt_ptr = 0;
 241                         *pending_gt_ptr = 0;
 242                         *best_len_ret = best_len;
 243                         return lz_matchptr;
 244                 }
 245         }
 246 }
 247
 248 /*
 249  * Advance the matchfinder, but don't record any matches.
 250  *
 251  * @mf
 252  *      The matchfinder structure.
 253  * @in_begin
 254  *      Pointer to the beginning of the input buffer.
 255  * @in_next
 256  *      Pointer to the next byte in the input buffer to process.
 257  * @in_end
 258  *      Pointer to the end of the input buffer.
 259  * @nice_len
 260  *      Stop searching if a match of at least this length is found.
 261  * @max_search_depth
 262  *      Limit on the number of potential matches to consider.
 263  * @next_hash
 264  *      Pointer to the hash code for the current sequence, which was computed
 265  *      one position in advance so that the binary tree root could be
 266  *      prefetched.  This is an input/output parameter.
 267  *
 268  * Note: this is very similar to bt_matchfinder_get_matches() because both
 269  * functions must do hashing and tree re-rooting.  This version just doesn't
 270  * actually record any matches.
 271  */
 272 static inline void
 273 TEMPLATED(bt_matchfinder_skip_position)(struct TEMPLATED(bt_matchfinder) * const restrict mf,
 274                                         const u8 * const in_begin,
 275                                         const u8 * const in_next,
 276                                         const u8 * const in_end,
 277                                         const unsigned nice_len,
 278                                         const unsigned max_search_depth,
 279                                         u32 * restrict next_hash)
 280 {
 281         unsigned depth_remaining = max_search_depth;
 282         u32 hash;
 283         pos_t cur_node;
 284         const u8 *matchptr;
 285         pos_t *pending_lt_ptr, *pending_gt_ptr;
 286         unsigned best_lt_len, best_gt_len;
 287         unsigned len;
 288
 289         if (unlikely(in_end - in_next < LZ_HASH3_REQUIRED_NBYTES + 1))
 290                 return;
 291
 292         hash = *next_hash;
 293         *next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
 294         cur_node = mf->hash_tab[hash];
 295         mf->hash_tab[hash] = in_next - in_begin;
 296         prefetchw(&mf->hash_tab[*next_hash]);
 297
 298         depth_remaining = max_search_depth;
 299         pending_lt_ptr = TEMPLATED(bt_left_child)(mf, in_next - in_begin);
 300         pending_gt_ptr = TEMPLATED(bt_right_child)(mf, in_next - in_begin);
 301         best_lt_len = 0;
 302         best_gt_len = 0;
 303         len = 0;
 304
 305         if (!cur_node) {
 306                 *pending_lt_ptr = 0;
 307                 *pending_gt_ptr = 0;
 308                 return;
 309         }
 310
 311         for (;;) {
 312                 matchptr = &in_begin[cur_node];
 313
 314                 if (matchptr[len] == in_next[len]) {
 315                         len = lz_extend(in_next, matchptr, len + 1, nice_len);
 316                         if (len == nice_len) {
 317                                 *pending_lt_ptr = *TEMPLATED(bt_left_child)(mf, cur_node);
 318                                 *pending_gt_ptr = *TEMPLATED(bt_right_child)(mf, cur_node);
 319                                 return;
 320                         }
 321                 }
 322
 323                 if (matchptr[len] < in_next[len]) {
 324                         *pending_lt_ptr = cur_node;
 325                         pending_lt_ptr = TEMPLATED(bt_right_child)(mf, cur_node);
 326                         cur_node = *pending_lt_ptr;
 327                         best_lt_len = len;
 328                         if (best_gt_len < len)
 329                                 len = best_gt_len;
 330                 } else {
 331                         *pending_gt_ptr = cur_node;
 332                         pending_gt_ptr = TEMPLATED(bt_left_child)(mf, cur_node);
 333                         cur_node = *pending_gt_ptr;
 334                         best_gt_len = len;
 335                         if (best_lt_len < len)
 336                                 len = best_lt_len;
 337                 }
 338
 339                 if (!cur_node || !--depth_remaining) {
 340                         *pending_lt_ptr = 0;
 341                         *pending_gt_ptr = 0;
 342                         return;
 343                 }
 344         }
 345 }