tasm_lib/arithmetic/u64/
wrapping_sub.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::arithmetic::u64::overflowing_sub::OverflowingSub;
6use crate::prelude::*;
7use crate::traits::basic_snippet::Reviewer;
8use crate::traits::basic_snippet::SignOffFingerprint;
9
10/// [Wrapping subtraction][sub] for unsigned 64-bit integers.
11///
12/// # Behavior
13///
14/// ```text
15/// BEFORE: _ [subtrahend: u64] [minuend: u64]
16/// AFTER:  _ [wrapped_difference: u64]
17/// ```
18///
19/// # Preconditions
20///
21/// - all input arguments are properly [`BFieldCodec`] encoded
22///
23/// # Postconditions
24///
25/// - the output `difference` is the `minuend` minus the `subtrahend`, wrapping
26///   around if the minuend is greater than the subtrahend
27/// - the output is properly [`BFieldCodec`] encoded
28///
29/// [sub]: u64::wrapping_sub
30#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
31pub struct WrappingSub;
32
33impl BasicSnippet for WrappingSub {
34    fn inputs(&self) -> Vec<(DataType, String)> {
35        OverflowingSub.inputs()
36    }
37
38    fn outputs(&self) -> Vec<(DataType, String)> {
39        vec![(DataType::U64, "wrapped_difference".to_string())]
40    }
41
42    fn entrypoint(&self) -> String {
43        "tasmlib_arithmetic_u64_wrapping_sub".to_string()
44    }
45
46    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
47        triton_asm! {
48            {self.entrypoint()}:
49                {&OverflowingSub::common_subtraction_code()}
50                // _ difference_lo (minuend_hi - subtrahend_hi - carry)
51
52                addi {1_u64 << 32}
53                split
54                // _ difference_lo !is_overflow difference_hi
55
56                place 2
57                pop 1
58                // _ difference_hi difference_lo
59
60                return
61        }
62    }
63
64    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
65        let mut sign_offs = HashMap::new();
66        sign_offs.insert(Reviewer("ferdinand"), 0xe6d83d5f88c389e3.into());
67        sign_offs
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74    use crate::test_prelude::*;
75
76    impl Closure for WrappingSub {
77        type Args = <OverflowingSub as Closure>::Args;
78
79        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
80            let minuend = pop_encodable::<u64>(stack);
81            let subtrahend = pop_encodable::<u64>(stack);
82            let difference = minuend.wrapping_sub(subtrahend);
83            push_encodable(stack, &difference);
84        }
85
86        fn pseudorandom_args(
87            &self,
88            seed: [u8; 32],
89            bench_case: Option<BenchmarkCase>,
90        ) -> Self::Args {
91            OverflowingSub.pseudorandom_args(seed, bench_case)
92        }
93
94        fn corner_case_args(&self) -> Vec<Self::Args> {
95            OverflowingSub.corner_case_args()
96        }
97    }
98
99    #[test]
100    fn rust_shadow() {
101        ShadowedClosure::new(WrappingSub).test()
102    }
103}
104
105#[cfg(test)]
106mod benches {
107    use super::*;
108    use crate::test_prelude::*;
109
110    #[test]
111    fn benchmark() {
112        ShadowedClosure::new(WrappingSub).bench()
113    }
114}