---
title: "Slides for P3642R4Carry-less product:std::clmul"
document: P3647R1
date: 2026-03-03
audience: LEWG
reply-to:
  - "Jan Schultke < <janschultke@gmail.com>"
paper-type: proposal
---

# Carry-less product:std::clmul
P3642R4

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 1

## Introduction

**Intuition**: "carry-less" means we use XOR instead of plus.

| Regular multiplication | Carry-less multiplication |
| --- | --- |
| x * 0b0110
== (x << 3) * 0
+ (x << 2) * 1
+ (x << 1) * 1
+ (x << 0) * 0 | clmul(x, 0b0110)
== (x << 3) * 0
^ (x << 2) * 1
^ (x << 1) * 1
^ (x << 0) * 0 |

- useful for CRC, AES-GCM, parsing, bit manipulation, …
- widespread hardware support (x86_64, ARM, RISC-V)
- a.k.a. "polynomial multiplication" and "XOR multiplication"

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 2

## Motivating example

- `clmul(x, -1u)` computes bitwise parity (inclusive)
- i.e. for each bit in `x`, `/* is 1-bit count to right odd? */ ? 1 : 0`
- can be used to check if character is inside/outside string in parallel

```
abc xxx "foobar" zzz "a"
000000001000000100000101 // quotes
000000000111111100000011 // clmul(quotes, -1u)
000000000111111000000010 // clmul(quotes, -1u) & ~quotes
```

This technique is used to accelerate string parsing in simdjson.

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 3

## Hardware support

| Operation | x86_64 | ARM | RV64 |
| --- | --- | --- | --- |
| clmul u64×4 → u128×4 | vpclmulqdq |  |  |
| clmul u64×2 → u128×2 | vpclmulqdq |  |  |
| clmul u64 → u128 | pclmulqdq | pmull+pmull2 | clmul+clmulh |
| clmul u64 → u128 | pclmulqdq | pmull+pmull2 | clmul+clmulh |
| clmul u64 → u64 |  | pmull | clmul |
| clmul u8×8 → u16×8 |  | pmull |  |
| clmul u8×8 → u8×8 |  | pmul |  |

Marked

rows are integrated in this proposal.

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 4

## Proposed design

template

<

unsigned-integer

T

>

T

clmul

(

T

x

,

T

y

)

noexcept

;

template

<

class

T

>

struct

mul_wide_result

{

//

yoinked from P3161R4:

T

low_bits

;

//

Unified integer overflow arithmetic

T

high_bits

;

}

;

template

<

unsigned-integer

T

>

constexpr

mul_wide_result

<

T

>

clmul_wide

(

T

x

,

T

y

)

noexcept

;

- `clmul` names used because it is most common (Intel, LLVM, RV64, etc.)
- `simd::clmul` also provided (but no `simd::clmul_wide`) (broken)

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 5

## Implementation and wording

#### Implementation

- naive fallback implementation is trivial
- just need to wrap platform intrinsics when available
- portable support with @llvm.clmul
  - could be wrapped in __builtin_clmul

#### Wording

- reviewed by SG6 for correctness
- *see paper*

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 6

k thx bye („• ֊ •„)

Jan Schultke
 | 
Slides for P3642R4
—
Carry-less product:

std::clmul

| 
Telecons 2026
 | 
Slide 7