binius_field/arch/portable/arithmetic/
ghash_sq.rs

1// Copyright 2026 The Binius Developers
2
3//! Portable GHASH² widening multiply: three independent GHASH multiplies over the coordinates.
4//!
5//! This is the strategy for targets whose widest carry-less multiply is 128 bits, where batching
6//! the Karatsuba diagonal into a two-lane packed GHASH multiply buys nothing — that packed multiply
7//! decomposes back into two independent 128-bit multiplies, each with its own reduction. Keeping
8//! the three Karatsuba products separate instead lets the multiply-by-`X` of the irreducible
9//! polynomial be applied to an *unreduced* product ([`MulXWide`]), which folds it into a reduction
10//! that has to happen anyway: two GHASH reductions per GHASH² product rather than three.
11
12use bytemuck::TransparentWrapper;
13
14use crate::{
15	BinaryField128bGhash, PackedGhashSq1x256b, SlicedGhashSqWide, WideMul,
16	arithmetic_traits::MulXWide,
17	packed_ghash_sq::{ghash_sq_coords, ghash_sq_from_coords},
18};
19
20/// The unreduced product of a single GHASH coordinate multiply.
21type GhashWide = <BinaryField128bGhash as WideMul>::Output;
22
23/// [`WideMul`] strategy for [`PackedGhashSq1x256b`] keeping the three Karatsuba products of the
24/// coordinate multiply separate, so that the multiply-by-`X` can be deferred into a reduction.
25#[repr(transparent)]
26#[derive(TransparentWrapper)]
27pub struct GhashSqSlicedWideMul<T>(T);
28
29impl WideMul for GhashSqSlicedWideMul<PackedGhashSq1x256b> {
30	type Output = SlicedGhashSqWide<GhashWide>;
31
32	/// Karatsuba over `Y`: defers the three GHASH products `a·e`, `b·f`, `(a+b)·(e+f)`.
33	#[inline]
34	fn wide_mul(a: Self, b: Self) -> Self::Output {
35		let [a0, a1] = ghash_sq_coords(Self::peel(a));
36		let [b0, b1] = ghash_sq_coords(Self::peel(b));
37
38		SlicedGhashSqWide {
39			t0: BinaryField128bGhash::wide_mul(a0, b0),
40			t2: BinaryField128bGhash::wide_mul(a1, b1),
41			t1: BinaryField128bGhash::wide_mul(a0 + a1, b0 + b1),
42		}
43	}
44
45	/// Folds `Y² = X·Y + X`, recovering the Karatsuba cross term as `t₁ + t₀ + t₂`:
46	/// `z₀ = t₀ + X·t₂` and `z₁ = (t₁ + t₀ + t₂) + X·t₂ = z₀ + t₁ + t₂`.
47	///
48	/// Scaling `t₂` by `X` while it is still unreduced turns `z₀` into a single reduction of an
49	/// accumulated wide product, so the two coordinates cost two reductions in total.
50	#[inline]
51	fn reduce(wide: Self::Output) -> Self {
52		let z0 = BinaryField128bGhash::reduce(wide.t0 + wide.t2.mul_x_wide());
53		let z1 = z0 + BinaryField128bGhash::reduce(wide.t1 + wide.t2);
54
55		Self::wrap(ghash_sq_from_coords([z0, z1]))
56	}
57}
binius_field/arch/portable/arithmetic/ghash_sq.rs

binius_field/arch/portable/arithmetic/
ghash_sq.rs
