kimchi_msm/serialization/
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 serialization 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 ∈ [0, 2^4]
14    RangeCheck4,
15    /// x ∈ [-2^14, 2^14-1]
16    RangeCheck14Abs,
17    /// x ∈ [-2^4, 2^4-1]
18    RangeCheck9Abs,
19    /// x ∈ [0, ff_highest] where ff_highest is the highest 15-bit
20    /// limb of the modulus of the foreign field `Ff`.
21    RangeCheckFfHighest(PhantomData<Ff>),
22    /// Communication bus for the multiplication circuit.
23    MultiplicationBus,
24}
25
26impl<Ff: PrimeField> LookupTableID for LookupTable<Ff> {
27    fn to_u32(&self) -> u32 {
28        match self {
29            Self::RangeCheck15 => 1,
30            Self::RangeCheck4 => 2,
31            Self::RangeCheck14Abs => 3,
32            Self::RangeCheck9Abs => 4,
33            Self::RangeCheckFfHighest(_) => 5,
34            Self::MultiplicationBus => 6,
35        }
36    }
37
38    fn from_u32(value: u32) -> Self {
39        match value {
40            1 => Self::RangeCheck15,
41            2 => Self::RangeCheck4,
42            3 => Self::RangeCheck14Abs,
43            4 => Self::RangeCheck9Abs,
44            5 => Self::RangeCheckFfHighest(PhantomData),
45            6 => Self::MultiplicationBus,
46            _ => panic!("Invalid lookup table id"),
47        }
48    }
49
50    fn is_fixed(&self) -> bool {
51        match self {
52            Self::RangeCheck15 => true,
53            Self::RangeCheck4 => true,
54            Self::RangeCheck14Abs => true,
55            Self::RangeCheck9Abs => true,
56            Self::RangeCheckFfHighest(_) => true,
57            Self::MultiplicationBus => false,
58        }
59    }
60
61    fn runtime_create_column(&self) -> bool {
62        match self {
63            Self::MultiplicationBus => false,
64            _ => panic!("runtime_create_column was called on a non-runtime table"),
65        }
66    }
67
68    fn length(&self) -> usize {
69        match self {
70            Self::RangeCheck15 => 1 << 15,
71            Self::RangeCheck4 => 1 << 4,
72            Self::RangeCheck14Abs => 1 << 15,
73            Self::RangeCheck9Abs => 1 << 10,
74            Self::RangeCheckFfHighest(_) => TryFrom::try_from(
75                crate::serialization::interpreter::ff_modulus_highest_limb::<Ff>(),
76            )
77            .unwrap(),
78            Self::MultiplicationBus => 1 << 15,
79        }
80    }
81
82    /// Converts a value to its index in the fixed table.
83    fn ix_by_value<F: PrimeField>(&self, value: &[F]) -> Option<usize> {
84        let value = value[0];
85        if self.is_fixed() {
86            assert!(self.is_member(value).unwrap());
87        }
88
89        match self {
90            Self::RangeCheck15 => Some(TryFrom::try_from(value.to_biguint()).unwrap()),
91            Self::RangeCheck4 => Some(TryFrom::try_from(value.to_biguint()).unwrap()),
92            Self::RangeCheck14Abs => {
93                if value < F::from(1u64 << 14) {
94                    Some(TryFrom::try_from(value.to_biguint()).unwrap())
95                } else {
96                    Some(
97                        TryFrom::try_from((value + F::from(2 * (1u64 << 14))).to_biguint())
98                            .unwrap(),
99                    )
100                }
101            }
102            Self::RangeCheck9Abs => {
103                if value < F::from(1u64 << 9) {
104                    Some(TryFrom::try_from(value.to_biguint()).unwrap())
105                } else {
106                    Some(
107                        TryFrom::try_from((value + F::from(2 * (1u64 << 9))).to_biguint()).unwrap(),
108                    )
109                }
110            }
111            Self::RangeCheckFfHighest(_) => Some(TryFrom::try_from(value.to_biguint()).unwrap()),
112            Self::MultiplicationBus => None,
113        }
114    }
115
116    fn all_variants() -> Vec<Self> {
117        vec![
118            Self::RangeCheck15,
119            Self::RangeCheck4,
120            Self::RangeCheck14Abs,
121            Self::RangeCheck9Abs,
122            Self::RangeCheckFfHighest(PhantomData),
123            Self::MultiplicationBus,
124        ]
125    }
126}
127
128impl<Ff: PrimeField> LookupTable<Ff> {
129    fn entries_ff_highest<F: PrimeField>(domain_d1_size: u64) -> Vec<F> {
130        let top_modulus_f =
131            F::from_biguint(&crate::serialization::interpreter::ff_modulus_highest_limb::<Ff>())
132                .unwrap();
133        (0..domain_d1_size)
134            .map(|i| {
135                if F::from(i) < top_modulus_f {
136                    F::from(i)
137                } else {
138                    F::zero()
139                }
140            })
141            .collect()
142    }
143
144    /// Provides a full list of entries for the given table.
145    pub fn entries<F: PrimeField>(&self, domain_d1_size: u64) -> Option<Vec<F>> {
146        assert!(domain_d1_size >= (1 << 15));
147        match self {
148            Self::RangeCheck15 => Some((0..domain_d1_size).map(|i| F::from(i)).collect()),
149            Self::RangeCheck4 => Some(
150                (0..domain_d1_size)
151                    .map(|i| if i < (1 << 4) { F::from(i) } else { F::zero() })
152                    .collect(),
153            ),
154            Self::RangeCheck14Abs => Some(
155                (0..domain_d1_size)
156                    .map(|i| {
157                        if i < (1 << 14) {
158                            // [0,1,2 ... (1<<14)-1]
159                            F::from(i)
160                        } else if i < 2 * (1 << 14) {
161                            // [-(i<<14),...-2,-1]
162                            F::from(i) - F::from(2u64 * (1 << 14))
163                        } else {
164                            F::zero()
165                        }
166                    })
167                    .collect(),
168            ),
169
170            Self::RangeCheck9Abs => Some(
171                (0..domain_d1_size)
172                    .map(|i| {
173                        if i < (1 << 9) {
174                            // [0,1,2 ... (1<<9)-1]
175                            F::from(i)
176                        } else if i < 2 * (1 << 9) {
177                            // [-(i<<9),...-2,-1]
178                            F::from(i) - F::from(2u64 * (1 << 9))
179                        } else {
180                            F::zero()
181                        }
182                    })
183                    .collect(),
184            ),
185            Self::RangeCheckFfHighest(_) => Some(Self::entries_ff_highest::<F>(domain_d1_size)),
186            _ => panic!("not possible"),
187        }
188    }
189
190    /// Checks if a value is in a given table.
191    pub fn is_member<F: PrimeField>(&self, value: F) -> Option<bool> {
192        match self {
193            Self::RangeCheck15 => Some(value.to_biguint() < BigUint::from(2u128.pow(15))),
194            Self::RangeCheck4 => Some(value.to_biguint() < BigUint::from(2u128.pow(4))),
195            Self::RangeCheck14Abs => {
196                Some(value < F::from(1u64 << 14) || value >= F::zero() - F::from(1u64 << 14))
197            }
198            Self::RangeCheck9Abs => {
199                Some(value < F::from(1u64 << 9) || value >= F::zero() - F::from(1u64 << 9))
200            }
201            Self::RangeCheckFfHighest(_) => {
202                let f_bui: BigUint = TryFrom::try_from(Ff::MODULUS).unwrap();
203                let top_modulus_f: F =
204                    F::from_biguint(&(f_bui >> ((N_LIMBS - 1) * LIMB_BITSIZE))).unwrap();
205                Some(value < top_modulus_f)
206            }
207            Self::MultiplicationBus => None,
208        }
209    }
210}
211
212pub type Lookup<F, Ff> = Logup<F, LookupTable<Ff>>;
kimchi_msm/serialization/lookups.rs

kimchi_msm/serialization/
lookups.rs
