1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief Optimized comparison of two buffers
6 // Author: Lasse Collin
8 // This file has been put into the public domain.
9 // You can do whatever you want with this file.
11 ///////////////////////////////////////////////////////////////////////////////
13 #ifndef LZMA_MEMCMPLEN_H
14 #define LZMA_MEMCMPLEN_H
18 #ifdef HAVE_IMMINTRIN_H
19 # include <immintrin.h>
22 // Only include <intrin.h> if it is needed. The header is only needed
23 // on Windows when using an MSVC compatible compiler. The Intel compiler
24 // can use the intrinsics without the header file.
25 #if defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
26 && (defined(_MSC_VER) \
28 && !defined(__INTEL_COMPILER))
33 /// Find out how many equal bytes the two buffers have.
35 /// \param buf1 First buffer
36 /// \param buf2 Second buffer
37 /// \param len How many bytes have already been compared and will
38 /// be assumed to match
39 /// \param limit How many bytes to compare at most, including the
40 /// already-compared bytes. This must be significantly
41 /// smaller than UINT32_MAX to avoid integer overflows.
42 /// Up to LZMA_MEMCMPLEN_EXTRA bytes may be read past
43 /// the specified limit from both buf1 and buf2.
45 /// \return Number of equal bytes in the buffers is returned.
46 /// This is always at least len and at most limit.
48 /// \note LZMA_MEMCMPLEN_EXTRA defines how many extra bytes may be read.
49 /// It's rounded up to 2^n. This extra amount needs to be
50 /// allocated in the buffers being used. It needs to be
51 /// initialized too to keep Valgrind quiet.
52 static inline uint32_t lzma_attribute((__always_inline__
))
53 lzma_memcmplen(const uint8_t *buf1
, const uint8_t *buf2
,
54 uint32_t len
, uint32_t limit
)
57 assert(limit
<= UINT32_MAX
/ 2);
59 #if defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
60 && ((TUKLIB_GNUC_REQ(3, 4) && defined(__x86_64__)) \
61 || (defined(__INTEL_COMPILER) && defined(__x86_64__)) \
62 || (defined(__INTEL_COMPILER) && defined(_M_X64)) \
63 || (defined(_MSC_VER) && defined(_M_X64)))
64 // I keep this x86-64 only for now since that's where I know this
65 // to be a good method. This may be fine on other 64-bit CPUs too.
66 // On big endian one should use xor instead of subtraction and switch
67 // to __builtin_clzll().
68 #define LZMA_MEMCMPLEN_EXTRA 8
70 const uint64_t x
= read64ne(buf1
+ len
) - read64ne(buf2
+ len
);
72 # if defined(_M_X64) // MSVC or Intel C compiler on Windows
74 _BitScanForward64(&tmp
, x
);
75 len
+= (uint32_t)tmp
>> 3;
76 # else // GCC, clang, or Intel C compiler
77 len
+= (uint32_t)__builtin_ctzll(x
) >> 3;
79 return my_min(len
, limit
);
87 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
88 && defined(HAVE__MM_MOVEMASK_EPI8) \
89 && (defined(__SSE2__) \
90 || (defined(_MSC_VER) && defined(_M_IX86_FP) \
92 // NOTE: This will use 128-bit unaligned access which
93 // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit,
94 // but it's convenient here since this is x86-only.
96 // SSE2 version for 32-bit and 64-bit x86. On x86-64 the above
97 // version is sometimes significantly faster and sometimes
98 // slightly slower than this SSE2 version, so this SSE2
99 // version isn't used on x86-64.
100 # define LZMA_MEMCMPLEN_EXTRA 16
101 while (len
< limit
) {
102 const uint32_t x
= 0xFFFF ^ (uint32_t)_mm_movemask_epi8(
104 _mm_loadu_si128((const __m128i
*)(buf1
+ len
)),
105 _mm_loadu_si128((const __m128i
*)(buf2
+ len
))));
109 return my_min(len
, limit
);
117 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && !defined(WORDS_BIGENDIAN)
118 // Generic 32-bit little endian method
119 # define LZMA_MEMCMPLEN_EXTRA 4
120 while (len
< limit
) {
121 uint32_t x
= read32ne(buf1
+ len
) - read32ne(buf2
+ len
);
123 if ((x
& 0xFFFF) == 0) {
131 return my_min(len
, limit
);
139 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN)
140 // Generic 32-bit big endian method
141 # define LZMA_MEMCMPLEN_EXTRA 4
142 while (len
< limit
) {
143 uint32_t x
= read32ne(buf1
+ len
) ^ read32ne(buf2
+ len
);
145 if ((x
& 0xFFFF0000) == 0) {
150 if ((x
& 0xFF000000) == 0)
153 return my_min(len
, limit
);
162 // Simple portable version that doesn't use unaligned access.
163 # define LZMA_MEMCMPLEN_EXTRA 0
164 while (len
< limit
&& buf1
[len
] == buf2
[len
])