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  * Author:      Eric Biggers
   7  * Year:        2014, 2015
   8  *
   9  * The author dedicates this file to the public domain.
  10  * You can do whatever you want with this file.
  11  */
  12
  13 #ifndef _LZ_REPSEARCH_H
  14 #define _LZ_REPSEARCH_H
  15
  16 #include "wimlib/lz_extend.h"
  17 #include "wimlib/unaligned.h"
  18
  19 extern u32
  20 lz_extend_repmatch(const u8 *strptr, const u8 *matchptr, u32 max_len);
  21
  22 /*
  23  * Given a pointer to the current string and a queue of 3 recent match offsets,
  24  * find the longest repeat offset match.
  25  *
  26  * If no match of at least 2 bytes is found, then return 0.
  27  *
  28  * If a match of at least 2 bytes is found, then return its length and set
  29  * *rep_max_idx_ret to the index of its offset in @recent_offsets.
  30 */
  31 static inline u32
  32 lz_repsearch3(const u8 * const strptr, const u32 max_len,
  33               const u32 recent_offsets[3], unsigned *rep_max_idx_ret)
  34 {
  35         unsigned rep_max_idx;
  36         u32 rep_len;
  37         u32 rep_max_len;
  38         const u16 str = load_u16_unaligned(strptr);
  39         const u8 *matchptr;
  40
  41         matchptr = strptr - recent_offsets[0];
  42         if (load_u16_unaligned(matchptr) == str)
  43                 rep_max_len = lz_extend_repmatch(strptr, matchptr, max_len);
  44         else
  45                 rep_max_len = 0;
  46         rep_max_idx = 0;
  47
  48         matchptr = strptr - recent_offsets[1];
  49         if (load_u16_unaligned(matchptr) == str) {
  50                 rep_len = lz_extend_repmatch(strptr, matchptr, max_len);
  51                 if (rep_len > rep_max_len) {
  52                         rep_max_len = rep_len;
  53                         rep_max_idx = 1;
  54                 }
  55         }
  56
  57         matchptr = strptr - recent_offsets[2];
  58         if (load_u16_unaligned(matchptr) == str) {
  59                 rep_len = lz_extend_repmatch(strptr, matchptr, max_len);
  60                 if (rep_len > rep_max_len) {
  61                         rep_max_len = rep_len;
  62                         rep_max_idx = 2;
  63                 }
  64         }
  65
  66         *rep_max_idx_ret = rep_max_idx;
  67         return rep_max_len;
  68 }
  69
  70 #endif /* _LZ_REPSEARCH_H */