miden_core_lib/handlers/
u64_div.rs

1//! U64_DIV system event handler for the Miden VM.
2//!
3//! This handler implements the U64_DIV operation that pushes the result of [u64] division
4//! (both the quotient and the remainder) onto the advice stack.
5
6use alloc::{vec, vec::Vec};
7
8use miden_processor::{
9    ProcessorState,
10    advice::AdviceMutation,
11    event::{EventError, EventName},
12};
13
14use crate::handlers::u64_to_u32_elements;
15
16/// Event name for the u64_div operation.
17pub const U64_DIV_EVENT_NAME: EventName = EventName::new("miden::core::math::u64::u64_div");
18
19/// U64_DIV system event handler.
20///
21/// Pushes the result of [u64] division (both the quotient and the remainder) onto the advice
22/// stack.
23///
24/// Inputs:
25///   Operand stack: [event_id, b_lo, b_hi, a_lo, a_hi, ...]
26///   Advice stack: [...]
27///
28/// Outputs:
29///   Advice stack: [q_lo, q_hi, r_lo, r_hi, ...]
30///
31/// Where (a_lo, a_hi) and (b_lo, b_hi) are the 32-bit limbs of the dividend and the divisor
32/// respectively (with lo representing the 32 least significant bits and hi representing the
33/// 32 most significant bits). Similarly, (q_lo, q_hi) and (r_lo, r_hi) represent the quotient
34/// and the remainder respectively.
35///
36/// # Errors
37/// Returns an error if the divisor is ZERO.
38pub fn handle_u64_div(process: &ProcessorState) -> Result<Vec<AdviceMutation>, EventError> {
39    // Read divisor from positions 1 (lo) and 2 (hi) - b is on top of stack
40    let divisor = {
41        let divisor_lo = process.get_stack_item(1).as_canonical_u64();
42        let divisor_hi = process.get_stack_item(2).as_canonical_u64();
43
44        // Ensure the divisor is a pair of u32 values
45        if divisor_lo > u32::MAX.into() {
46            return Err(U64DivError::NotU32Value {
47                value: divisor_lo,
48                position: "divisor_lo",
49            }
50            .into());
51        }
52        if divisor_hi > u32::MAX.into() {
53            return Err(U64DivError::NotU32Value {
54                value: divisor_hi,
55                position: "divisor_hi",
56            }
57            .into());
58        }
59
60        let divisor = (divisor_hi << 32) + divisor_lo;
61
62        if divisor == 0 {
63            return Err(U64DivError::DivideByZero.into());
64        }
65
66        divisor
67    };
68
69    // Read dividend from positions 3 (lo) and 4 (hi) - a is below b
70    let dividend = {
71        let dividend_lo = process.get_stack_item(3).as_canonical_u64();
72        let dividend_hi = process.get_stack_item(4).as_canonical_u64();
73
74        // Ensure the dividend is a pair of u32 values
75        if dividend_lo > u32::MAX.into() {
76            return Err(U64DivError::NotU32Value {
77                value: dividend_lo,
78                position: "dividend_lo",
79            }
80            .into());
81        }
82        if dividend_hi > u32::MAX.into() {
83            return Err(U64DivError::NotU32Value {
84                value: dividend_hi,
85                position: "dividend_hi",
86            }
87            .into());
88        }
89
90        (dividend_hi << 32) + dividend_lo
91    };
92
93    let quotient = dividend / divisor;
94    let remainder = dividend - quotient * divisor;
95
96    let (q_hi, q_lo) = u64_to_u32_elements(quotient);
97    let (r_hi, r_lo) = u64_to_u32_elements(remainder);
98
99    // Create mutations to extend the advice stack with the result.
100    // extend_stack([a,b,c,d]) puts 'a' on top due to reverse iteration + push_front
101    // So [q_hi, q_lo, r_hi, r_lo] puts q_hi on top
102    // After adv_push.2: pops q_hi then q_lo → operand stack [q_lo, q_hi, ...] (LE)
103    // After adv_push.2: pops r_hi then r_lo → operand stack [r_lo, r_hi, ...] (LE)
104    let mutation = AdviceMutation::extend_stack([q_hi, q_lo, r_hi, r_lo]);
105    Ok(vec![mutation])
106}
107
108// ERROR TYPES
109// ================================================================================================
110
111/// Error types that can occur during U64_DIV operations.
112#[derive(Debug, thiserror::Error)]
113pub enum U64DivError {
114    /// Division by zero error.
115    #[error("division by zero")]
116    DivideByZero,
117
118    /// Value is not a valid u32.
119    #[error("value {value} at {position} is not a valid u32")]
120    NotU32Value { value: u64, position: &'static str },
121}
miden_core_lib/handlers/u64_div.rs

miden_core_lib/handlers/
u64_div.rs
