miden_precompiles/math/uint/
spec.rs

1//! Fixed uint arithmetic specs shared by deferred evaluation and generated MASM support.
2
3use core::cmp::Ordering;
4
5use miden_core::Felt;
6
7use super::arithmetic::{
8    add_mod, barrett_mu, cmp, inv_mod_prime_barrett, mul_mod_barrett, sub_mod, sub_small,
9    wrapping_add, wrapping_mul, wrapping_sub,
10};
11
12/// Little-endian 256-bit value represented as eight `u32` limbs.
13pub type Limbs = [u32; 8];
14
15/// The canonical zero value in every supported uint domain.
16pub const ZERO_LIMBS: Limbs = [0; 8];
17
18/// The canonical one value in every supported uint domain.
19pub const ONE_LIMBS: Limbs = [1, 0, 0, 0, 0, 0, 0, 0];
20
21/// The canonical two value in every supported uint domain.
22pub const TWO_LIMBS: Limbs = [2, 0, 0, 0, 0, 0, 0, 0];
23
24/// Spec for one fixed uint arithmetic domain.
25pub trait UintSpec: 'static {
26    /// Stable local domain selector retained for host-side metadata.
27    const ID: Felt;
28
29    /// Encoded modulus limbs. `[0; 8]` is the `2^256` wrapping-domain sentinel.
30    const ENCODED_MODULUS: Limbs;
31
32    /// Barrett constant `floor(2^512 / modulus)` derived from [`Self::ENCODED_MODULUS`]. Unused by
33    /// the `2^256` wrapping sentinel, for which it is `[0; 9]`.
34    const BARRETT_MU: [u32; 9] = barrett_mu(Self::ENCODED_MODULUS);
35
36    /// Whether this domain supports prime-field helpers such as inversion.
37    const IS_PRIME_FIELD: bool = false;
38
39    /// Returns whether `value` is canonical for this domain.
40    fn is_canonical(value: &Limbs) -> bool {
41        if Self::ENCODED_MODULUS == ZERO_LIMBS {
42            true
43        } else {
44            cmp(value, &Self::ENCODED_MODULUS) == Ordering::Less
45        }
46    }
47
48    /// Adds two canonical values in this domain.
49    fn add(lhs: Limbs, rhs: Limbs) -> Limbs {
50        if Self::ENCODED_MODULUS == ZERO_LIMBS {
51            wrapping_add(lhs, rhs)
52        } else {
53            add_mod(lhs, rhs, Self::ENCODED_MODULUS)
54        }
55    }
56
57    /// Subtracts two canonical values in this domain.
58    fn sub(lhs: Limbs, rhs: Limbs) -> Limbs {
59        if Self::ENCODED_MODULUS == ZERO_LIMBS {
60            wrapping_sub(lhs, rhs)
61        } else {
62            sub_mod(lhs, rhs, Self::ENCODED_MODULUS)
63        }
64    }
65
66    /// Multiplies two canonical values in this domain.
67    fn mul(lhs: Limbs, rhs: Limbs) -> Limbs {
68        if Self::ENCODED_MODULUS == ZERO_LIMBS {
69            wrapping_mul(lhs, rhs)
70        } else {
71            mul_mod_barrett(lhs, rhs, Self::ENCODED_MODULUS, Self::BARRETT_MU)
72        }
73    }
74
75    /// Returns the multiplicative inverse of `value` for declared prime-field domains.
76    fn inv(value: Limbs) -> Option<Limbs> {
77        if Self::IS_PRIME_FIELD && Self::ENCODED_MODULUS != ZERO_LIMBS {
78            inv_mod_prime_barrett(value, Self::ENCODED_MODULUS, Self::BARRETT_MU)
79        } else {
80            None
81        }
82    }
83
84    /// Returns the canonical value `modulus - 1`, or `2^256 - 1` for U256.
85    fn minus_one() -> Limbs {
86        if Self::ENCODED_MODULUS == ZERO_LIMBS {
87            [u32::MAX; 8]
88        } else {
89            sub_small(Self::ENCODED_MODULUS, 1)
90        }
91    }
92
93    /// Returns the field constant `1 / 2`, if this is a declared prime-field domain.
94    fn half() -> Option<Limbs> {
95        Self::inv(TWO_LIMBS)
96    }
97
98    /// Returns `2^exponent` reduced into this prime-field domain.
99    fn pow2_mod(exponent: usize) -> Option<Limbs> {
100        if !Self::IS_PRIME_FIELD || Self::ENCODED_MODULUS == ZERO_LIMBS {
101            return None;
102        }
103
104        let mut value = ONE_LIMBS;
105        for _ in 0..exponent {
106            value = Self::add(value, value);
107        }
108        Some(value)
109    }
110}
miden_precompiles/math/uint/spec.rs

miden_precompiles/math/uint/
spec.rs
