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

   1 /*
   2  * lz_repsearch.h
   3  *
   4  * Fast searching for repeat offset matches.
   5  *
   6  * The author dedicates this file to the public domain.
   7  * You can do whatever you want with this file.
   8  */
   9
  10 #ifndef _LZ_REPSEARCH_H
  11 #define _LZ_REPSEARCH_H
  12
  13 #include "wimlib/lz_extend.h"
  14 #include "wimlib/util.h"
  15
  16 extern u32
  17 lz_extend_repmatch(const u8 *strptr, const u8 *matchptr, u32 max_len);
  18
  19 /*
  20  * Find the longest repeat offset match.
  21  *
  22  * If no match of at least 2 bytes is found, then return 0.
  23  *
  24  * If a match of at least 2 bytes is found, then return its length and set
  25  * *slot_ret to the index of its offset in @queue.
  26  */
  27 static inline u32
  28 lz_repsearch(const u8 * const strptr, const u32 bytes_remaining,
  29              const u32 max_match_len, const u32 repeat_offsets[],
  30              const unsigned num_repeat_offsets, unsigned *slot_ret)
  31 {
  32         u32 best_len = 0;
  33
  34         if (likely(bytes_remaining >= 2)) {
  35                 const u32 max_len = min(max_match_len, bytes_remaining);
  36                 const u16 str = *(const u16 *)strptr;
  37
  38                 for (unsigned i = 0; i < num_repeat_offsets; i++) {
  39                         const u8 * const matchptr = strptr - repeat_offsets[i];
  40
  41                         /* Check the first two bytes.  If they match, then
  42                          * extend the match to its full length.  */
  43                         if (*(const u16 *)matchptr == str) {
  44                                 const u32 len = lz_extend_repmatch(strptr, matchptr, max_len);
  45                                 if (len > best_len) {
  46                                         best_len = len;
  47                                         *slot_ret = i;
  48                                 }
  49                         }
  50                 }
  51         }
  52         return best_len;
  53 }
  54
  55 #endif /* _LZ_REPSEARCH_H */