1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

use crate::logup::LookupTableID;
use ark_ff::PrimeField;
use num_bigint::BigUint;
use o1_utils::FieldHelpers;
use strum_macros::EnumIter;

/// Enumeration of concrete lookup tables used in lookups circuit.
#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd, EnumIter)]
pub enum LookupTable {
    /// x ∈ [0, 2^15]
    RangeCheck15,
    /// x ∈ [-1, 0, 1]
    RangeCheck1BitSigned,
}

impl LookupTableID for LookupTable {
    fn to_u32(&self) -> u32 {
        match self {
            Self::RangeCheck15 => 1,
            Self::RangeCheck1BitSigned => 2,
        }
    }

    fn from_u32(value: u32) -> Self {
        match value {
            1 => Self::RangeCheck15,
            2 => Self::RangeCheck1BitSigned,
            _ => panic!("Invalid lookup table id"),
        }
    }

    /// All tables are fixed tables.
    fn is_fixed(&self) -> bool {
        true
    }

    fn runtime_create_column(&self) -> bool {
        panic!("No runtime tables specified");
    }

    fn length(&self) -> usize {
        match self {
            Self::RangeCheck15 => 1 << 15,
            Self::RangeCheck1BitSigned => 3,
        }
    }

    /// Converts a value to its index in the fixed table.
    fn ix_by_value<F: PrimeField>(&self, value: &[F]) -> Option<usize> {
        let value = value[0];
        Some(match self {
            Self::RangeCheck15 => TryFrom::try_from(value.to_biguint()).unwrap(),
            Self::RangeCheck1BitSigned => {
                if value == F::zero() {
                    0
                } else if value == F::one() {
                    1
                } else if value == F::zero() - F::one() {
                    2
                } else {
                    panic!("Invalid value for rangecheck1abs")
                }
            }
        })
    }

    fn all_variants() -> Vec<Self> {
        vec![Self::RangeCheck15, Self::RangeCheck1BitSigned]
    }
}

impl LookupTable {
    /// Provides a full list of entries for the given table.
    pub fn entries<F: PrimeField>(&self, domain_d1_size: u64) -> Vec<F> {
        assert!(domain_d1_size >= (1 << 15));
        match self {
            Self::RangeCheck1BitSigned => [F::zero(), F::one(), F::zero() - F::one()]
                .into_iter()
                .chain((3..domain_d1_size).map(|_| F::one())) // dummies are 1s
                .collect(),
            Self::RangeCheck15 => (0..domain_d1_size).map(|i| F::from(i)).collect(),
        }
    }

    /// Checks if a value is in a given table.
    pub fn is_member<F: PrimeField>(&self, value: F) -> bool {
        match self {
            Self::RangeCheck1BitSigned => {
                value == F::zero() || value == F::one() || value == F::zero() - F::one()
            }
            Self::RangeCheck15 => value.to_biguint() < BigUint::from(2u128.pow(15)),
        }
    }
}