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: 975239746 Change-Id: I40610e23dc81045f0511e08f39ce11dfe4447804
diff --git a/absl/crc/crc32c.cc b/absl/crc/crc32c.cc index 9020563..3c5e59b 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, false)); + crc_internal::Crc32CAndCopy(dest, src, count, initial_crc)); } // Remove a Suffix of given size from a buffer
diff --git a/absl/crc/internal/crc.cc b/absl/crc/internal/crc.cc index ec6a031..8019248 100644 --- a/absl/crc/internal/crc.cc +++ b/absl/crc/internal/crc.cc
@@ -43,6 +43,7 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <iterator> #include "absl/base/internal/endian.h" @@ -290,8 +291,7 @@ // 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,6 +425,12 @@ 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 90e05f1..49487c6 100644 --- a/absl/crc/internal/crc.h +++ b/absl/crc/internal/crc.h
@@ -47,6 +47,11 @@ 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 c50a301..3acde80 100644 --- a/absl/crc/internal/crc32_x86_arm_combined_simd.h +++ b/absl/crc/internal/crc32_x86_arm_combined_simd.h
@@ -16,8 +16,11 @@ #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__ @@ -55,6 +58,22 @@ #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 { @@ -70,11 +89,13 @@ using V128 = __m128i; #endif -#if defined(__AVX__) +#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) using V256 = __m256i; #else // Placeholder for V256 when AVX is not available. -using V256 = std::array<uint64_t, 4>; +struct alignas(32) V256 { + std::array<uint64_t, 4> val; +}; #endif // Starting with the initial value in |crc|, accumulates a CRC32 value for @@ -137,17 +158,41 @@ // Add packed 64-bit integers in |l| and |r|. V128 V128_Add64(const V128 l, const V128 r); -#if defined(__AVX__) -inline V256 V256_LoadU(const V256* src); -inline V256 V256_Broadcast128(const V128* src); +// 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); #else template <typename T = V256> -T V256_LoadU(const T* src); +T V256_LoadU(const void* 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) @@ -217,6 +262,8 @@ 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); } @@ -303,12 +350,11 @@ 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); @@ -325,21 +371,36 @@ inline V128 V128_Add64(const V128 l, const V128 r) { return vaddq_u64(l, r); } +inline void StoreFence() {} + #endif -#if defined(__AVX__) && defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) -inline V256 V256_LoadU(const V256* src) { return _mm256_loadu_si256(src); } +#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)); +} -inline V256 V256_Broadcast128(const V128* src) { +ABSL_INTERNAL_ATTRIBUTE_AVX 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 T* src) { - (void)src; - return T{}; +inline T V256_LoadU(const void* src) { + T res; + std::memcpy(&res, src, sizeof(T)); + return res; } template <typename T> @@ -347,8 +408,60 @@ (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 a0fed65..72d7ce4 100644 --- a/absl/crc/internal/crc_memcpy.h +++ b/absl/crc/internal/crc_memcpy.h
@@ -16,10 +16,12 @@ #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. @@ -50,11 +52,12 @@ public: static crc32c_t CrcAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - 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); + 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}; } // For testing only: get an architecture-specific engine for tests. @@ -110,9 +113,8 @@ // 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}, - bool non_temporal = false) { - return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc, non_temporal); + crc32c_t initial_crc = crc32c_t{0}) { + return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc); } } // namespace crc_internal
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index edffd36..eb93e57 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -16,6 +16,7 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <memory> #include <vector> @@ -217,6 +218,7 @@ }; enum class PclmulStreamType { + NONE, PCLMUL, VPCLMUL, NEON_PCLMUL, @@ -228,6 +230,12 @@ 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 @@ -239,7 +247,7 @@ #if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) template <bool kUseEor3 = false> ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul( - const uint8_t* p, V128* partialCRC) const { + V256 v0, V256 v1, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -252,10 +260,12 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - 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)); + 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]; partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -308,15 +318,16 @@ return crc; } - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(const uint8_t*, + template <bool copy_data = false> + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(V256, V256, V128*) const {} ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128*) const { return 0; } #else - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul( - const uint8_t* p, V128* partialCRC) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesPclmul(V256 v0, V256 v1, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -329,10 +340,12 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - 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)); + 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]; partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -353,7 +366,7 @@ // Reduce partialCRC produced by Process64BytesPclmul into a single value, // that represents crc checksum of all the processed bytes. - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { V128 partialCRC1 = partialCRC[0]; V128 partialCRC2 = partialCRC[1]; @@ -392,11 +405,12 @@ } template <bool kUseEor3 = false> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul(const uint8_t*, - V128*) const {} + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesNeonPclmul(V256, V256, V128*) const {} template <bool kUseEor3 = false> - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeNeonPclmulStream(V128*) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + FinalizeNeonPclmulStream(V128*) const { return 0; } #endif @@ -452,7 +466,8 @@ crc[2] = crc2; } -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ + (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_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 @@ -461,7 +476,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_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeVpclmulStream(V256* partialCRC) const { uint64_t crc = 0; uint64_t low64, high64; @@ -492,8 +507,9 @@ return crc; } - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul( - const uint8_t* p, V256* vpartialCRC, V256 loopMultiplicands) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesVpclmul(V256 v0, V256 v1, V256* vpartialCRC, + V256 loopMultiplicands) const { __asm__ volatile( "vpclmulqdq $0x11, %3, %0, %%ymm0 \n" "vpclmulqdq $0x11, %3, %1, %%ymm1 \n" @@ -501,23 +517,23 @@ "vpclmulqdq $0x00, %3, %1, %1 \n" "vpxor %%ymm0, %0, %0 \n" "vpxor %%ymm1, %1, %1 \n" - "vpxor (%2), %0, %0 \n" - "vpxor 32(%2), %1, %1 \n" + "vpxor %2, %0, %0 \n" + "vpxor %4, %1, %1 \n" : "+x"(vpartialCRC[0]), "+x"(vpartialCRC[1]) - : "r"(p), "x"(loopMultiplicands) + : "x"(v0), "x"(loopMultiplicands), "x"(v1) : "ymm0", "ymm1"); } #else template <typename T = V256> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(const uint8_t*, T*, - T) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(T, 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(_MSC_VER) || defined(__clang__)) +#endif // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && (defined(__AVX__) || + // defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && (!defined(_MSC_VER) || + // defined(__clang__)) // Constants generated by './scripts/gen-crc-consts.py x86_pclmul // crc32_lsb_0x82f63b78' from the Linux kernel. @@ -551,24 +567,54 @@ PclmulStreamType pclmul_stream_type> class CRC32AcceleratedX86ARMCombinedMultipleStreams : public CRC32AcceleratedX86ARMCombinedMultipleStreamsBase { - ABSL_ATTRIBUTE_HOT + public: 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 if (length < kMediumCutoff) { + } else { // 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. @@ -621,127 +667,6 @@ } } l = static_cast<uint32_t>(l64); - } 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; - } - - // 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; - } 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_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++) { - 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. - 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); @@ -767,50 +692,275 @@ *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 { + // 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); + for (size_t i = 0; i < num_crc_streams; i++) { + dst_crc_streams[i] = dst_stream_start; + dst_stream_start += bs * 64; + } + 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); + } + + 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; + } + + 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; + } + if constexpr (copy) { + 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; + } + } + } + + // 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); + } + } 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); + + 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; + } + private: - ABSL_ATTRIBUTE_ALWAYS_INLINE void InitPclmulStream( - const uint8_t** pclmul_stream, V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + 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) { V256* vpartialCRC = reinterpret_cast<V256*>(partialCRC); - vpartialCRC[0] = - V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 0)); - vpartialCRC[1] = - V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 1)); + vpartialCRC[0] = v0; + vpartialCRC[1] = v1; } else { - 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)); + 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]; } - *pclmul_stream += 16 * 4; } - 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); + 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; } else { - Process64BytesPclmul(*pclmul_stream, partialCRC); + 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); + } } - *pclmul_stream += 16 * 4; } - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { + return 0; + } else 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 == @@ -849,7 +999,8 @@ case CpuType::kAmdMilan: case CpuType::kAmdGenoa: case CpuType::kAmdTurin: -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ + (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ (!defined(_MSC_VER) || defined(__clang__)) // We don't have vector pclmul on arm, but this still needs to // compile. @@ -875,7 +1026,7 @@ case CpuType::kIntelSandybridge: case CpuType::kIntelWestmere: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::PCLMUL>(); + 3, 0, PclmulStreamType::NONE>(); case CpuType::kArmNeoverseN1: case CpuType::kArmNeoverseV1: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< @@ -905,7 +1056,7 @@ default: // Something else, play it safe and assume slow PCLMULQDQ. return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::PCLMUL>(); + 3, 0, PclmulStreamType::NONE>(); #endif } }