summaryrefslogtreecommitdiff
path: root/absl/strings/internal/fastmem.h
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings/internal/fastmem.h')
-rw-r--r--absl/strings/internal/fastmem.h215
1 files changed, 215 insertions, 0 deletions
diff --git a/absl/strings/internal/fastmem.h b/absl/strings/internal/fastmem.h
new file mode 100644
index 00000000..9989b12e
--- /dev/null
+++ b/absl/strings/internal/fastmem.h
@@ -0,0 +1,215 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Fast memory copying and comparison routines.
+// strings::fastmemcmp_inlined() replaces memcmp()
+// strings::memcpy_inlined() replaces memcpy()
+// strings::memeq(a, b, n) replaces memcmp(a, b, n) == 0
+//
+// strings::*_inlined() routines are inline versions of the
+// routines exported by this module. Sometimes using the inlined
+// versions is faster. Measure before using the inlined versions.
+//
+
+#ifndef ABSL_STRINGS_INTERNAL_FASTMEM_H_
+#define ABSL_STRINGS_INTERNAL_FASTMEM_H_
+
+#ifdef __SSE4_1__
+#include <immintrin.h>
+#endif
+#include <cstddef>
+#include <cstdint>
+#include <cstdio>
+#include <cstring>
+
+#include "absl/base/internal/unaligned_access.h"
+#include "absl/base/macros.h"
+#include "absl/base/port.h"
+
+namespace absl {
+namespace strings_internal {
+
+// Return true if the n bytes at a equal the n bytes at b.
+// The regions are allowed to overlap.
+//
+// The performance is similar to the performance of memcmp(), but faster for
+// moderately-sized inputs, or inputs that share a common prefix and differ
+// somewhere in their last 8 bytes. Further optimizations can be added later
+// if it makes sense to do so. Alternatively, if the compiler & runtime improve
+// to eliminate the need for this, we can remove it.
+inline bool memeq(const char* a, const char* b, size_t n) {
+ size_t n_rounded_down = n & ~static_cast<size_t>(7);
+ if (ABSL_PREDICT_FALSE(n_rounded_down == 0)) { // n <= 7
+ return memcmp(a, b, n) == 0;
+ }
+ // n >= 8
+ {
+ uint64_t u =
+ ABSL_INTERNAL_UNALIGNED_LOAD64(a) ^ ABSL_INTERNAL_UNALIGNED_LOAD64(b);
+ uint64_t v = ABSL_INTERNAL_UNALIGNED_LOAD64(a + n - 8) ^
+ ABSL_INTERNAL_UNALIGNED_LOAD64(b + n - 8);
+ if ((u | v) != 0) { // The first or last 8 bytes differ.
+ return false;
+ }
+ }
+ // The next line forces n to be a multiple of 8.
+ n = n_rounded_down;
+ if (n >= 80) {
+ // In 2013 or later, this should be fast on long strings.
+ return memcmp(a, b, n) == 0;
+ }
+ // Now force n to be a multiple of 16. Arguably, a "switch" would be smart
+ // here, but there's a difficult-to-evaluate code size vs. speed issue. The
+ // current approach often re-compares some bytes (worst case is if n initially
+ // was 16, 32, 48, or 64), but is fairly short.
+ size_t e = n & 8;
+ a += e;
+ b += e;
+ n -= e;
+ // n is now in {0, 16, 32, ...}. Process 0 or more 16-byte chunks.
+ while (n > 0) {
+#ifdef __SSE4_1__
+ __m128i u =
+ _mm_xor_si128(_mm_loadu_si128(reinterpret_cast<const __m128i*>(a)),
+ _mm_loadu_si128(reinterpret_cast<const __m128i*>(b)));
+ if (!_mm_test_all_zeros(u, u)) {
+ return false;
+ }
+#else
+ uint64_t x =
+ ABSL_INTERNAL_UNALIGNED_LOAD64(a) ^ ABSL_INTERNAL_UNALIGNED_LOAD64(b);
+ uint64_t y = ABSL_INTERNAL_UNALIGNED_LOAD64(a + 8) ^
+ ABSL_INTERNAL_UNALIGNED_LOAD64(b + 8);
+ if ((x | y) != 0) {
+ return false;
+ }
+#endif
+ a += 16;
+ b += 16;
+ n -= 16;
+ }
+ return true;
+}
+
+inline int fastmemcmp_inlined(const void* va, const void* vb, size_t n) {
+ const unsigned char* pa = static_cast<const unsigned char*>(va);
+ const unsigned char* pb = static_cast<const unsigned char*>(vb);
+ switch (n) {
+ default:
+ return memcmp(va, vb, n);
+ case 7:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 6:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 5:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 4:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 3:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 2:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ++pa;
+ ++pb;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 1:
+ if (*pa != *pb) return *pa < *pb ? -1 : +1;
+ ABSL_FALLTHROUGH_INTENDED;
+ case 0:
+ break;
+ }
+ return 0;
+}
+
+// The standard memcpy operation is slow for variable small sizes.
+// This implementation inlines the optimal realization for sizes 1 to 16.
+// To avoid code bloat don't use it in case of not performance-critical spots,
+// nor when you don't expect very frequent values of size <= 16.
+inline void memcpy_inlined(char* dst, const char* src, size_t size) {
+ // Compiler inlines code with minimal amount of data movement when third
+ // parameter of memcpy is a constant.
+ switch (size) {
+ case 1:
+ memcpy(dst, src, 1);
+ break;
+ case 2:
+ memcpy(dst, src, 2);
+ break;
+ case 3:
+ memcpy(dst, src, 3);
+ break;
+ case 4:
+ memcpy(dst, src, 4);
+ break;
+ case 5:
+ memcpy(dst, src, 5);
+ break;
+ case 6:
+ memcpy(dst, src, 6);
+ break;
+ case 7:
+ memcpy(dst, src, 7);
+ break;
+ case 8:
+ memcpy(dst, src, 8);
+ break;
+ case 9:
+ memcpy(dst, src, 9);
+ break;
+ case 10:
+ memcpy(dst, src, 10);
+ break;
+ case 11:
+ memcpy(dst, src, 11);
+ break;
+ case 12:
+ memcpy(dst, src, 12);
+ break;
+ case 13:
+ memcpy(dst, src, 13);
+ break;
+ case 14:
+ memcpy(dst, src, 14);
+ break;
+ case 15:
+ memcpy(dst, src, 15);
+ break;
+ case 16:
+ memcpy(dst, src, 16);
+ break;
+ default:
+ memcpy(dst, src, size);
+ break;
+ }
+}
+
+} // namespace strings_internal
+} // namespace absl
+
+#endif // ABSL_STRINGS_INTERNAL_FASTMEM_H_
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-31 14:42:23 +0000