* [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation
@ 2026-11-18 16:01 Shreesh Adiga
2026-11-18 16:29 ` Ard Biesheuvel
2026-11-21 20:46 ` Eric Biggers
0 siblings, 2 replies; 4+ messages in thread
From: Shreesh Adiga @ 2026-11-18 16:01 UTC (permalink / raw)
To: Eric Biggers, Ard Biesheuvel, Demian Shulhan; +Cc: linux-crypto, linux-kernel
Use 4-way folding in the shared NEON crc64_nvme for AArch64
as well as AArch32. This improves performance by about 2x for 512 byte
data size on Cortex-X925.
Add similar optimizations from x86 implementation like reducing
the 4x to 2x and doing a tail (len >= 32) 2x fold as well as partial
block handling to process lengths which are not multiple of 16 bytes.
The partial block stage is enabled only for AArch64 as it needs the
128-bit TBL instruction not available in AArch32.
Modified the loop dispatch on AArch64 to allow any len >= 128 rather
than just multiple of 16 bytes.
Modified the pmull intrinsics from crc64-neon.h to use inline
assembly as the intrinsic usage was causing the compiler to
generate the fold constants via mov+movk+fmov/dup which was about 10
instructions for 16-byte constant instead of expected adrp+ld1.
Signed-off-by: Shreesh Adiga <16567adigashreesh@gmail.com>
---
lib/crc/arm64/crc64-neon.h | 15 +++---
lib/crc/arm64/crc64.h | 18 ++++---
lib/crc/crc64-neon.c | 96 +++++++++++++++++++++++++++++++++++---
3 files changed, 110 insertions(+), 19 deletions(-)
diff --git a/lib/crc/arm64/crc64-neon.h b/lib/crc/arm64/crc64-neon.h
index fcd5b1e6f812..700a3a8619f4 100644
--- a/lib/crc/arm64/crc64-neon.h
+++ b/lib/crc/arm64/crc64-neon.h
@@ -2,20 +2,21 @@
static inline uint64x2_t pmull64(uint64x2_t a, uint64x2_t b)
{
- return vreinterpretq_u64_p128(vmull_p64(vgetq_lane_u64(a, 0),
- vgetq_lane_u64(b, 0)));
+ uint64x2_t r;
+
+ asm("pmull %0.1q, %1.1d, %2.1d" : "=w"(r) : "w" (a), "w" (b));
+ return r;
}
static inline uint64x2_t pmull64_high(uint64x2_t a, uint64x2_t b)
{
- poly64x2_t l = vreinterpretq_p64_u64(a);
- poly64x2_t m = vreinterpretq_p64_u64(b);
+ uint64x2_t r;
- return vreinterpretq_u64_p128(vmull_high_p64(l, m));
+ asm("pmull2 %0.1q, %1.2d, %2.2d" : "=w"(r) : "w" (a), "w" (b));
+ return r;
}
static inline uint64x2_t pmull64_hi_lo(uint64x2_t a, uint64x2_t b)
{
- return vreinterpretq_u64_p128(vmull_p64(vgetq_lane_u64(a, 1),
- vgetq_lane_u64(b, 0)));
+ return pmull64(vextq_u64(a, a, 1), b);
}
diff --git a/lib/crc/arm64/crc64.h b/lib/crc/arm64/crc64.h
index c7a69e1f3d8f..06dd08a21dd6 100644
--- a/lib/crc/arm64/crc64.h
+++ b/lib/crc/arm64/crc64.h
@@ -10,19 +10,25 @@
u64 crc64_nvme_neon(u64 crc, const u8 *p, size_t len);
+static __ro_after_init DEFINE_STATIC_KEY_FALSE(have_pmull);
+
#define crc64_be_arch crc64_be_generic
static inline u64 crc64_nvme_arch(u64 crc, const u8 *p, size_t len)
{
- if (len >= 128 && cpu_have_named_feature(PMULL) &&
+ if (static_branch_likely(&have_pmull) && len >= 128 &&
likely(may_use_simd())) {
- size_t chunk = len & ~15;
-
scoped_ksimd()
- crc = crc64_nvme_neon(crc, p, chunk);
+ crc = crc64_nvme_neon(crc, p, len);
- p += chunk;
- len &= 15;
+ return crc;
}
return crc64_nvme_generic(crc, p, len);
}
+
+#define crc64_mod_init_arch crc64_mod_init_arch
+static void crc64_mod_init_arch(void)
+{
+ if (cpu_have_named_feature(PMULL))
+ static_branch_enable(&have_pmull);
+}
diff --git a/lib/crc/crc64-neon.c b/lib/crc/crc64-neon.c
index 4753fb94a4be..03b46d0abcc4 100644
--- a/lib/crc/crc64-neon.c
+++ b/lib/crc/crc64-neon.c
@@ -10,6 +10,12 @@
u64 crc64_nvme_neon(u64 crc, const u8 *p, size_t len);
+/* x^575 mod G, x^511 mod G */
+static const u64 fold_consts_4x_val[2] = { 0x0c32cdb31e18a84aULL,
+ 0x62242240ace5045aULL };
+/* x^319 mod G, x^255 mod G */
+static const u64 fold_consts_2x_val[2] = { 0xb0bc2e589204f500ULL,
+ 0xe1e0bb9d45d7a44cULL };
/* x^191 mod G, x^127 mod G */
static const u64 fold_consts_val[2] = { 0xeadc41fd2ba3d420ULL,
0x21e9761e252621acULL };
@@ -17,23 +23,101 @@ static const u64 fold_consts_val[2] = { 0xeadc41fd2ba3d420ULL,
static const u64 bconsts_val[2] = { 0x27ecfa329aef9f77ULL,
0x34d926535897936aULL };
+static inline uint64x2_t fold_single_round(uint64x2_t fold, uint64x2_t temp,
+ uint64x2_t consts)
+{
+ uint64x2_t temp1 = pmull64(consts, fold);
+ uint64x2_t temp2 = pmull64_high(consts, fold);
+
+ return temp ^ temp1 ^ temp2;
+}
+
+#ifdef CONFIG_ARM64
+/* vqtbl1q_u8 is not available on AArch32. */
+static inline uint64x2_t fold_partial_block(uint64x2_t fold, uint64x2_t consts,
+ const u8 *p, size_t len)
+{
+ static const u8 crc_neon_shift_tab[32] = {
+ 0xff, 0xfe, 0xfd, 0xfc, 0xfb, 0xfa, 0xf9, 0xf8,
+ 0xf7, 0xf6, 0xf5, 0xf4, 0xf3, 0xf2, 0xf1, 0xf0,
+ 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+ 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f
+ };
+
+ uint8x16_t last16, t1, t2;
+ uint64x2_t a, b;
+
+ last16 = vld1q_u8(p + len - 16);
+ t1 = vld1q_u8(crc_neon_shift_tab + len);
+ a = vreinterpretq_u64_u8(vqtbl1q_u8(vreinterpretq_u8_u64(fold), t1));
+ t2 = vmvnq_u8(t1);
+ t2 = vqtbl1q_u8(vreinterpretq_u8_u64(fold), t2);
+ t1 = vcgezq_s8(vreinterpretq_s8_u8(t1));
+ b = vreinterpretq_u64_u8(vbslq_u8(t1, last16, t2));
+
+ return fold_single_round(a, b, consts);
+}
+#endif
+
u64 crc64_nvme_neon(u64 crc, const u8 *p, size_t len)
{
+ /* Assumes len >= 64. AArch32 also assumes len is multiple of 16. */
uint64x2_t fold_consts = vld1q_u64(fold_consts_val);
+ uint64x2_t fold_consts_4x = vld1q_u64(fold_consts_4x_val);
+ uint64x2_t fold_consts_2x = vld1q_u64(fold_consts_2x_val);
uint64x2_t v0 = { crc, 0 };
uint64x2_t zero = { };
+ uint64x2_t v1, v2, v3;
+
+ v0 ^= vreinterpretq_u64_u8(vld1q_u8(p));
+ v1 = vreinterpretq_u64_u8(vld1q_u8(p + 16));
+ v2 = vreinterpretq_u64_u8(vld1q_u8(p + 32));
+ v3 = vreinterpretq_u64_u8(vld1q_u8(p + 48));
- for (;;) {
- v0 ^= vreinterpretq_u64_u8(vld1q_u8(p));
+ p += 64;
+ len -= 64;
+ while (len >= 64) {
+ uint64x2_t t0 = vreinterpretq_u64_u8(vld1q_u8(p + 0));
+ uint64x2_t t1 = vreinterpretq_u64_u8(vld1q_u8(p + 16));
+ uint64x2_t t2 = vreinterpretq_u64_u8(vld1q_u8(p + 32));
+ uint64x2_t t3 = vreinterpretq_u64_u8(vld1q_u8(p + 48));
+ v0 = fold_single_round(v0, t0, fold_consts_4x);
+ v1 = fold_single_round(v1, t1, fold_consts_4x);
+ v2 = fold_single_round(v2, t2, fold_consts_4x);
+ v3 = fold_single_round(v3, t3, fold_consts_4x);
+ p += 64;
+ len -= 64;
+ }
+
+ v0 = fold_single_round(v0, v2, fold_consts_2x);
+ v1 = fold_single_round(v1, v3, fold_consts_2x);
+
+ if (len >= 32) {
+ uint64x2_t t0 = vreinterpretq_u64_u8(vld1q_u8(p + 0));
+ uint64x2_t t1 = vreinterpretq_u64_u8(vld1q_u8(p + 16));
+
+ v0 = fold_single_round(v0, t0, fold_consts_2x);
+ v1 = fold_single_round(v1, t1, fold_consts_2x);
+ p += 32;
+ len -= 32;
+ }
+
+ v0 = fold_single_round(v0, v1, fold_consts);
+
+ if (len >= 16) {
+ uint64x2_t t0 = vreinterpretq_u64_u8(vld1q_u8(p));
+
+ v0 = fold_single_round(v0, t0, fold_consts);
p += 16;
len -= 16;
- if (len < 16)
- break;
-
- v0 = pmull64(fold_consts, v0) ^ pmull64_high(fold_consts, v0);
}
+#ifdef CONFIG_ARM64
+ if (len)
+ v0 = fold_partial_block(v0, fold_consts, p, len);
+#endif
+
/* Multiply the 128-bit value by x^64 and reduce it back to 128 bits. */
v0 = vextq_u64(v0, zero, 1) ^ pmull64_hi_lo(fold_consts, v0);
--
2.56.1
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation
2026-11-18 16:01 [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation Shreesh Adiga
@ 2026-11-18 16:29 ` Ard Biesheuvel
2026-11-18 16:48 ` Shreesh Adiga
2026-11-21 20:46 ` Eric Biggers
1 sibling, 1 reply; 4+ messages in thread
From: Ard Biesheuvel @ 2026-11-18 16:29 UTC (permalink / raw)
To: Shreesh Adiga, Eric Biggers, Demian Shulhan; +Cc: linux-crypto, linux-kernel
On Wed, 18 Nov 2026, at 17:01, Shreesh Adiga wrote:
> Use 4-way folding in the shared NEON crc64_nvme for AArch64
> as well as AArch32. This improves performance by about 2x for 512 byte
> data size on Cortex-X925.
>
> Add similar optimizations from x86 implementation like reducing
> the 4x to 2x and doing a tail (len >= 32) 2x fold as well as partial
> block handling to process lengths which are not multiple of 16 bytes.
>
> The partial block stage is enabled only for AArch64 as it needs the
> 128-bit TBL instruction not available in AArch32.
> Modified the loop dispatch on AArch64 to allow any len >= 128 rather
> than just multiple of 16 bytes.
>
> Modified the pmull intrinsics from crc64-neon.h to use inline
> assembly as the intrinsic usage was causing the compiler to
> generate the fold constants via mov+movk+fmov/dup which was about 10
> instructions for 16-byte constant instead of expected adrp+ld1.
>
Why is that better?
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation
2026-11-18 16:29 ` Ard Biesheuvel
@ 2026-11-18 16:48 ` Shreesh Adiga
0 siblings, 0 replies; 4+ messages in thread
From: Shreesh Adiga @ 2026-11-18 16:48 UTC (permalink / raw)
To: Ard Biesheuvel; +Cc: Eric Biggers, Demian Shulhan, linux-crypto, linux-kernel
On Wed, Nov 18, 2026 at 9:59 PM Ard Biesheuvel <ardb@kernel.org> wrote:
>
>
> On Wed, 18 Nov 2026, at 17:01, Shreesh Adiga wrote:
> > Use 4-way folding in the shared NEON crc64_nvme for AArch64
> > as well as AArch32. This improves performance by about 2x for 512 byte
> > data size on Cortex-X925.
> >
> > Add similar optimizations from x86 implementation like reducing
> > the 4x to 2x and doing a tail (len >= 32) 2x fold as well as partial
> > block handling to process lengths which are not multiple of 16 bytes.
> >
> > The partial block stage is enabled only for AArch64 as it needs the
> > 128-bit TBL instruction not available in AArch32.
> > Modified the loop dispatch on AArch64 to allow any len >= 128 rather
> > than just multiple of 16 bytes.
> >
> > Modified the pmull intrinsics from crc64-neon.h to use inline
> > assembly as the intrinsic usage was causing the compiler to
> > generate the fold constants via mov+movk+fmov/dup which was about 10
> > instructions for 16-byte constant instead of expected adrp+ld1.
> >
>
> Why is that better?
Based on my counting, 10 instructions (mov + movk + movk + movk + dup;
mov + movk + movk + movk + fmov) for loading a single 16-byte fold
constant = 40 bytes. Whereas now it is 2 instructions = 8 bytes + 16
bytes rodata.
Since we have 4 such fold constants pairs (4x, 2x, 1x, barret) it
reduces the instruction count significantly as well.
So lesser read-only memory usage. Also for in-order cores I assume
that the instruction sequence has serial dependency as well.
Previous discussion with Demian who had highlighted this point and
suggested to use inline asm for PMULL rather than intrinsic:
"Scalar vmull_p64() makes compilers materialize the constants via
mov/movk + fmov (42/97 insns on Clang)."
Hopefully the above reasoning is sufficient justification for this change.
Thanks,
Shreesh
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation
2026-11-18 16:01 [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation Shreesh Adiga
2026-11-18 16:29 ` Ard Biesheuvel
@ 2026-11-21 20:46 ` Eric Biggers
1 sibling, 0 replies; 4+ messages in thread
From: Eric Biggers @ 2026-11-21 20:46 UTC (permalink / raw)
To: Shreesh Adiga; +Cc: Ard Biesheuvel, Demian Shulhan, linux-crypto, linux-kernel
On Wed, Nov 18, 2026 at 09:31:00PM +0530, Shreesh Adiga wrote:
> The partial block stage is enabled only for AArch64 as it needs the
> 128-bit TBL instruction not available in AArch32.
> Modified the loop dispatch on AArch64 to allow any len >= 128 rather
> than just multiple of 16 bytes.
Note that an AArch32 implementation of fold_partial_block() is possible,
e.g. vqtbl1q_u8() could be replaced with two vtbl2_u8(). Normally I'd
consider an AArch32 specific optimization not worth including, but it
might be worthwhile here since it would avoid divergence in the code due
to the following arch-specific precondition:
/* Assumes len >= 64. AArch32 also assumes len is multiple of 16. */
> lib/crc/arm64/crc64-neon.h | 15 +++---
> lib/crc/arm64/crc64.h | 18 ++++---
> lib/crc/crc64-neon.c | 96 +++++++++++++++++++++++++++++++++++---
> 3 files changed, 110 insertions(+), 19 deletions(-)
Anyway, I've applied this patch to
https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/log/?h=crc-next
In general I'd prefer better comments in the code though, especially
documenting nonobvious decisions like why pmull and pmull2 are accessed
using inline asm instead of intrinsics.
So if you'd like to do a follow-up patch, it could be worthwhile to
address the above two issues.
Thanks,
- Eric
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2026-11-21 20:46 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-18 16:01 [PATCH] lib/crc: Add 4-way folding in NEON crc64_nvme implementation Shreesh Adiga
2026-11-18 16:29 ` Ard Biesheuvel
2026-11-18 16:48 ` Shreesh Adiga
2026-11-21 20:46 ` Eric Biggers
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®