Carry-less product: std::clmul

Document number:: P3642R6
Date:: 2026-07-14
Audience:: LEWG, LWG
Project:: ISO/IEC 14882 Programming Languages — C++, ISO/IEC JTC1/SC22/WG21
Reply-to:: Jan Schultke <janschultke@gmail.com>
GitHub Issue:: wg21.link/P3642/github
Source:: github.com/Eisenwave/cpp-proposals/blob/master/src/clmul.cow

Add widening and non-widening carry-less multiplication functions.

Potential design changes following LWG review

6.1

Aggregate type `std::wide_result`

6.2

Alignment of `std::wide_result<std::uint64_t>`

6.3

1. Revision history

1.1. Changes since R5

The paper was forwarded from LEWG to LWG during the 2026-06 Brno meeting, but got stuck in LWG due to some design concerns that require LEWG input.

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 §6. Potential design changes following LWG review
Add wording for those design changes in §8. Optional wording changes A and §9. Optional wording changes B

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.2. Changes since R4

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

1.3. 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.4. Changes since R2

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

1.5. 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

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
Make §7. Proposed wording and design independent of [P3161R4]
Fix stray U type name in §7. Proposed wording, and improve wording generally
Rebase §7. Proposed wording on std::simd naming changes in [P3691R1]

1.6. Changes since R0

Generate the proposal using COWEL instead of bikeshed
Fix incorrect formula in §7. 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:

template

class

constexpr

clmul

(

)

noexcept

;

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

template

class

struct

wide_result

{

low_bits

;

high_bits

;

...

}

;

template

class

constexpr

wide_result

widening_clmul

(

)

noexcept

;

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.

The special form clmul(x, -1) computes the parity of each bit in x and the bits to its right. The most significant bit holds the parity of x as a whole.

bool

parity

(

std

uint32_t

)

{

return

std

clmul

(

)

;

}

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:

struct

pos

{

uint32_t

;

}

;

pos

naive_curve

(

uint32_t

)

{

return

{

}

;

}

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

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:

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

clmul can be used to compute the bitwise parity for each bit and the bits to its right, which is helpful for computing Hilbert curves. Note that the following example uses the std::bit_compress function from [P3104R3], which may also be accelerated using clmul.

pos

hilbert_to_xy

(

uint32_t

)

{

De-interleave the bits of i.

uint32_t

std

bit_compress

(

55555555

)

;

abcdefgh

→

bdfh

uint32_t

std

bit_compress

(

aaaaaaaa

)

;

abcdefgh

→

aceg

Undo the permutation that Hilbert curves apply on top of Z-order curves.

uint32_t

;

uint32_t

ffff

;

uint32_t

std

clmul

(

)

;

uint32_t

std

clmul

(

)

;

uint32_t

(

)

;

return

{

}

;

}

This specific example is taken from [FastHilbertCurves]. [HackersDelight] explains the basis behind this computation of Hilbert curves using bitwise operations.

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:

clmul can be used to implement bit-interleaving in order to generate a Z-order curves.

uint32_t

xy_to_morton

(

uint32_t

)

{

uint32_t

std

clmul

(

)

;

abcd -> 0a0b0c0d

uint32_t

std

clmul

(

)

;

abcd -> a0b0c0d0

return

;

}

In the example above, std::clmul(x, x) is equivalent to [P3104R3]'s std::bit_expand(x, 0x55555555u).

4. Possible implementation

A naive and unconstrained implementation looks as follows:

template

class

constexpr

clmul

(

const

)

noexcept

{

result

;

for

(

int

;

numeric_limits

digits

;

)

{

result

(

{

}

)

;

}

return

result

;

}

This implementation is particularly suited for auto-vectorization. Assuming the loop is unrolled, T{1} << i is constant and each bitwise AND and multiplication can be done in parallel. Lastly, all results have to be accumulated using a horizontal XOR.

Expressed in std::simd terms, this looks something like:

using

simd

vec

numeric_limits

digits

;

static

constexpr

powers

array

size

(

)

{

...

}

;

return

simd

reduce

(

)

(

)

powers

)

bit_xor

{

}

)

;

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].

The mathematical basis for the [NTL] implementation is described in [FasterMultiplicationInGF2].

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.

std::clmul is commutative, pure, re-entrant, non-throwing, does not affect the floating-point environment, etc. Not all of these properties can be easily communicated for a library function.
Carry-less multiplication with 0 or 1 can be simplified irrespective of the other factor.
If one factor has a large number of trailing zeroes, the operation can be simplified by shifting that factor to the right, performing the multiplication, and shifting back to the left. This may avoid multiprecision operations; that is, it can turn a 128-bit multiplication into a 64-bit multiplication.
If one factor is known to be a power of two, even if the exact value isn't known, normal multiplication can be used, which may be faster.
If one factor is a mask (that is, a sequence of contiguous one-bits), carry-less multiplication is equivalent to a parallel prefix XOR or bitwise parity operation, which is simpler than the usual software implementation.
std::clmul(x, x) is equivalent to interleaving bits of x with zeroes. This pattern of squaring can be recognized (even if the value of x is unknown) and transformed into std::bit_expand(x, 0x5555'5555u) if the PDEP instruction is available in hardware. On x86_64, this may be beneficial because carry-less multiplication is a vector instruction and PDEP may have less overhead.

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.

Operation	x86_64	ARM	RV64
clmul u64×4 → u128×4	vpclmulqdq^VPCLMULQDQ
clmul u64×2 → u128×2	vpclmulqdq^VPCLMULQDQ
clmul u64 → u128	pclmulqdq^PCLMULQDQ	pmull+pmull2^Neon	clmul+clmulh^{Zbc, Zbkc}
clmul u64 → u128	pclmulqdq^PCLMULQDQ	pmull+pmull2^Neon	clmul+clmulh^{Zbc, Zbkc}
clmul u64 → u64		pmull^Neon	clmul^{Zbc, Zbkc}
clmul u8×8 → u16×8		pmull^Neon
clmul u8×8 → u8×8		pmul^Neon

A limited x86_64 implementation of widening_clmul may look as follows:

#include <immintrin.h>

#include <cstdint>

wide_result

uint64_t

widening_clmul

(

uint64_t

)

noexcept

{

__m128i

x_128

_mm_set_epi64x

(

)

;

__m128i

y_128

_mm_set_epi64x

(

)

;

__m128i

result_128

_mm_clmulepi64_si128

(

x_128

y_128

)

;

return

{

low_bits

uint64_t

(

_mm_extract_epi64

(

result_128

)

high_bits

uint64_t

(

_mm_extract_epi64

(

result_128

)

}

;

}

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

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

template

class

struct

wide_result

{

low_bits

;

high_bits

;

friend

constexpr

bool

operator

(

const

wide_result

const

wide_result

)

default

;

friend

constexpr

strong_ordering

operator

<=>

(

const

wide_result

const

wide_result

)

noexcept

;

}

;

template

class

constexpr

wide_result

widening_clmul

(

)

noexcept

;

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 widening_mul function.
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.
The low_bits appear before the high_bits, so that on the more widespread little-endian architectures, the layout of the struct is identical to that of an integer, which is slightly better for calling conventions.

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.

Also, wide_result should be a broadly useful vocabulary type which may be instantiated with user-defined numeric types, simply because that seems like a useful side product of this proposal.

It would not be possible to simply return an integer with twice the width of the input because it is not guaranteed that such a type exists, especially in the case of unsigned long long inputs.

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:

template

simd-integral

constexpr

clmul

(

const

)

noexcept

;

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. Potential design changes following LWG review

The design in the preceding section is what has been approved by LEWG and what is reflected in §7. Proposed wording. This section discusses potentional additioal changes.

During LWG review, some minor wording changes were fixed. In addition, certain design questions have been raised during LWG review of the paper:

6.1. Aggregate type `std::wide_result`

Should std::wide_result actually be an aggregate type? A notable problem is that this permits structured bindings and list initialization, and the low bits first order was perceived as more surprising than the other way around. Furthermore, while big-endian architectures are uncommon, they do exist, and std::wide_result is less friendly in its layout to those. To solve this:

The type could be converted to a non-aggregate, with member functions for accessing the data members rather than making them public.
Structured bindings access could simply not be provided, which would prevent the potential resulting bugs.

The wording for this option is provided in §8. Optional wording changes A.

6.2. Alignment of `std::wide_result<std::uint64_t>`

Should std::wide_result<std::uint64_t> be required to be over-aligned to 128 bits? This would be consistent with __int128 but inconsistent with _BitInt(128); the latter is only aligned to 64 bits.

I personally believe that the standard should not mandate either one. Both options are plausible ipmlementation choices, and if the neither the C nor the C++ standard mandates specific alignment for integer types, why would we mandate it here? Mandating 128-bit alignment for std::wide_result<std::uint64_t> also suggests that several ABIs have made a mistake by under-aligning _BitInt(128), which is not a claim we should be making without extremely strong evidence and ABI expertise.

No wording for such a requirement is provided in this paper.

6.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. There also seems to be no good reason why that guarantee wouldn't be possible to provide, at least if std::wide_result is not an aggregate and the implementation has some more freedom regarding its layout.

That is, 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).

The wording for this option is provided in §9. Optional wording changes B.

7. Proposed wording

The proposed changes are relative to [N5032], with the changes accepted during the 2026-02 Croydon meeting applied.

[version.syn]

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

[…]

#define __cpp_lib_clmul 20????L

also in

[…]

#define __cpp_lib_simd_clmul 20????L

also in

<simd>

[numeric.ops]

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

[numeric.clmul], carry-less product

template

class

struct

wide_result

{

low_bits

;

high_bits

;

friend

constexpr

bool

operator

(

const

wide_result

const

wide_result

)

default

;

friend

constexpr

strong_ordering

operator

<=>

(

const

wide_result

const

wide_result

)

noexcept

;

}

;

template

class

constexpr

wide_result

widening_clmul

(

)

noexcept

;

template

class

constexpr

clmul

(

)

noexcept

;

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

Carry-less product [numeric.clmul]

1 A specialization wide_result<T> is ill-formed unless T is an unsigned integer type ([basic.fundamental]).

constexpr

strong_ordering

operator

<=>

(

const

wide_result

const

wide_result

)

noexcept

;

2 Returns: tie(x.high_bits, x.low_bits) <=> tie(y.high_bits, y.low_bits).

template

class

constexpr

wide_result

widening_clmul

(

)

noexcept

;

3 Let:

$⨁$ be a reduction using the exclusive OR operation ([expr.xor]);
for an integer $α$ , $α_{i}$ be the $i^{th}$ least significant bit in the base-2 representation of $α$ ;
$N$ be the width of T.

4 Constraints: T is an unsigned integer type ([basic.fundamental]).

5 Returns: A wide_result<T> object storing the bits of an integer $c$ of width $2 N$ , where the value of $c_{i}$ is given by Formula ?.?, $x$ is x, and $y$ is y. The result object is initialized so that

low_bits stores the $N$ least significant bits of $c$ , and
high_bits stores the subsequent $N$ bits of $c$ .

[FORMULA ?.?]

c_{i} = ⨁_{j = 0}^{i} x_{j} y_{i - j}

template

class

constexpr

clmul

(

)

noexcept

;

6 Constraints: T is an unsigned integer type ([basic.fundamental]).

7 Returns: widening_clmul(x, y).low_bits.

If the mathematical notation in the block above does not render for you, you are using an old browser with no MathML support. Please open the document in a recent version of Firefox or Chrome.

The formula is taken from [IntelClmul], with different variable names, and with no special case for the upper $N$ bits; we can simply treat the integers as mathematical integers with $2 N$ width.

See [iterator.concept.wine] for precedent on using $N$ to denote the width of a type.

See [sf.cmath.riemann.zeta] for precedent on wording which includes formulae.

The formula above in TeX notation is:

c_i = \

bigoplus

{j = 0}^i x_i y_{i - j}

[simd]

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

namespace

std

simd

{ […]

[simd.clmul], carry-less product

template

simd-integral

constexpr

clmul

(

const

)

noexcept

;

[simd.math], mathematical functions

template

math-floating-point

constexpr

deduced-simd-t

acos

(

const

)

; […] }

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

Carry-less product [simd.clmul]

template

simd-integral

constexpr

clmul

(

const

)

noexcept

;

1 Constraints: The type V::value_type is an unsigned integer type ([basic.fundamental]).

2 Returns: A basic_vec object where the $i^{th}$ element is initialized to the result of std::clmul(a[ $i$ ], b[ $i$ ]) ([numeric.clmul]) for all $i$ in the range [0, V::size()).

8. Optional wording changes A

Optionally, if std::wide_result is not to be an aggregate type, immediately apply the following changes on top of the preceding changes.

Change the declaration of std::wide_result in [numeric.ops.overview] as follows:

template

class

~~struct~~

class

wide_result

{

~~T low_bits;~~ ~~T high_bits;~~

public

constexpr

wide_result

(

high

low

)

noexcept

high-bits

(

high

)

low-bits

(

low

)

{

}

constexpr

high_bits

(

)

const

noexcept

{

return

high-bits

;

}

constexpr

low_bits

(

)

const

noexcept

{

return

low-bits

;

}

friend

constexpr

bool

operator

(

const

wide_result

const

wide_result

)

default

;

friend

constexpr

strong_ordering

operator

<=>

(

const

wide_result

const

wide_result

)

noexcept

;

private

high-bits

low-bits

;

exposition-only

}

;

Change [numeric.clmul] as follows:

1 A specialization wide_result<T> is ill-formed unless T is an unsigned integer type ([basic.fundamental]).

2 A specialization of wide_result is a standard-layout, trivially copyable class type. The members high-bits and low-bits of any specialization of wide_result may be reordered.

3 Recommended practice: The member low-bits should precede the member high-bits in all specializations of wide_result if endian::native equals endian::little ([bit.endian]).

Bulk edit: In the remainder of [numeric.clmul], replace any mention of ~~high_bits~~ with high-bits and any mention of ~~low_bits~~ with low-bits.

9. Optional wording changes B

Optionally, if we want to provide stricter guarantees regarding integer layout compatibility, immediately apply the following changes on top of the preceding changes.

If the changes from §8. Optional wording changes A have been applied, delete the Recommended practice element in [numeric.clmul]:

Recommended practice: The member low-bits should precede the member high-bits in all specializations of wide_result if endian::native equals endian::little ([bit.endian]).

In any case, insert a new paragraph immediately preceding the library declarations in [numeric.clmul]:

For two objects $w_{0}$ and $w_{1}$ of a type wide_result<T>, if T has no padding bits and there exists an unsigned integer type W with twice the width of T and with no padding bits, then $w_{0}$ <=> $w_{1}$ shall be equivalent to bit_cast<W>( $w_{0}$ ) <=> bit_cast<W>( $w_{1}$ ) and wide_result<T> shall have the same size and alignment as W.

10. References

[N5032] Thomas Köppe. Working Draft Programming Languages — C++ 2025-12-15 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/n5032.pdf

[P0543R3] Jens Maurer. Saturation arithmetic 2023-07-19 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p0543r3.html

[P3104R3] Jan Schultke. Bit permutations 2025-02-11 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3104r3.html

[P3161R4] Tiago Freire. Unified integer overflow arithmetic 2025-03-26 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3161r4.html

[P2933R4] Daniel Towner, Ruslan Arutyunyan. Extend <bit> header function with overloads for std::simd 2025-02-13 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p2933r4.html

[P3691R1] Matthias Kretz et al.. Reconsider naming of the namespace for "std::simd" 2025-06-17 https://wg21.link/p3691r1

[P4052R0] Jan Schultke, Corentin Jabot. Renaming saturation arithmetic functions 2025-03-13 https://wg21.link/p4052r0

[BitPermutations] Jan Schultke. C++26 Bit permutations reference implementation https://github.com/Eisenwave/cxx26-bit-permutations

[SimdJsonClmul] Geoff Langdale. Code Fragment: Finding quote pairs with carry-less multiply (PCLMULQD) 2019-03-06 https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/

[IntelClmul] Shay Gueron, Michael E. Kounavis. Intel® Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode https://www.intel.com/content/dam/develop/external/us/en/documents/clmul-wp-rev-2-02-2014-04-20.pdf

[IntelManual] Intel Corporation. Intel® 64 and IA-32 Architectures Software Developer's Manual https://software.intel.com/en-us/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4

[HackersDelight] Henry S. Warren, Jr. Hacker's Delight, Second Edition https://doc.lagout.org/security/Hackers'Delight.pdf

[FastHilbertCurves] rawrunprotected. 2D Hilbert curves in O(1) "http://threadlocalmutex.com/?p=188

[WikipediaClmul] Wikipedia community. Carry-less product https://en.wikipedia.org/wiki/Carry-less_product

[LLVMClmul] Documentation for 'llvm.clmul.*' Intrinsic https://llvm.org/docs/LangRef.html#llvm-clmul-intrinsic

[QuickBench] Benchmark of naive clmul vs. NTL clmul https://quick-bench.com/q/eG4Q5BR_udnfh4V5f-3d3h3fRHY

[NTL] Victor Shoup. NTL GitHub repository https://github.com/libntl/ntl

[FasterMultiplicationInGF2] Richard P. Brent, Pierrick Gaudry, Emmanuel Thomé, Paul Zimmermann. Faster Multiplication in GF(2)[x] 2008-11-07 https://inria.hal.science/inria-00188261v4/document

Carry-less product: std::clmul

Contents

Revision history

Changes since R5

Changes since R4

Changes since R3

Changes since R2

Changes since R1

Changes since R0

Introduction

Motivation

Parity computation and JSON parsing

Fast space-filling curves

Possible implementation

Intrinsic implementation

Hardware support

Design considerations

Naming

Widening operation

SIMD support

SIMD widening operations are out of scope

Potential design changes following LWG review

Aggregate type std::wide_result

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

Integer interoperability

Proposed wording

[version.syn]

[numeric.ops]

[simd]

Optional wording changes A

Optional wording changes B

References

1. Revision history

1.1. Changes since R5

1.2. Changes since R4

1.3. Changes since R3

1.4. Changes since R2

1.5. Changes since R1

1.6. Changes since R0

2. Introduction

3. Motivation

3.1. Parity computation and JSON parsing

3.2. Fast space-filling curves

4. Possible implementation

4.1. Intrinsic implementation

4.2. Hardware support

5. Design considerations

5.1. Naming

5.2. Widening operation

5.3. SIMD support

5.3.1. SIMD widening operations are out of scope

6. Potential design changes following LWG review

6.1. Aggregate type std::wide_result

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

6.3. Integer interoperability

7. Proposed wording

[version.syn]

[numeric.ops]

Carry-less product [numeric.clmul]

[simd]

Carry-less product [simd.clmul]

8. Optional wording changes A

9. Optional wording changes B

10. References

Aggregate type `std::wide_result`

Alignment of `std::wide_result<std::uint64_t>`

6.1. Aggregate type `std::wide_result`

6.2. Alignment of `std::wide_result<std::uint64_t>`