Carry-less product: std::clmul

Document number:: P3642R1
Date:: 2025-06-03
Audience:: LEWGI, SG6
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.

Revision history

Changes since R0

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

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

mul_wide_result

{

low_bits

;

high_bits

;

}

;

template

class

constexpr

mul_wide_result

clmul_wide

(

)

noexcept

;

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

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

2.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).

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

;

}

3.1. 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 clmul_wide may look as follows:

#include <immintrin.h>

#include <cstdint>

mul_wide_result

uint64_t

clmul_wide

(

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

)

}

;

}

There also exists an LLVM pull request ([LLVMClmul]) which would add an @llvm.clmul intrinsic function.

4. 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 mul_wide_result template, and
the decision to have a (T, T) parameter list.

4.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 (proposed) LLVM intrinsic function ([LLVMClmul]) is tentatively named @llvm.clmul.

4.2. SIMD support

The proposal is currently limited to the scalar version of clmul. However, <simd> support may be useful to add, and would be backed by hardware support to an extent.

If LEWG approves, should decide whether <simd> support should be added in this paper, or in a separate paper, if at all.

5. Proposed wording

The proposed changes are relative to the working draft of the standard as of [N5008], with the changes in [P3161R4] applied.

Update subclause [version.syn] paragraph 2 as follows:

#define __cpp_lib_clamp 201603L

also in <algorithm>

#define __cpp_lib_clmul 20????L

also in <numeric>

[...]

#define __cpp_lib_overflow_arithmetic

~~20????L~~

20????L

also in <numeric>

Update the synopsis in [numeric.ops.overview] as follows:

template

class

constexpr

saturate_cast

(

)

noexcept

;

freestanding

template

class

struct

add_carry_result

{

freestanding

low_bits

;

bool

overflow

;

}

;

template

class

using

sub_borrow_result

add_carry_result

;

freestanding

template

class

struct

mul_wide_result

{

freestanding

low_bits

;

high_bits

;

}

;

template

class

struct

div_result

{

freestanding

quotient

;

remainder

;

}

;

template

class

constexpr

add_carry_result

add_carry

(

bool

carry

)

noexcept

;

freestanding

template

class

constexpr

sub_borrow_result

sub_borrow

(

left

right

bool

borrow

)

noexcept

;

freestanding

template

class

constexpr

mul_wide_result

mul_wide

(

)

noexcept

;

freestanding

template

class

constexpr

mul_wide_result

clmul_wide

(

)

noexcept

;

freestanding

template

class

constexpr

div_result

div_wide

(

dividend_high

dividend_low

freestanding

divisor

)

noexcept

;

template

class

constexpr

bool

is_div_defined

(

dividend

divisor

)

noexcept

freestanding

template

class

constexpr

bool

is_div_wide_defined

(

dividend_high

freestanding

dividend_low

divisor

)

noexcept

;

[numeric.clmul], carry-less product

template

class

constexpr

clmul

(

)

noexcept

;

freestanding

In subclause [numeric.overflow] (known as [numeric.sat] at the time of writing), insert the following item, immediately following the description of mul_wide:

template

class

constexpr

mul_wide_result

clmul_wide

(

)

noexcept

;

Let ⊕ denote the exclusive OR operation ([expr.xor]). Given an integer $α$ , let $α_{i}$ denote the $i^{th}$ least significant bit in the base-2 representation of $α$ .

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

Returns: An object storing the bits of an integer $c$ , where the value of $c_{i}$ is given by Formula ?.?, $x$ is x, $y$ is y, and $N$ is the width of T. 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}

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}

In subclause [numeric.ops], append a subclause immediately following [numeric.overflow] (known as [numeric.sat] at the time of writing):

Carry-less product [numeric.clmul]

template

class

constexpr

clmul

(

)

noexcept

;

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

Returns: clmul_wide(x, y).low_bits ([numeric.overflow]).

6. References

[N5008] Thomas Köppe. Working Draft, Programming Languages — C++ 2025-03-15 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/n5008.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

[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. 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] Oscar Smith. [IR] Add llvm clmul intrinsic https://github.com/llvm/llvm-project/pull/140301

Carry-less product: std::clmul

Revision history

Changes since R0

Contents

Introduction

Motivation

Parity computation and JSON parsing

Fast space-filling curves

Possible implementation

Hardware support

Design considerations

Naming

SIMD support

Proposed wording

References

1. Introduction

2. Motivation

2.1. Parity computation and JSON parsing

2.2. Fast space-filling curves

3. Possible implementation

3.1. Hardware support

4. Design considerations

4.1. Naming

4.2. SIMD support

5. Proposed wording

Carry-less product [numeric.clmul]

6. References