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

   1 /*
   2  * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
   3  *
   4  * Copyright 2022 Eric Biggers
   5  *
   6  * Permission is hereby granted, free of charge, to any person
   7  * obtaining a copy of this software and associated documentation
   8  * files (the "Software"), to deal in the Software without
   9  * restriction, including without limitation the rights to use,
  10  * copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the
  12  * Software is furnished to do so, subject to the following
  13  * conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  20  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  22  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  23  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25  * OTHER DEALINGS IN THE SOFTWARE.
  26  */
  27
  28 #ifndef _WIMLIB_LZ_EXTEND_H
  29 #define _WIMLIB_LZ_EXTEND_H
  30
  31 #include "wimlib/bitops.h"
  32 #include "wimlib/unaligned.h"
  33
  34 /*
  35  * Return the number of bytes at @matchptr that match the bytes at @strptr, up
  36  * to a maximum of @max_len.  Initially, @len bytes are matched.
  37  */
  38 static forceinline u32
  39 lz_extend(const u8 * const strptr, const u8 * const matchptr,
  40           u32 len, const u32 max_len)
  41 {
  42         while (UNALIGNED_ACCESS_IS_FAST && len + WORDBYTES <= max_len) {
  43                 machine_word_t v = load_word_unaligned(matchptr + len) ^
  44                                    load_word_unaligned(strptr + len);
  45                 if (v != 0) {
  46                         if (CPU_IS_LITTLE_ENDIAN)
  47                                 len += bsfw(v) >> 3;
  48                         else
  49                                 len += (WORDBITS - 1 - bsrw(v)) >> 3;
  50                         return len;
  51                 }
  52                 len += WORDBYTES;
  53         }
  54
  55         while (len < max_len && matchptr[len] == strptr[len])
  56                 len++;
  57         return len;
  58 }
  59
  60 #endif /* _WIMLIB_LZ_EXTEND_H */