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, Mul, Sub, SubAssign},
7};
8
9use bytemuck::TransparentWrapper;
10
11/// Value that can be multiplied by itself
12pub trait Square {
13	/// Returns the value multiplied by itself
14	fn square(self) -> Self;
15}
16
17/// A field type that supports widening (unreduced) multiplication.
18///
19/// The multiply phase produces an [`Output`](Self::Output) value that can be accumulated via
20/// addition without overflow (XOR in characteristic 2). A single [`reduce`](Self::reduce) call at
21/// the end converts back to the field representation. For `GF(2^128)` inner products this lets us
22/// amortize the reduction across many products, which is a net win when reductions are comparable
23/// in cost to the widening multiply itself.
24///
25/// `WideMul` is a parent trait of both [`Field`](crate::Field) and
26/// [`PackedField`](crate::PackedField), so every field and packed field supports it (and each type
27/// implements it directly, leaving room for specialized impls). Most types use the trivial
28/// implementation — multiply eagerly, reduce to the identity — except the `GF(2^128)` scalar field
29/// and its CLMUL-accelerated packings (x86_64 and AArch64), which defer the reduction by
30/// accumulating an unreduced `WideGhashProduct`.
31pub trait WideMul: Sized {
32	type Output: Default
33		+ Clone
34		+ Sum
35		+ Add<Output = Self::Output>
36		+ AddAssign
37		+ Sub<Output = Self::Output>
38		+ SubAssign;
39
40	fn wide_mul(a: Self, b: Self) -> Self::Output;
41	fn reduce(wide: Self::Output) -> Self;
42}
43
44#[derive(TransparentWrapper)]
45#[repr(transparent)]
46pub struct TrivialWideMul<T>(T);
47
48impl<T> WideMul for TrivialWideMul<T>
49where
50	T: Default
51		+ Clone
52		+ Sum
53		+ Add<Output = T>
54		+ AddAssign
55		+ Sub<Output = T>
56		+ SubAssign
57		+ Mul<Output = T>,
58{
59	type Output = T;
60
61	#[inline]
62	fn wide_mul(a: Self, b: Self) -> T {
63		Self::peel(a) * Self::peel(b)
64	}
65
66	#[inline]
67	fn reduce(wide: T) -> Self {
68		Self::wrap(wide)
69	}
70}
71
72macro_rules! impl_trivial_wide_mul {
73	($name:ty) => {
74		impl $crate::arithmetic_traits::WideMul for $name {
75			type Output = Self;
76
77			#[inline]
78			fn wide_mul(a: Self, b: Self) -> Self {
79				a * b
80			}
81
82			#[inline]
83			fn reduce(wide: Self) -> Self {
84				wide
85			}
86		}
87	};
88}
89
90pub(crate) use impl_trivial_wide_mul;
91
92/// Value that can be inverted
93pub trait InvertOrZero {
94	/// Returns the inverted value or zero in case when `self` is zero
95	fn invert_or_zero(self) -> Self;
96
97	/// Returns the multiplicative inverse.
98	///
99	/// ## Safety
100	/// Requires that `self` is non-zero. Behavior is undefined otherwise.
101	#[inline]
102	unsafe fn invert(self) -> Self
103	where
104		Self: Sized,
105	{
106		self.invert_or_zero()
107	}
108}
109
110// The `@ strategy` arm wires `$name`'s `Mul` to a strategy wrapper: a `TransparentWrapper` struct
111// (e.g. `Gfni`, `MulFromWideMul`) that carries the actual algorithm. We wrap the inputs, run
112// the wrapper's `Mul`, and peel the result. `$strategy` is captured as raw token-trees (not
113// `:ty`/`:path`) because a matched type fragment is opaque and can't have `<$name>` appended to it.
114macro_rules! impl_mul_with {
115	($name:ident @ $($strategy:tt)*) => {
116		impl std::ops::Mul for $name {
117			type Output = Self;
118
119			#[inline]
120			fn mul(self, rhs: Self) -> Self {
121				$crate::tracing::trace_multiplication!($name);
122
123				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
124					<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self)
125						* <$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(rhs),
126				)
127			}
128		}
129	};
130	($name:ty => $bigger:ty) => {
131		impl std::ops::Mul for $name {
132			type Output = Self;
133
134			#[inline]
135			fn mul(self, rhs: Self) -> Self {
136				$crate::arch::portable::packed::mul_as_bigger_type::<_, $bigger>(self, rhs)
137			}
138		}
139	};
140}
141
142pub(crate) use impl_mul_with;
143
144macro_rules! impl_square_with {
145	($name:ident @ $($strategy:tt)*) => {
146		impl $crate::arithmetic_traits::Square for $name {
147			#[inline]
148			fn square(self) -> Self {
149				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
150					$crate::arithmetic_traits::Square::square(
151						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
152					),
153				)
154			}
155		}
156	};
157	($name:ty => $bigger:ty) => {
158		impl $crate::arithmetic_traits::Square for $name {
159			#[inline]
160			fn square(self) -> Self {
161				$crate::arch::portable::packed::square_as_bigger_type::<_, $bigger>(self)
162			}
163		}
164	};
165}
166
167pub(crate) use impl_square_with;
168
169macro_rules! impl_invert_with {
170	($name:ident @ $($strategy:tt)*) => {
171		impl $crate::arithmetic_traits::InvertOrZero for $name {
172			#[inline]
173			fn invert_or_zero(self) -> Self {
174				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
175					$crate::arithmetic_traits::InvertOrZero::invert_or_zero(
176						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
177					),
178				)
179			}
180		}
181	};
182	($name:ty => $bigger:ty) => {
183		impl $crate::arithmetic_traits::InvertOrZero for $name {
184			#[inline]
185			fn invert_or_zero(self) -> Self {
186				$crate::arch::portable::packed::invert_as_bigger_type::<_, $bigger>(self)
187			}
188		}
189	};
190}
191
192pub(crate) use impl_invert_with;
binius_field/arithmetic_traits.rs

binius_field/
arithmetic_traits.rs
