2 * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
4 * Copyright 2022 Eric Biggers
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
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
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.
28 #ifndef _WIMLIB_LZ_EXTEND_H
29 #define _WIMLIB_LZ_EXTEND_H
31 #include "wimlib/bitops.h"
32 #include "wimlib/unaligned.h"
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.
38 static forceinline u32
39 lz_extend(const u8 * const strptr, const u8 * const matchptr,
40 u32 len, const u32 max_len)
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);
46 if (CPU_IS_LITTLE_ENDIAN)
49 len += (WORDBITS - 1 - bsrw(v)) >> 3;
55 while (len < max_len && matchptr[len] == strptr[len])
60 #endif /* _WIMLIB_LZ_EXTEND_H */