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 inputs(&self) -> Vec<(DataType, String)> {
30        vec![(DataType::U64, "arg".to_string())]
31    }
32
33    fn outputs(&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"), 0xe77a12ba30ef339b.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);
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>) {
109            let arg = pop_encodable::<Self::Args>(stack);
110            push_encodable(stack, &(arg / 2));
111        }
112
113        fn pseudorandom_args(
114            &self,
115            seed: [u8; 32],
116            bench_case: Option<BenchmarkCase>,
117        ) -> Self::Args {
118            match bench_case {
119                Some(BenchmarkCase::CommonCase) => 0x8000_0000,
120                Some(BenchmarkCase::WorstCase) => 0xf000_0001_f000_0000,
121                None => StdRng::from_seed(seed).random(),
122            }
123        }
124    }
125
126    #[test]
127    fn rust_shadow() {
128        ShadowedClosure::new(Div2).test();
129    }
130
131    #[proptest]
132    fn lo_is_not_u32(hi: u32, #[strategy(1_u64 << 32..)] lo: u64) {
133        let stack = [Div2.init_stack_for_isolated_run(), bfe_vec![hi, lo]].concat();
134
135        let error = InstructionError::OpStackError(OpStackError::FailedU32Conversion(bfe!(lo)));
136        negative_test(
137            &ShadowedClosure::new(Div2),
138            InitVmState::with_stack(stack),
139            &[error],
140        );
141    }
142
143    #[proptest]
144    fn hi_is_not_u32(#[strategy(1_u64 << 32..)] hi: u64, lo: u32) {
145        let stack = [Div2.init_stack_for_isolated_run(), bfe_vec![hi, lo]].concat();
146
147        let error = InstructionError::OpStackError(OpStackError::FailedU32Conversion(bfe!(hi)));
148        negative_test(
149            &ShadowedClosure::new(Div2),
150            InitVmState::with_stack(stack),
151            &[error],
152        );
153    }
154
155    #[test]
156    fn div_2_test() {
157        let small_args = 0..9;
158        let mid_args = (0..9).map(|offset| (1 << 32) + offset);
159        let large_args = [0, 4, 1 << 31, 0b111 << 31].map(|offset| (1 << 63) + offset);
160
161        for arg in small_args.chain(mid_args).chain(large_args) {
162            Div2.assert_expected_behavior(arg);
163        }
164    }
165}
166
167#[cfg(test)]
168mod benches {
169    use super::*;
170    use crate::test_prelude::*;
171
172    #[test]
173    fn benchmark() {
174        ShadowedClosure::new(Div2).bench();
175    }
176}
tasm_lib/arithmetic/u64/div2.rs

tasm_lib/arithmetic/u64/
div2.rs
