binius_field/underlier/
underlier_type.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{
5	fmt::Debug,
6	ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not},
7};
8
9use bytemuck::{NoUninit, TransparentWrapper, Zeroable};
10
11use super::U1;
12use crate::{Divisible, Random};
13
14/// Primitive integer underlying a binary field or packed binary field implementation.
15/// Note that this type is not guaranteed to be POD, U1, U2 and U4 have some unused bits.
16pub trait UnderlierType:
17	Debug
18	+ Default
19	+ Eq
20	+ Ord
21	+ Copy
22	+ Random
23	+ NoUninit
24	+ Zeroable
25	+ Sized
26	+ Send
27	+ Sync
28	+ 'static
29	+ BitAnd<Self, Output = Self>
30	+ BitAndAssign<Self>
31	+ BitOr<Self, Output = Self>
32	+ BitOrAssign<Self>
33	+ BitXor<Self, Output = Self>
34	+ BitXorAssign<Self>
35	+ Not<Output = Self>
36	+ Divisible<U1>
37{
38	/// Number of bits in value
39	const LOG_BITS: usize;
40	/// Number of bits used to represent a value.
41	/// This may not be equal to the number of bits in a type instance.
42	const BITS: usize = 1 << Self::LOG_BITS;
43
44	const ZERO: Self;
45	const ONE: Self;
46	const ONES: Self;
47
48	/// Fill value with the given bit
49	/// `val` must be 0 or 1.
50	fn fill_with_bit(val: u8) -> Self {
51		Self::broadcast_subvalue(U1::new(val))
52	}
53
54	/// Interleave with the given bit size
55	fn interleave(self, other: Self, log_block_len: usize) -> (Self, Self);
56
57	/// Transpose with the given bit size
58	fn transpose(mut self, mut other: Self, log_block_len: usize) -> (Self, Self) {
59		assert!(log_block_len < Self::LOG_BITS);
60
61		for log_block_len in (log_block_len..Self::LOG_BITS).rev() {
62			(self, other) = self.interleave(other, log_block_len);
63		}
64
65		(self, other)
66	}
67
68	#[inline]
69	fn from_fn<T>(f: impl FnMut(usize) -> T) -> Self
70	where
71		T: UnderlierType,
72		Self: Divisible<T>,
73	{
74		Self::from_iter((0..<Self as Divisible<T>>::N).map(f))
75	}
76
77	/// Broadcast subvalue to fill `Self`.
78	/// `Self::BITS/T::BITS` is supposed to be a power of 2.
79	#[inline]
80	fn broadcast_subvalue<T>(value: T) -> Self
81	where
82		T: UnderlierType,
83		Self: Divisible<T>,
84	{
85		Divisible::<T>::broadcast(value)
86	}
87}
88
89/// A type that is transparently backed by an underlier.
90///
91/// This trait is needed to make it possible getting the underlier type from already defined type.
92/// Bidirectional `From` trait implementations are not enough, because they do not allow getting
93/// underlier type in a generic code.
94///
95/// # Safety
96/// `WithUnderlier` can be implemented for a type only if it's representation is a transparent
97/// `Underlier`'s representation. That's allows us casting references of type and it's underlier in
98/// both directions.
99pub unsafe trait WithUnderlier:
100	TransparentWrapper<Self::Underlier> + Sized + Zeroable + Copy + Send + Sync + 'static
101{
102	/// Underlier primitive type
103	type Underlier: UnderlierType;
104
105	/// Convert value to underlier.
106	#[inline]
107	fn to_underlier(self) -> Self::Underlier {
108		Self::peel(self)
109	}
110
111	#[inline]
112	fn to_underlier_ref(&self) -> &Self::Underlier {
113		Self::peel_ref(self)
114	}
115
116	#[inline]
117	fn to_underlier_ref_mut(&mut self) -> &mut Self::Underlier {
118		Self::peel_mut(self)
119	}
120
121	#[inline]
122	fn to_underliers_ref(val: &[Self]) -> &[Self::Underlier] {
123		Self::peel_slice(val)
124	}
125
126	#[inline]
127	fn to_underliers_ref_mut(val: &mut [Self]) -> &mut [Self::Underlier] {
128		Self::peel_slice_mut(val)
129	}
130
131	#[inline]
132	fn from_underlier(val: Self::Underlier) -> Self {
133		Self::wrap(val)
134	}
135
136	#[inline]
137	fn from_underlier_ref(val: &Self::Underlier) -> &Self {
138		Self::wrap_ref(val)
139	}
140
141	#[inline]
142	fn from_underlier_ref_mut(val: &mut Self::Underlier) -> &mut Self {
143		Self::wrap_mut(val)
144	}
145
146	#[inline]
147	fn from_underliers_ref(val: &[Self::Underlier]) -> &[Self] {
148		Self::wrap_slice(val)
149	}
150
151	#[inline]
152	fn from_underliers_ref_mut(val: &mut [Self::Underlier]) -> &mut [Self] {
153		Self::wrap_slice_mut(val)
154	}
155
156	#[inline]
157	fn mutate_underlier(self, f: impl FnOnce(Self::Underlier) -> Self::Underlier) -> Self {
158		Self::from_underlier(f(self.to_underlier()))
159	}
160}
binius_field/underlier/underlier_type.rs

binius_field/underlier/
underlier_type.rs
