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