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/types.h"
  14
  15 #if (defined(__x86_64__) || defined(__i386__)) && defined(__GNUC__)
  16 #  define HAVE_FAST_LZ_EXTEND 1
  17 #else
  18 #  define HAVE_FAST_LZ_EXTEND 0
  19 #endif
  20
  21 /* Return the number of bytes at @matchptr that match the bytes at @strptr, up
  22  * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
  23 static inline u32
  24 lz_extend(const u8 * const strptr, const u8 * const matchptr,
  25           const u32 start_len, const u32 max_len)
  26 {
  27         u32 len = start_len;
  28
  29 #if HAVE_FAST_LZ_EXTEND
  30
  31         while (len + sizeof(unsigned long) <= max_len) {
  32                 unsigned long x;
  33
  34                 x = *(const unsigned long *)&matchptr[len] ^
  35                     *(const unsigned long *)&strptr[len];
  36                 if (x != 0)
  37                         return len + (__builtin_ctzl(x) >> 3);
  38                 len += sizeof(unsigned long);
  39         }
  40
  41         if (sizeof(unsigned int) < sizeof(unsigned long) &&
  42             len + sizeof(unsigned int) <= max_len)
  43         {
  44                 unsigned int x;
  45
  46                 x = *(const unsigned int *)&matchptr[len] ^
  47                     *(const unsigned int *)&strptr[len];
  48                 if (x != 0)
  49                         return len + (__builtin_ctz(x) >> 3);
  50                 len += sizeof(unsigned int);
  51         }
  52
  53         if (sizeof(unsigned int) == 4) {
  54                 if (len < max_len && matchptr[len] == strptr[len]) {
  55                         len++;
  56                         if (len < max_len && matchptr[len] == strptr[len]) {
  57                                 len++;
  58                                 if (len < max_len && matchptr[len] == strptr[len]) {
  59                                         len++;
  60                                 }
  61                         }
  62                 }
  63                 return len;
  64         }
  65
  66 #endif /* HAVE_FAST_LZ_EXTEND */
  67
  68         while (len < max_len && matchptr[len] == strptr[len])
  69                 len++;
  70
  71         return len;
  72 }
  73
  74 #endif /* _WIMLIB_LZ_EXTEND_H */