sp1_curves/
params.rs

1use std::{
2    fmt::Debug,
3    ops::{Div, Index, IndexMut},
4    slice::Iter,
5};
6
7use serde::{de::DeserializeOwned, Serialize};
8
9use typenum::{Unsigned, U2, U4};
10
11use generic_array::{sequence::GenericSequence, ArrayLength, GenericArray};
12use num::BigUint;
13use sp1_stark::air::Polynomial;
14
15use p3_field::Field;
16
17use crate::utils::biguint_from_limbs;
18
19pub const NB_BITS_PER_LIMB: usize = 8;
20
21/// An array representing N limbs of T.
22///
23/// GenericArray allows us to constrain the correct array lengths so we can have # of limbs and # of
24/// witness limbs associated in NumLimbs / FieldParameters.
25/// See: https://github.com/RustCrypto/traits/issues/1481
26#[derive(Debug, Clone)]
27pub struct Limbs<T, N: ArrayLength>(pub GenericArray<T, N>);
28
29pub trait FieldParameters:
30    Send + Sync + Copy + 'static + Debug + Serialize + DeserializeOwned + NumLimbs
31{
32    const NB_BITS_PER_LIMB: usize = NB_BITS_PER_LIMB;
33    const NB_LIMBS: usize = Self::Limbs::USIZE;
34    const NB_WITNESS_LIMBS: usize = Self::Witness::USIZE;
35    const WITNESS_OFFSET: usize;
36
37    /// The bytes of the modulus in little-endian order.
38    const MODULUS: &'static [u8];
39
40    fn modulus() -> BigUint {
41        biguint_from_limbs(Self::MODULUS)
42    }
43
44    fn nb_bits() -> usize {
45        Self::NB_BITS_PER_LIMB * Self::NB_LIMBS
46    }
47
48    fn modulus_field_iter<F: Field>() -> impl Iterator<Item = F> {
49        Self::MODULUS.iter().map(|x| F::from_canonical_u8(*x)).take(Self::NB_LIMBS)
50    }
51
52    /// Convert a BigUint to a Vec of u8 limbs (with len NB_LIMBS).
53    fn to_limbs(x: &BigUint) -> Vec<u8> {
54        let mut bytes = x.to_bytes_le();
55        bytes.resize(Self::NB_LIMBS, 0u8);
56        bytes
57    }
58
59    /// Convert a BigUint to a Vec of F limbs (with len NB_LIMBS).
60    fn to_limbs_field_vec<E: From<F>, F: Field>(x: &BigUint) -> Vec<E> {
61        Self::to_limbs(x).into_iter().map(|x| F::from_canonical_u8(x).into()).collect::<Vec<_>>()
62    }
63
64    /// Convert a BigUint to Limbs<F, Self::Limbs>.
65    fn to_limbs_field<E: From<F>, F: Field>(x: &BigUint) -> Limbs<E, Self::Limbs> {
66        limbs_from_vec(Self::to_limbs_field_vec(x))
67    }
68}
69
70/// Convert a vec of F limbs to a Limbs of N length.
71pub fn limbs_from_vec<E: From<F>, N: ArrayLength, F: Field>(limbs: Vec<F>) -> Limbs<E, N> {
72    debug_assert_eq!(limbs.len(), N::USIZE);
73    let mut result = GenericArray::<E, N>::generate(|_i| F::zero().into());
74    for (i, limb) in limbs.into_iter().enumerate() {
75        result[i] = limb.into();
76    }
77    Limbs(result)
78}
79
80/// Trait that holds the typenum values for # of limbs and # of witness limbs.
81pub trait NumLimbs: Clone + Debug {
82    type Limbs: ArrayLength + Debug;
83    type Witness: ArrayLength + Debug;
84}
85
86/// Trait that holds number of words needed to represent a field element and a curve point.
87pub trait NumWords: Clone + Debug {
88    /// The number of words needed to represent a field element.
89    type WordsFieldElement: ArrayLength + Debug;
90    /// The number of words needed to represent a curve point (two field elements).
91    type WordsCurvePoint: ArrayLength + Debug;
92}
93
94/// Implement NumWords for NumLimbs where # Limbs is divisible by 4.
95///
96/// Using typenum we can do N/4 and N/2 in type-level arithmetic. Having it as a separate trait
97/// avoids needing the Div where clauses everywhere.
98impl<N: NumLimbs> NumWords for N
99where
100    N::Limbs: Div<U4>,
101    N::Limbs: Div<U2>,
102    <N::Limbs as Div<U4>>::Output: ArrayLength + Debug,
103    <N::Limbs as Div<U2>>::Output: ArrayLength + Debug,
104{
105    /// Each word has 4 limbs so we divide by 4.
106    type WordsFieldElement = <N::Limbs as Div<U4>>::Output;
107    /// Curve point has 2 field elements so we divide by 2.
108    type WordsCurvePoint = <N::Limbs as Div<U2>>::Output;
109}
110
111impl<T: Copy, N: ArrayLength> Copy for Limbs<T, N> where N::ArrayType<T>: Copy {}
112
113impl<T, N: ArrayLength> Default for Limbs<T, N>
114where
115    T: Default + Copy,
116{
117    fn default() -> Self {
118        Self(GenericArray::default())
119    }
120}
121
122impl<T, N: ArrayLength> Index<usize> for Limbs<T, N> {
123    type Output = T;
124
125    fn index(&self, index: usize) -> &Self::Output {
126        &self.0[index]
127    }
128}
129
130impl<T, N: ArrayLength> IndexMut<usize> for Limbs<T, N> {
131    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
132        &mut self.0[index]
133    }
134}
135
136impl<T, N: ArrayLength> IntoIterator for Limbs<T, N> {
137    type Item = T;
138    type IntoIter = <GenericArray<T, N> as IntoIterator>::IntoIter;
139
140    fn into_iter(self) -> Self::IntoIter {
141        self.0.into_iter()
142    }
143}
144
145impl<Var: Into<Expr> + Clone, N: ArrayLength, Expr: Clone> From<Limbs<Var, N>>
146    for Polynomial<Expr>
147{
148    fn from(value: Limbs<Var, N>) -> Self {
149        Polynomial::from_coefficients(&value.0.into_iter().map(|x| x.into()).collect::<Vec<_>>())
150    }
151}
152
153impl<T: Debug + Default + Clone, N: ArrayLength> From<Polynomial<T>> for Limbs<T, N> {
154    fn from(value: Polynomial<T>) -> Self {
155        let inner = value.as_coefficients().try_into().unwrap();
156        Self(inner)
157    }
158}
159
160impl<'a, T: Debug + Default + Clone, N: ArrayLength> From<Iter<'a, T>> for Limbs<T, N> {
161    fn from(value: Iter<'a, T>) -> Self {
162        let vec: Vec<T> = value.cloned().collect();
163        let inner = vec.try_into().unwrap();
164        Self(inner)
165    }
166}
167
168impl<T, N: ArrayLength> FromIterator<T> for Limbs<T, N> {
169    #[inline]
170    fn from_iter<I>(iter: I) -> Limbs<T, N>
171    where
172        I: IntoIterator<Item = T>,
173    {
174        Limbs(GenericArray::from_iter(iter))
175    }
176}
sp1_curves/params.rs

sp1_curves/
params.rs
