tasm_lib/arithmetic/u64/
shift_left.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::arithmetic::u64::shift_right::ShiftRight;
6use crate::prelude::*;
7use crate::traits::basic_snippet::Reviewer;
8use crate::traits::basic_snippet::SignOffFingerprint;
9
10/// [Shift left][shl] for unsigned 64-bit integers.
11///
12/// # Behavior
13///
14/// ```text
15/// BEFORE: _ [arg: u64] shift_amount
16/// AFTER:  _ [result: u64]
17/// ```
18///
19/// # Preconditions
20///
21/// - input argument `arg` is properly [`BFieldCodec`] encoded
22/// - input argument `shift_amount` is in `0..64`
23///
24/// # Postconditions
25///
26/// - the output is the input argument `arg` bit-shifted to the left by
27///   input argument `shift_amount`
28/// - the output is properly [`BFieldCodec`] encoded
29///
30/// [shl]: core::ops::Shl
31#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
32pub struct ShiftLeft;
33
34impl ShiftLeft {
35    pub const SHIFT_AMOUNT_TOO_BIG_ERROR_ID: i128 = 370;
36}
37
38impl BasicSnippet for ShiftLeft {
39    fn inputs(&self) -> Vec<(DataType, String)> {
40        ShiftRight.inputs()
41    }
42
43    fn outputs(&self) -> Vec<(DataType, String)> {
44        ShiftRight.outputs()
45    }
46
47    fn entrypoint(&self) -> String {
48        "tasmlib_arithmetic_u64_shift_left".to_string()
49    }
50
51    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
52        let entrypoint = self.entrypoint();
53        let handle_hi_shift = format!("{entrypoint}_handle_hi_shift");
54
55        triton_asm!(
56            // BEFORE: _ arg_hi arg_lo shift
57            // AFTER:  _ (arg<< shift)_hi (arg<< shift)_lo
58            {entrypoint}:
59                /* bounds check */
60                push 64
61                dup 1
62                lt
63                assert error_id {Self::SHIFT_AMOUNT_TOO_BIG_ERROR_ID}
64                // _ arg_hi arg_lo shift
65
66                /* special case: shift amount is greater than 32 */
67                dup 0
68                push 32
69                lt
70                // _ arg_hi arg_lo shift (shift > 32)
71
72                skiz call {handle_hi_shift}
73                // _ arg_hi arg_lo shift
74                // where 32 <= shift < 64
75
76                push 2
77                pow
78                // _ arg_hi arg_lo (2^shift)
79
80                pick 2
81                dup 1
82                mul
83                // _ arg_lo (2^shift) (arg_hi << shift)_bfe
84
85                split
86                place 3
87                pop 1
88                // _ (arg_hi << shift) arg_lo (2^shift)
89
90                mul
91                split
92                // _ (arg_hi << shift) carry (arg_lo << shift)
93
94                place 2
95                add
96                pick 1
97                // _ (arg << shift)_hi (arg_lo << shift)
98
99                return
100
101            // BEFORE: _ arg_hi arg_lo shift
102            // AFTER:  _ (arg<< 32)_hi (arg<< 32)_lo (shift - 32)
103            {handle_hi_shift}:
104                addi -32
105                // _ arg_hi arg_lo (shift - 32)
106
107                pick 2
108                pop 1
109                push 0
110                place 1
111                // _ arg_lo         0            (shift - 32)
112                // _ (arg<< 32)_hi (arg<< 32)_lo (shift - 32)
113
114                return
115        )
116    }
117
118    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
119        let mut sign_offs = HashMap::new();
120        sign_offs.insert(Reviewer("ferdinand"), 0x46e8b1129fe7b87c.into());
121        sign_offs
122    }
123}
124
125#[cfg(test)]
126pub(crate) mod tests {
127    use super::*;
128    use crate::test_prelude::*;
129
130    impl ShiftLeft {
131        pub fn assert_expected_behavior(&self, shift_amount: u32, arg: u64) {
132            let initial_stack = self.set_up_test_stack((arg, shift_amount));
133
134            let mut expected_stack = initial_stack.clone();
135            self.rust_shadow(&mut expected_stack);
136
137            test_rust_equivalence_given_complete_state(
138                &ShadowedClosure::new(Self),
139                &initial_stack,
140                &[],
141                &NonDeterminism::default(),
142                &None,
143                Some(&expected_stack),
144            );
145        }
146    }
147
148    impl Closure for ShiftLeft {
149        type Args = (u64, u32);
150
151        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
152            let (arg, shift_amount) = pop_encodable::<Self::Args>(stack);
153            assert!(shift_amount < 64);
154            push_encodable(stack, &(arg << shift_amount));
155        }
156
157        fn pseudorandom_args(
158            &self,
159            seed: [u8; 32],
160            bench_case: Option<BenchmarkCase>,
161        ) -> Self::Args {
162            let mut rng = StdRng::from_seed(seed);
163
164            match bench_case {
165                Some(BenchmarkCase::CommonCase) => (0x642, 15),
166                Some(BenchmarkCase::WorstCase) => (0x123456789abcdef, 33),
167                None => (rng.random(), rng.random_range(0..64)),
168            }
169        }
170
171        fn corner_case_args(&self) -> Vec<Self::Args> {
172            (0..64).map(|i| (1, i)).collect()
173        }
174    }
175
176    #[test]
177    fn rust_shadow() {
178        ShadowedClosure::new(ShiftLeft).test()
179    }
180
181    #[test]
182    fn edge_cases() {
183        for i in 0..64 {
184            ShiftLeft.assert_expected_behavior(i, u64::MAX);
185        }
186    }
187
188    #[proptest]
189    fn property_test(arg: u64, #[strategy(0_u32..64)] shift_amount: u32) {
190        ShiftLeft.assert_expected_behavior(shift_amount, arg);
191    }
192
193    #[proptest]
194    fn negative_property_test(arg: u64, #[strategy(64_u32..)] shift_amount: u32) {
195        test_assertion_failure(
196            &ShadowedClosure::new(ShiftLeft),
197            InitVmState::with_stack(ShiftLeft.set_up_test_stack((arg, shift_amount))),
198            &[ShiftLeft::SHIFT_AMOUNT_TOO_BIG_ERROR_ID],
199        );
200    }
201}
202
203#[cfg(test)]
204mod benches {
205    use super::*;
206    use crate::test_prelude::*;
207
208    #[test]
209    fn benchmark() {
210        ShadowedClosure::new(ShiftLeft).bench();
211    }
212}
tasm_lib/arithmetic/u64/shift_left.rs

tasm_lib/arithmetic/u64/
shift_left.rs
