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 #ifndef _HC_MATCHFINDER_H
  31 #define _HC_MATCHFINDER_H
  32
  33 #include "wimlib/lz_extend.h"
  34 #include "wimlib/lz_hash3.h"
  35 #include "wimlib/matchfinder_common.h"
  36 #include "wimlib/unaligned.h"
  37
  38 #ifndef HC_MATCHFINDER_HASH_ORDER
  39 #  if MATCHFINDER_WINDOW_ORDER < 14
  40 #    define HC_MATCHFINDER_HASH_ORDER 14
  41 #  else
  42 #    define HC_MATCHFINDER_HASH_ORDER 15
  43 #  endif
  44 #endif
  45
  46 #define HC_MATCHFINDER_HASH_LENGTH      (1UL << HC_MATCHFINDER_HASH_ORDER)
  47
  48 #define HC_MATCHFINDER_TOTAL_LENGTH     \
  49         (HC_MATCHFINDER_HASH_LENGTH + MATCHFINDER_WINDOW_SIZE)
  50
  51 struct hc_matchfinder {
  52         union {
  53                 pos_t mf_data[HC_MATCHFINDER_TOTAL_LENGTH];
  54                 struct {
  55                         pos_t hash_tab[HC_MATCHFINDER_HASH_LENGTH];
  56                         pos_t next_tab[MATCHFINDER_WINDOW_SIZE];
  57                 };
  58         };
  59 } _aligned_attribute(MATCHFINDER_ALIGNMENT);
  60
  61 /*
  62  * Call before running the first byte through the matchfinder.
  63  */
  64 static inline void
  65 hc_matchfinder_init(struct hc_matchfinder *mf)
  66 {
  67         matchfinder_init(mf->hash_tab, HC_MATCHFINDER_HASH_LENGTH);
  68 }
  69
  70 #if MATCHFINDER_IS_SLIDING
  71 static inline void
  72 hc_matchfinder_slide_window(struct hc_matchfinder *mf)
  73 {
  74         matchfinder_rebase(mf->mf_data, HC_MATCHFINDER_TOTAL_LENGTH);
  75 }
  76 #endif
  77
  78 /*
  79  * Find the longest match longer than 'best_len'.
  80  *
  81  * @mf
  82  *      The matchfinder structure.
  83  * @in_base
  84  *      Pointer to the next byte in the input buffer to process _at the last
  85  *      time hc_matchfinder_init() or hc_matchfinder_slide_window() was called_.
  86  * @in_next
  87  *      Pointer to the next byte in the input buffer to process.  This is the
  88  *      pointer to the bytes being matched against.
  89  * @best_len
  90  *      Require a match at least this long.
  91  * @max_len
  92  *      Maximum match length to return.
  93  * @nice_len
  94  *      Stop searching if a match of at least this length is found.
  95  * @max_search_depth
  96  *      Limit on the number of potential matches to consider.
  97  * @offset_ret
  98  *      The match offset is returned here.
  99  *
 100  * Return the length of the match found, or 'best_len' if no match longer than
 101  * 'best_len' was found.
 102  */
 103 static inline unsigned
 104 hc_matchfinder_longest_match(struct hc_matchfinder * const restrict mf,
 105                              const u8 * const in_base,
 106                              const u8 * const in_next,
 107                              unsigned best_len,
 108                              const unsigned max_len,
 109                              const unsigned nice_len,
 110                              const unsigned max_search_depth,
 111                              unsigned *offset_ret)
 112 {
 113         unsigned depth_remaining = max_search_depth;
 114         const u8 *best_matchptr = best_matchptr; /* uninitialized */
 115         const u8 *matchptr;
 116         unsigned len;
 117         unsigned hash;
 118         pos_t cur_match;
 119         u32 first_3_bytes;
 120
 121         /* Insert the current sequence into the appropriate hash chain.  */
 122         if (unlikely(max_len < LZ_HASH_REQUIRED_NBYTES))
 123                 goto out;
 124         first_3_bytes = load_u24_unaligned(in_next);
 125         hash = lz_hash_u24(first_3_bytes, HC_MATCHFINDER_HASH_ORDER);
 126         cur_match = mf->hash_tab[hash];
 127         mf->next_tab[in_next - in_base] = cur_match;
 128         mf->hash_tab[hash] = in_next - in_base;
 129
 130         if (unlikely(best_len >= max_len))
 131                 goto out;
 132
 133         /* Search the appropriate hash chain for matches.  */
 134
 135         if (!(matchfinder_match_in_window(cur_match, in_base, in_next)))
 136                 goto out;
 137
 138         if (best_len < 3) {
 139                 for (;;) {
 140                         /* No length 3 match found yet.
 141                          * Check the first 3 bytes.  */
 142                         matchptr = &in_base[cur_match];
 143
 144                         if (load_u24_unaligned(matchptr) == first_3_bytes)
 145                                 break;
 146
 147                         /* Not a match; keep trying.  */
 148                         cur_match = mf->next_tab[
 149                                         matchfinder_slot_for_match(cur_match)];
 150                         if (!matchfinder_match_in_window(cur_match,
 151                                                          in_base, in_next))
 152                                 goto out;
 153                         if (!--depth_remaining)
 154                                 goto out;
 155                 }
 156
 157                 /* Found a length 3 match.  */
 158                 best_matchptr = matchptr;
 159                 best_len = lz_extend(in_next, best_matchptr, 3, max_len);
 160                 if (best_len >= nice_len)
 161                         goto out;
 162                 cur_match = mf->next_tab[matchfinder_slot_for_match(cur_match)];
 163                 if (!matchfinder_match_in_window(cur_match, in_base, in_next))
 164                         goto out;
 165                 if (!--depth_remaining)
 166                         goto out;
 167         }
 168
 169         for (;;) {
 170                 for (;;) {
 171                         matchptr = &in_base[cur_match];
 172
 173                         /* Already found a length 3 match.  Try for a longer match;
 174                          * start by checking the last 2 bytes and the first 4 bytes.  */
 175                 #if UNALIGNED_ACCESS_IS_FAST
 176                         if ((load_u32_unaligned(matchptr + best_len - 3) ==
 177                              load_u32_unaligned(in_next + best_len - 3)) &&
 178                             (load_u32_unaligned(matchptr) ==
 179                              load_u32_unaligned(in_next)))
 180                 #else
 181                         if (matchptr[best_len] == in_next[best_len])
 182                 #endif
 183                                 break;
 184
 185                         cur_match = mf->next_tab[matchfinder_slot_for_match(cur_match)];
 186                         if (!matchfinder_match_in_window(cur_match, in_base, in_next))
 187                                 goto out;
 188                         if (!--depth_remaining)
 189                                 goto out;
 190                 }
 191
 192                 if (UNALIGNED_ACCESS_IS_FAST)
 193                         len = 4;
 194                 else
 195                         len = 0;
 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->next_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->next_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 }
 248
 249 #endif /* _HC_MATCHFINDER_H */