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

   1 /*
   2  * lz_extend.h
   3  *
   4  * Fast match extension for Lempel-Ziv matchfinding.
   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 _WIMLIB_LZ_EXTEND_H
  11 #define _WIMLIB_LZ_EXTEND_H
  12
  13 #include "wimlib/bitops.h"
  14 #include "wimlib/unaligned.h"
  15
  16 /* Return the number of bytes at @matchptr that match the bytes at @strptr, up
  17  * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
  18 static inline u32
  19 lz_extend(const u8 * const strptr, const u8 * const matchptr,
  20           const u32 start_len, const u32 max_len)
  21 {
  22         u32 len = start_len;
  23         machine_word_t v_word;
  24
  25         if (UNALIGNED_ACCESS_IS_FAST) {
  26
  27                 if (likely(max_len - len >= 4 * WORDSIZE)) {
  28
  29                 #define COMPARE_WORD_STEP                                       \
  30                         v_word = load_word_unaligned(&matchptr[len]) ^          \
  31                                  load_word_unaligned(&strptr[len]);             \
  32                         if (v_word != 0)                                        \
  33                                 goto word_differs;                              \
  34                         len += WORDSIZE;                                        \
  35
  36                         COMPARE_WORD_STEP
  37                         COMPARE_WORD_STEP
  38                         COMPARE_WORD_STEP
  39                         COMPARE_WORD_STEP
  40                 #undef COMPARE_WORD_STEP
  41                 }
  42
  43                 while (len + WORDSIZE <= max_len) {
  44                         v_word = load_word_unaligned(&matchptr[len]) ^
  45                                  load_word_unaligned(&strptr[len]);
  46                         if (v_word != 0)
  47                                 goto word_differs;
  48                         len += WORDSIZE;
  49                 }
  50         }
  51
  52         while (len < max_len && matchptr[len] == strptr[len])
  53                 len++;
  54         return len;
  55
  56 word_differs:
  57         if (CPU_IS_LITTLE_ENDIAN)
  58                 len += (ffsw(v_word) >> 3);
  59         else
  60                 len += (flsw(v_word) >> 3);
  61         return len;
  62 }
  63
  64 #endif /* _WIMLIB_LZ_EXTEND_H */