2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include "RangeSse42.h"
21 #include <glog/logging.h>
22 #include <folly/Portability.h>
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.
30 // TODO: Maybe this should be done by the build system....
31 #if !FOLLY_SSE_PREREQ(4, 2)
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);
58 #include <emmintrin.h>
59 #include <smmintrin.h>
60 #include <folly/Likely.h>
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
65 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67368
66 #if defined FOLLY_SANITIZE_ADDRESS && \
67 FOLLY_SANITIZE_ADDRESS == 1 && \
69 # define _mm_load_si128(p) (*(p))
70 # define _mm_loadu_si128(p) ((__m128i)__builtin_ia32_loaddqu((const char*)(p)))
77 // It's okay if pages are bigger than this (as powers of two), but they should
79 static constexpr size_t kMinPageSize = 4096;
80 static_assert(kMinPageSize >= 16,
81 "kMinPageSize must be at least SSE register size");
84 static inline uintptr_t page_for(T* addr) {
85 return reinterpret_cast<uintptr_t>(addr) / kMinPageSize;
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
95 static size_t qfind_first_byte_of_needles16(const StringPieceLite haystack,
96 const StringPieceLite needles)
97 FOLLY_DISABLE_ADDRESS_SANITIZER;
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);
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);
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);
137 return std::string::npos;
140 template <bool HAYSTACK_ALIGNED>
141 size_t scanHaystackBlock(const StringPieceLite haystack,
142 const StringPieceLite needles,
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;
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
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)));
164 if (HAYSTACK_ALIGNED) {
165 arr1 = _mm_load_si128(
166 reinterpret_cast<const __m128i*>(haystack.data() + blockStartIdx));
168 arr1 = _mm_loadu_si128(
169 reinterpret_cast<const __m128i*>(haystack.data() + blockStartIdx));
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);
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));
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);
190 return blockStartIdx + b;
192 return std::string::npos;
195 size_t qfind_first_byte_of_sse42(const StringPieceLite haystack,
196 const StringPieceLite needles);
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);
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);
214 return qfind_first_byte_of_byteset(haystack, needles);
217 auto ret = scanHaystackBlock<false>(haystack, needles, 0);
218 if (ret != std::string::npos) {
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) {
230 return std::string::npos;