| /* crc32_armv8_pmull_eor3.c -- ARMv8 CRC32 using PMULL + EOR3 (SHA3 extension) |
| * Copyright (C) 2025 Peter Cawley |
| * https://github.com/corsix/fast-crc32 |
| * For conditions of distribution and use, see copyright notice in zlib.h |
| * |
| * This uses EOR3 (3-way XOR) from ARMv8.2-A SHA3 extension to save instructions. |
| * Uses 3-way parallel scalar CRC + 9 PMULL vector lanes, processing 192 bytes/iter. |
| */ |
| |
| #ifdef ARM_PMULL_EOR3 |
| |
| #include "zbuild.h" |
| #include "zutil.h" |
| #include "acle_intrins.h" |
| #include "neon_intrins.h" |
| #include "crc32_armv8_p.h" |
| |
| /* Carryless multiply low 64 bits: a[0] * b[0] */ |
| static inline uint64x2_t clmul_lo(uint64x2_t a, uint64x2_t b) { |
| #ifdef _MSC_VER |
| return vreinterpretq_u64_p128(vmull_p64( |
| vget_low_p64(vreinterpret_p64_u64(a)), |
| vget_low_p64(vreinterpret_p64_u64(b)))); |
| #else |
| return vreinterpretq_u64_p128(vmull_p64( |
| vget_lane_p64(vreinterpret_p64_u64(vget_low_u64(a)), 0), |
| vget_lane_p64(vreinterpret_p64_u64(vget_low_u64(b)), 0))); |
| #endif |
| } |
| |
| /* Carryless multiply high 64 bits: a[1] * b[1] */ |
| static inline uint64x2_t clmul_hi(uint64x2_t a, uint64x2_t b) { |
| return vreinterpretq_u64_p128(vmull_high_p64(vreinterpretq_p64_u64(a), vreinterpretq_p64_u64(b))); |
| } |
| |
| /* Carryless multiply of two 32-bit scalars: a * b (returns 64-bit result in 128-bit vector) */ |
| static inline uint64x2_t clmul_scalar(uint32_t a, uint32_t b) { |
| #ifdef _MSC_VER |
| return vreinterpretq_u64_p128(vmull_p64(vdup_n_p64((poly64_t)a), vdup_n_p64((poly64_t)b))); |
| #else |
| return vreinterpretq_u64_p128(vmull_p64((poly64_t)a, (poly64_t)b)); |
| #endif |
| } |
| |
| /* Compute x^n mod P (CRC-32 polynomial) in log(n) time, where P = 0x104c11db7 */ |
| static uint32_t xnmodp(uint64_t n) { |
| uint64_t stack = ~(uint64_t)1; |
| uint32_t acc, low; |
| for (; n > 191; n = (n >> 1) - 16) { |
| stack = (stack << 1) + (n & 1); |
| } |
| stack = ~stack; |
| acc = ((uint32_t)0x80000000) >> (n & 31); |
| for (n >>= 5; n; --n) { |
| acc = __crc32w(acc, 0); |
| } |
| while ((low = stack & 1), stack >>= 1) { |
| poly8x8_t x = vreinterpret_p8_u64(vmov_n_u64(acc)); |
| uint64_t y = vgetq_lane_u64(vreinterpretq_u64_p16(vmull_p8(x, x)), 0); |
| acc = __crc32d(0, y << low); |
| } |
| return acc; |
| } |
| |
| /* Shift CRC forward by nbytes: equivalent to appending nbytes of zeros to the data stream */ |
| static inline uint64x2_t crc_shift(uint32_t crc, size_t nbytes) { |
| Assert(nbytes >= 5, "crc_shift requires nbytes >= 5"); |
| return clmul_scalar(crc, xnmodp(nbytes * 8 - 33)); |
| } |
| |
| Z_FORCEINLINE static Z_TARGET_PMULL_EOR3 uint32_t crc32_copy_impl(uint32_t crc, uint8_t *dst, const uint8_t *src, |
| size_t len, const int COPY) { |
| uint32_t crc0 = ~crc; |
| |
| if (UNLIKELY(len == 1)) { |
| if (COPY) |
| *dst = *src; |
| crc0 = __crc32b(crc0, *src); |
| return ~crc0; |
| } |
| |
| /* Align to 16-byte boundary for vector path */ |
| uintptr_t align_diff = ALIGN_DIFF(src, 16); |
| if (align_diff) |
| crc0 = crc32_hw_align(crc0, &dst, &src, &len, align_diff, COPY); |
| |
| /* 3-way scalar CRC + 9-way PMULL folding (192 bytes/iter) */ |
| if (len >= 192) { |
| size_t blk = len / 192; /* Number of 192-byte blocks */ |
| size_t klen = blk * 16; /* Scalar stride per CRC lane */ |
| const uint8_t *end = src + len; |
| const uint8_t *src0 = src; |
| const uint8_t *src1 = src + klen; |
| const uint8_t *src2 = src + klen * 2; |
| const uint8_t *srcv = src + klen * 3; /* Vector data starts after scalar lanes */ |
| uint32_t crc1 = 0, crc2 = 0; |
| uint64x2_t vc0, vc1, vc2; |
| uint64_t vc; |
| |
| /* Load first 9 vector chunks (144 bytes) */ |
| uint64x2_t x0 = vld1q_u64_ex((const uint64_t*)srcv, 128), y0; |
| uint64x2_t x1 = vld1q_u64_ex((const uint64_t*)(srcv + 16), 128), y1; |
| uint64x2_t x2 = vld1q_u64_ex((const uint64_t*)(srcv + 32), 128), y2; |
| uint64x2_t x3 = vld1q_u64_ex((const uint64_t*)(srcv + 48), 128), y3; |
| uint64x2_t x4 = vld1q_u64_ex((const uint64_t*)(srcv + 64), 128), y4; |
| uint64x2_t x5 = vld1q_u64_ex((const uint64_t*)(srcv + 80), 128), y5; |
| uint64x2_t x6 = vld1q_u64_ex((const uint64_t*)(srcv + 96), 128), y6; |
| uint64x2_t x7 = vld1q_u64_ex((const uint64_t*)(srcv + 112), 128), y7; |
| uint64x2_t x8 = vld1q_u64_ex((const uint64_t*)(srcv + 128), 128), y8; |
| uint64x2_t k; |
| /* k = {x^144 mod P, x^144+64 mod P} for 144-byte fold */ |
| { static const uint64_t ALIGNED_(16) k_[] = {0x26b70c3d, 0x3f41287a}; k = vld1q_u64_ex(k_, 128); } |
| |
| /* Per-region dst pointers */ |
| uint8_t *dst0 = dst; |
| uint8_t *dst1 = NULL; |
| uint8_t *dst2 = NULL; |
| uint8_t *dst_v = NULL; |
| |
| if (COPY) { |
| dst1 = dst + klen; |
| dst2 = dst + klen * 2; |
| dst_v = dst + klen * 3; |
| vst1q_u8(dst_v, vreinterpretq_u8_u64(x0)); |
| vst1q_u8(dst_v + 16, vreinterpretq_u8_u64(x1)); |
| vst1q_u8(dst_v + 32, vreinterpretq_u8_u64(x2)); |
| vst1q_u8(dst_v + 48, vreinterpretq_u8_u64(x3)); |
| vst1q_u8(dst_v + 64, vreinterpretq_u8_u64(x4)); |
| vst1q_u8(dst_v + 80, vreinterpretq_u8_u64(x5)); |
| vst1q_u8(dst_v + 96, vreinterpretq_u8_u64(x6)); |
| vst1q_u8(dst_v + 112, vreinterpretq_u8_u64(x7)); |
| vst1q_u8(dst_v + 128, vreinterpretq_u8_u64(x8)); |
| dst_v += 144; |
| } |
| srcv += 144; |
| |
| /* Fold 9 vectors + 3-way parallel scalar CRC */ |
| if (blk > 1) { |
| /* Only form a limit pointer when we have at least 2 blocks. */ |
| const uint8_t *limit = src0 + klen - 32; |
| while (src0 <= limit) { |
| /* Fold all 9 vector lanes using PMULL */ |
| y0 = clmul_lo(x0, k), x0 = clmul_hi(x0, k); |
| y1 = clmul_lo(x1, k), x1 = clmul_hi(x1, k); |
| y2 = clmul_lo(x2, k), x2 = clmul_hi(x2, k); |
| y3 = clmul_lo(x3, k), x3 = clmul_hi(x3, k); |
| y4 = clmul_lo(x4, k), x4 = clmul_hi(x4, k); |
| y5 = clmul_lo(x5, k), x5 = clmul_hi(x5, k); |
| y6 = clmul_lo(x6, k), x6 = clmul_hi(x6, k); |
| y7 = clmul_lo(x7, k), x7 = clmul_hi(x7, k); |
| y8 = clmul_lo(x8, k), x8 = clmul_hi(x8, k); |
| |
| /* EOR3: combine hi*k, lo*k, and new data in one instruction */ |
| { |
| uint64x2_t d0 = vld1q_u64_ex((const uint64_t*)srcv, 128); |
| uint64x2_t d1 = vld1q_u64_ex((const uint64_t*)(srcv + 16), 128); |
| uint64x2_t d2 = vld1q_u64_ex((const uint64_t*)(srcv + 32), 128); |
| uint64x2_t d3 = vld1q_u64_ex((const uint64_t*)(srcv + 48), 128); |
| uint64x2_t d4 = vld1q_u64_ex((const uint64_t*)(srcv + 64), 128); |
| uint64x2_t d5 = vld1q_u64_ex((const uint64_t*)(srcv + 80), 128); |
| uint64x2_t d6 = vld1q_u64_ex((const uint64_t*)(srcv + 96), 128); |
| uint64x2_t d7 = vld1q_u64_ex((const uint64_t*)(srcv + 112), 128); |
| uint64x2_t d8 = vld1q_u64_ex((const uint64_t*)(srcv + 128), 128); |
| if (COPY) { |
| vst1q_u8(dst_v, vreinterpretq_u8_u64(d0)); |
| vst1q_u8(dst_v + 16, vreinterpretq_u8_u64(d1)); |
| vst1q_u8(dst_v + 32, vreinterpretq_u8_u64(d2)); |
| vst1q_u8(dst_v + 48, vreinterpretq_u8_u64(d3)); |
| vst1q_u8(dst_v + 64, vreinterpretq_u8_u64(d4)); |
| vst1q_u8(dst_v + 80, vreinterpretq_u8_u64(d5)); |
| vst1q_u8(dst_v + 96, vreinterpretq_u8_u64(d6)); |
| vst1q_u8(dst_v + 112, vreinterpretq_u8_u64(d7)); |
| vst1q_u8(dst_v + 128, vreinterpretq_u8_u64(d8)); |
| dst_v += 144; |
| } |
| x0 = veor3q_u64(x0, y0, d0); |
| x1 = veor3q_u64(x1, y1, d1); |
| x2 = veor3q_u64(x2, y2, d2); |
| x3 = veor3q_u64(x3, y3, d3); |
| x4 = veor3q_u64(x4, y4, d4); |
| x5 = veor3q_u64(x5, y5, d5); |
| x6 = veor3q_u64(x6, y6, d6); |
| x7 = veor3q_u64(x7, y7, d7); |
| x8 = veor3q_u64(x8, y8, d8); |
| } |
| |
| /* 3-way parallel scalar CRC (16 bytes each) */ |
| { |
| uint64_t s0a = *(const uint64_t*)src0; |
| uint64_t s0b = *(const uint64_t*)(src0 + 8); |
| uint64_t s1a = *(const uint64_t*)src1; |
| uint64_t s1b = *(const uint64_t*)(src1 + 8); |
| uint64_t s2a = *(const uint64_t*)src2; |
| uint64_t s2b = *(const uint64_t*)(src2 + 8); |
| if (COPY) { |
| memcpy(dst0, &s0a, 8); |
| memcpy(dst0 + 8, &s0b, 8); |
| dst0 += 16; |
| memcpy(dst1, &s1a, 8); |
| memcpy(dst1 + 8, &s1b, 8); |
| dst1 += 16; |
| memcpy(dst2, &s2a, 8); |
| memcpy(dst2 + 8, &s2b, 8); |
| dst2 += 16; |
| } |
| crc0 = __crc32d(crc0, s0a); |
| crc0 = __crc32d(crc0, s0b); |
| crc1 = __crc32d(crc1, s1a); |
| crc1 = __crc32d(crc1, s1b); |
| crc2 = __crc32d(crc2, s2a); |
| crc2 = __crc32d(crc2, s2b); |
| } |
| src0 += 16; |
| src1 += 16; |
| src2 += 16; |
| srcv += 144; |
| } |
| } |
| |
| /* Reduce 9 vectors to 1 using tree reduction */ |
| /* Step 1: x0 = fold(x0, x1), shift x2..x8 down */ |
| { static const uint64_t ALIGNED_(16) k_[] = {0xae689191, 0xccaa009e}; k = vld1q_u64_ex(k_, 128); } |
| y0 = clmul_lo(x0, k), x0 = clmul_hi(x0, k); |
| x0 = veor3q_u64(x0, y0, x1); |
| x1 = x2, x2 = x3, x3 = x4, x4 = x5, x5 = x6, x6 = x7, x7 = x8; |
| |
| /* Step 2: fold pairs (x0,x1), (x2,x3), (x4,x5), (x6,x7) */ |
| y0 = clmul_lo(x0, k), x0 = clmul_hi(x0, k); |
| y2 = clmul_lo(x2, k), x2 = clmul_hi(x2, k); |
| y4 = clmul_lo(x4, k), x4 = clmul_hi(x4, k); |
| y6 = clmul_lo(x6, k), x6 = clmul_hi(x6, k); |
| x0 = veor3q_u64(x0, y0, x1); |
| x2 = veor3q_u64(x2, y2, x3); |
| x4 = veor3q_u64(x4, y4, x5); |
| x6 = veor3q_u64(x6, y6, x7); |
| |
| /* Step 3: fold pairs (x0,x2), (x4,x6) */ |
| { static const uint64_t ALIGNED_(16) k_[] = {0xf1da05aa, 0x81256527}; k = vld1q_u64_ex(k_, 128); } |
| y0 = clmul_lo(x0, k), x0 = clmul_hi(x0, k); |
| y4 = clmul_lo(x4, k), x4 = clmul_hi(x4, k); |
| x0 = veor3q_u64(x0, y0, x2); |
| x4 = veor3q_u64(x4, y4, x6); |
| |
| /* Step 4: final fold (x0, x4) -> x0 */ |
| { static const uint64_t ALIGNED_(16) k_[] = {0x8f352d95, 0x1d9513d7}; k = vld1q_u64_ex(k_, 128); } |
| y0 = clmul_lo(x0, k), x0 = clmul_hi(x0, k); |
| x0 = veor3q_u64(x0, y0, x4); |
| |
| /* Process final scalar chunk */ |
| { |
| uint64_t s0a = *(const uint64_t*)src0; |
| uint64_t s0b = *(const uint64_t*)(src0 + 8); |
| uint64_t s1a = *(const uint64_t*)src1; |
| uint64_t s1b = *(const uint64_t*)(src1 + 8); |
| uint64_t s2a = *(const uint64_t*)src2; |
| uint64_t s2b = *(const uint64_t*)(src2 + 8); |
| if (COPY) { |
| memcpy(dst0, &s0a, 8); |
| memcpy(dst0 + 8, &s0b, 8); |
| memcpy(dst1, &s1a, 8); |
| memcpy(dst1 + 8, &s1b, 8); |
| memcpy(dst2, &s2a, 8); |
| memcpy(dst2 + 8, &s2b, 8); |
| } |
| crc0 = __crc32d(crc0, s0a); |
| crc0 = __crc32d(crc0, s0b); |
| crc1 = __crc32d(crc1, s1a); |
| crc1 = __crc32d(crc1, s1b); |
| crc2 = __crc32d(crc2, s2a); |
| crc2 = __crc32d(crc2, s2b); |
| } |
| |
| /* Shift and combine 3 scalar CRCs */ |
| vc0 = crc_shift(crc0, klen * 2 + blk * 144); |
| vc1 = crc_shift(crc1, klen + blk * 144); |
| vc2 = crc_shift(crc2, blk * 144); |
| vc = vgetq_lane_u64(veor3q_u64(vc0, vc1, vc2), 0); |
| |
| /* Final reduction: 128-bit vector + scalar CRCs -> 32-bit */ |
| crc0 = __crc32d(0, vgetq_lane_u64(x0, 0)); |
| crc0 = __crc32d(crc0, vc ^ vgetq_lane_u64(x0, 1)); |
| if (COPY) |
| dst += blk * 192; |
| src = srcv; |
| len = end - srcv; |
| } |
| |
| /* 3-way scalar CRC (24 bytes/iter) */ |
| if (len >= 80) { |
| size_t klen = ((len - 8) / 24) * 8; /* Stride for 3-way parallel */ |
| const uint8_t *buf0 = src; |
| const uint8_t *buf1 = src + klen; |
| const uint8_t *buf2 = src + klen * 2; |
| uint32_t crc1 = 0, crc2 = 0; |
| uint64x2_t vc0, vc1; |
| uint64_t vc; |
| |
| /* Per-lane dst pointers */ |
| uint8_t *dst0 = dst; |
| uint8_t *dst1 = NULL; |
| uint8_t *dst2 = NULL; |
| if (COPY) { |
| dst1 = dst + klen; |
| dst2 = dst + klen * 2; |
| } |
| |
| /* 3-way parallel scalar CRC */ |
| do { |
| uint64_t v0 = *(const uint64_t*)buf0; |
| uint64_t v1 = *(const uint64_t*)buf1; |
| uint64_t v2 = *(const uint64_t*)buf2; |
| if (COPY) { |
| memcpy(dst0, &v0, 8); |
| dst0 += 8; |
| memcpy(dst1, &v1, 8); |
| dst1 += 8; |
| memcpy(dst2, &v2, 8); |
| dst2 += 8; |
| } |
| crc0 = __crc32d(crc0, v0); |
| crc1 = __crc32d(crc1, v1); |
| crc2 = __crc32d(crc2, v2); |
| buf0 += 8; |
| buf1 += 8; |
| buf2 += 8; |
| len -= 24; |
| } while (len >= 32); |
| |
| /* Combine the 3 CRCs */ |
| vc0 = crc_shift(crc0, klen * 2 + 8); |
| vc1 = crc_shift(crc1, klen + 8); |
| vc = vgetq_lane_u64(veorq_u64(vc0, vc1), 0); |
| |
| /* Process final 8 bytes with combined CRC */ |
| crc0 = crc2; |
| { |
| uint64_t vf = *(const uint64_t*)buf2; |
| if (COPY) |
| memcpy(dst2, &vf, 8); |
| crc0 = __crc32d(crc0, vf ^ vc); |
| } |
| src = buf2 + 8; |
| len -= 8; |
| if (COPY) |
| dst = dst2 + 8; |
| } |
| |
| /* Process remaining bytes */ |
| return crc32_hw_tail(crc0, dst, src, len, COPY); |
| } |
| |
| Z_INTERNAL Z_TARGET_PMULL_EOR3 uint32_t crc32_armv8_pmull_eor3(uint32_t crc, const uint8_t *buf, size_t len) { |
| return crc32_copy_impl(crc, NULL, buf, len, 0); |
| } |
| |
| Z_INTERNAL Z_TARGET_PMULL_EOR3 uint32_t crc32_copy_armv8_pmull_eor3(uint32_t crc, uint8_t *dst, const uint8_t *src, size_t len) { |
| #if OPTIMAL_CMP >= 32 |
| return crc32_copy_impl(crc, dst, src, len, 1); |
| #else |
| /* Without unaligned access, interleaved stores get decomposed into byte ops */ |
| crc = crc32_armv8_pmull_eor3(crc, src, len); |
| memcpy(dst, src, len); |
| return crc; |
| #endif |
| } |
| #endif |
