tasm_lib/arithmetic/u64/
mul_two_u64s_to_u128.rs

1use triton_vm::prelude::*;
2
3use crate::arithmetic::u64::safe_mul::SafeMul;
4use crate::prelude::*;
5
6/// Multiply two `u64`s, resulting in a `u128`.
7///
8/// ### Behavior
9///
10/// ```text
11/// BEFORE: _ [right: u64] [left: u64]
12/// AFTER:  _ [left · right: u128]
13/// ```
14///
15/// ### Preconditions
16///
17/// - all input arguments are properly [`BFieldCodec`] encoded
18///
19/// ### Postconditions
20///
21/// - the output is the product of the input
22/// - the output is properly [`BFieldCodec`] encoded
23#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, Hash)]
24pub struct MulTwoU64sToU128;
25
26impl BasicSnippet for MulTwoU64sToU128 {
27    fn inputs(&self) -> Vec<(DataType, String)> {
28        SafeMul.inputs()
29    }
30
31    fn outputs(&self) -> Vec<(DataType, String)> {
32        vec![(DataType::U128, "product".to_string())]
33    }
34
35    fn entrypoint(&self) -> String {
36        "tasmlib_arithmetic_u64_mul_two_u64s_to_u128_u64".to_string()
37    }
38
39    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
40        triton_asm!(
41            // BEFORE: _ r_hi r_lo l_hi l_lo
42            // AFTER:  _ p_3 p_2 p_1 p_0
43            {self.entrypoint()}:
44                /*
45                 *  p_0 is low limb, c_0 high limb of l_lo·r_lo
46                 *  p_1 is low limb, c_1 high limb of (l_lo·r_hi)_lo + (l_hi·r_lo)_lo + c_0
47                 *  p_2 is low limb, c_2 high limb of (l_lo·r_hi)_hi + (l_hi·r_lo)_hi + (l_hi·r_hi)_lo + c_1
48                 *  p_3 is low limb (l_hi·r_hi)_hi + c_2
49                 *
50                 * There's no carry c_3 because max value of (l_hi·r_hi)_hi is 0xfffffffe.
51                 */
52
53                /* p_0 */
54                dup 0
55                dup 3
56                mul
57                split       // _ r_hi r_lo l_hi l_lo c_0 p_0
58
59                /* p_1 */
60                swap 2      // _ r_hi r_lo l_hi p_0 c_0 l_lo
61                dup 5
62                mul
63                split       // _ r_hi r_lo l_hi p_0 c_0 (l_lo·r_hi)_hi (l_lo·r_hi)_lo
64                pick 1
65                swap 5      // _ r_hi (l_lo·r_hi)_hi l_hi p_0 c_0 (l_lo·r_hi)_lo r_lo
66                dup 4
67                mul
68                split       // _ r_hi (l_lo·r_hi)_hi l_hi p_0 c_0 (l_lo·r_hi)_lo (r_lo·l_hi)_hi (r_lo·l_hi)_lo
69                pick 1
70                place 3     // _ r_hi (l_lo·r_hi)_hi l_hi p_0 (r_lo·l_hi)_hi c_0 (l_lo·r_hi)_lo (r_lo·l_hi)_lo
71                add
72                add
73                split       // _ r_hi (l_lo·r_hi)_hi l_hi p_0 (r_lo·l_hi)_hi c_1 p_1
74
75                /* p_2 */
76                swap 4      // _ r_hi (l_lo·r_hi)_hi p_1 p_0 (r_lo·l_hi)_hi c_1 l_hi
77                pick 6      // _ (l_lo·r_hi)_hi p_1 p_0 (r_lo·l_hi)_hi c_1 l_hi r_hi
78                mul
79                split       // _ (l_lo·r_hi)_hi p_1 p_0 (r_lo·l_hi)_hi c_1 (l_hi·r_hi)_hi (l_hi·r_hi)_lo
80                pick 1
81                swap 6      // _ (l_hi·r_hi)_hi p_1 p_0 (r_lo·l_hi)_hi c_1 (l_hi·r_hi)_lo (l_lo·r_hi)_hi
82                add
83                add
84                add
85                split       // _ (l_hi·r_hi)_hi p_1 p_0 c_2 p_2
86
87                /* p_3 */
88                swap 4      // _ p_2 p_1 p_0 c_2 (l_hi·r_hi)_hi
89                add         // _ p_2 p_1 p_0 p_3
90                place 3     // _ p_3 p_2 p_1 p_0
91
92                return
93        )
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100    use crate::arithmetic::u64::and::And;
101    use crate::test_prelude::*;
102
103    impl Closure for MulTwoU64sToU128 {
104        type Args = (u64, u64);
105
106        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
107            let (right, left) = pop_encodable::<Self::Args>(stack);
108            let product = u128::from(left) * u128::from(right);
109            push_encodable(stack, &product);
110        }
111
112        fn pseudorandom_args(
113            &self,
114            seed: [u8; 32],
115            bench_case: Option<BenchmarkCase>,
116        ) -> Self::Args {
117            match bench_case {
118                Some(BenchmarkCase::CommonCase) => (1 << 63, (1 << 45) - 1),
119                Some(BenchmarkCase::WorstCase) => (1 << 63, (1 << 63) - 1),
120                None => StdRng::from_seed(seed).random(),
121            }
122        }
123
124        fn corner_case_args(&self) -> Vec<Self::Args> {
125            And.corner_case_args()
126        }
127    }
128
129    #[test]
130    fn rust_shadow() {
131        ShadowedClosure::new(MulTwoU64sToU128).test();
132    }
133}
134
135#[cfg(test)]
136mod benches {
137    use super::*;
138    use crate::test_prelude::*;
139
140    #[test]
141    fn benchmark() {
142        ShadowedClosure::new(MulTwoU64sToU128).bench();
143    }
144}
tasm_lib/arithmetic/u64/mul_two_u64s_to_u128.rs

tasm_lib/arithmetic/u64/
mul_two_u64s_to_u128.rs
