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 /// How many extra bytes lzma_memcmplen() may read. This depends on 23 /// the method but since it is just a few bytes the biggest possible 24 /// value is used here. 25 #define LZMA_MEMCMPLEN_EXTRA 16 26 27 28 /// Find out how many equal bytes the two buffers have. 29 /// 30 /// \param buf1 First buffer 31 /// \param buf2 Second buffer 32 /// \param len How many bytes have already been compared and will 33 /// be assumed to match 34 /// \param limit How many bytes to compare at most, including the 35 /// already-compared bytes. This must be significantly 36 /// smaller than UINT32_MAX to avoid integer overflows. 37 /// Up to LZMA_MEMCMPLEN_EXTRA bytes may be read past 38 /// the specified limit from both buf1 and buf2. 39 /// 40 /// \return Number of equal bytes in the buffers is returned. 41 /// This is always at least len and at most limit. 42 static inline uint32_t lzma_attribute((__always_inline__)) 43 lzma_memcmplen(const uint8_t *buf1, const uint8_t *buf2, 44 uint32_t len, uint32_t limit) 45 { 46 assert(len <= limit); 47 assert(limit <= UINT32_MAX / 2); 48 49 #if defined(TUKLIB_FAST_UNALIGNED_ACCESS) \ 50 && ((TUKLIB_GNUC_REQ(3, 4) && defined(__x86_64__)) \ 51 || (defined(__INTEL_COMPILER) && defined(__x86_64__)) \ 52 || (defined(__INTEL_COMPILER) && defined(_M_X64)) \ 53 || (defined(_MSC_VER) && defined(_M_X64))) 54 // NOTE: This will use 64-bit unaligned access which 55 // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit, but 56 // it's convenient here at least as long as it's x86-64 only. 57 // 58 // I keep this x86-64 only for now since that's where I know this 59 // to be a good method. This may be fine on other 64-bit CPUs too. 60 // On big endian one should use xor instead of subtraction and switch 61 // to __builtin_clzll(). 62 while (len < limit) { 63 const uint64_t x = *(const uint64_t *)(buf1 + len) 64 - *(const uint64_t *)(buf2 + len); 65 if (x != 0) { 66 # if defined(_M_X64) // MSVC or Intel C compiler on Windows 67 unsigned long tmp; 68 _BitScanForward64(&tmp, x); 69 len += (uint32_t)tmp >> 3; 70 # else // GCC, clang, or Intel C compiler 71 len += (uint32_t)__builtin_ctzll(x) >> 3; 72 # endif 73 return my_min(len, limit); 74 } 75 76 len += 8; 77 } 78 79 return limit; 80 81 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \ 82 && defined(HAVE__MM_MOVEMASK_EPI8) \ 83 && ((defined(__GNUC__) && defined(__SSE2_MATH__)) \ 84 || (defined(__INTEL_COMPILER) && defined(__SSE2__)) \ 85 || (defined(_MSC_VER) && defined(_M_IX86_FP) \ 86 && _M_IX86_FP >= 2)) 87 // NOTE: Like above, this will use 128-bit unaligned access which 88 // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit. 89 // 90 // SSE2 version for 32-bit and 64-bit x86. On x86-64 the above 91 // version is sometimes significantly faster and sometimes 92 // slightly slower than this SSE2 version, so this SSE2 93 // version isn't used on x86-64. 94 while (len < limit) { 95 const uint32_t x = 0xFFFF ^ _mm_movemask_epi8(_mm_cmpeq_epi8( 96 _mm_loadu_si128((const __m128i *)(buf1 + len)), 97 _mm_loadu_si128((const __m128i *)(buf2 + len)))); 98 99 if (x != 0) { 100 # if defined(__INTEL_COMPILER) 101 len += _bit_scan_forward(x); 102 # elif defined(_MSC_VER) 103 unsigned long tmp; 104 _BitScanForward(&tmp, x); 105 len += tmp; 106 # else 107 len += __builtin_ctz(x); 108 # endif 109 return my_min(len, limit); 110 } 111 112 len += 16; 113 } 114 115 return limit; 116 117 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && !defined(WORDS_BIGENDIAN) 118 // Generic 32-bit little endian method 119 while (len < limit) { 120 uint32_t x = *(const uint32_t *)(buf1 + len) 121 - *(const uint32_t *)(buf2 + len); 122 if (x != 0) { 123 if ((x & 0xFFFF) == 0) { 124 len += 2; 125 x >>= 16; 126 } 127 128 if ((x & 0xFF) == 0) 129 ++len; 130 131 return my_min(len, limit); 132 } 133 134 len += 4; 135 } 136 137 return limit; 138 139 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN) 140 // Generic 32-bit big endian method 141 while (len < limit) { 142 uint32_t x = *(const uint32_t *)(buf1 + len) 143 ^ *(const uint32_t *)(buf2 + len); 144 if (x != 0) { 145 if ((x & 0xFFFF0000) == 0) { 146 len += 2; 147 x <<= 16; 148 } 149 150 if ((x & 0xFF000000) == 0) 151 ++len; 152 153 return my_min(len, limit); 154 } 155 156 len += 4; 157 } 158 159 return limit; 160 161 #else 162 // Simple portable version that doesn't use unaligned access. 163 while (len < limit && buf1[len] == buf2[len]) 164 ++len; 165 166 return len; 167 #endif 168 } 169 170 #endif 171