Carry-less product: std::clmul

Contents

1. Revision history

1.1. Changes since R6

• Convert std::wide_result from an aggregate type to a class with low() and high() accessors
• Turn the former sections containing LWG suggestions into subsections of §5.2. Widening operation and std::wide_result
• Make various minor updates to discussion based on recent developments, such as Rust's widening_carryless_mul operation
• Extend drafting note in § [numeric.ops] with reference to [bit.permute]
• Rebase §6. Proposed wording on [N5054]

1.2. Changes since R5

As requested by LEWG during the 2026 Brno meeting:

• Replace the bump of __cpp_lib_simd with a new __cpp_lib_simd_clmul
• Constrain std::wide_result to unsigned integer types

Also, following LWG review during the 2026 Brno meeting:

• Apply various wording adjustments during review
• Add section discussing potential design changes discussed in LWG review
• Add wording for those design changes in optional wording sections

Furthermore, some editorial changes:

• Mention in §4.1. Intrinsic implementation that __builtin_elementwise_clmul is available in Clang 23
• Expand §4.1. Intrinsic implementation with possible optimizations

1.3. Changes since R4

• Rename std::clmul_wide to std::widening_clmul
• Fix std::simd::clmul specified as a unary function (should be binary)
• Rebase §6. Proposed wording on N5032 with post-Croydon changes applied

1.4. Changes since R3

• Reference faster possible implementations in §4. Possible implementation
• Add some thoughts on why implementations in the compiler are better than pure library implementations
• Mention that @llvm.clmul has now been added to LLVM ([LLVMClmul])
• Change operator<=> for wide_result to be a hidden friend again

1.5. Changes since R2

• Add missing <T> for operator<=>
• Provide a §4. Possible implementation better suited for SIMD parallelization
• Rebase §6. Proposed wording on N5014
• Improve §6. Proposed wording editorially

1.6. Changes since R1

The paper was seen by SG6 at Sofia 2025 with the following feedback:

Summary: SG6 had no numerics concerns but recommended to include std::simd overloads into the paper.

POLL: Forward P3642R1 to LEWG with the expectation that the next revision includes std::simd overloads.

SF	F	N	A	SA
7	4	0	0	0

The following changes were made:

• Provide (non-widening) §5.3. SIMD support
• Use two-space indentation, and generally match the code style of the C++ standard
• Provide detailed design description for §5.2. Widening operation and std::wide_result
• Make §6. Proposed wording and design independent of [P3161R4]
• Fix stray U type name in §6. Proposed wording, and improve wording generally
• Rebase §6. Proposed wording on std::simd naming changes in [P3691R1]

1.7. Changes since R0

• Generate the proposal using COWEL instead of bikeshed
• Fix incorrect formula in §6. Proposed wording for bits ≥ the integer width
• Fix §4.2. Hardware support missing new VPCLMULQDQ instructions
• Fix improper uses of std::unsigned_integral in §2. Introduction
• Make slight editorial wording adjustments
• Rebase on N5008 and [P3161R4]
• Mention [SimdJsonClmul] in §3. Motivation

2. Introduction

Carry-less multiplication is a simple numerical operation on unsigned integers. It can be a seen as a regular multiplication where xor is being used as a reduction instead of +.

It is also known as "XOR multiplication" and "polynomial multiplication". The latter name is used because mathematically, it is equivalent to performing a multiplication of two polynomials in GF(2), where each bit is a coefficient.

I propose a std::clmul function to perform this operation:

I also propose a widening operation in the style of [P3161R4], as follows:

3. Motivation

Carry-less multiplication is an important operation in a number of use cases:

• CRC Computation: While cyclic redundancy checks can theoretically be performed with a finite field of any length, in practice, GF(2)[X], the polynomial ring over the Galois field with two elements is used. Polynomial addition in this ring can be implemented via xor, and multiplication via clmul, which makes cyclic redundancy checks considerably faster.
• Cryptography: clmul may be used to implement AES-GCM. [IntelClmul] describes this process in great detail and motivates hardware support for carry-less multiplication via the pclmulqdq instruction.
• Bit manipulation: clmul performs a large amount of << and xor operations in parallel. This is utilized in the reference implementation [BitPermutations] of std::bit_compressr, proposed in [P3104R3]. For example, the form clmul(x, -1u) computes the bitwise inclusive parity for each bit of x and the bits to its right.

Carry-less multiplication is of such great utility that there is widespread hardware support, some dating back more than a decade. See below for motivating examples.

3.1. Parity computation and JSON parsing

The parity of an integer x is 0 if the number of one-bits is even, and 1 if it is odd. The parity can also be computed with popcount(x) & 1.

While the parity of all bits can be obtained with clmul, it computes the inclusive cumulative parity, which can be used to accelerate parsing JSON and other file formats ([SimdJsonClmul]). This can be done by mapping each " character onto a 1-bit, and any other character onto 0. clmul(x, -1) would then produce masks where string characters corresponds to a 1-bit.

abc xxx "foobar" zzz "a" // input string
000000001000000100000101 // quote_mask
00000000.111111.00000.1. // clmul(quote_mask, -1), ignoring 1-bits of quote_mask

3.2. Fast space-filling curves

The special form clmul(x, -1) can be used to accelerate the computation of Hilbert curves. To properly understand this example, I will explain the basic notion of space-filling curves.

We can fill space using a 2D curve by mapping the index i on the curve onto Cartesian coordinates x and y. A naive curve that fills a 4x4 square can be computed as follows:

When mapping the index i = 0, 1, ..., 0xf onto the returned 2D coordinates, we obtain the following pattern:

0 1 2 3
4 5 6 7
8 9 a b
c d e f

The problem with such a naive curve is that adjacent indices can be positioned very far apart (the distance increases with row length). For image processing, if we store pixels in this pattern, cache locality is bad; two adjacent pixels can be very far apart in memory.

A Hilbert curve is a family of space-filling curves where the distance between two adjacent elements is 1:

0 1 e f
3 2 d c
4 7 8 b
5 6 9 a

De-interleaving bits of i into x and y yields a Z-order curve, and performing further transformations yields a Hilbert curve.

When working with space-filling curves, the inverse operation is also common: mapping the Cartesian coordinates onto an index on the curve. In the case of Z-order curves aka. Morton curves, this can be done by simply interleaving the bits of x and y. A Z-order curve is laid out as follows:

0 1 4 5
2 3 6 7
8 9 c d
a b e f

4. Possible implementation

A naive and unconstrained implementation looks as follows:

Such a naive implementation is far from optimal though. [QuickBench] shows that a naive clmul implementation which computes both the high and the low bits performs 9.2× worse than an efficient implementation taken from [NTL].

4.1. Intrinsic implementation

Since Clang 23, LLVM also provides a portable @llvm.clmul intrinsic function ([LLVMClmul]), and Clang provides a __builtin_elementwise_clmul intrinsic. Thus, the operation can be lowered like: std::clmul → __builtin_clmul → @llvm.clmul → pclmulqdq.

While a pure library implementation of std::clmul is possible, it misses out on many optimization opportunities.

4.2. Hardware support

The implementation difficulty lies mostly in utilizing available hardware instructions, not in the naive fallback implementation.

In the following table, let uN denote N-bit unsigned integer operands, and ×N denote the amount of operands that are processed in parallel.

5. Design considerations

Multiple design choices lean on [P0543R3] and [P3161R4]. Specifically,

• the choice of header <numeric>,
• the choice to have a widening operation,
• the _wide naming scheme,
• the wide_result template, and
• the decision to have a (T, T) parameter list.

5.1. Naming

Carry-less multiplication is also commonly called "Galois Field Multiplication" or "Polynomial Multiplication".

The name clmul was chosen because it carries no domain-specific connotation, and because it is widespread:

• Intel refers to PCLMULQDQ As "Carry-Less Multiplication Quadword" in its manual; see [IntelManual].
• RISC-V refers to clmul as carry-less multiplication, and this is obvious from the mnemonic.
• The Wikipedia article ([WikipediaClmul]) for this operation is titled "Carry-less product".
• The portable LLVM intrinsic function ([LLVMClmul]) is named @llvm.clmul.

5.2. Widening operation and std::wide_result

In addition to the std::clmul function template, there exists a std::widening_clmul function template:

Such a widening function is important in a various cryptographic use cases. There is universal §4.2. Hardware support for obtaining all 128 bits of a multiplication for that reason.

Most of the design choices take the design of [P3161R4] and [P4052R0] into consideration:

• The function is named widening_clmul to be symmetrical with std::saturating_mul from [P4052R0] (merged into C++26). That proposal broadly advocated for a naming scheme leaning on Rust, and the Rust standard library has a nightly-only widening_mul function. Rust also has a nightly-only widening_carryless_mul function, but that name seems comically long and is being contested on the tracking issue.
• The result type is deliberately not named wide_clmul_result so that future widening_mul and other operations can use the same result type, which avoids creating an ever-growing set of equivalent (but distinct) types.
• [P3161R4] orders the low bits before the high bits to cater to little-endian architectures. That choice is not enforced in this paper (high-bits and low-bits may be reordered), but made possible for implementations (see §5.2.1. Aggregate type std::wide_result).

However, the comparison operators are a novel invention of this proposal. They are intended to behave as if the comparisons were performed on an integer with twice the width of T. These comparisons exists so that the result can be easily compared against expected results in test cases, stored in containers like std::set, used out of the box with std::sort, etc. There is an obvious and mathematically meaningful ordering of wide_results, so it would be strange not to add a comparison operator.

For now, T is constrained to be an unsigned integer type. If the aforementioned std::widening_mul operation were added to the standard, those constraints could be relaxed, but for now, only unsigned integer types are needed since std::widening_clmul has that constraint.

5.2.1. Aggregate type std::wide_result

Earlier revisions of this paper made std::wide_result an aggregate type, largely because of the simplicity in specification and usability this provides. LEWG reviewed this issue extensively during 2026 telecons, and the decision to use a non-aggregate type was made for a number of reasons:

• With an aggregate type, the order of members is fixed, so some having a layout that is optimal for the native endianness is not always possible.
• An aggregate type permits structured bindings, which may be bug-prone because the order of members may not match the user's auto [high, low] expected order.
• To optimize for more popular little-endian architectures, the low bits would ideally come first, which conflicts with how we write integer literals (most significant digit first).

5.2.2. Alignment of std::wide_result<std::uint64_t>

It may be reasonable to over-align std::wide_result. For example, std::wide_result<std::uint32_t> could be over-aligned to 64 bits, and std::wide_result<std::uint64_t> could be over-aligned to 128 bits, rather than having the natural alignment of a struct containing two objects of type T.

This decision should be left up to implementers, and is a freedom generally available. Whether the decision to over-align makes sense depends on the target architecture, among other factors.

5.2.3. Integer interoperability

While std::wide_result<std::uint32_t> is strongly implied to have the same layout as std::uint64_t, and while this is desired, it's not actually guaranteed. We could guarantee that std::wide_result<_BitInt(N)> has the same layout as _BitInt(N * 2) (though phrased generally, not just for bit-precise integers).

However, this would arguably over-specify the layout. A conversion wide_result and integers could just as well be provided as a operator T. Such a conversion operator can always be added in a future paper.

5.2.4. Naming of low() and high()

The names low and high are concise and sufficiently clear. Earlier revisions used low_bits and high_bits for either non-static data members or for member functions, but this was seen as problematic during LEWG review, in part because the C++ standard doesn't use the bits terminology generally in respect to integers. Core wording talks about coefficients in the base-2 representation of integers.

Furthermore, the bits part provides little additional clarity. widening_clmul(x, y).low() should be sufficiently clear.

5.3. SIMD support

Upon seeing this proposal at Sofia 2025, SG6 recommended to add SIMD support. This recommendation was provided under the assumption that it would be a simple addition in the style of [P2933R4]. Therefore, this proposal provides non-widening SIMD carry-less multiplication with the following signature:

5.3.1. SIMD widening operations are out of scope

AVX-512 provides a u64×4 → u128×4 operation, and there is currently no precedent for such widening operations in the SIMD library. Specifically, the VPCLMULQDQ instruction ignores one of each u64×2 pairs, and produces a 128-bit output for each such pair.

It would take considerable design and wording effort to standardize this, especially if one wants to expose the full VPCLMULQDQ behavior, which allows choosing for each u64×2 integer pair, which of these integers is multiplied and which is ignored. Procedurally, that design effort should be part of [P3161R4] (which proposes widening operations in general) or some follow-up proposal for SIMD widening operations. Some other SIMD instructions like PMULUDQ perform multiple widening multiplications in parallel, in the same style as VPCLMULQDQ, while some others compute just the upper bits, like VPMULHUW. This is a broad design space.

In conclusion, a proposal for widening SIMD operations in general would be well-motivated. For std::clmul, designing SIMD widening operations would be scope creep.

6. Proposed wording

The proposed changes are relative to [N5054].

[version.syn]

Add feature test macros to [version.syn] paragraph 2 as follows:

[numeric.ops]

Add the following declarations to the synopsis in [numeric.ops.overview], immediately following the declarations associated with [numeric.sat]:

In subclause [numeric.ops], append a subclause immediately following [numeric.sat]:

[simd]

Add the following declarations to the synopsis in [simd.syn]:

In subclause [simd], append a subclause immediately preceding [simd.math]:

7. References