tasm_lib/arithmetic/u128/
shift_left.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::arithmetic::u128::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 128-bit integers.
11///
12/// # Behavior
13///
14/// ```text
15/// BEFORE: _ [arg: u128] shift_amount
16/// AFTER:  _ [result: u128]
17/// ```
18///
19/// # Preconditions
20///
21/// - input argument `arg` is properly [`BFieldCodec`] encoded
22/// - input argument `shift_amount` is in `0..128`
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 = 530;
36}
37
38impl BasicSnippet for ShiftLeft {
39    fn parameters(&self) -> Vec<(DataType, String)> {
40        ShiftRight.parameters()
41    }
42
43    fn return_values(&self) -> Vec<(DataType, String)> {
44        ShiftRight.return_values()
45    }
46
47    fn entrypoint(&self) -> String {
48        "tasmlib_arithmetic_u128_shift_left".to_string()
49    }
50
51    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
52        let entrypoint = self.entrypoint();
53        let shift_amount_gt_32 = format!("{entrypoint}_shift_amount_gt_32");
54
55        triton_asm!(
56            // BEFORE: _ v_3 v_2 v_1 v_0 s
57            // AFTER:  _ (value << s)_3 (value << s)_2 (value << s)_1 (value << s)_0
58            {entrypoint}:
59                /* bounds check */
60                push 128
61                dup 1
62                lt
63                assert error_id {Self::SHIFT_AMOUNT_TOO_BIG_ERROR_ID}
64                            // _ v_3 v_2 v_1 v_0 s
65
66                /* special case if shift amount is greater than 32 */
67                dup 0
68                push 32
69                lt
70                skiz
71                    call {shift_amount_gt_32}
72                            // _ v_3 v_2 v_1 v_0 s
73
74                push 2
75                pow         // _ v_3 v_2 v_1 v_0 (2^s)
76
77                dup 0
78                pick 5      // _ v_2 v_1 v_0 (2^s) (2^s) v_3
79                mul
80                place 4     // _ v_3<<s v_2 v_1 v_0 (2^s)
81                xb_mul      // _ v_3<<s v_2<<s v_1<<s v_0<<s
82
83                pick 3
84                split
85                pick 4
86                split
87                pick 5
88                split
89                pick 6
90                split       // _ v_3s_hi v_3s_lo v_2s_hi v_2s_lo v_1s_hi v_1s_lo v_0s_hi v_0s_lo
91                            // _ ╰─ 🗑 ╯ ╰──── w_3 ────╯ ╰──── w_2 ────╯ ╰──── w_1 ────╯ ╰ w_0 ╯
92                place 7
93                add
94                place 6
95                add
96                place 5
97                add
98                place 4
99                pop 1
100
101                return
102
103            // BEFORE: _ [v: u128] s
104            // AFTER:  _ [v << i·32: u128] (s - i·32)
105            // such that i·32 <= s < (i+1)·32
106            {shift_amount_gt_32}:
107                addi -32    // _ v_3 v_2 v_1 v_0 (s - 32)
108                pick 4
109                pop 1       // _ v_2 v_1 v_0 (s - 32)
110                push 0
111                place 1     // _ v_2 v_1 v_0 0 (s - 32)
112
113                dup 0
114                push 32
115                lt
116                skiz
117                    recurse
118                return
119        )
120    }
121
122    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
123        let mut sign_offs = HashMap::new();
124        sign_offs.insert(Reviewer("ferdinand"), 0x4d9d78686bfa6221.into());
125        sign_offs
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    use rand::rngs::StdRng;
132
133    use super::*;
134    use crate::test_prelude::*;
135
136    impl Closure for ShiftLeft {
137        type Args = <ShiftRight as Closure>::Args;
138
139        fn rust_shadow(&self, stack: &mut Vec<BFieldElement>) {
140            let (arg, shift_amount) = pop_encodable::<Self::Args>(stack);
141            assert!(shift_amount < 128);
142            push_encodable(stack, &(arg << shift_amount));
143        }
144
145        fn pseudorandom_args(
146            &self,
147            seed: [u8; 32],
148            bench_case: Option<BenchmarkCase>,
149        ) -> Self::Args {
150            let mut rng = StdRng::from_seed(seed);
151
152            match bench_case {
153                Some(BenchmarkCase::CommonCase) => (0x1282, 15),
154                Some(BenchmarkCase::WorstCase) => (0x123456789abcdef, 125),
155                None => (rng.random(), rng.random_range(0..128)),
156            }
157        }
158
159        fn corner_case_args(&self) -> Vec<Self::Args> {
160            ShiftRight.corner_case_args()
161        }
162    }
163
164    #[test]
165    fn rust_shadow() {
166        ShadowedClosure::new(ShiftLeft).test();
167    }
168
169    #[proptest]
170    fn too_large_shift_crashes_vm(arg: u128, #[strategy(128_u32..)] shift_amount: u32) {
171        test_assertion_failure(
172            &ShadowedClosure::new(ShiftLeft),
173            InitVmState::with_stack(ShiftLeft.set_up_test_stack((arg, shift_amount))),
174            &[ShiftLeft::SHIFT_AMOUNT_TOO_BIG_ERROR_ID],
175        )
176    }
177}
178
179#[cfg(test)]
180mod benches {
181    use super::*;
182    use crate::test_prelude::*;
183
184    #[test]
185    fn benchmark() {
186        ShadowedClosure::new(ShiftLeft).bench();
187    }
188}
tasm_lib/arithmetic/u128/shift_left.rs

tasm_lib/arithmetic/u128/
shift_left.rs
