polyval: detect VPCLMULQDQ at runtime

As of #44, polyval will compile to VPCLMULQDQ instructions on new enough CPU architectures.

We might be able to use a trick similar to RustCrypto/password-hashes#440 where we detect the relevant CPU features and call a special function annotated with target_feature to ensure it's always used where available.

This is reply to this comment.

POLYVAL/GHASH can be broken down into a parallelizable portion and a sequential portion... there's an accumulation of the output that is inherently sequential, but multiplication of the inputs can be performed in parallel.

I am not sure I understand. In our implementation we XOR input block x with inner state y, multiply the XOR result with h, and store the multiplication result in y. I don't see where we can process 4 input blocks at once, which can be done with _mm512_clmulepi64_epi128

Maybe you had Poly1305 in mind?

We already implement POLYVAL in parallel using ILP. It could use VPCLMULQDQ instead (automatically, when available, as opposed to requiring special RUSTFLAGS)

We process one block at a time. ILP is used only for the 3 _mm_clmulepi64_si128 calls, only 2 of which use the same immediate argument. Here is generated assembly for our current implementation: https://rust.godbolt.org/z/zs1acTozM In my understanding, at most we can explicitly merge 2 CLMUL calls with 0x00 immediate into one _mm256_clmulepi64_epi128 call.

The optimization I wanted to explore in this particular issue is to find a way to enable VPCLMULQDQ optimizations without the user having to pass -C target-cpu=skylake as RUSTFLAGS, i.e. by enabling the required features via target_feature(enable = "...")

I don't see where we can process 4 input blocks at once, which can be done with _mm512_clmulepi64_epi128

I think that instruction in particular could line up quite nicely with #290, and would be able to process 4 message blocks in parallel.

There's also _mm256_clmulepi64_epi128, though it seems like CPUs that support that probably also support _mm512_clmulepi64_epi128? I think the latter probably better aligns with our problem, and would reduce amortized CLMULs per block to 1 AFAICT.

There's still a reduction to work out, but that should be 1 CLMUL.

FWIW the relevant code that could use AVX-512 looks like:

/// Process 4 blocks with R/F algorithm and aggregated reduction
///
/// Uses 16 CLMULs for multiplication (4 per block) + 1 CLMUL for reduction = 17 CLMULs total
#[target_feature(enable = "avx2", enable = "pclmulqdq")]
#[inline]
unsafe fn process_4_blocks(&mut self, data: &[u8]) {
    debug_assert!(data.len() == 64);

    // Load all 4 blocks (no byte swap for POLYVAL)
    let m0 = _mm_loadu_si128(data.as_ptr() as *const __m128i);
    let m1 = _mm_loadu_si128(data[16..].as_ptr() as *const __m128i);
    let m2 = _mm_loadu_si128(data[32..].as_ptr() as *const __m128i);
    let m3 = _mm_loadu_si128(data[48..].as_ptr() as *const __m128i);

    // XOR first block with accumulator
    let y0 = _mm_xor_si128(self.acc, m0);

    // R/F multiply all 4 blocks (16 CLMULs)
    let (r0, f0) = rf_mul_unreduced(y0, self.key.h4, self.key.d4);
    let (r1, f1) = rf_mul_unreduced(m1, self.key.h3, self.key.d3);
    let (r2, f2) = rf_mul_unreduced(m2, self.key.h2, self.key.d2);
    let (r3, f3) = rf_mul_unreduced(m3, self.key.h1, self.key.d1);

    // Aggregate R and F values
    let r = _mm_xor_si128(_mm_xor_si128(r0, r1), _mm_xor_si128(r2, r3));
    let f = _mm_xor_si128(_mm_xor_si128(f0, f1), _mm_xor_si128(f2, f3));

    // Single reduction (1 CLMUL)
    self.acc = reduce_rf(r, f);
}

/// R/F multiplication using 4 CLMULs per block
///
/// Given M = [M1 : M0] and precomputed H = [H1 : H0], D = [D1 : D0]:
/// - R = M0×D1 ⊕ M1×H1 (2 CLMULs)
/// - F = M0×D0 ⊕ M1×H0 (2 CLMULs)
///
/// Returns (R, F) for later reduction
#[target_feature(enable = "pclmulqdq")]
#[inline]
unsafe fn rf_mul_unreduced(m: __m128i, h: __m128i, d: __m128i) -> (__m128i, __m128i) {
    // R = M0×D1 ⊕ M1×H1
    let r0 = _mm_clmulepi64_si128(m, d, 0x10); // M0 × D1
    let r1 = _mm_clmulepi64_si128(m, h, 0x11); // M1 × H1
    let r = _mm_xor_si128(r0, r1);

    // F = M0×D0 ⊕ M1×H0
    let f0 = _mm_clmulepi64_si128(m, d, 0x00); // M0 × D0
    let f1 = _mm_clmulepi64_si128(m, h, 0x01); // M1 × H0
    let f = _mm_xor_si128(f0, f1);

    (r, f)
}

/// Reduction using Lemma 3: Result = R ⊕ F1 ⊕ (x^64×F0) ⊕ (P1×F0)
///
/// Uses 1 CLMUL for reduction
#[target_feature(enable = "pclmulqdq")]
#[inline]
unsafe fn reduce_rf(r: __m128i, f: __m128i) -> __m128i {
    let p1 = _mm_set_epi64x(0, P1 as i64);

    // F1 in low position
    let f1 = _mm_srli_si128(f, 8);

    // x^64×F0 (shift F0 to high position)
    let f0_shifted = _mm_slli_si128(f, 8);

    // P1×F0
    let p1_f0 = _mm_clmulepi64_si128(f, p1, 0x00);

    // Result = R ⊕ F1 ⊕ (x^64×F0) ⊕ (P1×F0)
    let result = _mm_xor_si128(r, f1);
    let result = _mm_xor_si128(result, f0_shifted);
    _mm_xor_si128(result, p1_f0)
}

Particularly the "R/F multiply all 4 blocks (16 CLMULs)" step could be reduced to 4 512-bit CLMULs that operate over 4 blocks in parallel.

I'm also curious if target_feature(enable = "vpclmulqdq") if LLVM would be able to simply promote code like that to using 512-bit ops. I swear I saw it do that in Godbolt one time.

@newpavlov

Okay, after a lot of confusion I think I finally understand what's going on here.

So investigating #316 I observed the behavior I was poorly recalling in my previous comment.

The R/F algorithm implementation we adapted describes itself as "AVX2" and enables the avx2 target feature, but @newpavlov observed it wasn't actually using any AVX2 instructions, despite the original implementation being heavily described as an AVX2 implementation.

I observed there was one effect of adding avx2 to target_features: the compiler emitted VPCLMULQDQ instead of PCLMULQDQ, which is what this issue is all about achieving.

However, it's using VPCLMULQDQ with XMM registers, so again no actual AVX2 dependency.

Sooo... enabling avx2 indirectly enables avx. And that's all we actually need to get rustc/LLVM to emit VPCLMULQDQ:

https://godbolt.org/z/d3PEM9ec8

I think we can just change the CPU feature detection to look for a combination of avx and pclmulqdq, which should be widely supported on x86 hardware, and drop all mention of "AVX2" (for now).

As noted in other comments in this issue there is opportunity for AVX2 (_mm256_clmulepi64_epi128) and AVX-512 (_mm512_clmulepi64_epi128) support, namely those are the VPCLMULQDQ instructions that act on YMM and ZMM registers respectively, but I think we can open separate issues for those if there's interest.

We could just switch to the vpclmulqdq target feature since it implies both avx and pclmulqdq. Wider intrinsics are gated on AVX2 or AVX-512 in addition to vpclmulqdq.

Nice, yeah that sounds like the actual correct solution.

Edit: MSRV 1.89+

polyval: use `vpclmulqdq` feature on `x86`/`x86_64`

polyval: use `avx`+`pclmulqdq` feature on `x86`/`x86_64`

polyval: use `avx`+`pclmulqdq` features on `x86`/`x86_64` (RustCrypto…

Navigation Menu

Repository navigation

polyval: detect VPCLMULQDQ at runtime #184

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

polyval: detect VPCLMULQDQ at runtime #184

Description

Activity

newpavlov commented on Jul 27, 2023

tarcieri commented on Jul 27, 2023

newpavlov commented on Jul 27, 2023

tarcieri commented on Jul 27, 2023

tarcieri commented on Feb 8, 2026

tarcieri commented on Feb 8, 2026

tarcieri commented on Feb 8, 2026

tarcieri commented on Feb 28, 2026

newpavlov commented on Feb 28, 2026

tarcieri commented on Feb 28, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions