plonky2/gadgets/
lookup.rs

1#[cfg(not(feature = "std"))]
2use alloc::{borrow::ToOwned, vec};
3
4use crate::field::extension::Extendable;
5use crate::gates::lookup::LookupGate;
6use crate::gates::lookup_table::{LookupTable, LookupTableGate};
7use crate::gates::noop::NoopGate;
8use crate::hash::hash_types::RichField;
9use crate::iop::target::Target;
10use crate::plonk::circuit_builder::CircuitBuilder;
11
12/// Lookup tables used in the tests and benchmarks.
13///
14/// The following table was taken from the Tip5 paper.
15pub const TIP5_TABLE: [u16; 256] = [
16    0, 7, 26, 63, 124, 215, 85, 254, 214, 228, 45, 185, 140, 173, 33, 240, 29, 177, 176, 32, 8,
17    110, 87, 202, 204, 99, 150, 106, 230, 14, 235, 128, 213, 239, 212, 138, 23, 130, 208, 6, 44,
18    71, 93, 116, 146, 189, 251, 81, 199, 97, 38, 28, 73, 179, 95, 84, 152, 48, 35, 119, 49, 88,
19    242, 3, 148, 169, 72, 120, 62, 161, 166, 83, 175, 191, 137, 19, 100, 129, 112, 55, 221, 102,
20    218, 61, 151, 237, 68, 164, 17, 147, 46, 234, 203, 216, 22, 141, 65, 57, 123, 12, 244, 54, 219,
21    231, 96, 77, 180, 154, 5, 253, 133, 165, 98, 195, 205, 134, 245, 30, 9, 188, 59, 142, 186, 197,
22    181, 144, 92, 31, 224, 163, 111, 74, 58, 69, 113, 196, 67, 246, 225, 10, 121, 50, 60, 157, 90,
23    122, 2, 250, 101, 75, 178, 159, 24, 36, 201, 11, 243, 132, 198, 190, 114, 233, 39, 52, 21, 209,
24    108, 238, 91, 187, 18, 104, 194, 37, 153, 34, 200, 143, 126, 155, 236, 118, 64, 80, 172, 89,
25    94, 193, 135, 183, 86, 107, 252, 13, 167, 206, 136, 220, 207, 103, 171, 160, 76, 182, 227, 217,
26    158, 56, 174, 4, 66, 109, 139, 162, 184, 211, 249, 47, 125, 232, 117, 43, 16, 42, 127, 20, 241,
27    25, 149, 105, 156, 51, 53, 168, 145, 247, 223, 79, 78, 226, 15, 222, 82, 115, 70, 210, 27, 41,
28    1, 170, 40, 131, 192, 229, 248, 255,
29];
30
31/// This is a table with 256 arbitrary values.
32pub const OTHER_TABLE: [u16; 256] = [
33    2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7,
34    0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10,
35    19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216,
36    247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57,
37    126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3,
38    9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35,
39    10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45,
40    216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39,
41    57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25,
42    3, 9, 7, 0, 3, 25, 35, 10, 19, 36, 45, 216, 247, 35, 39, 57, 126, 2, 6, 25, 3, 9, 7, 0, 3, 25,
43    35, 10, 19, 36, 45, 216, 247,
44];
45
46/// This is a smaller lookup table with arbitrary values.
47pub const SMALLER_TABLE: [u16; 8] = [2, 24, 56, 100, 128, 16, 20, 49];
48
49impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilder<F, D> {
50    /// Adds a lookup table to the list of stored lookup tables `self.luts` based on a table of (input, output) pairs. It returns the index of the LUT within `self.luts`.
51    pub fn add_lookup_table_from_pairs(&mut self, table: LookupTable) -> usize {
52        self.update_luts_from_pairs(table)
53    }
54
55    /// Adds a lookup table to the list of stored lookup tables `self.luts` based on a table, represented as a slice `&[u16]` of inputs and a slice `&[u16]` of outputs. It returns the index of the LUT within `self.luts`.
56    pub fn add_lookup_table_from_table(&mut self, inps: &[u16], outs: &[u16]) -> usize {
57        self.update_luts_from_table(inps, outs)
58    }
59
60    /// Adds a lookup table to the list of stored lookup tables `self.luts` based on a function. It returns the index of the LUT within `self.luts`.
61    pub fn add_lookup_table_from_fn(&mut self, f: fn(u16) -> u16, inputs: &[u16]) -> usize {
62        self.update_luts_from_fn(f, inputs)
63    }
64
65    /// Adds a lookup (input, output) pair to the stored lookups. Takes a `Target` input and returns a `Target` output.
66    pub fn add_lookup_from_index(&mut self, looking_in: Target, lut_index: usize) -> Target {
67        assert!(
68            lut_index < self.get_luts_length(),
69            "lut number {} not in luts (length = {})",
70            lut_index,
71            self.get_luts_length()
72        );
73        let looking_out = self.add_virtual_target();
74        self.update_lookups(looking_in, looking_out, lut_index);
75        looking_out
76    }
77
78    /// We call this function at the end of circuit building right before the PI gate to add all `LookupTableGate` and `LookupGate`.
79    /// It also updates `self.lookup_rows` accordingly.
80    pub fn add_all_lookups(&mut self) {
81        for lut_index in 0..self.num_luts() {
82            assert!(
83                !self.get_lut_lookups(lut_index).is_empty(),
84                "LUT number {:?} is unused",
85                lut_index
86            );
87            if !self.get_lut_lookups(lut_index).is_empty() {
88                // Create LU gates. Connect them to the stored lookups.
89                let last_lu_gate = self.num_gates();
90
91                let lut = self.get_lut(lut_index);
92
93                let lookups = self.get_lut_lookups(lut_index).to_owned();
94
95                let gate = LookupGate::new_from_table(&self.config, lut.clone());
96                let num_slots = LookupGate::num_slots(&self.config);
97
98                // Given the number of lookups and the number of slots for each gate, it is possible
99                // to compute the number of gates that will employ all their slots; such gates can
100                // can be instantiated with `add_gate` rather than being instantiated slot by slot
101
102                // lookup_iter will iterate over the lookups that can be placed in fully utilized
103                // gates, splitting them in chunks that can be placed in the same `LookupGate`
104                let lookup_iter = lookups.chunks_exact(num_slots);
105                // `last_chunk` will contain the remainder of lookups, which cannot fill all the
106                // slots of a `LookupGate`; this last chunk will be processed by incrementally
107                // filling slots, to avoid that the `LookupGenerator` is run on unused slots
108                let last_chunk = lookup_iter.remainder();
109                // handle chunks that can fill all the slots of a `LookupGate`
110                lookup_iter.for_each(|chunk| {
111                    let row = self.add_gate(gate.clone(), vec![]);
112                    for (i, (looking_in, looking_out)) in chunk.iter().enumerate() {
113                        let gate_in = Target::wire(row, LookupGate::wire_ith_looking_inp(i));
114                        let gate_out = Target::wire(row, LookupGate::wire_ith_looking_out(i));
115                        self.connect(gate_in, *looking_in);
116                        self.connect(gate_out, *looking_out);
117                    }
118                });
119                // deal with the last chunk
120                for (looking_in, looking_out) in last_chunk.iter() {
121                    let (gate, i) =
122                        self.find_slot(gate.clone(), &[F::from_canonical_usize(lut_index)], &[]);
123                    let gate_in = Target::wire(gate, LookupGate::wire_ith_looking_inp(i));
124                    let gate_out = Target::wire(gate, LookupGate::wire_ith_looking_out(i));
125                    self.connect(gate_in, *looking_in);
126                    self.connect(gate_out, *looking_out);
127                }
128
129                // Create LUT gates. Nothing is connected to them.
130                let last_lut_gate = self.num_gates();
131                let num_lut_entries = LookupTableGate::num_slots(&self.config);
132                let num_lut_rows = (self.get_luts_idx_length(lut_index) - 1) / num_lut_entries + 1;
133                let gate =
134                    LookupTableGate::new_from_table(&self.config, lut.clone(), last_lut_gate);
135                // Also instances of `LookupTableGate` can be placed with the `add_gate` function
136                // rather than being instantiated slot by slot; note that in this case there is no
137                // need to separately handle the last chunk of LUT entries that cannot fill all the
138                // slots of a `LookupTableGate`, as the generator already handles empty slots
139                for _ in 0..num_lut_rows {
140                    self.add_gate(gate.clone(), vec![]);
141                }
142
143                let first_lut_gate = self.num_gates() - 1;
144
145                // Will ensure the next row's wires will be all zeros. With this, there is no distinction between the transition constraints on the first row
146                // and on the other rows. Additionally, initial constraints become a simple zero check.
147                self.add_gate(NoopGate, vec![]);
148
149                // These elements are increasing: the gate rows are deliberately upside down.
150                // This is necessary for constraint evaluation so that you do not need values of the next
151                // row's wires, which aren't provided in the evaluation variables.
152                self.add_lookup_rows(last_lu_gate, last_lut_gate, first_lut_gate);
153            }
154        }
155    }
156}
plonky2/gadgets/lookup.rs

plonky2/gadgets/
lookup.rs
