src/liblzma/common/memcmplen.h

   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
  23 /// Find out how many equal bytes the two buffers have.
  24 ///
  25 /// \param      buf1    First buffer
  26 /// \param      buf2    Second buffer
  27 /// \param      len     How many bytes have already been compared and will
  28 ///                     be assumed to match
  29 /// \param      limit   How many bytes to compare at most, including the
  30 ///                     already-compared bytes. This must be significantly
  31 ///                     smaller than UINT32_MAX to avoid integer overflows.
  32 ///                     Up to LZMA_MEMCMPLEN_EXTRA bytes may be read past
  33 ///                     the specified limit from both buf1 and buf2.
  34 ///
  35 /// \return     Number of equal bytes in the buffers is returned.
  36 ///             This is always at least len and at most limit.
  37 ///
  38 /// \note       LZMA_MEMCMPLEN_EXTRA defines how many extra bytes may be read.
  39 ///             It's rounded up to 2^n. This extra amount needs to be
  40 ///             allocated in the buffers being used. It needs to be
  41 ///             initialized too to keep Valgrind quiet.
  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 #define LZMA_MEMCMPLEN_EXTRA 8
  63         while (len < limit) {
  64                 const uint64_t x = *(const uint64_t *)(buf1 + len)
  65                                 - *(const uint64_t *)(buf2 + len);
  66                 if (x != 0) {
  67 #       if defined(_M_X64) // MSVC or Intel C compiler on Windows
  68                         unsigned long tmp;
  69                         _BitScanForward64(&tmp, x);
  70                         len += (uint32_t)tmp >> 3;
  71 #       else // GCC, clang, or Intel C compiler
  72                         len += (uint32_t)__builtin_ctzll(x) >> 3;
  73 #       endif
  74                         return my_min(len, limit);
  75                 }
  76
  77                 len += 8;
  78         }
  79
  80         return limit;
  81
  82 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) \
  83                 && defined(HAVE__MM_MOVEMASK_EPI8) \
  84                 && ((defined(__GNUC__) && defined(__SSE2_MATH__)) \
  85                         || (defined(__INTEL_COMPILER) && defined(__SSE2__)) \
  86                         || (defined(_MSC_VER) && defined(_M_IX86_FP) \
  87                                 && _M_IX86_FP >= 2))
  88         // NOTE: Like above, this will use 128-bit unaligned access which
  89         // TUKLIB_FAST_UNALIGNED_ACCESS wasn't meant to permit.
  90         //
  91         // SSE2 version for 32-bit and 64-bit x86. On x86-64 the above
  92         // version is sometimes significantly faster and sometimes
  93         // slightly slower than this SSE2 version, so this SSE2
  94         // version isn't used on x86-64.
  95 #       define LZMA_MEMCMPLEN_EXTRA 16
  96         while (len < limit) {
  97                 const uint32_t x = 0xFFFF ^ _mm_movemask_epi8(_mm_cmpeq_epi8(
  98                         _mm_loadu_si128((const __m128i *)(buf1 + len)),
  99                         _mm_loadu_si128((const __m128i *)(buf2 + len))));
 100
 101                 if (x != 0) {
 102 #       if defined(__INTEL_COMPILER)
 103                         len += _bit_scan_forward(x);
 104 #       elif defined(_MSC_VER)
 105                         unsigned long tmp;
 106                         _BitScanForward(&tmp, x);
 107                         len += tmp;
 108 #       else
 109                         len += __builtin_ctz(x);
 110 #       endif
 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 = *(const uint32_t *)(buf1 + len)
 124                                 - *(const uint32_t *)(buf2 + len);
 125                 if (x != 0) {
 126                         if ((x & 0xFFFF) == 0) {
 127                                 len += 2;
 128                                 x >>= 16;
 129                         }
 130
 131                         if ((x & 0xFF) == 0)
 132                                 ++len;
 133
 134                         return my_min(len, limit);
 135                 }
 136
 137                 len += 4;
 138         }
 139
 140         return limit;
 141
 142 #elif defined(TUKLIB_FAST_UNALIGNED_ACCESS) && defined(WORDS_BIGENDIAN)
 143         // Generic 32-bit big endian method
 144 #       define LZMA_MEMCMPLEN_EXTRA 4
 145         while (len < limit) {
 146                 uint32_t x = *(const uint32_t *)(buf1 + len)
 147                                 ^ *(const uint32_t *)(buf2 + len);
 148                 if (x != 0) {
 149                         if ((x & 0xFFFF0000) == 0) {
 150                                 len += 2;
 151                                 x <<= 16;
 152                         }
 153
 154                         if ((x & 0xFF000000) == 0)
 155                                 ++len;
 156
 157                         return my_min(len, limit);
 158                 }
 159
 160                 len += 4;
 161         }
 162
 163         return limit;
 164
 165 #else
 166         // Simple portable version that doesn't use unaligned access.
 167 #       define LZMA_MEMCMPLEN_EXTRA 0
 168         while (len < limit && buf1[len] == buf2[len])
 169                 ++len;
 170
 171         return len;
 172 #endif
 173 }
 174
 175 #endif