summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--absl/strings/ascii.cc62
-rw-r--r--absl/strings/ascii_benchmark.cc4
2 files changed, 61 insertions, 5 deletions
diff --git a/absl/strings/ascii.cc b/absl/strings/ascii.cc
index df905e05..c696a5b1 100644
--- a/absl/strings/ascii.cc
+++ b/absl/strings/ascii.cc
@@ -15,8 +15,10 @@
#include "absl/strings/ascii.h"
#include <climits>
+#include <cstdint>
#include <cstring>
#include <string>
+#include <type_traits>
#include "absl/base/config.h"
#include "absl/base/nullability.h"
@@ -160,6 +162,19 @@ ABSL_DLL const char kToUpper[256] = {
};
// clang-format on
+template <class T>
+static constexpr T BroadcastByte(unsigned char value) {
+ static_assert(std::is_integral<T>::value && sizeof(T) <= sizeof(uint64_t) &&
+ std::is_unsigned<T>::value,
+ "only unsigned integers up to 64-bit allowed");
+ T result = value;
+ constexpr size_t result_bit_width = sizeof(result) * CHAR_BIT;
+ result |= result << ((CHAR_BIT << 0) & (result_bit_width - 1));
+ result |= result << ((CHAR_BIT << 1) & (result_bit_width - 1));
+ result |= result << ((CHAR_BIT << 2) & (result_bit_width - 1));
+ return result;
+}
+
// Returns whether `c` is in the a-z/A-Z range (w.r.t. `ToUpper`).
// Implemented by:
// 1. Pushing the a-z/A-Z range to [SCHAR_MIN, SCHAR_MIN + 26).
@@ -175,8 +190,42 @@ constexpr bool AsciiInAZRange(unsigned char c) {
}
template <bool ToUpper>
-constexpr void AsciiStrCaseFold(absl::Nonnull<char*> p,
- absl::Nonnull<char*> end) {
+static constexpr char* PartialAsciiStrCaseFold(absl::Nonnull<char*> p,
+ absl::Nonnull<char*> end) {
+ using vec_t = size_t;
+ const size_t n = static_cast<size_t>(end - p);
+
+ // SWAR algorithm: http://0x80.pl/notesen/2016-01-06-swar-swap-case.html
+ constexpr char ch_a = ToUpper ? 'a' : 'A', ch_z = ToUpper ? 'z' : 'Z';
+ char* const swar_end = p + (n / sizeof(vec_t)) * sizeof(vec_t);
+ while (p < swar_end) {
+ vec_t v = vec_t();
+
+ // memcpy the vector, but constexpr
+ for (size_t i = 0; i < sizeof(vec_t); ++i) {
+ v |= static_cast<vec_t>(static_cast<unsigned char>(p[i]))
+ << (i * CHAR_BIT);
+ }
+
+ constexpr unsigned int msb = 1u << 7;
+ vec_t a = v + ascii_internal::BroadcastByte<vec_t>(msb - ch_a - 0),
+ z = v + ascii_internal::BroadcastByte<vec_t>(msb - ch_z - 1);
+ v ^= ((a & ~z) & ascii_internal::BroadcastByte<vec_t>(msb)) >> 2;
+
+ // memcpy the vector, but constexpr
+ for (size_t i = 0; i < sizeof(vec_t); ++i) {
+ p[i] = static_cast<char>(v >> (i * CHAR_BIT));
+ }
+
+ p += sizeof(v);
+ }
+
+ return p;
+}
+
+template <bool ToUpper>
+static constexpr void AsciiStrCaseFold(absl::Nonnull<char*> p,
+ absl::Nonnull<char*> end) {
// The upper- and lowercase versions of ASCII characters differ by only 1 bit.
// When we need to flip the case, we can xor with this bit to achieve the
// desired result. Note that the choice of 'a' and 'A' here is arbitrary. We
@@ -184,10 +233,17 @@ constexpr void AsciiStrCaseFold(absl::Nonnull<char*> p,
// have the same single bit difference.
constexpr unsigned char kAsciiCaseBitFlip = 'a' ^ 'A';
- for (; p < end; ++p) {
+ using vec_t = size_t;
+ // TODO(b/316380338): When FDO becomes able to vectorize these,
+ // revert this manual optimization and just leave the naive loop.
+ if (static_cast<size_t>(end - p) >= sizeof(vec_t)) {
+ p = ascii_internal::PartialAsciiStrCaseFold<ToUpper>(p, end);
+ }
+ while (p < end) {
unsigned char v = static_cast<unsigned char>(*p);
v ^= AsciiInAZRange<ToUpper>(v) ? kAsciiCaseBitFlip : 0;
*p = static_cast<char>(v);
+ ++p;
}
}
diff --git a/absl/strings/ascii_benchmark.cc b/absl/strings/ascii_benchmark.cc
index 3aecdb8b..4ae73174 100644
--- a/absl/strings/ascii_benchmark.cc
+++ b/absl/strings/ascii_benchmark.cc
@@ -113,7 +113,7 @@ static void BM_StrToLower(benchmark::State& state) {
BENCHMARK(BM_StrToLower)
->DenseRange(0, 32)
->RangeMultiplier(2)
- ->Range(64, 1 << 20);
+ ->Range(64, 1 << 26);
static void BM_StrToUpper(benchmark::State& state) {
const int size = state.range(0);
@@ -127,6 +127,6 @@ static void BM_StrToUpper(benchmark::State& state) {
BENCHMARK(BM_StrToUpper)
->DenseRange(0, 32)
->RangeMultiplier(2)
- ->Range(64, 1 << 20);
+ ->Range(64, 1 << 26);
} // namespace