miden_core_lib/handlers/
u128_div.rs

1//! U128_DIV system event handler for the Miden VM.
2//!
3//! This handler implements the U128_DIV operation that pushes the result of [u128] division
4//! (both the quotient and the remainder) onto the advice stack.
5
6use alloc::{vec, vec::Vec};
7
8use miden_core::Felt;
9use miden_processor::{
10    ProcessorState,
11    advice::AdviceMutation,
12    event::{EventError, EventName},
13};
14
15/// Event name for the u128_div operation.
16pub const U128_DIV_EVENT_NAME: EventName = EventName::new("miden::core::math::u128::u128_div");
17
18/// U128_DIV system event handler.
19///
20/// Pushes the result of [u128] division (both the quotient and the remainder) onto the advice
21/// stack.
22///
23/// Inputs:
24///   Operand stack: [event_id, b0, b1, b2, b3, a0, a1, a2, a3, ...]
25///   Advice stack: [...]
26///
27/// Outputs:
28///   Advice stack: [r0, r1, r2, r3, q0, q1, q2, q3, ...]
29///
30/// Where (b0..b3) and (a0..a3) are the 32-bit limbs of the divisor and dividend respectively,
31/// with b0/a0 being the least significant limb.
32///
33/// After two `padw adv_loadw` in MASM:
34///   First:  loads [r0, r1, r2, r3] onto operand stack
35///   Second: loads [q0, q1, q2, q3] onto operand stack
36///
37/// # Errors
38/// Returns an error if the divisor is ZERO or any limb is not a valid u32.
39pub fn handle_u128_div(process: &ProcessorState) -> Result<Vec<AdviceMutation>, EventError> {
40    let divisor = read_u128_from_stack(process, 1, "divisor")?;
41
42    if divisor == 0 {
43        return Err(U128DivError::DivideByZero.into());
44    }
45
46    let dividend = read_u128_from_stack(process, 5, "dividend")?;
47
48    let quotient = dividend / divisor;
49    let remainder = dividend - quotient * divisor;
50
51    let (q0, q1, q2, q3) = u128_to_u32_felts(quotient);
52    let (r0, r1, r2, r3) = u128_to_u32_felts(remainder);
53
54    let mutation = AdviceMutation::extend_stack([r0, r1, r2, r3, q0, q1, q2, q3]);
55    Ok(vec![mutation])
56}
57
58/// Reads a u128 value from 4 consecutive stack positions starting at `start`.
59fn read_u128_from_stack(
60    process: &ProcessorState,
61    start: usize,
62    name: &'static str,
63) -> Result<u128, EventError> {
64    let mut value: u128 = 0;
65    for i in (0..4).rev() {
66        let limb = process.get_stack_item(start + i).as_canonical_u64();
67        if limb > u32::MAX as u64 {
68            return Err(U128DivError::NotU32Value {
69                value: limb,
70                position: name,
71                limb_index: i,
72            }
73            .into());
74        }
75        value = (value << 32) | limb as u128;
76    }
77    Ok(value)
78}
79
80/// Splits a u128 into 4 Felt values representing u32 limbs, least significant first.
81fn u128_to_u32_felts(value: u128) -> (Felt, Felt, Felt, Felt) {
82    let limb0 = Felt::from_u32(value as u32);
83    let limb1 = Felt::from_u32((value >> 32) as u32);
84    let limb2 = Felt::from_u32((value >> 64) as u32);
85    let limb3 = Felt::from_u32((value >> 96) as u32);
86    (limb0, limb1, limb2, limb3)
87}
88
89// ERROR TYPES
90// ================================================================================================
91
92/// Error types that can occur during U128_DIV operations.
93#[derive(Debug, thiserror::Error)]
94pub enum U128DivError {
95    /// Division by zero error.
96    #[error("division by zero")]
97    DivideByZero,
98
99    /// Value is not a valid u32.
100    #[error("value {value} at {position} limb {limb_index} is not a valid u32")]
101    NotU32Value {
102        value: u64,
103        position: &'static str,
104        limb_index: usize,
105    },
106}
miden_core_lib/handlers/u128_div.rs

miden_core_lib/handlers/
u128_div.rs
