/*
- * lz_extend.h
+ * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
*
- * Fast match extension for Lempel-Ziv matchfinding.
+ * Copyright 2022 Eric Biggers
*
- * Author: Eric Biggers
- * Year: 2014, 2015
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
*
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef _WIMLIB_LZ_EXTEND_H
#include "wimlib/bitops.h"
#include "wimlib/unaligned.h"
-/* Return the number of bytes at @matchptr that match the bytes at @strptr, up
- * to a maximum of @max_len. Initially, @start_len bytes are matched. */
-static inline u32
+/*
+ * Return the number of bytes at @matchptr that match the bytes at @strptr, up
+ * to a maximum of @max_len. Initially, @len bytes are matched.
+ */
+static forceinline u32
lz_extend(const u8 * const strptr, const u8 * const matchptr,
- const u32 start_len, const u32 max_len)
+ u32 len, const u32 max_len)
{
- u32 len = start_len;
- machine_word_t v_word;
-
- if (UNALIGNED_ACCESS_IS_FAST) {
-
- if (likely(max_len - len >= 4 * WORDSIZE)) {
-
- #define COMPARE_WORD_STEP \
- v_word = load_word_unaligned(&matchptr[len]) ^ \
- load_word_unaligned(&strptr[len]); \
- if (v_word != 0) \
- goto word_differs; \
- len += WORDSIZE; \
-
- COMPARE_WORD_STEP
- COMPARE_WORD_STEP
- COMPARE_WORD_STEP
- COMPARE_WORD_STEP
- #undef COMPARE_WORD_STEP
- }
-
- while (len + WORDSIZE <= max_len) {
- v_word = load_word_unaligned(&matchptr[len]) ^
- load_word_unaligned(&strptr[len]);
- if (v_word != 0)
- goto word_differs;
- len += WORDSIZE;
+ while (UNALIGNED_ACCESS_IS_FAST && len + WORDBYTES <= max_len) {
+ machine_word_t v = load_word_unaligned(matchptr + len) ^
+ load_word_unaligned(strptr + len);
+ if (v != 0) {
+ if (CPU_IS_LITTLE_ENDIAN)
+ len += bsfw(v) >> 3;
+ else
+ len += (WORDBITS - 1 - bsrw(v)) >> 3;
+ return len;
}
+ len += WORDBYTES;
}
while (len < max_len && matchptr[len] == strptr[len])
len++;
return len;
-
-word_differs:
- if (CPU_IS_LITTLE_ENDIAN)
- len += (ffsw(v_word) >> 3);
- else
- len += (flsw(v_word) >> 3);
- return len;
}
#endif /* _WIMLIB_LZ_EXTEND_H */
git://wimlib.net / wimlib / blobdiff