tasm_lib/arithmetic/u64/
wrapping_mul.rs

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
use std::collections::HashMap;

use triton_vm::prelude::*;

use crate::prelude::*;
use crate::traits::basic_snippet::Reviewer;
use crate::traits::basic_snippet::SignOffFingerprint;

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct WrappingMul;

impl BasicSnippet for WrappingMul {
    fn inputs(&self) -> Vec<(DataType, String)> {
        ["rhs", "lhs"]
            .map(|side| (DataType::U64, side.to_string()))
            .to_vec()
    }

    fn outputs(&self) -> Vec<(DataType, String)> {
        vec![(DataType::U64, "product".to_string())]
    }

    fn entrypoint(&self) -> String {
        "tasmlib_arithmetic_u64_wrapping_mul".to_string()
    }

    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
        triton_asm!(
            // BEFORE: _ right_hi right_lo left_hi left_lo
            // AFTER:  _ prod_hi prod_lo
            {self.entrypoint()}:
                /* left_lo · right_lo */
                dup 0
                dup 3
                mul
                // _ right_hi right_lo left_hi left_lo (left_lo · right_lo)

                /* left_lo · right_hi (consume both) */
                swap 4
                mul
                // _ (left_lo · right_lo) right_lo left_hi (left_lo · right_hi)

                /* left_hi · right_lo (consume both) */
                swap 2
                mul
                // _ (left_lo · right_lo) (left_lo · right_hi) (left_hi · right_lo)
                // _ lolo                 lohi                 hilo

                /* prod_hi = lolo_hi + lohi_lo + hilo_lo */
                split
                pick 1
                pop 1
                // _ lolo lohi hilo_lo

                pick 1
                split
                pick 1
                pop 1
                // _ lolo hilo_lo lohi_lo

                pick 2
                split
                // _ hilo_lo lohi_lo lolo_hi lolo_lo
                // _ hilo_lo lohi_lo lolo_hi prod_lo

                place 3
                add
                add
                // _ prod_lo (hilo_lo + lohi_lo + lolo_hi)

                split
                pick 1
                pop 1
                // _ prod_lo (hilo_lo + lohi_lo + lolo_hi)_lo
                // _ prod_lo prod_hi

                place 1
                return
        )
    }

    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
        let mut sign_offs = HashMap::new();
        sign_offs.insert(Reviewer("ferdinand"), 0x98526c7c401009ed.into());
        sign_offs
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::test_prelude::*;

    impl Closure for WrappingMul {
        type Args = (u64, u64);

        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
            let (right, left) = pop_encodable::<Self::Args>(stack);
            push_encodable(stack, &left.wrapping_mul(right));
        }

        fn pseudorandom_args(
            &self,
            seed: [u8; 32],
            bench_case: Option<BenchmarkCase>,
        ) -> Self::Args {
            match bench_case {
                Some(BenchmarkCase::CommonCase) => (1 << 31, (1 << 25) - 1),
                Some(BenchmarkCase::WorstCase) => (1 << 53, (1 << 33) - 1),
                None => StdRng::from_seed(seed).random(),
            }
        }
    }

    #[test]
    fn rust_shadow() {
        ShadowedClosure::new(WrappingMul).test();
    }
}

#[cfg(test)]
mod benches {
    use super::*;
    use crate::test_prelude::*;

    #[test]
    fn benchmark() {
        ShadowedClosure::new(WrappingMul).bench();
    }
}