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
42macro_rules! impl_trivial_wide_mul {
43	($name:ty) => {
44		impl $crate::arithmetic_traits::WideMul for $name {
45			type Output = Self;
46
47			#[inline]
48			fn wide_mul(a: Self, b: Self) -> Self {
49				a * b
50			}
51
52			#[inline]
53			fn reduce(wide: Self) -> Self {
54				wide
55			}
56		}
57	};
58}
59
60pub(crate) use impl_trivial_wide_mul;
61
62/// Value that can be inverted
63pub trait InvertOrZero {
64	/// Returns the inverted value or zero in case when `self` is zero
65	fn invert_or_zero(self) -> Self;
66}
67
68/// Multiplication that is parameterized with some some strategy.
69pub trait TaggedMul<Strategy> {
70	fn mul(self, rhs: Self) -> Self;
71}
72
73macro_rules! impl_mul_with {
74	($name:ident @ $strategy:ty) => {
75		impl std::ops::Mul for $name {
76			type Output = Self;
77
78			#[inline]
79			fn mul(self, rhs: Self) -> Self {
80				$crate::tracing::trace_multiplication!($name);
81
82				$crate::arithmetic_traits::TaggedMul::<$strategy>::mul(self, rhs)
83			}
84		}
85	};
86	($name:ty => $bigger:ty) => {
87		impl std::ops::Mul for $name {
88			type Output = Self;
89
90			#[inline]
91			fn mul(self, rhs: Self) -> Self {
92				$crate::arch::portable::packed::mul_as_bigger_type::<_, $bigger>(self, rhs)
93			}
94		}
95	};
96}
97
98pub(crate) use impl_mul_with;
99
100/// Square operation that is parameterized with some some strategy.
101pub trait TaggedSquare<Strategy> {
102	fn square(self) -> Self;
103}
104
105macro_rules! impl_square_with {
106	($name:ident @ $strategy:ty) => {
107		impl $crate::arithmetic_traits::Square for $name {
108			#[inline]
109			fn square(self) -> Self {
110				$crate::arithmetic_traits::TaggedSquare::<$strategy>::square(self)
111			}
112		}
113	};
114	($name:ty => $bigger:ty) => {
115		impl $crate::arithmetic_traits::Square for $name {
116			#[inline]
117			fn square(self) -> Self {
118				$crate::arch::portable::packed::square_as_bigger_type::<_, $bigger>(self)
119			}
120		}
121	};
122}
123
124pub(crate) use impl_square_with;
125
126/// Invert or zero operation that is parameterized with some some strategy.
127pub trait TaggedInvertOrZero<Strategy> {
128	fn invert_or_zero(self) -> Self;
129}
130
131macro_rules! impl_invert_with {
132	($name:ident @ $strategy:ty) => {
133		impl $crate::arithmetic_traits::InvertOrZero for $name {
134			#[inline]
135			fn invert_or_zero(self) -> Self {
136				$crate::arithmetic_traits::TaggedInvertOrZero::<$strategy>::invert_or_zero(self)
137			}
138		}
139	};
140	($name:ty => $bigger:ty) => {
141		impl $crate::arithmetic_traits::InvertOrZero for $name {
142			#[inline]
143			fn invert_or_zero(self) -> Self {
144				$crate::arch::portable::packed::invert_as_bigger_type::<_, $bigger>(self)
145			}
146		}
147	};
148}
149
150pub(crate) use impl_invert_with;
binius_field/arithmetic_traits.rs

binius_field/
arithmetic_traits.rs
