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/// Scales a value by `X`, the generator of the field's polynomial basis.
16///
17/// A one-bit shift plus a masked exclusive or, not a field multiply.
18///
19/// The scaling is `GF(2)`-linear, so it commutes with the modular reduction.
20/// That is what lets one trait serve both a reduced element and an unreduced product:
21///
22/// ```text
23///     reduce(mul_x(wide)) == mul_x(reduce(wide))
24/// ```
25///
26/// Scaling an unreduced product folds the `X` of an irreducible polynomial into a reduction the
27/// caller is going to pay for anyway.
28pub trait MulX {
29	/// Returns the value scaled by `X`.
30	#[must_use]
31	fn mul_x(self) -> Self;
32}
33
34/// A field type that supports widening (unreduced) multiplication.
35///
36/// The multiply phase produces an [`Output`](Self::Output) value that can be accumulated via
37/// addition without overflow (XOR in characteristic 2). A single [`reduce`](Self::reduce) call at
38/// the end converts back to the field representation. For `GF(2^128)` inner products this lets us
39/// amortize the reduction across many products, which is a net win when reductions are comparable
40/// in cost to the widening multiply itself.
41///
42/// `WideMul` is a parent trait of both [`Field`](crate::Field) and
43/// [`PackedField`](crate::PackedField), so every field and packed field supports it (and each type
44/// implements it directly, leaving room for specialized impls). Most types use the trivial
45/// implementation — multiply eagerly, reduce to the identity — except the `GF(2^128)` scalar field
46/// and its CLMUL-accelerated packings (x86_64 and AArch64), which defer the reduction by
47/// accumulating an unreduced `WideGhashProduct`.
48pub trait WideMul: Sized {
49	type Output: Default
50		+ Clone
51		+ Sum
52		+ Add<Output = Self::Output>
53		+ AddAssign
54		+ Sub<Output = Self::Output>
55		+ SubAssign;
56
57	fn wide_mul(a: Self, b: Self) -> Self::Output;
58	fn reduce(wide: Self::Output) -> Self;
59}
60
61/// Value that can be inverted
62pub trait InvertOrZero {
63	/// Returns the inverted value or zero in case when `self` is zero
64	fn invert_or_zero(self) -> Self;
65
66	/// Returns the multiplicative inverse.
67	///
68	/// ## Safety
69	/// Requires that `self` is non-zero. Behavior is undefined otherwise.
70	#[inline]
71	unsafe fn invert(self) -> Self
72	where
73		Self: Sized,
74	{
75		self.invert_or_zero()
76	}
77}
78
79// A strategy is captured as raw token-trees rather than a type fragment.
80// A matched type fragment is opaque, so it cannot take the packed type as a generic argument.
81macro_rules! impl_square_with {
82	($name:ident @ $($strategy:tt)*) => {
83		impl $crate::arithmetic_traits::Square for $name {
84			#[inline]
85			fn square(self) -> Self {
86				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
87					$crate::arithmetic_traits::Square::square(
88						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
89					),
90				)
91			}
92		}
93	};
94}
95
96pub(crate) use impl_square_with;
97
98macro_rules! impl_mul_x_with {
99	($name:ident @ $($strategy:tt)*) => {
100		impl $crate::arithmetic_traits::MulX for $name {
101			#[inline]
102			fn mul_x(self) -> Self {
103				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
104					$crate::arithmetic_traits::MulX::mul_x(
105						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
106					),
107				)
108			}
109		}
110	};
111}
112
113pub(crate) use impl_mul_x_with;
114
115macro_rules! impl_invert_with {
116	($name:ident @ $($strategy:tt)*) => {
117		impl $crate::arithmetic_traits::InvertOrZero for $name {
118			#[inline]
119			fn invert_or_zero(self) -> Self {
120				<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::peel(
121					$crate::arithmetic_traits::InvertOrZero::invert_or_zero(
122						<$($strategy)* <$name> as ::bytemuck::TransparentWrapper<$name>>::wrap(self),
123					),
124				)
125			}
126		}
127	};
128}
129
130pub(crate) use impl_invert_with;
binius_field/arithmetic_traits.rs

binius_field/
arithmetic_traits.rs
