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