52x52 -> 104-bit multiply (VPMADD52-style): op shape + IFMA target gating
- Dominant language
- C++
- Stars
- 5.8k
- Forks
- 471
- Avg merge
- 1d 6h
- Merged PRs (30d)
- 81
Description
### The op
`g3doc/op_wishlist.md` lists **"52x52=104-bit multiply — For crypto. Native on Icelake+."** I'd like to implement it and wanted to check the shape and the target gating before writing much.
Proposed as two ops on `u64` lanes, matching the AVX-512 IFMA `VPMADD52LUQ` / `VPMADD52HUQ` semantics (both inputs assumed `< 2^52`; results wrap at 64 bits like the hardware):
```
V MulAdd52Lo(V c, V a, V b) // c + ( (a*b) & (2^52 - 1) )
V MulAdd52Hi(V c, V a, V b) // c + ( (a*b) >> 52 )
```
Multiply-add rather than a bare multiply because that's what the hardware does in one instruction, and it's the form the users want (limb accumulation in a bignum multiply, the reduction step in Poly1305 / Curve25519-style MACs, Montgomery multiplication). A plain `MulWide52 -> (hi, lo)` could be layered on top by passing `c = 0`.
### Emulated fallback
For `a, b < 2^52`, split into 26-bit limbs (`a = a1*2^26 + a0`, `a0,a1 < 2^26`) so every partial product fits exactly in `u64`:
```
p0 = a0*b0 // < 2^52
p1 = a1*b0 + a0*b1 // < 2^53
p2 = a1*b1 // < 2^52
lo52 = (p0 + ((p1 & 0x3FFFFFF) << 26)) & 0xFFFFFFFFFFFFF
carry = (p0 + ((p1 & 0x3FFFFFF) << 26)) >> 52 // 0 or 1
hi52 = p2 + (p1 >> 26) + carry
```
`Mul` on `u64` (low 64 bits) is exact for all three products. ~12-15 ops per result, shared subexpressions between Lo and Hi. Lives in `generic_ops-inl.h` behind a `HWY_NATIVE_MUL_52` toggle, same pattern as `MulByPow2` etc.
### The question: native IFMA gating
`HWY_TARGET_STR_AVX3_DL` currently pulls in `vpclmulqdq, avx512vbmi, avx512vbmi2, vaes, avx512vnni, avx512bitalg, avx512vpopcntdq, gfni` but **not `avx512ifma`**, and `detect_targets.h` doesn't check `__AVX512IFMA__`. Ice Lake and Zen4 both have IFMA, so it *would* be correct to add it to the DL feature set — but that's a target-semantics change I didn't want to make unilaterally. Options as I see them:
1. Add `,avx512ifma` to `HWY_TARGET_STR_AVX3_DL` + `__AVX512IFMA__` to the DL detection. Ice Lake / Zen4 / SPR all get the native path; matches what those CPUs actually are.
2. Native only under `HWY_AVX3_SPR` (which is already the superset target), generic elsewhere. Smallest blast radius, but Ice Lake / Zen4 fall back to emulation despite having the instruction.
3. Generic-only for now, native IFMA as a follow-up once the API is settled.
I'd lean towards (1) but it's your call. Also happy to take a different name than `MulAdd52Lo/Hi` if you have a preferred convention.
### Where this is heading (separate, later PR — just checking the direction)
The reason I want the op is a fixed-width big-integer multiply. My plan would be a `hwy/contrib/multiprec/` layer, **not** a core op: a schoolbook (later Karatsuba) `u128`/`u192`/`u256` × same-width multiply, each width a compile-time template parameter (`WideMul`), built on `MulAdd52*` + `MulEven`, with `if constexpr` over the limb count — the same way `contrib/math` builds transcendentals on core ops. One compiled instantiation per width, no runtime dispatch. Targets crypto (RSA/ECC) and arbitrary-precision arithmetic where the operands are held across lanes.
Does a fixed-width SIMD bignum multiply belong in `hwy/contrib/`, or would you rather keep Highway out of that and point people at a dedicated library? Happy either way — just don't want to build toward it if it's out of scope.
Would the `MulAdd52*` op be welcome, and which gating do you prefer?
Contributor guide
Research direction
Start with g3doc/op_wishlist.md, then inspect the operation patterns in generic_ops-inl.h and target handling in detect_targets.h, including HWY_TARGET_STR_AVX3_DL. Resolve the MulAdd52Lo/Hi API and IFMA gating choice before implementation; done means the shape, emulated fallback, native target coverage, and later contrib direction are agreed and covered by the project’s relevant tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100