tasm_lib/arithmetic/u32/
shift_left.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::arithmetic::u32::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 32-bit integers.
11///
12/// # Behavior
13///
14/// ```text
15/// BEFORE: _ [arg: u32] shift_amount
16/// AFTER:  _ [result: u32]
17/// ```
18///
19/// # Preconditions
20///
21/// - input argument `arg` is properly [`BFieldCodec`] encoded
22/// - input argument `shift_amount` is in `0..32`
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, Default, Copy, Clone, Eq, PartialEq, Hash)]
32pub struct ShiftLeft;
33
34impl ShiftLeft {
35    pub const SHIFT_AMOUNT_TOO_BIG_ERROR_ID: i128 = 480;
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_u32_shift_left".to_string()
49    }
50
51    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
52        triton_asm!(
53            // BEFORE: _ value shift
54            // AFTER:  _ (value << shift)
55            {self.entrypoint()}:
56                /* bounds check mimics Rust's behavior */
57                push 32
58                dup 1
59                lt
60                assert error_id {Self::SHIFT_AMOUNT_TOO_BIG_ERROR_ID}
61
62                push 2
63                pow
64                mul
65                split
66                pick 1
67                pop 1
68
69                return
70        )
71    }
72
73    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
74        let mut sign_offs = HashMap::new();
75        sign_offs.insert(Reviewer("ferdinand"), 0xec49012951c99eb1.into());
76        sign_offs
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::test_prelude::*;
84
85    impl Closure for ShiftLeft {
86        type Args = (u32, u32);
87
88        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
89            let (arg, shift_amount) = pop_encodable::<Self::Args>(stack);
90            assert!(shift_amount < 32);
91            push_encodable(stack, &(arg << shift_amount));
92        }
93
94        fn pseudorandom_args(
95            &self,
96            seed: [u8; 32],
97            bench_case: Option<BenchmarkCase>,
98        ) -> Self::Args {
99            let mut rng = StdRng::from_seed(seed);
100            match bench_case {
101                Some(BenchmarkCase::CommonCase) => ((1 << 16) - 1, 16),
102                Some(BenchmarkCase::WorstCase) => (u32::MAX, 31),
103                None => (rng.random(), rng.random_range(0..32)),
104            }
105        }
106
107        fn corner_case_args(&self) -> Vec<Self::Args> {
108            (0..32).map(|i| (u32::MAX, i)).collect()
109        }
110    }
111
112    #[test]
113    fn rust_shadow() {
114        ShadowedClosure::new(ShiftLeft).test();
115    }
116
117    #[proptest]
118    fn too_big_shift_amount_crashes_vm(arg: u32, #[strategy(32_u32..)] shift_amount: u32) {
119        test_assertion_failure(
120            &ShadowedClosure::new(ShiftLeft),
121            InitVmState::with_stack(ShiftLeft.set_up_test_stack((arg, shift_amount))),
122            &[ShiftLeft::SHIFT_AMOUNT_TOO_BIG_ERROR_ID],
123        )
124    }
125}
126
127#[cfg(test)]
128mod benches {
129    use super::*;
130    use crate::test_prelude::*;
131
132    #[test]
133    fn benchmark() {
134        ShadowedClosure::new(ShiftLeft).bench();
135    }
136}
tasm_lib/arithmetic/u32/shift_left.rs

tasm_lib/arithmetic/u32/
shift_left.rs
