miden-processor 0.22.1

Miden VM processor
Documentation 
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use super::{ColMatrix, Felt, LookupTableRow};

// PROCESSOR RANGE CHECKS
// ================================================================================================

/// A struct containing all the range check lookups requested by user operations at a single clock
/// cycle, grouped by the processor performing the lookup.
#[derive(Debug, Clone)]
pub struct CycleRangeChecks {
    memory: Option<RangeCheckRequest>,
    stack: Option<RangeCheckRequest>,
}

impl CycleRangeChecks {
    // CONSTRUCTORS
    // --------------------------------------------------------------------------------------------

    /// Creates a new set of cycle range checks from range checks requested by the Memory processor.
    pub fn new_from_memory(values: &[u16; 2]) -> Self {
        Self {
            stack: None,
            memory: Some(RangeCheckRequest::Memory([Felt::from(values[0]), Felt::from(values[1])])),
        }
    }

    /// Creates a new set of cycle range checks from range checks requested by the Stack processor.
    pub fn new_from_stack(values: &[u16; 4]) -> Self {
        Self {
            memory: None,
            stack: Some(RangeCheckRequest::Stack([
                Felt::from(values[0]),
                Felt::from(values[1]),
                Felt::from(values[2]),
                Felt::from(values[3]),
            ])),
        }
    }

    // STATE MUTATORS
    // --------------------------------------------------------------------------------------------

    /// Adds a set of range checks requested by memory to an existing set of cycle range checks. It
    /// is assumed that the existing instance does not already contain checks from Memory.
    pub fn add_memory_checks(&mut self, values: &[u16]) {
        debug_assert_eq!(self.memory, None);
        self.memory =
            Some(RangeCheckRequest::Memory([Felt::from(values[0]), Felt::from(values[1])]));
    }

    // ACCESSORS
    // --------------------------------------------------------------------------------------------

    /// Reduces all range checks requested at this cycle by the Stack processor to a single field
    /// element in the field specified by E.
    pub fn to_stack_value<E: ExtensionField<Felt>>(
        &self,
        main_trace: &MainTrace,
        alphas: &[E],
    ) -> E {
        let mut value = E::ONE;

        if let Some(stack_checks) = &self.stack {
            value *= stack_checks.to_value(main_trace, alphas);
        }

        value
    }

    /// Reduces all range checks requested at this cycle by the Memory processor to a single field
    /// element in the field specified by E.
    fn to_mem_value<E: ExtensionField<Felt>>(
        &self,
        main_trace: &MainTrace,
        alphas: &[E],
    ) -> E {
        let mut value = E::ONE;

        if let Some(mem_checks) = &self.memory {
            value = mem_checks.to_value(main_trace, alphas)
        }

        value
    }
}

impl LookupTableRow for CycleRangeChecks {
    /// Reduces this row to a single field element in the field specified by E. This requires
    /// at least 1 alpha value. Includes all values included at this cycle from all processors.
    fn to_value<E: ExtensionField<Felt>>(
        &self,
        main_trace: &MainTrace,
        alphas: &[E],
    ) -> E {
        let stack_value = self.to_stack_value(main_trace, alphas);
        let mem_value = self.to_mem_value(main_trace, alphas);

        if stack_value != E::ONE {
            stack_value * mem_value
        } else {
            mem_value
        }
    }
}

/// Range check lookups requested by a processor at a single cycle, carrying the values to be
/// range-checked.
#[derive(Debug, Clone, PartialEq, Eq)]
enum RangeCheckRequest {
    Memory([Felt; 2]),
    Stack([Felt; 4]),
}

impl LookupTableRow for RangeCheckRequest {
    /// Reduces this row to a single field element in the field specified by E. This requires
    /// at least 1 alpha value.
    fn to_value<E: ExtensionField<Felt>>(
        &self,
        _main_trace: &MainTrace,
        alphas: &[E],
    ) -> E {
        let alpha: E = alphas[0];
        let mut value = E::ONE;

        let values_iter = match self {
            Self::Memory(values) => values.iter(),
            Self::Stack(values) => values.iter(),
        };

        for &rc_value in values_iter {
            value *= alpha + rc_value.into();
        }

        value
    }
}