tasm_lib/arithmetic/u64/
div2.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::prelude::*;
6use crate::traits::basic_snippet::Reviewer;
7use crate::traits::basic_snippet::SignOffFingerprint;
8
9/// Integer-divide the argument by 2.
10///
11/// ### Behavior
12///
13/// ```text
14/// BEFORE: _ [arg: u64]
15/// AFTER:  _ [arg/2: u64]
16/// ```
17///
18/// ### Preconditions
19///
20/// - the input is properly [`BFieldCodec`] encoded
21///
22/// ### Postconditions
23///
24/// - the output is properly [`BFieldCodec`] encoded
25#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
26pub struct Div2;
27
28impl BasicSnippet for Div2 {
29    fn parameters(&self) -> Vec<(DataType, String)> {
30        vec![(DataType::U64, "arg".to_string())]
31    }
32
33    fn return_values(&self) -> Vec<(DataType, String)> {
34        vec![(DataType::U64, "(arg/2)".to_string())]
35    }
36
37    fn entrypoint(&self) -> String {
38        "tasmlib_arithmetic_u64_div2".to_string()
39    }
40
41    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
42        triton_asm!(
43            // BEFORE: _ arg_hi arg_lo
44            // AFTER:  _ (arg / 2)_hi (arg / 2)_lo
45            {self.entrypoint()}:
46                /* divide low part */
47                push 2
48                pick 1
49                div_mod
50                pop 1
51                // _ arg_hi (arg_lo / 2)
52
53                /* divide high part, carry its least significant bit into the low part */
54                push 2
55                pick 2
56                div_mod
57                // _ (arg_lo / 2) (arg_hi / 2) (arg_hi % 2)
58                // _ (arg_lo / 2) (arg / 2)_hi (arg_hi % 2)
59
60                push {1_u32 << 31}
61                hint two_pow_31: u32 = stack[0]
62                mul
63                hint carry: u32 = stack[0]
64                // _ (arg_lo / 2) (arg / 2)_hi carry
65
66                pick 2
67                add
68                // _ (arg / 2)_hi (arg / 2)_lo
69
70                return
71        )
72    }
73
74    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
75        let mut sign_offs = HashMap::new();
76        sign_offs.insert(Reviewer("ferdinand"), 0x23322a6d8af4bb90.into());
77        sign_offs
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84    use crate::test_helpers::negative_test;
85    use crate::test_prelude::*;
86
87    impl Div2 {
88        fn assert_expected_behavior(&self, arg: u64) {
89            let initial_stack = self.set_up_test_stack(arg);
90
91            let mut expected_stack = initial_stack.clone();
92            self.rust_shadow(&mut expected_stack).unwrap();
93
94            test_rust_equivalence_given_complete_state(
95                &ShadowedClosure::new(Self),
96                &initial_stack,
97                &[],
98                &NonDeterminism::default(),
99                &None,
100                Some(&expected_stack),
101            );
102        }
103    }
104
105    impl Closure for Div2 {
106        type Args = u64;
107
108        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) -> Result<(), RustShadowError> {
109            let arg = pop_encodable::<Self::Args>(stack)?;
110            push_encodable(stack, &(arg / 2));
111            Ok(())
112        }
113
114        fn pseudorandom_args(
115            &self,
116            seed: [u8; 32],
117            bench_case: Option<BenchmarkCase>,
118        ) -> Self::Args {
119            match bench_case {
120                Some(BenchmarkCase::CommonCase) => 0x8000_0000,
121                Some(BenchmarkCase::WorstCase) => 0xf000_0001_f000_0000,
122                None => StdRng::from_seed(seed).random(),
123            }
124        }
125    }
126
127    #[macro_rules_attr::apply(test)]
128    fn rust_shadow() {
129        ShadowedClosure::new(Div2).test();
130    }
131
132    #[macro_rules_attr::apply(proptest)]
133    fn lo_is_not_u32(hi: u32, #[strategy(1_u64 << 32..)] lo: u64) {
134        let stack = [Div2.init_stack_for_isolated_run(), bfe_vec![hi, lo]].concat();
135
136        let error = InstructionError::OpStackError(OpStackError::FailedU32Conversion(bfe!(lo)));
137        negative_test(
138            &ShadowedClosure::new(Div2),
139            InitVmState::with_stack(stack),
140            &[error],
141        );
142    }
143
144    #[macro_rules_attr::apply(proptest)]
145    fn hi_is_not_u32(#[strategy(1_u64 << 32..)] hi: u64, lo: u32) {
146        let stack = [Div2.init_stack_for_isolated_run(), bfe_vec![hi, lo]].concat();
147
148        let error = InstructionError::OpStackError(OpStackError::FailedU32Conversion(bfe!(hi)));
149        negative_test(
150            &ShadowedClosure::new(Div2),
151            InitVmState::with_stack(stack),
152            &[error],
153        );
154    }
155
156    #[macro_rules_attr::apply(test)]
157    fn div_2_test() {
158        let small_args = 0..9;
159        let mid_args = (0..9).map(|offset| (1 << 32) + offset);
160        let large_args = [0, 4, 1 << 31, 0b111 << 31].map(|offset| (1 << 63) + offset);
161
162        for arg in small_args.chain(mid_args).chain(large_args) {
163            Div2.assert_expected_behavior(arg);
164        }
165    }
166}
167
168#[cfg(test)]
169mod benches {
170    use super::*;
171    use crate::test_prelude::*;
172
173    #[macro_rules_attr::apply(test)]
174    fn benchmark() {
175        ShadowedClosure::new(Div2).bench();
176    }
177}
tasm_lib/arithmetic/u64/div2.rs

tasm_lib/arithmetic/u64/
div2.rs
