1 // SPDX-License-Identifier: 0BSD 2 3 /////////////////////////////////////////////////////////////////////////////// 4 // 5 /// \file memcmplen.h 6 /// \brief Optimized comparison of two buffers 7 // 8 // Author: Lasse Collin 9 // 10 /////////////////////////////////////////////////////////////////////////////// 11 12 #ifndef LZMA_MEMCMPLEN_H 13 #define LZMA_MEMCMPLEN_H 14 15 #include "common.h" 16 17 #ifdef HAVE_IMMINTRIN_H 18 # include <immintrin.h> 19 #endif 20 21 // Only include <intrin.h> if it is needed. The header is only needed 22 // on Windows when using an MSVC compatible compiler. The Intel compiler 23 // can use the intrinsics without the header file. 24 #if defined(TUKLIB_FAST_UNALIGNED_ACCESS) \ 25 && defined(_MSC_VER) \ 26 && (defined(_M_X64) \ 27 || defined(_M_ARM64) || defined(_M_ARM64EC)) \ 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(__clang__)) \ 61 && SIZE_MAX == UINT64_MAX) \ 62 || (defined(__INTEL_COMPILER) && defined(__x86_64__)) \ 63 || (defined(__INTEL_COMPILER) && defined(_M_X64)) \ 64 || (defined(_MSC_VER) && (defined(_M_X64) \ 65 || defined(_M_ARM64) || defined(_M_ARM64EC)))) 66 // This is only for x86-64 and ARM64 for now. This might be fine on 67 // other 64-bit processors too. 68 // 69 // Reasons to use subtraction instead of xor: 70 // 71 // - On some x86-64 processors (Intel Sandy Bridge to Tiger Lake), 72 // sub+jz and sub+jnz can be fused but xor+jz or xor+jnz cannot. 73 // Thus using subtraction has potential to be a tiny amount faster 74 // since the code checks if the quotient is non-zero. 75 // 76 // - Some processors (Intel Pentium 4) used to have more ALU 77 // resources for add/sub instructions than and/or/xor. 78 // 79 // The processor info is based on Agner Fog's microarchitecture.pdf 80 // version 2023-05-26. https://www.agner.org/optimize/ 81 #define LZMA_MEMCMPLEN_EXTRA 8 82 while (len < limit) { 83 # ifdef WORDS_BIGENDIAN 84 const uint64_t x = read64ne(buf1 + len) ^ read64ne(buf2 + len); 85 # else 86 const uint64_t x = read64ne(buf1 + len) - read64ne(buf2 + len); 87 # endif 88 if (x != 0) { 89 // MSVC or Intel C compiler on Windows 90 # if defined(_MSC_VER) || defined(__INTEL_COMPILER) 91 unsigned long tmp; 92 _BitScanForward64(&tmp, x); 93 len += (uint32_t)tmp >> 3; 94 // GCC, Clang, or Intel C compiler 95 # elif defined(WORDS_BIGENDIAN) 96 len += (uint32_t)__builtin_clzll(x) >> 3; 97 # else 98 len += (uint32_t)__builtin_ctzll(x) >> 3; 99 # endif 100 return my_min(len, limit); 101 } 102 103 len += 8; 104 } 105 106 return limit; 107 108 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \ 109 && defined(HAVE__MM_MOVEMASK_EPI8) \ 110 && (defined(__SSE2__) \ 111 || (defined(_MSC_VER) && defined(_M_IX86_FP) \ 112 && _M_IX86_FP >= 2)) 113 // NOTE: This will use 128-bit unaligned access which 114 // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit, 115 // but it's convenient here since this is x86-only. 116 // 117 // SSE2 version for 32-bit and 64-bit x86. On x86-64 the above 118 // version is sometimes significantly faster and sometimes 119 // slightly slower than this SSE2 version, so this SSE2 120 // version isn't used on x86-64. 121 # define LZMA_MEMCMPLEN_EXTRA 16 122 while (len < limit) { 123 #ifndef __lint__ 124 const uint32_t x = 0xFFFF ^ (uint32_t)_mm_movemask_epi8( 125 _mm_cmpeq_epi8( 126 _mm_loadu_si128((const __m128i *)(buf1 + len)), 127 _mm_loadu_si128((const __m128i *)(buf2 + len)))); 128 #else 129 const uint32_t x = buf1[len] + buf2[len]; // Wrong obviously 130 #endif 131 132 if (x != 0) { 133 len += ctz32(x); 134 return my_min(len, limit); 135 } 136 137 len += 16; 138 } 139 140 return limit; 141 142 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && !defined(WORDS_BIGENDIAN) 143 // Generic 32-bit little endian method 144 # define LZMA_MEMCMPLEN_EXTRA 4 145 while (len < limit) { 146 uint32_t x = read32ne(buf1 + len) - read32ne(buf2 + len); 147 if (x != 0) { 148 if ((x & 0xFFFF) == 0) { 149 len += 2; 150 x >>= 16; 151 } 152 153 if ((x & 0xFF) == 0) 154 ++len; 155 156 return my_min(len, limit); 157 } 158 159 len += 4; 160 } 161 162 return limit; 163 164 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN) 165 // Generic 32-bit big endian method 166 # define LZMA_MEMCMPLEN_EXTRA 4 167 while (len < limit) { 168 uint32_t x = read32ne(buf1 + len) ^ read32ne(buf2 + len); 169 if (x != 0) { 170 if ((x & 0xFFFF0000) == 0) { 171 len += 2; 172 x <<= 16; 173 } 174 175 if ((x & 0xFF000000) == 0) 176 ++len; 177 178 return my_min(len, limit); 179 } 180 181 len += 4; 182 } 183 184 return limit; 185 186 #else 187 // Simple portable version that doesn't use unaligned access. 188 # define LZMA_MEMCMPLEN_EXTRA 0 189 while (len < limit && buf1[len] == buf2[len]) 190 ++len; 191 192 return len; 193 #endif 194 } 195 196 #endif 197
Indexes created Fri Jul 24 00:25:35 UTC 2026