X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=lzma%2Fcommon%2Fmemcmplen.h;fp=lzma%2Fcommon%2Fmemcmplen.h;h=c1efc9e28b77ce360587453c49edbc16b3348af7;hb=32b8a6b26ed8843828e03e505d2256960bda0980;hp=0000000000000000000000000000000000000000;hpb=d48fc23a4bcf8ca3c406d6e8c8a6f8c6b0fa2f1e;p=zpackage

diff --git a/lzma/common/memcmplen.h b/lzma/common/memcmplen.h
new file mode 100644
index 0000000..c1efc9e
--- /dev/null
+++ b/lzma/common/memcmplen.h
@@ -0,0 +1,175 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       memcmplen.h
+/// \brief      Optimized comparison of two buffers
+//
+//  Author:     Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_MEMCMPLEN_H
+#define LZMA_MEMCMPLEN_H
+
+#include "common.h"
+
+#ifdef HAVE_IMMINTRIN_H
+#	include <immintrin.h>
+#endif
+
+
+/// Find out how many equal bytes the two buffers have.
+///
+/// \param      buf1    First buffer
+/// \param      buf2    Second buffer
+/// \param      len     How many bytes have already been compared and will
+///                     be assumed to match
+/// \param      limit   How many bytes to compare at most, including the
+///                     already-compared bytes. This must be significantly
+///                     smaller than UINT32_MAX to avoid integer overflows.
+///                     Up to LZMA_MEMCMPLEN_EXTRA bytes may be read past
+///                     the specified limit from both buf1 and buf2.
+///
+/// \return     Number of equal bytes in the buffers is returned.
+///             This is always at least len and at most limit.
+///
+/// \note       LZMA_MEMCMPLEN_EXTRA defines how many extra bytes may be read.
+///             It's rounded up to 2^n. This extra amount needs to be
+///             allocated in the buffers being used. It needs to be
+///             initialized too to keep Valgrind quiet.
+static inline uint32_t lzma_attribute((__always_inline__))
+lzma_memcmplen(const uint8_t *buf1, const uint8_t *buf2,
+		uint32_t len, uint32_t limit)
+{
+	assert(len <= limit);
+	assert(limit <= UINT32_MAX / 2);
+
+#if defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
+		&& ((TUKLIB_GNUC_REQ(3, 4) && defined(__x86_64__)) \
+			|| (defined(__INTEL_COMPILER) && defined(__x86_64__)) \
+			|| (defined(__INTEL_COMPILER) && defined(_M_X64)) \
+			|| (defined(_MSC_VER) && defined(_M_X64)))
+	// NOTE: This will use 64-bit unaligned access which
+	// TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit, but
+	// it's convenient here at least as long as it's x86-64 only.
+	//
+	// I keep this x86-64 only for now since that's where I know this
+	// to be a good method. This may be fine on other 64-bit CPUs too.
+	// On big endian one should use xor instead of subtraction and switch
+	// to __builtin_clzll().
+#define LZMA_MEMCMPLEN_EXTRA 8
+	while (len < limit) {
+		const uint64_t x = *(const uint64_t *)(buf1 + len)
+				- *(const uint64_t *)(buf2 + len);
+		if (x != 0) {
+#	if defined(_M_X64) // MSVC or Intel C compiler on Windows
+			unsigned long tmp;
+			_BitScanForward64(&tmp, x);
+			len += (uint32_t)tmp >> 3;
+#	else // GCC, clang, or Intel C compiler
+			len += (uint32_t)__builtin_ctzll(x) >> 3;
+#	endif
+			return my_min(len, limit);
+		}
+
+		len += 8;
+	}
+
+	return limit;
+
+#elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
+		&& defined(HAVE__MM_MOVEMASK_EPI8) \
+		&& ((defined(__GNUC__) && defined(__SSE2_MATH__)) \
+			|| (defined(__INTEL_COMPILER) && defined(__SSE2__)) \
+			|| (defined(_MSC_VER) && defined(_M_IX86_FP) \
+				&& _M_IX86_FP >= 2))
+	// NOTE: Like above, this will use 128-bit unaligned access which
+	// TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit.
+	//
+	// SSE2 version for 32-bit and 64-bit x86. On x86-64 the above
+	// version is sometimes significantly faster and sometimes
+	// slightly slower than this SSE2 version, so this SSE2
+	// version isn't used on x86-64.
+#	define LZMA_MEMCMPLEN_EXTRA 16
+	while (len < limit) {
+		const uint32_t x = 0xFFFF ^ _mm_movemask_epi8(_mm_cmpeq_epi8(
+			_mm_loadu_si128((const __m128i *)(buf1 + len)),
+			_mm_loadu_si128((const __m128i *)(buf2 + len))));
+
+		if (x != 0) {
+#	if defined(__INTEL_COMPILER)
+			len += _bit_scan_forward(x);
+#	elif defined(_MSC_VER)
+			unsigned long tmp;
+			_BitScanForward(&tmp, x);
+			len += tmp;
+#	else
+			len += __builtin_ctz(x);
+#	endif
+			return my_min(len, limit);
+		}
+
+		len += 16;
+	}
+
+	return limit;
+
+#elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && !defined(WORDS_BIGENDIAN)
+	// Generic 32-bit little endian method
+#	define LZMA_MEMCMPLEN_EXTRA 4
+	while (len < limit) {
+		uint32_t x = *(const uint32_t *)(buf1 + len)
+				- *(const uint32_t *)(buf2 + len);
+		if (x != 0) {
+			if ((x & 0xFFFF) == 0) {
+				len += 2;
+				x >>= 16;
+			}
+
+			if ((x & 0xFF) == 0)
+				++len;
+
+			return my_min(len, limit);
+		}
+
+		len += 4;
+	}
+
+	return limit;
+
+#elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN)
+	// Generic 32-bit big endian method
+#	define LZMA_MEMCMPLEN_EXTRA 4
+	while (len < limit) {
+		uint32_t x = *(const uint32_t *)(buf1 + len)
+				^ *(const uint32_t *)(buf2 + len);
+		if (x != 0) {
+			if ((x & 0xFFFF0000) == 0) {
+				len += 2;
+				x <<= 16;
+			}
+
+			if ((x & 0xFF000000) == 0)
+				++len;
+
+			return my_min(len, limit);
+		}
+
+		len += 4;
+	}
+
+	return limit;
+
+#else
+	// Simple portable version that doesn't use unaligned access.
+#	define LZMA_MEMCMPLEN_EXTRA 0
+	while (len < limit && buf1[len] == buf2[len])
+		++len;
+
+	return len;
+#endif
+}
+
+#endif