kimchi/circuits/lookup/tables/
xor.rs

1use crate::circuits::lookup::tables::{LookupTable, XOR_TABLE_ID};
2use ark_ff::Field;
3
4//~ The lookup table for 4-bit xor.
5//~ Note that it is constructed so that `(0, 0, 0)` is the last position in the table.
6//~
7//~ This is because tables are extended to the full size of a column (essentially)
8//~ by padding them with their final value. And, having the value `(0, 0, 0)` here means
9//~ that when we commit to this table and use the dummy value in the `lookup_sorted`
10//~ columns, those entries that have the dummy value of
11//~
12//~ $$0 = 0 + j*0 + j^2*0$$
13//~
14//~ will translate into a scalar multiplication by 0, which is free.
15
16/// Returns the XOR lookup table
17///
18/// # Panics
19///
20/// Will panic if `data` is invalid.
21pub fn xor_table<F: Field>() -> LookupTable<F> {
22    let mut data = vec![vec![]; 3];
23
24    // XOR for all possible four-bit arguments.
25    // I suppose this could be computed a bit faster using symmetry but it's quite
26    // small (16*16 = 256 entries) so let's just keep it simple.
27    for i in 0u32..=0b1111 {
28        for j in 0u32..=0b1111 {
29            data[0].push(F::from(i));
30            data[1].push(F::from(j));
31            data[2].push(F::from(i ^ j));
32        }
33    }
34
35    for r in &mut data {
36        r.reverse();
37        // Just to be safe.
38        assert!(r[r.len() - 1].is_zero());
39    }
40    LookupTable {
41        id: XOR_TABLE_ID,
42        data,
43    }
44}
45
46pub const TABLE_SIZE: usize = 256;
kimchi/circuits/lookup/tables/xor.rs

kimchi/circuits/lookup/tables/
xor.rs
