1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file memcmplen.h
4 /// \brief Optimized comparison of two buffers
5 //
6 // Author: Lasse Collin
7 //
8 // This file has been put into the public domain.
9 // You can do whatever you want with this file.
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12
13 #ifndef LZMA_MEMCMPLEN_H
14 #define LZMA_MEMCMPLEN_H
15
16 #include "common.h"
17
18 #ifdef HAVE_IMMINTRIN_H
19 # include <immintrin.h>
20 #endif
21
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) \
27 && defined(_M_X64) \
28 && !defined(__INTEL_COMPILER)
29 # include <intrin.h>
30 #endif
31
32
33 /// Find out how many equal bytes the two buffers have.
34 ///
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.
44 ///
45 /// \return Number of equal bytes in the buffers is returned.
46 /// This is always at least len and at most limit.
47 ///
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 lzma_always_inline uint32_t
53 lzma_memcmplen(const uint8_t *buf1, const uint8_t *buf2,
54 uint32_t len, uint32_t limit)
55 {
56 assert(len <= limit);
57 assert(limit <= UINT32_MAX / 2);
58
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
69 while (len < limit) {
70 const uint64_t x = read64ne(buf1 + len) - read64ne(buf2 + len);
71 if (x != 0) {
72 // MSVC or Intel C compiler on Windows
73 # if (defined(_MSC_VER) || defined(__INTEL_COMPILER)) && defined(_M_X64)
74 unsigned long tmp;
75 _BitScanForward64(&tmp, x);
76 len += (uint32_t)tmp >> 3;
77 // GCC, Clang, or Intel C compiler
78 # else
79 len += (uint32_t)__builtin_ctzll(x) >> 3;
80 # endif
81 return my_min(len, limit);
82 }
83
84 len += 8;
85 }
86
87 return limit;
88
89 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
90 && defined(HAVE__MM_MOVEMASK_EPI8) \
91 && (defined(__SSE2__) \
92 || (defined(_MSC_VER) && defined(_M_IX86_FP) \
93 && _M_IX86_FP >= 2))
94 // NOTE: This will use 128-bit unaligned access which
95 // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit,
96 // but it's convenient here since this is x86-only.
97 //
98 // SSE2 version for 32-bit and 64-bit x86. On x86-64 the above
99 // version is sometimes significantly faster and sometimes
100 // slightly slower than this SSE2 version, so this SSE2
101 // version isn't used on x86-64.
102 # define LZMA_MEMCMPLEN_EXTRA 16
103 while (len < limit) {
104 const uint32_t x = 0xFFFF ^ (uint32_t)_mm_movemask_epi8(
105 _mm_cmpeq_epi8(
106 _mm_loadu_si128((const __m128i *)(buf1 + len)),
107 _mm_loadu_si128((const __m128i *)(buf2 + len))));
108
109 if (x != 0) {
110 len += ctz32(x);
111 return my_min(len, limit);
112 }
113
114 len += 16;
115 }
116
117 return limit;
118
119 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && !defined(WORDS_BIGENDIAN)
120 // Generic 32-bit little endian method
121 # define LZMA_MEMCMPLEN_EXTRA 4
122 while (len < limit) {
123 uint32_t x = read32ne(buf1 + len) - read32ne(buf2 + len);
124 if (x != 0) {
125 if ((x & 0xFFFF) == 0) {
126 len += 2;
127 x >>= 16;
128 }
129
130 if ((x & 0xFF) == 0)
131 ++len;
132
133 return my_min(len, limit);
134 }
135
136 len += 4;
137 }
138
139 return limit;
140
141 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN)
142 // Generic 32-bit big endian method
143 # define LZMA_MEMCMPLEN_EXTRA 4
144 while (len < limit) {
145 uint32_t x = read32ne(buf1 + len) ^ read32ne(buf2 + len);
146 if (x != 0) {
147 if ((x & 0xFFFF0000) == 0) {
148 len += 2;
149 x <<= 16;
150 }
151
152 if ((x & 0xFF000000) == 0)
153 ++len;
154
155 return my_min(len, limit);
156 }
157
158 len += 4;
159 }
160
161 return limit;
162
163 #else
164 // Simple portable version that doesn't use unaligned access.
165 # define LZMA_MEMCMPLEN_EXTRA 0
166 while (len < limit && buf1[len] == buf2[len])
167 ++len;
168
169 return len;
170 #endif
171 }
172
173 #endif