Merge CRC+memcpy functionality into Extend function. This improves performance through improved instruction level parallelism. We mostly do the copying separately, but in lockstep with the crc streams. We don't reuse the loads between the crc calculation and the copy, since the loads are to different register types, except for VPCLMUL streams. We also force AVX loads and stores for platforms that support them, even if the rest of the binary is built without AVX support. Also explicitly disallow PCLMUL streams on platforms that do not support AVX, so we can split out the AVX instructions to an implementation only for large copies that support AVX (or are not x86). PiperOrigin-RevId: 975556504 Change-Id: Ib2f4f6c339de5259ae83816f4953469a002e9c47
diff --git a/absl/crc/crc32c.cc b/absl/crc/crc32c.cc index 3c5e59b..9020563 100644 --- a/absl/crc/crc32c.cc +++ b/absl/crc/crc32c.cc
@@ -74,7 +74,7 @@ crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count, crc32c_t initial_crc) { return static_cast<crc32c_t>( - crc_internal::Crc32CAndCopy(dest, src, count, initial_crc)); + crc_internal::Crc32CAndCopy(dest, src, count, initial_crc, false)); } // Remove a Suffix of given size from a buffer
diff --git a/absl/crc/internal/crc.cc b/absl/crc/internal/crc.cc index 8019248..ec6a031 100644 --- a/absl/crc/internal/crc.cc +++ b/absl/crc/internal/crc.cc
@@ -43,7 +43,6 @@ #include <cstddef> #include <cstdint> -#include <cstring> #include <iterator> #include "absl/base/internal/endian.h" @@ -291,7 +290,8 @@ // starting at `ptr` and twelve zero bytes, so that four CRCs can be // built incrementally and combined at the end. const auto step_swath = [this](uint32_t crc_in, const std::uint8_t* ptr) { - return absl::little_endian::Load32(ptr) ^ this->table_[3][crc_in & 0xff] ^ + return absl::little_endian::Load32(ptr) ^ + this->table_[3][crc_in & 0xff] ^ this->table_[2][(crc_in >> 8) & 0xff] ^ this->table_[1][(crc_in >> 16) & 0xff] ^ this->table_[0][crc_in >> 24]; @@ -425,12 +425,6 @@ CRC::~CRC() {} CRC::CRC() {} -void CRC::ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const { - std::memcpy(dst, src, length); - Extend(crc, dst, length); -} - // The "constructor" for a CRC32C with a standard polynomial. CRC* CRC::Crc32c() { static CRC* singleton = CRCImpl::NewInternal();
diff --git a/absl/crc/internal/crc.h b/absl/crc/internal/crc.h index 49487c6..90e05f1 100644 --- a/absl/crc/internal/crc.h +++ b/absl/crc/internal/crc.h
@@ -47,11 +47,6 @@ virtual void Extend(uint32_t* crc, const void* bytes, size_t length) const = 0; - // Copy 'length' bytes from 'src' to 'dst' and extend the CRC with the copied - // bytes. - virtual void ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const; - // Equivalent to Extend(crc, bytes, length) where "bytes" // points to an array of "length" zero bytes. virtual void ExtendByZeroes(uint32_t* crc, size_t length) const = 0;
diff --git a/absl/crc/internal/crc32_x86_arm_combined_simd.h b/absl/crc/internal/crc32_x86_arm_combined_simd.h index 3acde80..c50a301 100644 --- a/absl/crc/internal/crc32_x86_arm_combined_simd.h +++ b/absl/crc/internal/crc32_x86_arm_combined_simd.h
@@ -16,11 +16,8 @@ #define ABSL_CRC_INTERNAL_CRC32_X86_ARM_COMBINED_SIMD_H_ #include <array> -#include <cstddef> #include <cstdint> -#include <cstring> -#include "absl/base/attributes.h" #include "absl/base/config.h" #ifdef __SSE4_2__ @@ -58,22 +55,6 @@ #endif -// We try to force AVX instructions so that we can use them when AVX is -// available at runtime even if the translation unit isn't built with AVX -// support. Clang on Windows has gnu::target but does not make AVX types like -// __m256i available when trying to force specific functions to use AVX -// compiles. -#if ABSL_HAVE_CPP_ATTRIBUTE(gnu::target) && !defined(_MSC_VER) && \ - (defined(__x86_64__) || defined(__i386__)) -#define ABSL_INTERNAL_CAN_FORCE_AVX 1 -#endif - -#if defined(ABSL_INTERNAL_CAN_FORCE_AVX) -#define ABSL_INTERNAL_ATTRIBUTE_AVX [[gnu::target("avx")]] -#else -#define ABSL_INTERNAL_ATTRIBUTE_AVX -#endif - namespace absl { ABSL_NAMESPACE_BEGIN namespace crc_internal { @@ -89,13 +70,11 @@ using V128 = __m128i; #endif -#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) +#if defined(__AVX__) using V256 = __m256i; #else // Placeholder for V256 when AVX is not available. -struct alignas(32) V256 { - std::array<uint64_t, 4> val; -}; +using V256 = std::array<uint64_t, 4>; #endif // Starting with the initial value in |crc|, accumulates a CRC32 value for @@ -158,41 +137,17 @@ // Add packed 64-bit integers in |l| and |r|. V128 V128_Add64(const V128 l, const V128 r); -// Performs a store fence on architectures that require it. -void StoreFence(); - -#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) -ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_LoadU(const void* src); -ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_Broadcast128(const V128* src); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreU(void* dst, V256 data); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreNonTemporal(void* dst, - V256 data); +#if defined(__AVX__) +inline V256 V256_LoadU(const V256* src); +inline V256 V256_Broadcast128(const V128* src); #else template <typename T = V256> -T V256_LoadU(const void* src); +T V256_LoadU(const T* src); template <typename T = V256> T V256_Broadcast128(const V128* src); - -template <typename T = V256> -void V256_StoreU(void* dst, const T& data); - -template <typename T = V256> -void V256_StoreNonTemporal(void* dst, const T& data); #endif -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_LoadPairU(const void* src, - V256* v0, V256* v1); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairU(void* dst, V256 v0, - V256 v1); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairNonTemporal(void* dst, - V256 v0, - V256 v1); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairU(void* dst, - const void* src); -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairNonTemporal( - void* dst, const void* src); - #endif #if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) @@ -262,8 +217,6 @@ return _mm_add_epi64(l, r); } -inline void StoreFence() { _mm_sfence(); } - #elif defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) inline uint32_t CRC32_u8(uint32_t crc, uint8_t v) { return __crc32cb(crc, v); } @@ -350,11 +303,12 @@ return V128_Xor(V128_Xor(a, b), c); } -inline V128 V128_From64WithZeroFill(const uint64_t r) { +inline V128 V128_From64WithZeroFill(const uint64_t r){ constexpr uint64x2_t kZero = {0, 0}; return vsetq_lane_u64(r, kZero, 0); } + template <int imm> inline int V128_Extract32(const V128 l) { return vgetq_lane_s32(vreinterpretq_s32_u64(l), imm); @@ -371,36 +325,21 @@ inline V128 V128_Add64(const V128 l, const V128 r) { return vaddq_u64(l, r); } -inline void StoreFence() {} - #endif -#if (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ - defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) -ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_LoadU(const void* src) { - return _mm256_loadu_si256(reinterpret_cast<const __m256i*>(src)); -} +#if defined(__AVX__) && defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) +inline V256 V256_LoadU(const V256* src) { return _mm256_loadu_si256(src); } -ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_Broadcast128(const V128* src) { +inline V256 V256_Broadcast128(const V128* src) { return _mm256_castps_si256( _mm256_broadcast_ps(reinterpret_cast<const __m128*>(src))); } - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreU(void* dst, V256 data) { - _mm256_storeu_si256(reinterpret_cast<__m256i*>(dst), data); -} - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreNonTemporal(void* dst, - V256 data) { - _mm256_stream_si256(reinterpret_cast<__m256i*>(dst), data); -} #elif defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) || \ defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) template <typename T> -inline T V256_LoadU(const void* src) { - T res; - std::memcpy(&res, src, sizeof(T)); - return res; +inline T V256_LoadU(const T* src) { + (void)src; + return T{}; } template <typename T> @@ -408,60 +347,8 @@ (void)src; return T{}; } - -template <typename T> -inline void V256_StoreU(void* dst, const T& data) { - std::memcpy(dst, &data, sizeof(T)); -} - -template <typename T> -inline void V256_StoreNonTemporal(void* dst, const T& data) { - std::memcpy(dst, &data, sizeof(T)); -} #endif -#if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || \ - defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_LoadPairU(const void* src, - V256* v0, V256* v1) { - const char* src_ptr = reinterpret_cast<const char*>(src); - *v0 = V256_LoadU(src_ptr); - *v1 = V256_LoadU(src_ptr + sizeof(V256)); -} - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairU(void* dst, V256 v0, - V256 v1) { - char* dst_ptr = reinterpret_cast<char*>(dst); - V256_StoreU(dst_ptr, v0); - V256_StoreU(dst_ptr + sizeof(V256), v1); -} - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairNonTemporal(void* dst, - V256 v0, - V256 v1) { - char* dst_ptr = reinterpret_cast<char*>(dst); - V256_StoreNonTemporal(dst_ptr, v0); - V256_StoreNonTemporal(dst_ptr + sizeof(V256), v1); -} - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairU(void* dst, - const void* src) { - V256 v0, v1; - V256_LoadPairU(src, &v0, &v1); - V256_StorePairU(dst, v0, v1); -} - -ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairNonTemporal( - void* dst, const void* src) { - V256 v0, v1; - V256_LoadPairU(src, &v0, &v1); - V256_StorePairNonTemporal(dst, v0, v1); -} - -#endif // defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || - // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) - } // namespace crc_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/crc/internal/crc_memcpy.h b/absl/crc/internal/crc_memcpy.h index 72d7ce4..a0fed65 100644 --- a/absl/crc/internal/crc_memcpy.h +++ b/absl/crc/internal/crc_memcpy.h
@@ -16,12 +16,10 @@ #define ABSL_CRC_INTERNAL_CRC_MEMCPY_H_ #include <cstddef> -#include <cstdint> #include <memory> #include "absl/base/config.h" #include "absl/crc/crc32c.h" -#include "absl/crc/internal/crc.h" #include "absl/crc/internal/crc32_x86_arm_combined_simd.h" // Defined if the class AcceleratedCrcMemcpyEngine exists. @@ -52,12 +50,11 @@ public: static crc32c_t CrcAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}) { - uint32_t crc = static_cast<uint32_t>(initial_crc); - crc ^= 0xffffffffU; - CRC::Crc32c()->ExtendAndCopy(&crc, dst, src, length); - crc ^= 0xffffffffU; - return crc32c_t{crc}; + crc32c_t initial_crc = crc32c_t{0}, + bool non_temporal = false) { + static const ArchSpecificEngines engines = GetArchSpecificEngines(); + auto* engine = non_temporal ? engines.non_temporal : engines.temporal; + return engine->Compute(dst, src, length, initial_crc); } // For testing only: get an architecture-specific engine for tests. @@ -113,8 +110,9 @@ // the generic fallback version. inline crc32c_t Crc32CAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}) { - return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc); + crc32c_t initial_crc = crc32c_t{0}, + bool non_temporal = false) { + return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc, non_temporal); } } // namespace crc_internal
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index eb93e57..edffd36 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -16,7 +16,6 @@ #include <cstddef> #include <cstdint> -#include <cstring> #include <memory> #include <vector> @@ -218,7 +217,6 @@ }; enum class PclmulStreamType { - NONE, PCLMUL, VPCLMUL, NEON_PCLMUL, @@ -230,12 +228,6 @@ class CRC32AcceleratedX86ARMCombinedMultipleStreamsBase : public CRC32AcceleratedX86ARMCombined { protected: - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE static void - Copy64Bytes(char* dst, const uint8_t* src) { - PrefetchToLocalCache(reinterpret_cast<const char*>(src) + kPrefetchHorizon); - V256_CopyPairU(dst, src); - } - // Update partialCRC with crc of 64 byte block. Calling FinalizePclmulStream // would produce a single crc checksum, but it is expensive. PCLMULQDQ has a // high latency, so we run 4 128-bit partial checksums that can be reduced to @@ -247,7 +239,7 @@ #if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) template <bool kUseEor3 = false> ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul( - V256 v0, V256 v1, V128* partialCRC) const { + const uint8_t* p, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -260,12 +252,10 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); - const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); - V128 data1 = data_ptr0[0]; - V128 data2 = data_ptr0[1]; - V128 data3 = data_ptr1[0]; - V128 data4 = data_ptr1[1]; + V128 data1 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 0)); + V128 data2 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 1)); + V128 data3 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 2)); + V128 data4 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 3)); partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -318,16 +308,15 @@ return crc; } - template <bool copy_data = false> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(V256, V256, + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(const uint8_t*, V128*) const {} ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128*) const { return 0; } #else - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void - Process64BytesPclmul(V256 v0, V256 v1, V128* partialCRC) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul( + const uint8_t* p, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -340,12 +329,10 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); - const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); - V128 data1 = data_ptr0[0]; - V128 data2 = data_ptr0[1]; - V128 data3 = data_ptr1[0]; - V128 data4 = data_ptr1[1]; + V128 data1 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 0)); + V128 data2 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 1)); + V128 data3 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 2)); + V128 data4 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 3)); partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -366,7 +353,7 @@ // Reduce partialCRC produced by Process64BytesPclmul into a single value, // that represents crc checksum of all the processed bytes. - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { V128 partialCRC1 = partialCRC[0]; V128 partialCRC2 = partialCRC[1]; @@ -405,12 +392,11 @@ } template <bool kUseEor3 = false> - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void - Process64BytesNeonPclmul(V256, V256, V128*) const {} + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul(const uint8_t*, + V128*) const {} template <bool kUseEor3 = false> - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t - FinalizeNeonPclmulStream(V128*) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeNeonPclmulStream(V128*) const { return 0; } #endif @@ -466,8 +452,7 @@ crc[2] = crc2; } -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ - (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ (!defined(_MSC_VER) || defined(__clang__)) // This is only used if we have vector version of PCLMULQDQ. // We don't have it on arm, and it isn't supported by default @@ -476,7 +461,7 @@ // with new and default flags or use inline asm. // The code below is the same as FinalizePclmulStream, but with // PCLMUL and XOR operating on 2 values in a vector at the same time. - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeVpclmulStream(V256* partialCRC) const { uint64_t crc = 0; uint64_t low64, high64; @@ -507,9 +492,8 @@ return crc; } - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void - Process64BytesVpclmul(V256 v0, V256 v1, V256* vpartialCRC, - V256 loopMultiplicands) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul( + const uint8_t* p, V256* vpartialCRC, V256 loopMultiplicands) const { __asm__ volatile( "vpclmulqdq $0x11, %3, %0, %%ymm0 \n" "vpclmulqdq $0x11, %3, %1, %%ymm1 \n" @@ -517,23 +501,23 @@ "vpclmulqdq $0x00, %3, %1, %1 \n" "vpxor %%ymm0, %0, %0 \n" "vpxor %%ymm1, %1, %1 \n" - "vpxor %2, %0, %0 \n" - "vpxor %4, %1, %1 \n" + "vpxor (%2), %0, %0 \n" + "vpxor 32(%2), %1, %1 \n" : "+x"(vpartialCRC[0]), "+x"(vpartialCRC[1]) - : "x"(v0), "x"(loopMultiplicands), "x"(v1) + : "r"(p), "x"(loopMultiplicands) : "ymm0", "ymm1"); } #else template <typename T = V256> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(T, T, T*, T) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(const uint8_t*, T*, + T) const { static_assert(sizeof(T) == 0, "Vector PCLMUL not supported"); } ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeVpclmulStream(V256*) const { return 0; } -#endif // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && (defined(__AVX__) || - // defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && (!defined(_MSC_VER) || - // defined(__clang__)) +#endif // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && + // (!defined(_MSC_VER) || defined(__clang__)) // Constants generated by './scripts/gen-crc-consts.py x86_pclmul // crc32_lsb_0x82f63b78' from the Linux kernel. @@ -567,54 +551,24 @@ PclmulStreamType pclmul_stream_type> class CRC32AcceleratedX86ARMCombinedMultipleStreams : public CRC32AcceleratedX86ARMCombinedMultipleStreamsBase { - public: + ABSL_ATTRIBUTE_HOT void Extend(uint32_t* crc, const void* bytes, const size_t length) const override { - Extend<false>(crc, bytes, length); - } - - void ExtendAndCopy(uint32_t* crc, void* __restrict dst, - const void* __restrict src, size_t length) const override { - Extend<true>(crc, src, length, dst); - StoreFence(); - } - - template <bool copy = false> - ABSL_ATTRIBUTE_HOT void Extend(uint32_t* crc, const void* bytes, - const size_t length, - void* __restrict dst = nullptr) const { - if constexpr (pclmul_stream_type != PclmulStreamType::NONE) { - if (length >= kMediumCutoff) { - ExtendWithPclmul<copy>(crc, bytes, length, dst); - return; - } - } - ExtendWithoutPclmul<copy>(crc, bytes, length, dst); - } - - template <bool copy = false> - ABSL_ATTRIBUTE_HOT void ExtendWithoutPclmul( - uint32_t* crc, const void* bytes, const size_t length, - void* __restrict dst = nullptr) const { static_assert(num_crc_streams >= 1 && num_crc_streams <= kMaxStreams, "Invalid number of crc streams"); static_assert(num_pclmul_streams >= 0 && num_pclmul_streams <= kMaxStreams, "Invalid number of pclmul streams"); const uint8_t* p = static_cast<const uint8_t*>(bytes); const uint8_t* e = p + length; - char* d = static_cast<char*>(dst); uint32_t l = *crc; uint64_t l64; - if constexpr (copy) { - std::memcpy(d, p, length); - } // For small blocks just run simple loop, because cost of combining multiple // streams is significant. if (num_crc_streams > 1 && (length < kSmallCutoff)) { // fallthrough; Use the same strategy as we do for processing the // remaining bytes after any other strategy. - } else { + } else if (length < kMediumCutoff) { // For medium blocks we run 3 crc streams and combine them as described in // Intel paper above. Running 4th stream doesn't help, because crc // instruction has latency 3 and throughput 1. @@ -667,162 +621,39 @@ } } l = static_cast<uint32_t>(l64); - } - - uint64_t remaining_bytes = static_cast<uint64_t>(e - p); - // Process the remaining bytes. - while ((e - p) >= 16) { - ABSL_INTERNAL_STEP8(l, p); - ABSL_INTERNAL_STEP8(l, p); - } - - if (remaining_bytes & 8) { - ABSL_INTERNAL_STEP8(l, p); - } - if (remaining_bytes & 4) { - ABSL_INTERNAL_STEP4(l, p); - } - if (remaining_bytes & 2) { - ABSL_INTERNAL_STEP2(l, p); - } - if (remaining_bytes & 1) { - ABSL_INTERNAL_STEP1(l, p); - } - - *crc = l; - } - - template <bool copy = false> - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_HOT void ExtendWithPclmul( - uint32_t* crc, const void* bytes, const size_t length, - void* __restrict dst = nullptr) const { - static_assert(num_crc_streams >= 1 && num_crc_streams <= kMaxStreams, - "Invalid number of crc streams"); - static_assert(num_pclmul_streams >= 0 && num_pclmul_streams <= kMaxStreams, - "Invalid number of pclmul streams"); - const uint8_t* p = static_cast<const uint8_t*>(bytes); - const uint8_t* e = p + length; - char* d = static_cast<char*>(dst); - uint32_t l = *crc; - uint64_t l64; - - if constexpr (copy) { - // Align destination pointer for V256 non-temporal stores. - constexpr size_t kAlignment = 64; - uintptr_t dst_addr = reinterpret_cast<uintptr_t>(d); - size_t bytes_to_align = - (kAlignment - (dst_addr & (kAlignment - 1))) & (kAlignment - 1); - std::memcpy(d, p, bytes_to_align); - d += bytes_to_align; - while (bytes_to_align >= 8) { - ABSL_INTERNAL_STEP8(l, p); - bytes_to_align -= 8; - } - while (bytes_to_align > 0) { - ABSL_INTERNAL_STEP1(l, p); - bytes_to_align -= 1; - } } else { + // There is a lot of data, we can ignore combine costs and run all + // requested streams (num_crc_streams + num_pclmul_streams), + // using prefetch. CRC and PCLMULQDQ use different cpu execution units, + // so on some cpus it makes sense to execute both of them for different + // streams. + // Point x at first 8-byte aligned byte in string. const uint8_t* x = RoundUp<8>(p); // Process bytes until p is 8-byte aligned, if that isn't past the end. while (p != x) { ABSL_INTERNAL_STEP1(l, p); } - } - size_t bs = static_cast<size_t>(e - p) / - (num_crc_streams + num_pclmul_streams) / 64; - const uint8_t* stream_start = p; - const uint8_t* crc_streams[kMaxStreams]; - for (size_t i = 0; i < num_crc_streams; i++) { - crc_streams[i] = stream_start; - stream_start += bs * 64; - } - const uint8_t* pclmul_streams[kMaxStreams]; - for (size_t i = 0; i < num_pclmul_streams; i++) { - pclmul_streams[i] = stream_start; - stream_start += bs * 64; - } - - uint8_t* dst_crc_streams[kMaxStreams]; - uint8_t* dst_pclmul_streams[kMaxStreams]; - if constexpr (copy) { - uint8_t* dst_stream_start = reinterpret_cast<uint8_t*>(d); + size_t bs = static_cast<size_t>(e - p) / + (num_crc_streams + num_pclmul_streams) / 64; + const uint8_t* stream_start = p; + const uint8_t* crc_streams[kMaxStreams]; for (size_t i = 0; i < num_crc_streams; i++) { - dst_crc_streams[i] = dst_stream_start; - dst_stream_start += bs * 64; + crc_streams[i] = stream_start; + stream_start += bs * 64; } + const uint8_t* pclmul_streams[kMaxStreams]; for (size_t i = 0; i < num_pclmul_streams; i++) { - dst_pclmul_streams[i] = dst_stream_start; - dst_stream_start += bs * 64; - } - } - - // Per stream crc sums. - uint64_t l64_crc[kMaxStreams] = {l}; - uint64_t l64_pclmul[kMaxStreams] = {0}; - - V256 pclmul_v0_0[kMaxStreams]; - V256 pclmul_v1_0[kMaxStreams]; - for (size_t j = 0; j < num_pclmul_streams; j++) { - V256_LoadPairU(pclmul_streams[j], &pclmul_v0_0[j], &pclmul_v1_0[j]); - } - - if constexpr (copy) { - for (size_t j = 0; j < num_crc_streams; j++) { - V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j]); - dst_crc_streams[j] += 64; - } - for (size_t j = 0; j < num_pclmul_streams; j++) { - V256_StorePairNonTemporal(dst_pclmul_streams[j], pclmul_v0_0[j], - pclmul_v1_0[j]); - dst_pclmul_streams[j] += 64; - } - } - - if (num_crc_streams == 1) { - l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); - crc_streams[0] += 16 * 4; - } else if (num_crc_streams == 2) { - Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - } else { - Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], crc_streams[2], - l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - crc_streams[2] += 16 * 4; - } - - // Align to 32 bytes for vpclmul implementation. - alignas(32) V128 partialCRC[kMaxStreams][4]; - for (size_t i = 0; i < num_pclmul_streams; i++) { - InitPclmulStream(pclmul_v0_0[i], pclmul_v1_0[i], partialCRC[i]); - pclmul_streams[i] += 64; - } - - for (size_t i = 1; i < bs; i++) { - // Prefetch data for next iterations. - for (size_t j = 0; j < num_crc_streams; j++) { - PrefetchToLocalCache(crc_streams[j] + kPrefetchHorizon); - } - for (size_t j = 0; j < num_pclmul_streams; j++) { - PrefetchToLocalCache(pclmul_streams[j] + kPrefetchHorizon); + pclmul_streams[i] = stream_start; + stream_start += bs * 64; } - for (size_t j = 0; j < num_pclmul_streams; j++) { - if constexpr (copy) { - ProcessPclmulStream<true>(pclmul_streams[j], dst_pclmul_streams[j], - partialCRC[j]); - dst_pclmul_streams[j] += 64; - } else { - ProcessPclmulStream<false>(pclmul_streams[j], nullptr, partialCRC[j]); - } - pclmul_streams[j] += 64; - } + // Per stream crc sums. + uint64_t l64_crc[kMaxStreams] = {l}; + uint64_t l64_pclmul[kMaxStreams] = {0}; + // Peel first iteration, because PCLMULQDQ stream, needs setup. if (num_crc_streams == 1) { l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); crc_streams[0] += 16 * 4; @@ -837,51 +668,81 @@ crc_streams[1] += 16 * 4; crc_streams[2] += 16 * 4; } - if constexpr (copy) { + + // Align to 32 bytes for vpclmul implementation. + alignas(32) V128 partialCRC[kMaxStreams][4]; + for (size_t i = 0; i < num_pclmul_streams; i++) { + InitPclmulStream(&pclmul_streams[i], partialCRC[i]); + } + + for (size_t i = 1; i < bs; i++) { + // Prefetch data for next iterations. for (size_t j = 0; j < num_crc_streams; j++) { - V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j] - 64); - dst_crc_streams[j] += 64; + PrefetchToLocalCache( + reinterpret_cast<const char*>(crc_streams[j] + kPrefetchHorizon)); + } + for (size_t j = 0; j < num_pclmul_streams; j++) { + PrefetchToLocalCache(reinterpret_cast<const char*>(pclmul_streams[j] + + kPrefetchHorizon)); + } + + // We process each stream in 64 byte blocks. This can be written as + // for (int i = 0; i < num_pclmul_streams; i++) { + // Process64BytesPclmul(pclmul_streams[i], partialCRC[i]); + // pclmul_streams[i] += 16 * 4; + // } + // for (int i = 0; i < num_crc_streams; i++) { + // l64_crc[i] = Process64BytesCRC(crc_streams[i], l64_crc[i]); + // crc_streams[i] += 16*4; + // } + // But unrolling and interleaving PCLMULQDQ and CRC blocks manually + // gives ~2% performance boost. + if (num_crc_streams == 1) { + l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); + crc_streams[0] += 16 * 4; + } else if (num_crc_streams == 2) { + Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + } else { + Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], + crc_streams[2], l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + crc_streams[2] += 16 * 4; + } + for (size_t j = 0; j < num_pclmul_streams; j++) { + ProcessPclmulStream(&pclmul_streams[j], partialCRC[j]); } } - } - // PCLMULQDQ based streams require special final step; - // CRC based don't. - for (size_t i = 0; i < num_pclmul_streams; i++) { - l64_pclmul[i] = FinalizePclmulStream(partialCRC[i]); - } - - // Combine all streams into single result. - static_assert(64 % (1 << kNumDroppedBits) == 0); - uint32_t magic = ComputeZeroConstant(bs * 64); - l64 = l64_crc[0]; - for (size_t i = 1; i < num_crc_streams; i++) { - l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); - l64 ^= l64_crc[i]; - } - for (size_t i = 0; i < num_pclmul_streams; i++) { - l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); - l64 ^= l64_pclmul[i]; - } - - // Update p and d. - if constexpr (num_pclmul_streams > 0) { - p = pclmul_streams[num_pclmul_streams - 1]; - if constexpr (copy) { - d = reinterpret_cast<char*>(dst_pclmul_streams[num_pclmul_streams - 1]); - size_t remaining_to_copy = static_cast<size_t>(e - p); - std::memcpy(d, p, remaining_to_copy); + // PCLMULQDQ based streams require special final step; + // CRC based don't. + for (size_t i = 0; i < num_pclmul_streams; i++) { + l64_pclmul[i] = FinalizePclmulStream(partialCRC[i]); } - } else { - p = crc_streams[num_crc_streams - 1]; - if constexpr (copy) { - d = reinterpret_cast<char*>(dst_crc_streams[num_crc_streams - 1]); - size_t remaining_to_copy = static_cast<size_t>(e - p); - std::memcpy(d, p, remaining_to_copy); - } - } - l = static_cast<uint32_t>(l64); + // Combine all streams into single result. + static_assert(64 % (1 << kNumDroppedBits) == 0); + uint32_t magic = ComputeZeroConstant(bs * 64); + l64 = l64_crc[0]; + for (size_t i = 1; i < num_crc_streams; i++) { + l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); + l64 ^= l64_crc[i]; + } + for (size_t i = 0; i < num_pclmul_streams; i++) { + l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); + l64 ^= l64_pclmul[i]; + } + + // Update p. + if constexpr (num_pclmul_streams > 0) { + p = pclmul_streams[num_pclmul_streams - 1]; + } else { + p = crc_streams[num_crc_streams - 1]; + } + l = static_cast<uint32_t>(l64); + } uint64_t remaining_bytes = static_cast<uint64_t>(e - p); // Process the remaining bytes. @@ -907,60 +768,49 @@ } private: - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void - InitPclmulStream(V256 v0, V256 v1, V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { - return; - } else if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + ABSL_ATTRIBUTE_ALWAYS_INLINE void InitPclmulStream( + const uint8_t** pclmul_stream, V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { V256* vpartialCRC = reinterpret_cast<V256*>(partialCRC); - vpartialCRC[0] = v0; - vpartialCRC[1] = v1; + vpartialCRC[0] = + V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 0)); + vpartialCRC[1] = + V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 1)); } else { - const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); - const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); - partialCRC[0] = data_ptr0[0]; - partialCRC[1] = data_ptr0[1]; - partialCRC[2] = data_ptr1[0]; - partialCRC[3] = data_ptr1[1]; + partialCRC[0] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 0)); + partialCRC[1] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 1)); + partialCRC[2] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 2)); + partialCRC[3] = + V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 3)); } + *pclmul_stream += 16 * 4; } - template <bool copy = false> - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void - ProcessPclmulStream(const uint8_t* stream, uint8_t* dst_stream, - V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { - return; + ABSL_ATTRIBUTE_ALWAYS_INLINE void ProcessPclmulStream( + const uint8_t** pclmul_stream, V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + V256 loopMultiplicands = + V256_Broadcast128(reinterpret_cast<const V128*>(kFoldAcross512Bits)); + Process64BytesVpclmul(*pclmul_stream, reinterpret_cast<V256*>(partialCRC), + loopMultiplicands); + } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL || + pclmul_stream_type == + PclmulStreamType::NEON_PCLMUL_EOR3) { + constexpr bool kUseEor3 = + (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL_EOR3); + Process64BytesNeonPclmul<kUseEor3>(*pclmul_stream, partialCRC); } else { - const uint8_t* src_ptr = stream; - V256 v0, v1; - V256_LoadPairU(src_ptr, &v0, &v1); - if constexpr (copy) { - V256_StorePairNonTemporal(dst_stream, v0, v1); - } - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { - V256 loopMultiplicands = V256_Broadcast128( - reinterpret_cast<const V128*>(kFoldAcross512Bits)); - Process64BytesVpclmul(v0, v1, reinterpret_cast<V256*>(partialCRC), - loopMultiplicands); - } else if constexpr (pclmul_stream_type == - PclmulStreamType::NEON_PCLMUL || - pclmul_stream_type == - PclmulStreamType::NEON_PCLMUL_EOR3) { - constexpr bool kUseEor3 = - (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL_EOR3); - Process64BytesNeonPclmul<kUseEor3>(v0, v1, partialCRC); - } else { - Process64BytesPclmul(v0, v1, partialCRC); - } + Process64BytesPclmul(*pclmul_stream, partialCRC); } + *pclmul_stream += 16 * 4; } - ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { - return 0; - } else if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { return FinalizeVpclmulStream(reinterpret_cast<V256*>(partialCRC)); } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL || pclmul_stream_type == @@ -999,8 +849,7 @@ case CpuType::kAmdMilan: case CpuType::kAmdGenoa: case CpuType::kAmdTurin: -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ - (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ (!defined(_MSC_VER) || defined(__clang__)) // We don't have vector pclmul on arm, but this still needs to // compile. @@ -1026,7 +875,7 @@ case CpuType::kIntelSandybridge: case CpuType::kIntelWestmere: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::NONE>(); + 3, 0, PclmulStreamType::PCLMUL>(); case CpuType::kArmNeoverseN1: case CpuType::kArmNeoverseV1: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< @@ -1056,7 +905,7 @@ default: // Something else, play it safe and assume slow PCLMULQDQ. return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::NONE>(); + 3, 0, PclmulStreamType::PCLMUL>(); #endif } }