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-2016 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 /*
  28  * Return the number of bytes at @matchptr that match the bytes at @strptr, up
  29  * to a maximum of @max_len.  Initially, @len bytes are matched.
  30  */
  31 static inline u32
  32 lz_extend(const u8 * const strptr, const u8 * const matchptr,
  33           u32 len, const u32 max_len)
  34 {
  35         while (UNALIGNED_ACCESS_IS_FAST && len + WORDBYTES <= max_len) {
  36                 machine_word_t v = load_word_unaligned(matchptr + len) ^
  37                                    load_word_unaligned(strptr + len);
  38                 if (v != 0) {
  39                         if (CPU_IS_LITTLE_ENDIAN)
  40                                 len += bsfw(v) >> 3;
  41                         else
  42                                 len += (WORDBITS - 1 - bsrw(v)) >> 3;
  43                         return len;
  44                 }
  45                 len += WORDBYTES;
  46         }
  47
  48         while (len < max_len && matchptr[len] == strptr[len])
  49                 len++;
  50         return len;
  51 }
  52
  53 #endif /* _WIMLIB_LZ_EXTEND_H */