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