Tracking Issue for `uint_carryless_mul`

[okaneco]

Feature gate: #![feature(uint_carryless_mul)]

This is a tracking issue for functions that return the carryless product (XOR multiplication) of unsigned integers.
carryless_mul returns the low-order bits of the result, and widening_carryless_mul returns the full result in the next wider unsigned integer type.

Public API

widening_carryless_mul is not implemented for u128 because there is no larger integer type to return.

impl uN {
    /// Returns the low-order bits of the carryless product of `self` and `rhs`.
    pub const fn carryless_mul(self, rhs: Self) -> Self;
}

impl u8 {
    /// Returns the full carryless product result of `self` and `rhs` in the next wider power-of-two unsigned integer.
    pub const fn widening_carryless_mul(self, rhs: Self) -> u16;
}
impl u16 {
    pub const fn widening_carryless_mul(self, rhs: Self) -> u32;
}
impl u32 {
    pub const fn widening_carryless_mul(self, rhs: Self) -> u64;
}
impl u64 {
    pub const fn widening_carryless_mul(self, rhs: Self) -> u128;
}

Steps / History

• ACP: ACP: Add carryless product for unsigned integers libs-team#738
• Implementation: implement carryless_mul #152132
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• carrying_carryless_mul?: In the ACP, there was a voicing of desire for a function that returned the product as a 2-sized tuple with the same sized integer, (Self, Self).
• Evaluate the quality of codegen before stabilization: Not all architectures have these operations as hardware instructions and the instructions are not uniform in their integer coverage, nor are the hardware instructions part of the baseline of some targets. However, even without hardware instructions, the intrinsics that these functions wrap should produce equal or better code than a (naive) user implementation.

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[okaneco]

I would appreciate if someone with LLVM and compiler intrinsic experience could implement this.

As noted here rust-lang/libs-team#738 (comment), a Miri implementation exists of a shim for x86's pclmulqdq.
https://github.com/rust-lang/miri/blob/ef278a4ef6e35ac3414e381203f44ced183e9c04/src/shims/x86/mod.rs#L1145

Feel free to adjust the labels accordingly.
@rustbot label +E-help-wanted

[programmerjake]

the default runtime implementation can just call llvm.clmul.*

[apps4uco]

Hi, I am the author of the clmul crate https://crates.io/crates/clmul tested on intel and arm (macos) in the crate there are some benchmarks that compare performance to portable code, in case it is useful to move forward with this proposal.

I just implemented @programmerjake 's suggestion to use llvm intrinsics to the crate under the feature flag llvm. Feel free to submit PRs on the clmul crate if you want to test or benchmark anything out before being implemented in std.

[okaneco]

@rustbot label -E-help-wanted -S-tracking-unimplemented