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/unaligned.h"
  15
  16 extern u32
  17 lz_extend_repmatch(const u8 *strptr, const u8 *matchptr, u32 max_len);
  18
  19 /*
  20  * Given a pointer to the current string and a queue of 3 recent match offsets,
  21  * find the longest repeat offset match.
  22  *
  23  * If no match of at least 2 bytes is found, then return 0.
  24  *
  25  * If a match of at least 2 bytes is found, then return its length and set
  26  * *rep_max_idx_ret to the index of its offset in @recent_offsets.
  27 */
  28 static inline u32
  29 lz_repsearch3(const u8 * const strptr, const u32 max_len,
  30               const u32 recent_offsets[3], unsigned *rep_max_idx_ret)
  31 {
  32         unsigned rep_max_idx;
  33         u32 rep_len;
  34         u32 rep_max_len;
  35         const u16 str = load_u16_unaligned(strptr);
  36         const u8 *matchptr;
  37
  38         matchptr = strptr - recent_offsets[0];
  39         if (load_u16_unaligned(matchptr) == str)
  40                 rep_max_len = lz_extend_repmatch(strptr, matchptr, max_len);
  41         else
  42                 rep_max_len = 0;
  43         rep_max_idx = 0;
  44
  45         matchptr = strptr - recent_offsets[1];
  46         if (load_u16_unaligned(matchptr) == str) {
  47                 rep_len = lz_extend_repmatch(strptr, matchptr, max_len);
  48                 if (rep_len > rep_max_len) {
  49                         rep_max_len = rep_len;
  50                         rep_max_idx = 1;
  51                 }
  52         }
  53
  54         matchptr = strptr - recent_offsets[2];
  55         if (load_u16_unaligned(matchptr) == str) {
  56                 rep_len = lz_extend_repmatch(strptr, matchptr, max_len);
  57                 if (rep_len > rep_max_len) {
  58                         rep_max_len = rep_len;
  59                         rep_max_idx = 2;
  60                 }
  61         }
  62
  63         *rep_max_idx_ret = rep_max_idx;
  64         return rep_max_len;
  65 }
  66
  67 #endif /* _LZ_REPSEARCH_H */