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