kimchi_msm/ffa/
lookups.rs

1use crate::logup::LookupTableID;
2use ark_ff::PrimeField;
3use num_bigint::BigUint;
4use o1_utils::FieldHelpers;
5use strum_macros::EnumIter;
6
7/// Enumeration of concrete lookup tables used in lookups circuit.
8#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd, EnumIter)]
9pub enum LookupTable {
10    /// x ∈ [0, 2^15]
11    RangeCheck15,
12    /// x ∈ [-1, 0, 1]
13    RangeCheck1BitSigned,
14}
15
16impl LookupTableID for LookupTable {
17    fn to_u32(&self) -> u32 {
18        match self {
19            Self::RangeCheck15 => 1,
20            Self::RangeCheck1BitSigned => 2,
21        }
22    }
23
24    fn from_u32(value: u32) -> Self {
25        match value {
26            1 => Self::RangeCheck15,
27            2 => Self::RangeCheck1BitSigned,
28            _ => panic!("Invalid lookup table id"),
29        }
30    }
31
32    /// All tables are fixed tables.
33    fn is_fixed(&self) -> bool {
34        true
35    }
36
37    fn runtime_create_column(&self) -> bool {
38        panic!("No runtime tables specified");
39    }
40
41    fn length(&self) -> usize {
42        match self {
43            Self::RangeCheck15 => 1 << 15,
44            Self::RangeCheck1BitSigned => 3,
45        }
46    }
47
48    /// Converts a value to its index in the fixed table.
49    fn ix_by_value<F: PrimeField>(&self, value: &[F]) -> Option<usize> {
50        let value = value[0];
51        Some(match self {
52            Self::RangeCheck15 => TryFrom::try_from(value.to_biguint()).unwrap(),
53            Self::RangeCheck1BitSigned => {
54                if value == F::zero() {
55                    0
56                } else if value == F::one() {
57                    1
58                } else if value == F::zero() - F::one() {
59                    2
60                } else {
61                    panic!("Invalid value for rangecheck1abs")
62                }
63            }
64        })
65    }
66
67    fn all_variants() -> Vec<Self> {
68        vec![Self::RangeCheck15, Self::RangeCheck1BitSigned]
69    }
70}
71
72impl LookupTable {
73    /// Provides a full list of entries for the given table.
74    pub fn entries<F: PrimeField>(&self, domain_d1_size: u64) -> Vec<F> {
75        assert!(domain_d1_size >= (1 << 15));
76        match self {
77            Self::RangeCheck1BitSigned => [F::zero(), F::one(), F::zero() - F::one()]
78                .into_iter()
79                .chain((3..domain_d1_size).map(|_| F::one())) // dummies are 1s
80                .collect(),
81            Self::RangeCheck15 => (0..domain_d1_size).map(|i| F::from(i)).collect(),
82        }
83    }
84
85    /// Checks if a value is in a given table.
86    pub fn is_member<F: PrimeField>(&self, value: F) -> bool {
87        match self {
88            Self::RangeCheck1BitSigned => {
89                value == F::zero() || value == F::one() || value == F::zero() - F::one()
90            }
91            Self::RangeCheck15 => value.to_biguint() < BigUint::from(2u128.pow(15)),
92        }
93    }
94}
kimchi_msm/ffa/lookups.rs

kimchi_msm/ffa/
lookups.rs
