kimchi_msm/fec/
lookups.rs

1use crate::{logup::LookupTableID, Logup, LIMB_BITSIZE, N_LIMBS};
2use ark_ff::PrimeField;
3use num_bigint::BigUint;
4use o1_utils::FieldHelpers;
5use std::marker::PhantomData;
6use strum_macros::EnumIter;
7
8/// Enumeration of concrete lookup tables used in FEC circuit.
9#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd, EnumIter)]
10pub enum LookupTable<Ff> {
11    /// x ∈ [0, 2^15]
12    RangeCheck15,
13    /// x ∈ [-2^14, 2^14-1]
14    RangeCheck14Abs,
15    /// x ∈ [-2^9, 2^9-1]
16    RangeCheck9Abs,
17    /// x ∈ [0, ff_highest] where ff_highest is the highest 15-bit
18    /// limb of the modulus of the foreign field `Ff`.
19    RangeCheckFfHighest(PhantomData<Ff>),
20}
21
22impl<Ff: PrimeField> LookupTableID for LookupTable<Ff> {
23    fn to_u32(&self) -> u32 {
24        match self {
25            Self::RangeCheck15 => 1,
26            Self::RangeCheck14Abs => 2,
27            Self::RangeCheck9Abs => 3,
28            Self::RangeCheckFfHighest(_) => 4,
29        }
30    }
31
32    fn from_u32(value: u32) -> Self {
33        match value {
34            1 => Self::RangeCheck15,
35            2 => Self::RangeCheck14Abs,
36            3 => Self::RangeCheck9Abs,
37            4 => Self::RangeCheckFfHighest(PhantomData),
38            _ => panic!("Invalid lookup table id"),
39        }
40    }
41
42    /// All tables are fixed tables.
43    fn is_fixed(&self) -> bool {
44        true
45    }
46
47    fn runtime_create_column(&self) -> bool {
48        panic!("No runtime tables specified");
49    }
50
51    fn length(&self) -> usize {
52        match self {
53            Self::RangeCheck15 => 1 << 15,
54            Self::RangeCheck14Abs => 1 << 15,
55            Self::RangeCheck9Abs => 1 << 10,
56            Self::RangeCheckFfHighest(_) => TryFrom::try_from(
57                crate::serialization::interpreter::ff_modulus_highest_limb::<Ff>(),
58            )
59            .unwrap(),
60        }
61    }
62
63    /// Converts a value to its index in the fixed table.
64    fn ix_by_value<F: PrimeField>(&self, value: &[F]) -> Option<usize> {
65        let value = value[0];
66        assert!(self.is_member(value));
67        Some(match self {
68            Self::RangeCheck15 => TryFrom::try_from(value.to_biguint()).unwrap(),
69            Self::RangeCheck14Abs => {
70                if value < F::from(1u64 << 14) {
71                    TryFrom::try_from(value.to_biguint()).unwrap()
72                } else {
73                    TryFrom::try_from((value + F::from(2 * (1u64 << 14))).to_biguint()).unwrap()
74                }
75            }
76            Self::RangeCheck9Abs => {
77                if value < F::from(1u64 << 9) {
78                    TryFrom::try_from(value.to_biguint()).unwrap()
79                } else {
80                    TryFrom::try_from((value + F::from(2 * (1u64 << 9))).to_biguint()).unwrap()
81                }
82            }
83            Self::RangeCheckFfHighest(_) => TryFrom::try_from(value.to_biguint()).unwrap(),
84        })
85    }
86
87    fn all_variants() -> Vec<Self> {
88        vec![
89            Self::RangeCheck15,
90            Self::RangeCheck14Abs,
91            Self::RangeCheck9Abs,
92            Self::RangeCheckFfHighest(PhantomData),
93        ]
94    }
95}
96
97impl<Ff: PrimeField> LookupTable<Ff> {
98    fn entries_ff_highest<F: PrimeField>(domain_d1_size: u64) -> Vec<F> {
99        let top_modulus_f =
100            F::from_biguint(&crate::serialization::interpreter::ff_modulus_highest_limb::<Ff>())
101                .unwrap();
102        (0..domain_d1_size)
103            .map(|i| {
104                if F::from(i) < top_modulus_f {
105                    F::from(i)
106                } else {
107                    F::zero()
108                }
109            })
110            .collect()
111    }
112
113    /// Provides a full list of entries for the given table.
114    pub fn entries<F: PrimeField>(&self, domain_d1_size: u64) -> Vec<F> {
115        assert!(domain_d1_size >= (1 << 15));
116        match self {
117            Self::RangeCheck15 => (0..domain_d1_size).map(|i| F::from(i)).collect(),
118            Self::RangeCheck14Abs => (0..domain_d1_size)
119                .map(|i| {
120                    if i < (1 << 14) {
121                        F::from(i)
122                    } else if i < 2 * (1 << 14) {
123                        F::from(i) - F::from(2u64 * (1 << 14))
124                    } else {
125                        F::zero()
126                    }
127                })
128                .collect(),
129            Self::RangeCheck9Abs => (0..domain_d1_size)
130                .map(|i| {
131                    if i < (1 << 9) {
132                        // [0,1,2 ... (1<<9)-1]
133                        F::from(i)
134                    } else if i < 2 * (1 << 9) {
135                        // [-(i<<9),...-2,-1]
136                        F::from(i) - F::from(2u64 * (1 << 9))
137                    } else {
138                        F::zero()
139                    }
140                })
141                .collect(),
142            Self::RangeCheckFfHighest(_) => Self::entries_ff_highest::<F>(domain_d1_size),
143        }
144    }
145
146    /// Checks if a value is in a given table.
147    pub fn is_member<F: PrimeField>(&self, value: F) -> bool {
148        match self {
149            Self::RangeCheck15 => value.to_biguint() < BigUint::from(2u128.pow(15)),
150            Self::RangeCheck14Abs => {
151                value < F::from(1u64 << 14) || value >= F::zero() - F::from(1u64 << 14)
152            }
153            Self::RangeCheck9Abs => {
154                value < F::from(1u64 << 9) || value >= F::zero() - F::from(1u64 << 9)
155            }
156            Self::RangeCheckFfHighest(_) => {
157                let f_bui: BigUint = TryFrom::try_from(Ff::MODULUS).unwrap();
158                let top_modulus_f: F =
159                    F::from_biguint(&(f_bui >> ((N_LIMBS - 1) * LIMB_BITSIZE))).unwrap();
160                value < top_modulus_f
161            }
162        }
163    }
164}
165
166pub type Lookup<F, Ff> = Logup<F, LookupTable<Ff>>;
kimchi_msm/fec/lookups.rs

kimchi_msm/fec/
lookups.rs
