zkevm_circuits 0.153.12

ZKsync Era circuits for EraVM
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

use super::*;

use boojum::cs::implementations::lookup_table::LookupTable;
use boojum::field::SmallField;

const TABLE_NAME: &'static str = "WNAFDECOMP table";

#[derive(Derivative)]
#[derivative(Clone, Copy, Debug, PartialEq, Eq)]
pub struct WnafDecompTable;

pub const WNAF_WINDOW_SIZE: usize = 2;
pub const WNAF_TABLE_SIZE: i8 = 1 << (WNAF_WINDOW_SIZE + 1);
const HALF_TABLE_SIZE: i8 = 1 << WNAF_WINDOW_SIZE;
const MASK_FOR_MOD_TABLE_SIZE: u8 = (WNAF_TABLE_SIZE as u8) - 1;

// Lookups for wNAF decomposition of scalars.
pub fn create_wnaf_decomp_table<F: SmallField>() -> LookupTable<F, 3> {
    let mut all_keys = Vec::with_capacity(1 << 8);
    for a in 0..=u8::MAX {
        let key = smallvec::smallvec![F::from_u64_unchecked(a as u64)];
        all_keys.push(key);
    }
    LookupTable::new_from_keys_and_generation_function(
        &all_keys,
        TABLE_NAME.to_string(),
        1,
        |keys| {
            let mut a = keys[0].as_u64_reduced() as u8;
            let mut v = Vec::with_capacity(4);
            let mut carry_bit = false;
            for _ in 0..2 {
                if a % 2 == 1 {
                    let mut naf = (a & MASK_FOR_MOD_TABLE_SIZE) as i8;
                    if naf >= HALF_TABLE_SIZE {
                        naf -= WNAF_TABLE_SIZE
                    };

                    let naf_abs = naf.abs() as u8;
                    if naf < 0 {
                        if carry_bit {
                            a += naf_abs;
                        } else {
                            (a, carry_bit) = a.overflowing_add(naf_abs);
                        }
                    } else {
                        a -= naf_abs;
                    }
                    v.push(naf);
                } else {
                    v.push(0i8);
                }

                a >>= 1;
            }

            let concat = {
                let mut res = 0u32;
                res |= (v[0] as u8) as u32;
                let shifted_v1 = ((v[1] as u8) as u32) << 8;
                res |= shifted_v1;
                // Add carry bit if we overflowed
                if carry_bit {
                    res |= 1 << 16;
                }
                res
            };
            smallvec::smallvec![
                F::from_u64_unchecked(concat as u64),
                F::from_u64_unchecked(a as u64)
            ]
        },
    )
}