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

   1 /*
   2  * hc_matchfinder.h
   3  *
   4  * Copyright (c) 2014 Eric Biggers.  All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
  21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  24  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  25  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  27  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #pragma once
  31
  32 #include "wimlib/lz_extend.h"
  33 #include "wimlib/lz_hash3.h"
  34 #include "wimlib/matchfinder_common.h"
  35 #include "wimlib/unaligned.h"
  36
  37 #ifndef HC_MATCHFINDER_HASH_ORDER
  38 #  if MATCHFINDER_WINDOW_ORDER < 14
  39 #    define HC_MATCHFINDER_HASH_ORDER 14
  40 #  else
  41 #    define HC_MATCHFINDER_HASH_ORDER 15
  42 #  endif
  43 #endif
  44
  45 #define HC_MATCHFINDER_HASH_LENGTH      (1UL << HC_MATCHFINDER_HASH_ORDER)
  46
  47 #define HC_MATCHFINDER_TOTAL_LENGTH     \
  48         (HC_MATCHFINDER_HASH_LENGTH + MATCHFINDER_WINDOW_SIZE)
  49
  50 struct hc_matchfinder {
  51         union {
  52                 pos_t mf_data[HC_MATCHFINDER_TOTAL_LENGTH];
  53                 struct {
  54                         pos_t hash_tab[HC_MATCHFINDER_HASH_LENGTH];
  55                         pos_t child_tab[MATCHFINDER_WINDOW_SIZE];
  56                 };
  57         };
  58 } _aligned_attribute(MATCHFINDER_ALIGNMENT);
  59
  60 /*
  61  * Call before running the first byte through the matchfinder.
  62  */
  63 static inline void
  64 hc_matchfinder_init(struct hc_matchfinder *mf)
  65 {
  66         matchfinder_init(mf->hash_tab, HC_MATCHFINDER_HASH_LENGTH);
  67 }
  68
  69 #if MATCHFINDER_IS_SLIDING
  70 static inline void
  71 hc_matchfinder_slide_window(struct hc_matchfinder *mf)
  72 {
  73         matchfinder_rebase(mf->mf_data, HC_MATCHFINDER_TOTAL_LENGTH);
  74 }
  75 #endif
  76
  77 /*
  78  * Find the longest match longer than 'best_len'.
  79  *
  80  * @mf
  81  *      The matchfinder structure.
  82  * @in_base
  83  *      Pointer to the next byte in the input buffer to process _at the last
  84  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
  85  * @in_next
  86  *      Pointer to the next byte in the input buffer to process.  This is the
  87  *      pointer to the bytes being matched against.
  88  * @best_len
  89  *      Require a match at least this long.
  90  * @max_len
  91  *      Maximum match length to return.
  92  * @nice_len
  93  *      Stop searching if a match of at least this length is found.
  94  * @max_search_depth
  95  *      Limit on the number of potential matches to consider.
  96  * @offset_ret
  97  *      The match offset is returned here.
  98  *
  99  * Return the length of the match found, or 'best_len' if no match longer than
 100  * 'best_len' was found.
 101  */
 102 static inline unsigned
 103 hc_matchfinder_longest_match(struct hc_matchfinder * const restrict mf,
 104                              const u8 * const in_base,
 105                              const u8 * const in_next,
 106                              unsigned best_len,
 107                              const unsigned max_len,
 108                              const unsigned nice_len,
 109                              const unsigned max_search_depth,
 110                              unsigned *offset_ret)
 111 {
 112         unsigned depth_remaining = max_search_depth;
 113         const u8 *best_matchptr = best_matchptr; /* uninitialized */
 114         const u8 *matchptr;
 115         unsigned len;
 116         unsigned hash;
 117         pos_t cur_match;
 118         u32 first_3_bytes;
 119
 120         /* Insert the current sequence into the appropriate hash chain.  */
 121         if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES))
 122                 goto out;
 123         first_3_bytes = load_u24_unaligned(in_next);
 124         hash = lz_hash_u24(first_3_bytes, HC_MATCHFINDER_HASH_ORDER);
 125         cur_match = mf->hash_tab[hash];
 126         mf->child_tab[in_next - in_base] = cur_match;
 127         mf->hash_tab[hash] = in_next - in_base;
 128
 129         if (unlikely(best_len >= max_len))
 130                 goto out;
 131
 132         /* Search the appropriate hash chain for matches.  */
 133
 134         if (!(matchfinder_match_in_window(cur_match, in_base, in_next)))
 135                 goto out;
 136
 137         if (best_len < 3) {
 138                 for (;;) {
 139                         /* No length 3 match found yet.
 140                          * Check the first 3 bytes.  */
 141                         matchptr = &in_base[cur_match];
 142
 143                         if (load_u24_unaligned(matchptr) == first_3_bytes)
 144                                 break;
 145
 146                         /* Not a match; keep trying.  */
 147                         cur_match = mf->child_tab[
 148                                         matchfinder_slot_for_match(cur_match)];
 149                         if (!matchfinder_match_in_window(cur_match,
 150                                                          in_base, in_next))
 151                                 goto out;
 152                         if (!--depth_remaining)
 153                                 goto out;
 154                 }
 155
 156                 /* Found a length 3 match.  */
 157                 best_matchptr = matchptr;
 158                 best_len = lz_extend(in_next, best_matchptr, 3, max_len);
 159                 if (best_len >= nice_len)
 160                         goto out;
 161                 cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
 162                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
 163                         goto out;
 164                 if (!--depth_remaining)
 165                         goto out;
 166         }
 167
 168         for (;;) {
 169                 for (;;) {
 170                         matchptr = &in_base[cur_match];
 171
 172                         /* Already found a length 3 match.  Try for a longer match;
 173                          * start by checking the last 2 bytes and the first 4 bytes.  */
 174                 #if UNALIGNED_ACCESS_IS_FAST
 175                         if ((load_u32_unaligned(matchptr + best_len - 3) ==
 176                              load_u32_unaligned(in_next + best_len - 3)) &&
 177                             (load_u32_unaligned(matchptr) ==
 178                              load_u32_unaligned(in_next)))
 179                 #else
 180                         if (matchptr[best_len] == in_next[best_len])
 181                 #endif
 182                                 break;
 183
 184                         cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
 185                         if (!matchfinder_match_in_window(cur_match, in_base, in_next))
 186                                 goto out;
 187                         if (!--depth_remaining)
 188                                 goto out;
 189                 }
 190
 191         #if UNALIGNED_ACCESS_IS_FAST
 192                 len = 4;
 193         #else
 194                 len = 0;
 195         #endif
 196                 len = lz_extend(in_next, matchptr, len, max_len);
 197                 if (len > best_len) {
 198                         best_len = len;
 199                         best_matchptr = matchptr;
 200                         if (best_len >= nice_len)
 201                                 goto out;
 202                 }
 203                 cur_match = mf->child_tab[matchfinder_slot_for_match(cur_match)];
 204                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
 205                         goto out;
 206                 if (!--depth_remaining)
 207                         goto out;
 208         }
 209 out:
 210         *offset_ret = in_next - best_matchptr;
 211         return best_len;
 212 }
 213
 214 /*
 215  * Advance the match-finder, but don't search for matches.
 216  *
 217  * @mf
 218  *      The matchfinder structure.
 219  * @in_base
 220  *      Pointer to the next byte in the input buffer to process _at the last
 221  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
 222  * @in_next
 223  *      Pointer to the next byte in the input buffer to process.
 224  * @in_end
 225  *      Pointer to the end of the input buffer.
 226  * @count
 227  *      Number of bytes to skip; must be > 0.
 228  */
 229 static inline void
 230 hc_matchfinder_skip_positions(struct hc_matchfinder * restrict mf,
 231                               const u8 *in_base,
 232                               const u8 *in_next,
 233                               const u8 *in_end,
 234                               unsigned count)
 235 {
 236         unsigned hash;
 237
 238         if (unlikely(in_next + count >= in_end - LZ_HASH_REQUIRED_NBYTES))
 239                 return;
 240
 241         do {
 242                 hash = lz_hash(in_next, HC_MATCHFINDER_HASH_ORDER);
 243                 mf->child_tab[in_next - in_base] = mf->hash_tab[hash];
 244                 mf->hash_tab[hash] = in_next - in_base;
 245                 in_next++;
 246         } while (--count);
 247 }