miden_core_lib/handlers/
falcon_div.rs

1//! FALCON_DIV system event handler for the Miden VM.
2//!
3//! This handler implements the FALCON_DIV operation that pushes the result of dividing
4//! a [u64] by the Falcon prime (M = 12289) onto the advice stack.
5
6use alloc::{vec, vec::Vec};
7
8use miden_core::{ZERO, events::EventName};
9use miden_processor::{ProcessorState, advice::AdviceMutation, event::EventError};
10
11use crate::handlers::u64_to_u32_elements;
12
13/// Falcon signature prime.
14const M: u64 = 12289;
15
16/// Event name for the falcon_div operation.
17pub const FALCON_DIV_EVENT_NAME: EventName =
18    EventName::new("miden::core::crypto::dsa::falcon512_poseidon2::falcon_div");
19
20/// FALCON_DIV system event handler.
21///
22/// Pushes the result of divison (both the quotient and the remainder) of a [u64] by the Falcon
23/// prime (M = 12289) onto the advice stack.
24///
25/// Inputs:
26///   Operand stack: [event_id, a1, a0, ...]
27///   Advice stack: [...]
28///
29/// Outputs:
30///   Advice stack: [q1, q0, r, ...]
31///
32/// where (a0, a1) are the 32-bit limbs of the dividend (with a0 representing the 32 least
33/// significant bits and a1 representing the 32 most significant bits).
34/// Similarly, (q0, q1) represent the quotient and r the remainder.
35///
36/// # Errors
37/// - Returns an error if the divisor is ZERO.
38/// - Returns an error if either a0 or a1 is not a u32.
39pub fn handle_falcon_div(process: &ProcessorState) -> Result<Vec<AdviceMutation>, EventError> {
40    let dividend_hi = process.get_stack_item(1).as_canonical_u64();
41    let dividend_lo = process.get_stack_item(2).as_canonical_u64();
42
43    if dividend_lo > u32::MAX.into() {
44        return Err(FalconDivError::InputNotU32 {
45            value: dividend_lo,
46            position: "dividend_lo",
47        }
48        .into());
49    }
50    if dividend_hi > u32::MAX.into() {
51        return Err(FalconDivError::InputNotU32 {
52            value: dividend_hi,
53            position: "dividend_hi",
54        }
55        .into());
56    }
57
58    let dividend = (dividend_hi << 32) + dividend_lo;
59
60    let (quotient, remainder) = (dividend / M, dividend % M);
61
62    let (q_hi, q_lo) = u64_to_u32_elements(quotient);
63    let (r_hi, r_lo) = u64_to_u32_elements(remainder);
64
65    // Assertion from the original code: r_hi should always be zero for Falcon modulus
66    assert_eq!(r_hi, ZERO);
67
68    // `mod_12289` consumes the quotient via `adv_push.2` followed by the remainder via
69    // `adv_push.1`. Push the remainder first (so it stays below the quotient) and rely on
70    // `extend_stack_for_adv_push` to take care of the per-word little-endian layout.
71    let remainder = AdviceMutation::extend_stack([r_lo]);
72    let quotient = AdviceMutation::extend_stack([q_hi, q_lo]);
73    Ok(vec![remainder, quotient])
74}
75
76// ERROR TYPES
77// ================================================================================================
78
79/// Error types that can occur during FALCON_DIV operations.
80#[derive(Debug, thiserror::Error)]
81pub enum FalconDivError {
82    /// Input value is not a valid u32.
83    #[error("input value {value} at {position} is not a valid u32")]
84    InputNotU32 { value: u64, position: &'static str },
85}
miden_core_lib/handlers/falcon_div.rs

miden_core_lib/handlers/
falcon_div.rs
