diff options
Diffstat (limited to 'absl/strings/internal/fastmem.h')
| -rw-r--r-- | absl/strings/internal/fastmem.h | 215 |
1 files changed, 0 insertions, 215 deletions
diff --git a/absl/strings/internal/fastmem.h b/absl/strings/internal/fastmem.h deleted file mode 100644 index 9989b12e34d3..000000000000 --- a/absl/strings/internal/fastmem.h +++ /dev/null @@ -1,215 +0,0 @@ -// 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_ |