/*
- * Copyright 2013 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
// @author Mark Rabkin (mrabkin@fb.com)
// @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
-#include "folly/Range.h"
+#include <folly/Range.h>
+#if FOLLY_HAVE_EMMINTRIN_H
#include <emmintrin.h> // __v16qi
-#include "folly/Likely.h"
+#endif
+#include <iostream>
namespace folly {
const AsciiCaseSensitive asciiCaseSensitive = AsciiCaseSensitive();
const AsciiCaseInsensitive asciiCaseInsensitive = AsciiCaseInsensitive();
-std::ostream& operator<<(std::ostream& os, const StringPiece& piece) {
+std::ostream& operator<<(std::ostream& os, const StringPiece piece) {
+ os.write(piece.start(), piece.size());
+ return os;
+}
+
+std::ostream& operator<<(std::ostream& os, const MutableStringPiece piece) {
os.write(piece.start(), piece.size());
return os;
}
namespace detail {
-size_t qfind_first_byte_of_memchr(const StringPiece& haystack,
- const StringPiece& needles) {
+size_t qfind_first_byte_of_memchr(const StringPiece haystack,
+ const StringPiece needles) {
size_t best = haystack.size();
for (char needle: needles) {
const void* ptr = memchr(haystack.data(), needle, best);
#define PAGE_FOR(addr) \
(reinterpret_cast<uintptr_t>(addr) / kMinPageSize)
+
+// Earlier versions of GCC (for example, Clang on Mac OS X, which is based on
+// GCC 4.2) do not have a full compliment of SSE builtins.
+#if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
inline size_t nextAlignedIndex(const char* arr) {
- auto firstPossible = reinterpret_cast<uintptr_t>(arr) + 1;
- return 1 + // add 1 because the index starts at 'arr'
- ((firstPossible + 15) & ~0xF) // round up to next multiple of 16
- - firstPossible;
+ auto firstPossible = reinterpret_cast<uintptr_t>(arr) + 1;
+ return 1 + // add 1 because the index starts at 'arr'
+ ((firstPossible + 15) & ~0xF) // round up to next multiple of 16
+ - firstPossible;
}
-#if FOLLY_HAVE_EMMINTRIN_H
// build sse4.2-optimized version even if -msse4.2 is not passed to GCC
-size_t qfind_first_byte_of_needles16(const StringPiece& haystack,
- const StringPiece& needles)
- __attribute__ ((__target__("sse4.2"), noinline));
+size_t qfind_first_byte_of_needles16(const StringPiece haystack,
+ const StringPiece needles)
+ __attribute__ ((__target__("sse4.2"), noinline))
+ FOLLY_DISABLE_ADDRESS_SANITIZER;
// helper method for case where needles.size() <= 16
-size_t qfind_first_byte_of_needles16(const StringPiece& haystack,
- const StringPiece& needles) {
+size_t qfind_first_byte_of_needles16(const StringPiece haystack,
+ const StringPiece needles) {
DCHECK(!haystack.empty());
DCHECK(!needles.empty());
DCHECK_LE(needles.size(), 16);
}
return StringPiece::npos;
}
-#endif // FOLLY_HAVE_EMMINTRIN_H
+#endif // FOLLY_HAVE_EMMINTRIN_H && GCC 4.6+
// Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
// of Computer Algorithms" (1974), but the best description is here:
namespace detail {
-size_t qfind_first_byte_of_byteset(const StringPiece& haystack,
- const StringPiece& needles) {
+size_t qfind_first_byte_of_byteset(const StringPiece haystack,
+ const StringPiece needles) {
FastByteSet s;
for (auto needle: needles) {
s.add(needle);
return StringPiece::npos;
}
-#if FOLLY_HAVE_EMMINTRIN_H
+#if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
template <bool HAYSTACK_ALIGNED>
-inline size_t scanHaystackBlock(const StringPiece& haystack,
- const StringPiece& needles,
- int64_t idx)
+size_t scanHaystackBlock(const StringPiece haystack,
+ const StringPiece needles,
+ int64_t idx)
// inline is okay because it's only called from other sse4.2 functions
- __attribute__ ((__target__("sse4.2")));
+ __attribute__ ((__target__("sse4.2")))
+// Turn off ASAN because the "arr2 = ..." assignment in the loop below reads
+// up to 15 bytes beyond end of the buffer in #needles#. That is ok because
+// ptr2 is always 16-byte aligned, so the read can never span a page boundary.
+// Also, the extra data that may be read is never actually used.
+ FOLLY_DISABLE_ADDRESS_SANITIZER;
// Scans a 16-byte block of haystack (starting at blockStartIdx) to find first
// needle. If HAYSTACK_ALIGNED, then haystack must be 16byte aligned.
// If !HAYSTACK_ALIGNED, then caller must ensure that it is safe to load the
// block.
template <bool HAYSTACK_ALIGNED>
-inline size_t scanHaystackBlock(const StringPiece& haystack,
- const StringPiece& needles,
- int64_t blockStartIdx) {
+size_t scanHaystackBlock(const StringPiece haystack,
+ const StringPiece needles,
+ int64_t blockStartIdx) {
DCHECK_GT(needles.size(), 16); // should handled by *needles16() method
DCHECK(blockStartIdx + 16 <= haystack.size() ||
(PAGE_FOR(haystack.data() + blockStartIdx) ==
return StringPiece::npos;
}
-size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
- const StringPiece& needles)
+size_t qfind_first_byte_of_sse42(const StringPiece haystack,
+ const StringPiece needles)
__attribute__ ((__target__("sse4.2"), noinline));
-size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
- const StringPiece& needles) {
+size_t qfind_first_byte_of_sse42(const StringPiece haystack,
+ const StringPiece needles) {
if (UNLIKELY(needles.empty() || haystack.empty())) {
return StringPiece::npos;
} else if (needles.size() <= 16) {
return StringPiece::npos;
}
-#endif // FOLLY_HAVE_EMMINTRIN_H
+#endif // FOLLY_HAVE_EMMINTRIN_H && GCC 4.6+
-size_t qfind_first_byte_of_nosse(const StringPiece& haystack,
- const StringPiece& needles) {
+size_t qfind_first_byte_of_nosse(const StringPiece haystack,
+ const StringPiece needles) {
if (UNLIKELY(needles.empty() || haystack.empty())) {
return StringPiece::npos;
}
projects / folly.git / blobdiff