folly/detail/RangeSse42.cpp

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17
  18
  19 #include "RangeSse42.h"
  20
  21 #include <glog/logging.h>
  22 #include <folly/Portability.h>
  23
  24
  25
  26 //  Essentially, two versions of this file: one with an SSE42 implementation
  27 //  and one with a fallback implementation. We determine which version to use by
  28 //  testing for the presence of the required headers.
  29 //
  30 //  TODO: Maybe this should be done by the build system....
  31 #if !FOLLY_SSE_PREREQ(4, 2)
  32
  33
  34
  35 namespace folly {
  36
  37 namespace detail {
  38
  39 size_t qfind_first_byte_of_sse42(const StringPieceLite haystack,
  40                                  const StringPieceLite needles) {
  41   CHECK(false) << "Function " << __func__ << " only works with SSE42!";
  42   return qfind_first_byte_of_nosse(haystack, needles);
  43 }
  44
  45 }
  46
  47 }
  48
  49
  50
  51 # else
  52
  53
  54
  55 #include <cstdint>
  56 #include <limits>
  57 #include <string>
  58 #include <emmintrin.h>
  59 #include <smmintrin.h>
  60 #include <folly/Likely.h>
  61
  62 //  GCC 4.9 with ASAN has a problem: a function with no_sanitize_address calling
  63 //  a function with always_inline fails to build. The _mm_* functions are marked
  64 //  always_inline.
  65 //  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67368
  66 #if defined FOLLY_SANITIZE_ADDRESS && \
  67     FOLLY_SANITIZE_ADDRESS == 1 && \
  68     __GNUC_PREREQ(4, 9)
  69 # define _mm_load_si128(p) (*(p))
  70 # define _mm_loadu_si128(p) ((__m128i)__builtin_ia32_loaddqu((const char*)(p)))
  71 #endif
  72
  73 namespace folly {
  74
  75 namespace detail {
  76
  77 // It's okay if pages are bigger than this (as powers of two), but they should
  78 // not be smaller.
  79 static constexpr size_t kMinPageSize = 4096;
  80 static_assert(kMinPageSize >= 16,
  81               "kMinPageSize must be at least SSE register size");
  82
  83 template <typename T>
  84 static inline uintptr_t page_for(T* addr) {
  85   return reinterpret_cast<uintptr_t>(addr) / kMinPageSize;
  86 }
  87
  88 static inline size_t nextAlignedIndex(const char* arr) {
  89    auto firstPossible = reinterpret_cast<uintptr_t>(arr) + 1;
  90    return 1 +                       // add 1 because the index starts at 'arr'
  91      ((firstPossible + 15) & ~0xF)  // round up to next multiple of 16
  92      - firstPossible;
  93 }
  94
  95 static size_t qfind_first_byte_of_needles16(const StringPieceLite haystack,
  96                                             const StringPieceLite needles)
  97   FOLLY_DISABLE_ADDRESS_SANITIZER;
  98
  99 // helper method for case where needles.size() <= 16
 100 size_t qfind_first_byte_of_needles16(const StringPieceLite haystack,
 101                                      const StringPieceLite needles) {
 102   DCHECK_GT(haystack.size(), 0);
 103   DCHECK_GT(needles.size(), 0);
 104   DCHECK_LE(needles.size(), 16);
 105   if ((needles.size() <= 2 && haystack.size() >= 256) ||
 106       // must bail if we can't even SSE-load a single segment of haystack
 107       (haystack.size() < 16 &&
 108        page_for(haystack.end() - 1) != page_for(haystack.data() + 15)) ||
 109       // can't load needles into SSE register if it could cross page boundary
 110       page_for(needles.end() - 1) != page_for(needles.data() + 15)) {
 111     return detail::qfind_first_byte_of_nosse(haystack, needles);
 112   }
 113
 114   auto arr2 = _mm_loadu_si128(
 115       reinterpret_cast<const __m128i*>(needles.data()));
 116   // do an unaligned load for first block of haystack
 117   auto arr1 = _mm_loadu_si128(
 118       reinterpret_cast<const __m128i*>(haystack.data()));
 119   auto index = __builtin_ia32_pcmpestri128((__v16qi)arr2, needles.size(),
 120                                            (__v16qi)arr1, haystack.size(), 0);
 121   if (index < 16) {
 122     return index;
 123   }
 124
 125   // Now, we can do aligned loads hereafter...
 126   size_t i = nextAlignedIndex(haystack.data());
 127   for (; i < haystack.size(); i+= 16) {
 128     auto arr1 = _mm_load_si128(
 129         reinterpret_cast<const __m128i*>(haystack.data() + i));
 130     auto index = __builtin_ia32_pcmpestri128(
 131         (__v16qi)arr2, needles.size(),
 132         (__v16qi)arr1, haystack.size() - i, 0);
 133     if (index < 16) {
 134       return i + index;
 135     }
 136   }
 137   return std::string::npos;
 138 }
 139
 140 template <bool HAYSTACK_ALIGNED>
 141 size_t scanHaystackBlock(const StringPieceLite haystack,
 142                          const StringPieceLite needles,
 143                          uint64_t idx)
 144 // Turn off ASAN because the "arr2 = ..." assignment in the loop below reads
 145 // up to 15 bytes beyond end of the buffer in #needles#.  That is ok because
 146 // ptr2 is always 16-byte aligned, so the read can never span a page boundary.
 147 // Also, the extra data that may be read is never actually used.
 148   FOLLY_DISABLE_ADDRESS_SANITIZER;
 149
 150 // Scans a 16-byte block of haystack (starting at blockStartIdx) to find first
 151 // needle. If HAYSTACK_ALIGNED, then haystack must be 16byte aligned.
 152 // If !HAYSTACK_ALIGNED, then caller must ensure that it is safe to load the
 153 // block.
 154 template <bool HAYSTACK_ALIGNED>
 155 size_t scanHaystackBlock(const StringPieceLite haystack,
 156                          const StringPieceLite needles,
 157                          uint64_t blockStartIdx) {
 158   DCHECK_GT(needles.size(), 16);  // should handled by *needles16() method
 159   DCHECK(blockStartIdx + 16 <= haystack.size() ||
 160          (page_for(haystack.data() + blockStartIdx) ==
 161           page_for(haystack.data() + blockStartIdx + 15)));
 162
 163   __m128i arr1;
 164   if (HAYSTACK_ALIGNED) {
 165     arr1 = _mm_load_si128(
 166         reinterpret_cast<const __m128i*>(haystack.data() + blockStartIdx));
 167   } else {
 168     arr1 = _mm_loadu_si128(
 169         reinterpret_cast<const __m128i*>(haystack.data() + blockStartIdx));
 170   }
 171
 172   // This load is safe because needles.size() >= 16
 173   auto arr2 = _mm_loadu_si128(
 174       reinterpret_cast<const __m128i*>(needles.data()));
 175   size_t b = __builtin_ia32_pcmpestri128(
 176     (__v16qi)arr2, 16, (__v16qi)arr1, haystack.size() - blockStartIdx, 0);
 177
 178   size_t j = nextAlignedIndex(needles.data());
 179   for (; j < needles.size(); j += 16) {
 180     arr2 = _mm_load_si128(
 181         reinterpret_cast<const __m128i*>(needles.data() + j));
 182
 183     auto index = __builtin_ia32_pcmpestri128(
 184       (__v16qi)arr2, needles.size() - j,
 185       (__v16qi)arr1, haystack.size() - blockStartIdx, 0);
 186     b = std::min<size_t>(index, b);
 187   }
 188
 189   if (b < 16) {
 190     return blockStartIdx + b;
 191   }
 192   return std::string::npos;
 193 }
 194
 195 size_t qfind_first_byte_of_sse42(const StringPieceLite haystack,
 196                                  const StringPieceLite needles);
 197
 198 size_t qfind_first_byte_of_sse42(const StringPieceLite haystack,
 199                                  const StringPieceLite needles) {
 200   if (UNLIKELY(needles.empty() || haystack.empty())) {
 201     return std::string::npos;
 202   } else if (needles.size() <= 16) {
 203     // we can save some unnecessary load instructions by optimizing for
 204     // the common case of needles.size() <= 16
 205     return qfind_first_byte_of_needles16(haystack, needles);
 206   }
 207
 208   if (haystack.size() < 16 &&
 209       page_for(haystack.end() - 1) != page_for(haystack.data() + 16)) {
 210     // We can't safely SSE-load haystack. Use a different approach.
 211     if (haystack.size() <= 2) {
 212       return qfind_first_byte_of_std(haystack, needles);
 213     }
 214     return qfind_first_byte_of_byteset(haystack, needles);
 215   }
 216
 217   auto ret = scanHaystackBlock<false>(haystack, needles, 0);
 218   if (ret != std::string::npos) {
 219     return ret;
 220   }
 221
 222   size_t i = nextAlignedIndex(haystack.data());
 223   for (; i < haystack.size(); i += 16) {
 224     auto ret = scanHaystackBlock<true>(haystack, needles, i);
 225     if (ret != std::string::npos) {
 226       return ret;
 227     }
 228   }
 229
 230   return std::string::npos;
 231 }
 232
 233 }
 234
 235 }
 236
 237
 238
 239 #endif