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 174