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

   1 /*
   2  * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
   3  *
   4  * The following copying information applies to this specific source code file:
   5  *
   6  * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
   7  *
   8  * To the extent possible under law, the author(s) have dedicated all copyright
   9  * and related and neighboring rights to this software to the public domain
  10  * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
  11  * Dedication (the "CC0").
  12  *
  13  * This software is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15  * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
  16  *
  17  * You should have received a copy of the CC0 along with this software; if not
  18  * see <http://creativecommons.org/publicdomain/zero/1.0/>.
  19  */
  20
  21 #ifndef _WIMLIB_LZ_EXTEND_H
  22 #define _WIMLIB_LZ_EXTEND_H
  23
  24 #include "wimlib/bitops.h"
  25 #include "wimlib/unaligned.h"
  26
  27 /* Return the number of bytes at @matchptr that match the bytes at @strptr, up
  28  * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
  29 static inline u32
  30 lz_extend(const u8 * const strptr, const u8 * const matchptr,
  31           const u32 start_len, const u32 max_len)
  32 {
  33         u32 len = start_len;
  34         machine_word_t v_word;
  35
  36         if (UNALIGNED_ACCESS_IS_FAST) {
  37
  38                 if (likely(max_len - len >= 4 * WORDSIZE)) {
  39
  40                 #define COMPARE_WORD_STEP                                       \
  41                         v_word = load_word_unaligned(&matchptr[len]) ^          \
  42                                  load_word_unaligned(&strptr[len]);             \
  43                         if (v_word != 0)                                        \
  44                                 goto word_differs;                              \
  45                         len += WORDSIZE;                                        \
  46
  47                         COMPARE_WORD_STEP
  48                         COMPARE_WORD_STEP
  49                         COMPARE_WORD_STEP
  50                         COMPARE_WORD_STEP
  51                 #undef COMPARE_WORD_STEP
  52                 }
  53
  54                 while (len + WORDSIZE <= max_len) {
  55                         v_word = load_word_unaligned(&matchptr[len]) ^
  56                                  load_word_unaligned(&strptr[len]);
  57                         if (v_word != 0)
  58                                 goto word_differs;
  59                         len += WORDSIZE;
  60                 }
  61         }
  62
  63         while (len < max_len && matchptr[len] == strptr[len])
  64                 len++;
  65         return len;
  66
  67 word_differs:
  68         if (CPU_IS_LITTLE_ENDIAN)
  69                 len += (ffsw(v_word) >> 3);
  70         else
  71                 len += (8 * WORDSIZE - 1 - flsw(v_word)) >> 3;
  72         return len;
  73 }
  74
  75 #endif /* _WIMLIB_LZ_EXTEND_H */