binius_field/
arithmetic_traits.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{
5	iter::Sum,
6	ops::{Add, AddAssign, Sub, SubAssign},
7};
8
9/// Value that can be multiplied by itself
10pub trait Square {
11	/// Returns the value multiplied by itself
12	fn square(self) -> Self;
13}
14
15/// A field type that supports widening (unreduced) multiplication.
16///
17/// The multiply phase produces an [`Output`](Self::Output) value that can be accumulated via
18/// addition without overflow (XOR in characteristic 2). A single [`reduce`](Self::reduce) call at
19/// the end converts back to the field representation. For `GF(2^128)` inner products this lets us
20/// amortize the reduction across many products, which is a net win when reductions are comparable
21/// in cost to the widening multiply itself.
22///
23/// `WideMul` is a parent trait of both [`Field`](crate::Field) and
24/// [`PackedField`](crate::PackedField), so every field and packed field supports it (and each type
25/// implements it directly, leaving room for specialized impls). Most types use the trivial
26/// implementation — multiply eagerly, reduce to the identity — except the `GF(2^128)` scalar field
27/// and its CLMUL-accelerated packings (x86_64 and AArch64), which defer the reduction by
28/// accumulating an unreduced `WideGhashProduct`.
29pub trait WideMul: Sized {
30	type Output: Default
31		+ Clone
32		+ Sum
33		+ Add<Output = Self::Output>
34		+ AddAssign
35		+ Sub<Output = Self::Output>
36		+ SubAssign;
37
38	fn wide_mul(a: Self, b: Self) -> Self::Output;
39	fn reduce(wide: Self::Output) -> Self;
40}
41
42/// An unreduced widening product (a [`WideMul::Output`]) that can be scaled by the field element
43/// `X` while still unreduced.
44///
45/// Scaling by `X` and the modular reduction are both `GF(2)`-linear, and they commute:
46/// `reduce(wide.mul_x_wide()) == reduce(wide).mul_x()`. Doing the scaling on the unreduced product
47/// lets an extension-field multiply fold the `X` of its irreducible polynomial into a product it is
48/// going to reduce anyway, saving a reduction over scaling the reduced coordinate.
49pub trait MulXWide {
50	/// Returns the unreduced product scaled by `X`.
51	fn mul_x_wide(self) -> Self;
52}
53
54/// Value that can be inverted
55pub trait InvertOrZero {
56	/// Returns the inverted value or zero in case when `self` is zero
57	fn invert_or_zero(self) -> Self;
58
59	/// Returns the multiplicative inverse.
60	///
61	/// ## Safety
62	/// Requires that `self` is non-zero. Behavior is undefined otherwise.
63	#[inline]
64	unsafe fn invert(self) -> Self
65	where
66		Self: Sized,
67	{
68		self.invert_or_zero()
69	}
70}
71
72// The `@ strategy` arm wires `$name`'s `Mul` to a strategy wrapper: a `TransparentWrapper` struct
73// (e.g. `Gfni`, `MulFromWideMul`) that carries the actual algorithm. We wrap the inputs, run
74// the wrapper's `Mul`, and peel the result. `$strategy` is captured as raw token-trees (not
75// `:ty`/`:path`) because a matched type fragment is opaque and can't have `<$name>` appended to it.
76macro_rules! impl_mul_with {
77	($name:ident @ $($strategy:tt)*) => {
78		impl std::ops::Mul for $name {
79			type Output = Self;
80
81			#[inline]
82			fn mul(self, rhs: Self) -> Self {
83				$crate::tracing::trace_multiplication!($name);
84
85				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
86					<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self)
87						* <$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(rhs),
88				)
89			}
90		}
91	};
92}
93
94pub(crate) use impl_mul_with;
95
96macro_rules! impl_square_with {
97	($name:ident @ $($strategy:tt)*) => {
98		impl $crate::arithmetic_traits::Square for $name {
99			#[inline]
100			fn square(self) -> Self {
101				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
102					$crate::arithmetic_traits::Square::square(
103						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
104					),
105				)
106			}
107		}
108	};
109}
110
111pub(crate) use impl_square_with;
112
113macro_rules! impl_invert_with {
114	($name:ident @ $($strategy:tt)*) => {
115		impl $crate::arithmetic_traits::InvertOrZero for $name {
116			#[inline]
117			fn invert_or_zero(self) -> Self {
118				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
119					$crate::arithmetic_traits::InvertOrZero::invert_or_zero(
120						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
121					),
122				)
123			}
124		}
125	};
126}
127
128pub(crate) use impl_invert_with;
binius_field/arithmetic_traits.rs

binius_field/
arithmetic_traits.rs
