ACP: Add carryless product for unsigned integers

[okaneco]

Proposal

Problem statement

Carryless product (also known as XOR multiplication) is backed by hardware instructions on many platforms, but there's no way for users to write code which uses these instructions without accessing them through hardware intrinsics. This results in users having to write more platform specific code or rely on less optimized, scalar expressions of the operation for portable applications.

Motivating examples or use cases

Carryless product can be used to accelerate checksums (like CRC/cyclic redundancy checks) and aid in implementing some cryptographic algorithms. Since many left shifts and XORs are executed in parallel, there are also applications of it speeding up bit manipulation operations. In the links section are some example applications: one showing the acceleration of JSON parsing by finding pairs of quotation marks using carryless multiplication to perform a prefix XOR, another showing accelerated Morton code/Z-order curve calculations.

This operation can also be referred to as "polynomial multiplication" since it's equivalent to the multiplication of two polynomials in GF(2), the finite field with 2 elements (polynomials can be represented as bitstrings).

Solution sketch

Intrinsic support was recently added in LLVM 22 and has the following semantics according to the LangRef:

The ‘llvm.clmul’ intrinsic computes carry-less multiply of its arguments, which is the result of applying the standard multiplication algorithm, where all of the additions are replaced with XORs, and returns the low-bits. The vector variants operate lane-wise.

A widening variant is also proposed which returns a tuple of (low_bits, high_bits).

impl uN {
    /// Calculates the carryless product of `self` and `rhs`, returning the low-order bits.
    ///
    /// Instead of addition, XOR (exclusive-or) is applied as the reduction operation.
    ///
    /// If the high-order bits are needed, see [`Self::widening_carryless_mul`].
    /// ```
    ///     let x = 0b1101;
    ///     let y = 0b0110;
    ///     let z = 0b1111;
    ///     assert_eq!(0b00101110, x.carryless_mul(y));
    ///     assert_eq!(0b01010101, z.carryless_mul(z));
    /// ```
    pub const fn carryless_mul(self, rhs: Self) -> Self;

    /// Calculates the carryless product of `self` and `rhs`, returning a tuple of low-order
    /// bits and high-order bits in that order.
    ///
    /// Instead of addition, XOR (exclusive-or) is applied as the reduction operation.
    ///
    /// If only the low-order bits are needed, consider using [`Self::carryless_mul`].
    /// ```
    ///     let x = 0b10100010;
    ///     let y = 0b10010110;
    ///     let z = 0b11111111;
    ///     let (lo, hi) = x.widening_carryless_mul(y);
    ///     assert_eq!(0b11101100, lo);
    ///     assert_eq!(0b01011000, hi);
    ///     assert_eq!((0b01010101, 0b01010101), z.widening_carryless_mul(z));
    /// ```
    pub const fn widening_carryless_mul(self, rhs: Self) -> (Self, Self); 
}

Alternatives

1. Do nothing, rely on the compiler recognizing scalar implementations of these patterns or require users to use intrinsics.
2. Wait until LLVM 23 for implementing this. More widespread use of this intrinsic in LLVM optimizations and architecture backends won't reach Rust until LLVM 23 since the intrinsic landed not long before the version branch.
3. Should the widening variant instead return the next integer size larger, and not be implemented for u128? So u8->u16, u16->u32, u32->u64, but nothing for u128.

Links and related work

https://llvm.org/docs/LangRef.html#llvm-clmul-intrinsic
Jan Schultke, active C++29 proposal - Carry-less product: std::clmul

Hardware instructions

x86: pclmulqdq, wikipedia:CLMUL instruction set
Arm NEON: pmull/pmull2 for low and high bits, respectively
RISC-V: clmul/clmulh/clmulr(reversed), the Zbc extension
SPARC: XMULX/XMULXHI, "XOR multiply"
POWER: vpmsum, "vector polynomial multiply sum"

Applications/articles

Geoff Langdale - Finding quote pairs with carry-less multiply
Wunkolo - pclmulqdq Tricks
Intel white paper - Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[hanna-kruppe]

As with #695 (tracking issue), I think this has the potential to be a serious performance footgun:

• Software fallback is very expensive in the general (both inputs variable) case
• It's not part of any x86 target's baseline so runtime target_feature detection is usually necessary to avoid the software fallback
• While some form of carryless multiply exists in many architectures, the details (SIMD and/or scalar, supported integer widths and lane counts) vary a lot, as the C++ proposal illustrates
• The more creative uses of carryless multiply are only profitable when there's efficient hardware support, falling back to a generic software implementation is much worse than just solving the original problem more directly

So I would suggest that stabilization of these functions should be blocked on seeing how efficient LLVM's lowering of the intrinsic is for common use cases, and deciding whether that outweighs the potential for performance footguns.

It may also be worth considering autovectorization support and the implications for portable SIMD, since hardware support is often tied to SIMD for good reasons.

[scottmcm]

pub const fn widening_carryless_mul(self, rhs: Self) -> (Self, Self);

Note that in rust-lang/rust#144494 (comment) it was decided not to stabilize the existing widening_* methods, so you probably don't want to use that name here. The "think in limb" ones are the carrying_* ones, but certainly carrying_carryless_mul sounds weird, so I don't know what to do for names.

---

To me the obvious alternative here that's not explicitly mentioned is just "use the arch methods directly".

If someone wants to experiment on nightly, that can be done via rust-lang/rust#29602.

[programmerjake]

pub const fn widening_carryless_mul(self, rhs: Self) -> (Self, Self);

Note that in rust-lang/rust#144494 (comment) it was decided not to stabilize the existing widening_* methods, so you probably don't want to use that name here. The "think in limb" ones are the carrying_* ones, but certainly carrying_carryless_mul sounds weird, so I don't know what to do for names.

what about something like carryless_mul_wide_parts? that conveys that it's widening but returning the low/high parts instead of a wider integer type.

[folkertdev]

I was curious, here is the current codegen for a SIMD and scalar example:

https://godbolt.org/z/KK957d33r

On aarch64 the SIMD variant just miscompiles, the scalar variant generates terrible code (though perhaps you can't really do better there). We'll probably want the intrinsics for stdarch though, at which point we may as well expose them.

Also as an implementation note, Miri already implements carry-less multiplication

https://github.com/rust-lang/miri/blob/ef278a4ef6e35ac3414e381203f44ced183e9c04/src/shims/x86/mod.rs#L1145

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting, and as with #695 we are happy to have this on nightly for now. Additionally, as per the decision in rust-lang/rust#152016 (comment), we would like the widening method to return a larger integer size and not be available on u128.

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[traviscross]

We talked about this in the libs-api call today (as @Amanieu also notes above). We were generally inclined to do this.

As @scottmcm noted, one thing that came up was general unhappiness with the way that widening_ things work in nightly in the standard library today -- we want them to return the next-wider integer type (and simply not be available for our widest integer type).

At the same time, it's often desirable (in the algorithms for which these are useful) to work exclusively with integers of a certain width. For those cases, the carrying_ variants can be used.

Consequently, in this ACP, for my own part, I'd want to see a carrying_carryless_mul (even though the name is unfortunate).

[tarcieri]

As with #695 (rust-lang/rust#149069), I think this has the potential to be a serious performance footgun:

Software fallback is very expensive in the general (both inputs variable) case

Looking at what they proposed, they are implementing what is to my knowledge the best available technique, which is the one which BearSSL uses for GHASH (and the one we implement in the polyval crate, which uses "holes" to mask out carries:

https://groups.google.com/g/llvm-dev/c/5cpOboKOBg4/m/kJ9z_xkVAQAJ

If the CPU does not have a dedication clmul operation, it can be lowered to regular multiplication, by using holes to avoid carrys.

It's certainly much slower than the intrinsics, but if your target doesn't have those intrinsics to my knowledge there isn't a better alternative.

Having just worked on four different implementations of this operation (CLMUL, PMULL, and 32-bit/64-bit portable) having an intrinsic for this sounds great!

[hanna-kruppe]

It's interesting to know that there is a more efficient lowering than the naive one (though per @folkertdev's compiler explorer link and the current expansion, LLVM doesn't seem to implement it yet). Getting easy access to that on targets without the instruction could be nice for cases where you really need that operation in its full generality because you have to implement some algorithm/standard involving GF(2) polynominal multiplication.

However, the smarter software fallback still seems way to expensive to be usable for "CLMUL as bit manipulation multitool" tricks like simd-json's quote matching. One open question is whether LLVM will be able to synthesize something tolerable (better than general both-inputs-variable) for special cases like clmul(x, -1) for "prefix xor of bit vector x". And, of course, if you're just trying to implement any fast universal hash family (don't have to match some standard or get consistent results across machines), you'd rather use a different family entirely when CLMUL is not fast.

[okaneco]

Created a tracking issue rust-lang/rust#152080

[apps4uco]

Hi, I am the author of the clmul crate https://crates.io/crates/clmul tested on intel and arm (macos) I have some benchmarks that compare performance to portable code.