include/wimlib/integrity.h \
include/wimlib/lcpit_matchfinder.h \
include/wimlib/list.h \
- include/wimlib/lz_extend.h \
- include/wimlib/lz_hash.h \
include/wimlib/lzms_common.h \
include/wimlib/lzms_constants.h \
include/wimlib/lzx_common.h \
include/wimlib/lzx_constants.h \
+ include/wimlib/matchfinder_common.h \
include/wimlib/metadata.h \
include/wimlib/object_id.h \
include/wimlib/pathlist.h \
#include <string.h>
-#include "wimlib/lz_extend.h"
-#include "wimlib/lz_hash.h"
+#include "wimlib/matchfinder_common.h"
#define BT_MATCHFINDER_HASH3_ORDER 15
#define BT_MATCHFINDER_HASH3_WAYS 2
* the case if the function contains only static assertions. */
#define _unused_attribute __attribute__((unused))
-/* Endianness definitions. Either CPU_IS_BIG_ENDIAN or CPU_IS_LITTLE_ENDIAN is
- * set to 1. The other is set to 0. Note that newer gcc supports
+/* Endianness definitions. Either CPU_IS_BIG_ENDIAN() or CPU_IS_LITTLE_ENDIAN()
+ * evaluates to 1. The other evaluates to 0. Note that newer gcc supports
* __BYTE_ORDER__ for easily determining the endianness; older gcc doesn't. In
* the latter case we fall back to a configure-time check. */
#ifdef __BYTE_ORDER__
-# define CPU_IS_BIG_ENDIAN (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
+# define CPU_IS_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
#elif defined(HAVE_CONFIG_H)
# include "config.h"
# ifdef WORDS_BIGENDIAN
-# define CPU_IS_BIG_ENDIAN 1
+# define CPU_IS_BIG_ENDIAN() 1
# else
-# define CPU_IS_BIG_ENDIAN 0
+# define CPU_IS_BIG_ENDIAN() 0
# endif
#endif
-#define CPU_IS_LITTLE_ENDIAN (!CPU_IS_BIG_ENDIAN)
+#define CPU_IS_LITTLE_ENDIAN() (!CPU_IS_BIG_ENDIAN())
/* UNALIGNED_ACCESS_IS_FAST should be defined to 1 if unaligned memory accesses
* can be performed efficiently on the target platform. */
#define bswap32(n) (__builtin_constant_p(n) ? bswap32_const(n) : do_bswap32(n))
#define bswap64(n) (__builtin_constant_p(n) ? bswap64_const(n) : do_bswap64(n))
-#if CPU_IS_BIG_ENDIAN
+#if CPU_IS_BIG_ENDIAN()
# define cpu_to_le16(n) ((_force_attr le16)bswap16(n))
# define cpu_to_le32(n) ((_force_attr le32)bswap32(n))
# define cpu_to_le64(n) ((_force_attr le64)bswap64(n))
#include <string.h>
-#include "wimlib/lz_extend.h"
-#include "wimlib/lz_hash.h"
-#include "wimlib/unaligned.h"
+#include "wimlib/matchfinder_common.h"
#define HC_MATCHFINDER_HASH3_ORDER 15
#define HC_MATCHFINDER_HASH4_ORDER 16
+++ /dev/null
-/*
- * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
- *
- * Copyright 2022 Eric Biggers
- *
- * 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 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
-#define _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, @len bytes are matched.
- */
-static forceinline u32
-lz_extend(const u8 * const strptr, const u8 * const matchptr,
- u32 len, const u32 max_len)
-{
- 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;
-}
-
-#endif /* _WIMLIB_LZ_EXTEND_H */
+++ /dev/null
-/*
- * lz_hash.h - hashing for Lempel-Ziv matchfinding
- *
- * Copyright 2022 Eric Biggers
- *
- * 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 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 _LZ_HASH_H
-#define _LZ_HASH_H
-
-#include "wimlib/types.h"
-
-/*
- * The hash function: given a sequence prefix held in the low-order bits of a
- * 32-bit value, multiply by a carefully-chosen large constant. Discard any
- * bits of the product that don't fit in a 32-bit value, but take the
- * next-highest @num_bits bits of the product as the hash value, as those have
- * the most randomness.
- */
-static forceinline u32
-lz_hash(u32 seq, unsigned num_bits)
-{
- return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
-}
-
-#endif /* _LZ_HASH_H */
--- /dev/null
+/*
+ * matchfinder_common.h - common code for Lempel-Ziv matchfinding
+ *
+ * Copyright 2022 Eric Biggers
+ *
+ * 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 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_MATCHFINDER_COMMON_H
+#define _WIMLIB_MATCHFINDER_COMMON_H
+
+#include "wimlib/bitops.h"
+#include "wimlib/unaligned.h"
+
+/*
+ * Given a 32-bit value that was loaded with the platform's native endianness,
+ * return a 32-bit value whose high-order 8 bits are 0 and whose low-order 24
+ * bits contain the first 3 bytes, arranged in octets in a platform-dependent
+ * order, at the memory location from which the input 32-bit value was loaded.
+ */
+static forceinline u32
+loaded_u32_to_u24(u32 v)
+{
+ if (CPU_IS_LITTLE_ENDIAN())
+ return v & 0xFFFFFF;
+ else
+ return v >> 8;
+}
+
+/*
+ * Load the next 3 bytes from @p into the 24 low-order bits of a 32-bit value.
+ * The order in which the 3 bytes will be arranged as octets in the 24 bits is
+ * platform-dependent. At least 4 bytes (not 3) must be available at @p.
+ */
+static forceinline u32
+load_u24_unaligned(const u8 *p)
+{
+#if UNALIGNED_ACCESS_IS_FAST
+ return loaded_u32_to_u24(load_u32_unaligned(p));
+#else
+ if (CPU_IS_LITTLE_ENDIAN())
+ return ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
+ else
+ return ((u32)p[2] << 0) | ((u32)p[1] << 8) | ((u32)p[0] << 16);
+#endif
+}
+
+/*
+ * The hash function: given a sequence prefix held in the low-order bits of a
+ * 32-bit value, multiply by a carefully-chosen large constant. Discard any
+ * bits of the product that don't fit in a 32-bit value, but take the
+ * next-highest @num_bits bits of the product as the hash value, as those have
+ * the most randomness.
+ */
+static forceinline u32
+lz_hash(u32 seq, unsigned num_bits)
+{
+ return (u32)(seq * 0x1E35A7BD) >> (32 - num_bits);
+}
+
+/*
+ * 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 forceinline unsigned
+lz_extend(const u8 * const strptr, const u8 * const matchptr,
+ const unsigned start_len, const unsigned max_len)
+{
+ unsigned len = start_len;
+ machine_word_t v_word;
+
+ if (UNALIGNED_ACCESS_IS_FAST) {
+
+ if (likely(max_len - len >= 4 * WORDBYTES)) {
+
+ #define COMPARE_WORD_STEP \
+ v_word = load_word_unaligned(&matchptr[len]) ^ \
+ load_word_unaligned(&strptr[len]); \
+ if (v_word != 0) \
+ goto word_differs; \
+ len += WORDBYTES; \
+
+ COMPARE_WORD_STEP
+ COMPARE_WORD_STEP
+ COMPARE_WORD_STEP
+ COMPARE_WORD_STEP
+ #undef COMPARE_WORD_STEP
+ }
+
+ while (len + WORDBYTES <= max_len) {
+ v_word = load_word_unaligned(&matchptr[len]) ^
+ load_word_unaligned(&strptr[len]);
+ if (v_word != 0)
+ goto word_differs;
+ len += WORDBYTES;
+ }
+ }
+
+ while (len < max_len && matchptr[len] == strptr[len])
+ len++;
+ return len;
+
+word_differs:
+ if (CPU_IS_LITTLE_ENDIAN())
+ len += (bsfw(v_word) >> 3);
+ else
+ len += (WORDBITS - 1 - bsrw(v_word)) >> 3;
+ return len;
+}
+
+#endif /* _WIMLIB_MATCHFINDER_COMMON_H */
}
}
-/*
- * Given a 32-bit value that was loaded with the platform's native endianness,
- * return a 32-bit value whose high-order 8 bits are 0 and whose low-order 24
- * bits contain the first 3 bytes, arranged in octets in a platform-dependent
- * order, at the memory location from which the input 32-bit value was loaded.
- */
-static forceinline u32
-loaded_u32_to_u24(u32 v)
-{
- if (CPU_IS_LITTLE_ENDIAN)
- return v & 0xFFFFFF;
- else
- return v >> 8;
-}
-
-/*
- * Load the next 3 bytes from the memory location @p into the 24 low-order bits
- * of a 32-bit value. The order in which the 3 bytes will be arranged as octets
- * in the 24 bits is platform-dependent. At least LOAD_U24_REQUIRED_NBYTES
- * bytes must be available at @p; note that this may be more than 3.
- */
-static forceinline u32
-load_u24_unaligned(const u8 *p)
-{
-#if UNALIGNED_ACCESS_IS_FAST
-# define LOAD_U24_REQUIRED_NBYTES 4
- return loaded_u32_to_u24(load_u32_unaligned(p));
-#else
-# define LOAD_U24_REQUIRED_NBYTES 3
-# if CPU_IS_BIG_ENDIAN
- return ((u32)p[2] << 0) | ((u32)p[1] << 8) | ((u32)p[0] << 16);
-# else
- return ((u32)p[0] << 0) | ((u32)p[1] << 8) | ((u32)p[2] << 16);
-# endif
-#endif
-}
-
-
#endif /* _WIMLIB_UNALIGNED_H */
#include "wimlib/compressor_ops.h"
#include "wimlib/error.h"
#include "wimlib/lcpit_matchfinder.h"
-#include "wimlib/lz_extend.h"
-#include "wimlib/lz_hash.h"
#include "wimlib/lzms_common.h"
+#include "wimlib/matchfinder_common.h"
#include "wimlib/unaligned.h"
#include "wimlib/util.h"
avail = BITBUF_NBITS - is->bitsleft;
- if (UNALIGNED_ACCESS_IS_FAST && CPU_IS_LITTLE_ENDIAN &&
+ if (UNALIGNED_ACCESS_IS_FAST && CPU_IS_LITTLE_ENDIAN() &&
WORDBYTES == 8 && likely(is->next - is->begin >= 8))
{
is->next -= (avail & ~15) >> 3;
#include "wimlib/compress_common.h"
#include "wimlib/compressor_ops.h"
#include "wimlib/error.h"
-#include "wimlib/lz_extend.h"
#include "wimlib/lzx_common.h"
#include "wimlib/unaligned.h"
#include "wimlib/util.h"