zisk-sm-binary 1.1.0-alpha

Binary operations state machine for the ZisK zkVM
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
95
96
97

#![allow(dead_code)]
//! Legacy FROPS (binary extension) — snapshot of `binary_extension_frops.rs` as of commit d978059
//! ("Big opcode refactor"), the last version before the FROPS overhaul.
//!
//! Kept only for comparison: `ziskemu --legacy-frops` uses these membership tests so a new
//! FROPS version can be measured against the previous (legacy) one. The table-generation
//! machinery (build_table / generate_* / fixed .bin) is intentionally omitted — only the pure
//! `is_frequent_op` / `get_row` predicates (and their private offset helpers) remain, so this
//! module depends solely on `ZiskOp`.

use zisk_core::zisk_ops::ZiskOp;

const OP_SIGNEXTENDB: u8 = ZiskOp::SignExtendB.code();
const OP_SIGNEXTENDH: u8 = ZiskOp::SignExtendH.code();
const OP_SIGNEXTENDW: u8 = ZiskOp::SignExtendW.code();
const OP_SLL: u8 = ZiskOp::Sll.code();
const OP_SLLW: u8 = ZiskOp::SllW.code();
const OP_SRA: u8 = ZiskOp::Sra.code();
const OP_SRL: u8 = ZiskOp::Srl.code();
const OP_SRAW: u8 = ZiskOp::SraW.code();
const OP_SRLW: u8 = ZiskOp::SrlW.code();

const MAX_A_LOW_VALUE: u64 = 386;
const MAX_B_LOW_VALUE: u64 = 386;
const LOW_VALUE_SIZE: usize = MAX_A_LOW_VALUE as usize * MAX_B_LOW_VALUE as usize;
const MAX_U64: u64 = 0xFFFF_FFFF_FFFF_FFFF;

const SLR_MASK_FROM: u64 = 0xFFFF_FFFF_FFFF_F000;
const SLR_TO_B: u64 = 64;

// table autogenerated with FrequentOpsTable::print_table_offsets()
// this table is used to calculate the offset (row) of each operation
const OP_TABLE_OFFSETS_START: usize = 33;
const OP_TABLE_OFFSETS: [usize; 9] =
    [0, 148996, 564232, 713228, 862224, 1011220, 1160216, 1309212, 1458208];

#[derive(Debug, Clone, Default)]
pub struct BinaryExtensionLegacyFrops;

impl BinaryExtensionLegacyFrops {
    pub const NO_FROPS: usize = usize::MAX;

    #[inline(always)]
    fn is_frequent_srl(a: u64, b: u64) -> bool {
        (a < MAX_A_LOW_VALUE && b < MAX_B_LOW_VALUE) || (a >= SLR_MASK_FROM && b <= SLR_TO_B)
    }
    #[inline(always)]
    fn get_srl_offset(a: u64, b: u64) -> usize {
        if a < MAX_A_LOW_VALUE && b < MAX_B_LOW_VALUE {
            Self::get_low_values_offset(a, b)
        } else if a >= SLR_MASK_FROM && b <= SLR_TO_B {
            LOW_VALUE_SIZE + ((a - SLR_MASK_FROM) * (SLR_TO_B + 1) + b) as usize
        } else {
            Self::NO_FROPS
        }
    }

    #[inline(always)]
    fn get_low_values_offset(a: u64, b: u64) -> usize {
        (a * MAX_B_LOW_VALUE + b) as usize
    }

    #[inline(always)]
    pub fn is_frequent_op(op: u8, a: u64, b: u64) -> bool {
        // Use lookup table for faster branching instead of match on enum
        match op {
            // Low value operations - check bounds first (most common case)
            OP_SIGNEXTENDB | OP_SIGNEXTENDH | OP_SIGNEXTENDW | OP_SLL | OP_SLLW | OP_SRA
            | OP_SRAW | OP_SRLW => a < MAX_A_LOW_VALUE && b < MAX_B_LOW_VALUE,
            // Special cases - inline the logic to avoid function calls
            OP_SRL => Self::is_frequent_srl(a, b),
            _ => false,
        }
    }

    #[inline(always)]
    pub fn get_row(op: u8, a: u64, b: u64) -> usize {
        // ecall/system call functions are not candidates to be usual
        let relative_offset = match op {
            OP_SIGNEXTENDB | OP_SIGNEXTENDH | OP_SIGNEXTENDW | OP_SLL | OP_SLLW | OP_SRA
            | OP_SRAW | OP_SRLW => {
                if a < MAX_A_LOW_VALUE && b < MAX_B_LOW_VALUE {
                    Self::get_low_values_offset(a, b)
                } else {
                    Self::NO_FROPS
                }
            }
            OP_SRL => Self::get_srl_offset(a, b),
            _ => Self::NO_FROPS,
        };
        if relative_offset == Self::NO_FROPS {
            Self::NO_FROPS
        } else {
            relative_offset + OP_TABLE_OFFSETS[op as usize - OP_TABLE_OFFSETS_START]
        }
    }
}