revm_interpreter/interpreter/
stack.rs

Help
1use crate::{
2    primitives::{B256, U256},
3    InstructionResult,
4};
5use core::{fmt, ptr};
6use std::vec::Vec;
7
8/// EVM interpreter stack limit.
9pub const STACK_LIMIT: usize = 1024;
10
11/// EVM stack with [STACK_LIMIT] capacity of words.
12#[derive(Debug, PartialEq, Eq, Hash)]
13#[cfg_attr(feature = "serde", derive(serde::Serialize))]
14pub struct Stack {
15    /// The underlying data of the stack.
16    data: Vec<U256>,
17}
18
19impl fmt::Display for Stack {
20    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
21        f.write_str("[")?;
22        for (i, x) in self.data.iter().enumerate() {
23            if i > 0 {
24                f.write_str(", ")?;
25            }
26            write!(f, "{x}")?;
27        }
28        f.write_str("]")
29    }
30}
31
32impl Default for Stack {
33    #[inline]
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl Stack {
40    /// Instantiate a new stack with the [default stack limit][STACK_LIMIT].
41    #[inline]
42    pub fn new() -> Self {
43        Self {
44            // SAFETY: expansion functions assume that capacity is `STACK_LIMIT`.
45            data: Vec::with_capacity(STACK_LIMIT),
46        }
47    }
48
49    /// Returns the length of the stack in words.
50    #[inline]
51    pub fn len(&self) -> usize {
52        self.data.len()
53    }
54
55    /// Returns whether the stack is empty.
56    #[inline]
57    pub fn is_empty(&self) -> bool {
58        self.data.is_empty()
59    }
60
61    /// Returns a reference to the underlying data buffer.
62    #[inline]
63    pub fn data(&self) -> &Vec<U256> {
64        &self.data
65    }
66
67    /// Returns a mutable reference to the underlying data buffer.
68    #[inline]
69    pub fn data_mut(&mut self) -> &mut Vec<U256> {
70        &mut self.data
71    }
72
73    /// Consumes the stack and returns the underlying data buffer.
74    #[inline]
75    pub fn into_data(self) -> Vec<U256> {
76        self.data
77    }
78
79    /// Removes the topmost element from the stack and returns it, or `StackUnderflow` if it is
80    /// empty.
81    #[inline]
82    pub fn pop(&mut self) -> Result<U256, InstructionResult> {
83        self.data.pop().ok_or(InstructionResult::StackUnderflow)
84    }
85
86    /// Removes the topmost element from the stack and returns it.
87    ///
88    /// # Safety
89    ///
90    /// The caller is responsible for checking the length of the stack.
91    #[inline]
92    pub unsafe fn pop_unsafe(&mut self) -> U256 {
93        self.data.pop().unwrap_unchecked()
94    }
95
96    /// Peeks the top of the stack.
97    ///
98    /// # Safety
99    ///
100    /// The caller is responsible for checking the length of the stack.
101    #[inline]
102    pub unsafe fn top_unsafe(&mut self) -> &mut U256 {
103        let len = self.data.len();
104        self.data.get_unchecked_mut(len - 1)
105    }
106
107    /// Pop the topmost value, returning the value and the new topmost value.
108    ///
109    /// # Safety
110    ///
111    /// The caller is responsible for checking the length of the stack.
112    #[inline]
113    pub unsafe fn pop_top_unsafe(&mut self) -> (U256, &mut U256) {
114        let pop = self.pop_unsafe();
115        let top = self.top_unsafe();
116        (pop, top)
117    }
118
119    /// Pops 2 values from the stack.
120    ///
121    /// # Safety
122    ///
123    /// The caller is responsible for checking the length of the stack.
124    #[inline]
125    pub unsafe fn pop2_unsafe(&mut self) -> (U256, U256) {
126        let pop1 = self.pop_unsafe();
127        let pop2 = self.pop_unsafe();
128        (pop1, pop2)
129    }
130
131    /// Pops 2 values from the stack and returns them, in addition to the new topmost value.
132    ///
133    /// # Safety
134    ///
135    /// The caller is responsible for checking the length of the stack.
136    #[inline]
137    pub unsafe fn pop2_top_unsafe(&mut self) -> (U256, U256, &mut U256) {
138        let pop1 = self.pop_unsafe();
139        let pop2 = self.pop_unsafe();
140        let top = self.top_unsafe();
141
142        (pop1, pop2, top)
143    }
144
145    /// Pops 3 values from the stack.
146    ///
147    /// # Safety
148    ///
149    /// The caller is responsible for checking the length of the stack.
150    #[inline]
151    pub unsafe fn pop3_unsafe(&mut self) -> (U256, U256, U256) {
152        let pop1 = self.pop_unsafe();
153        let pop2 = self.pop_unsafe();
154        let pop3 = self.pop_unsafe();
155
156        (pop1, pop2, pop3)
157    }
158
159    /// Pops 4 values from the stack.
160    ///
161    /// # Safety
162    ///
163    /// The caller is responsible for checking the length of the stack.
164    #[inline]
165    pub unsafe fn pop4_unsafe(&mut self) -> (U256, U256, U256, U256) {
166        let pop1 = self.pop_unsafe();
167        let pop2 = self.pop_unsafe();
168        let pop3 = self.pop_unsafe();
169        let pop4 = self.pop_unsafe();
170
171        (pop1, pop2, pop3, pop4)
172    }
173
174    /// Pops 5 values from the stack.
175    ///
176    /// # Safety
177    ///
178    /// The caller is responsible for checking the length of the stack.
179    #[inline]
180    pub unsafe fn pop5_unsafe(&mut self) -> (U256, U256, U256, U256, U256) {
181        let pop1 = self.pop_unsafe();
182        let pop2 = self.pop_unsafe();
183        let pop3 = self.pop_unsafe();
184        let pop4 = self.pop_unsafe();
185        let pop5 = self.pop_unsafe();
186
187        (pop1, pop2, pop3, pop4, pop5)
188    }
189
190    /// Push a new value into the stack. If it will exceed the stack limit,
191    /// returns `StackOverflow` error and leaves the stack unchanged.
192    #[inline]
193    pub fn push_b256(&mut self, value: B256) -> Result<(), InstructionResult> {
194        self.push(value.into())
195    }
196
197    /// Push a new value onto the stack.
198    ///
199    /// If it will exceed the stack limit, returns `StackOverflow` error and leaves the stack
200    /// unchanged.
201    #[inline]
202    pub fn push(&mut self, value: U256) -> Result<(), InstructionResult> {
203        // Allows the compiler to optimize out the `Vec::push` capacity check.
204        assume!(self.data.capacity() == STACK_LIMIT);
205        if self.data.len() == STACK_LIMIT {
206            return Err(InstructionResult::StackOverflow);
207        }
208        self.data.push(value);
209        Ok(())
210    }
211
212    /// Peek a value at given index for the stack, where the top of
213    /// the stack is at index `0`. If the index is too large,
214    /// `StackError::Underflow` is returned.
215    #[inline]
216    pub fn peek(&self, no_from_top: usize) -> Result<U256, InstructionResult> {
217        if self.data.len() > no_from_top {
218            Ok(self.data[self.data.len() - no_from_top - 1])
219        } else {
220            Err(InstructionResult::StackUnderflow)
221        }
222    }
223
224    /// Duplicates the `N`th value from the top of the stack.
225    ///
226    /// # Panics
227    ///
228    /// Panics if `n` is 0.
229    #[inline]
230    #[cfg_attr(debug_assertions, track_caller)]
231    pub fn dup(&mut self, n: usize) -> Result<(), InstructionResult> {
232        assume!(n > 0, "attempted to dup 0");
233        let len = self.data.len();
234        if len < n {
235            Err(InstructionResult::StackUnderflow)
236        } else if len + 1 > STACK_LIMIT {
237            Err(InstructionResult::StackOverflow)
238        } else {
239            // SAFETY: check for out of bounds is done above and it makes this safe to do.
240            unsafe {
241                let ptr = self.data.as_mut_ptr().add(len);
242                ptr::copy_nonoverlapping(ptr.sub(n), ptr, 1);
243                self.data.set_len(len + 1);
244            }
245            Ok(())
246        }
247    }
248
249    /// Swaps the topmost value with the `N`th value from the top.
250    ///
251    /// # Panics
252    ///
253    /// Panics if `n` is 0.
254    #[inline(always)]
255    #[cfg_attr(debug_assertions, track_caller)]
256    pub fn swap(&mut self, n: usize) -> Result<(), InstructionResult> {
257        self.exchange(0, n)
258    }
259
260    /// Exchange two values on the stack.
261    ///
262    /// `n` is the first index, and the second index is calculated as `n + m`.
263    ///
264    /// # Panics
265    ///
266    /// Panics if `m` is zero.
267    #[inline]
268    #[cfg_attr(debug_assertions, track_caller)]
269    pub fn exchange(&mut self, n: usize, m: usize) -> Result<(), InstructionResult> {
270        assume!(m > 0, "overlapping exchange");
271        let len = self.data.len();
272        let n_m_index = n + m;
273        if n_m_index >= len {
274            return Err(InstructionResult::StackUnderflow);
275        }
276        // SAFETY: `n` and `n_m` are checked to be within bounds, and they don't overlap.
277        unsafe {
278            // NOTE: `ptr::swap_nonoverlapping` is more efficient than `slice::swap` or `ptr::swap`
279            // because it operates under the assumption that the pointers do not overlap,
280            // eliminating an intemediate copy,
281            // which is a condition we know to be true in this context.
282            let top = self.data.as_mut_ptr().add(len - 1);
283            core::ptr::swap_nonoverlapping(top.sub(n), top.sub(n_m_index), 1);
284        }
285        Ok(())
286    }
287
288    /// Pushes an arbitrary length slice of bytes onto the stack, padding the last word with zeros
289    /// if necessary.
290    #[inline]
291    pub fn push_slice(&mut self, slice: &[u8]) -> Result<(), InstructionResult> {
292        if slice.is_empty() {
293            return Ok(());
294        }
295
296        let n_words = (slice.len() + 31) / 32;
297        let new_len = self.data.len() + n_words;
298        if new_len > STACK_LIMIT {
299            return Err(InstructionResult::StackOverflow);
300        }
301
302        // SAFETY: length checked above.
303        unsafe {
304            let dst = self.data.as_mut_ptr().add(self.data.len()).cast::<u64>();
305            self.data.set_len(new_len);
306
307            let mut i = 0;
308
309            // write full words
310            let words = slice.chunks_exact(32);
311            let partial_last_word = words.remainder();
312            for word in words {
313                // Note: we unroll `U256::from_be_bytes` here to write directly into the buffer,
314                // instead of creating a 32 byte array on the stack and then copying it over.
315                for l in word.rchunks_exact(8) {
316                    dst.add(i).write(u64::from_be_bytes(l.try_into().unwrap()));
317                    i += 1;
318                }
319            }
320
321            if partial_last_word.is_empty() {
322                return Ok(());
323            }
324
325            // write limbs of partial last word
326            let limbs = partial_last_word.rchunks_exact(8);
327            let partial_last_limb = limbs.remainder();
328            for l in limbs {
329                dst.add(i).write(u64::from_be_bytes(l.try_into().unwrap()));
330                i += 1;
331            }
332
333            // write partial last limb by padding with zeros
334            if !partial_last_limb.is_empty() {
335                let mut tmp = [0u8; 8];
336                tmp[8 - partial_last_limb.len()..].copy_from_slice(partial_last_limb);
337                dst.add(i).write(u64::from_be_bytes(tmp));
338                i += 1;
339            }
340
341            debug_assert_eq!((i + 3) / 4, n_words, "wrote too much");
342
343            // zero out upper bytes of last word
344            let m = i % 4; // 32 / 8
345            if m != 0 {
346                dst.add(i).write_bytes(0, 4 - m);
347            }
348        }
349
350        Ok(())
351    }
352
353    /// Set a value at given index for the stack, where the top of the
354    /// stack is at index `0`. If the index is too large,
355    /// `StackError::Underflow` is returned.
356    #[inline]
357    pub fn set(&mut self, no_from_top: usize, val: U256) -> Result<(), InstructionResult> {
358        if self.data.len() > no_from_top {
359            let len = self.data.len();
360            self.data[len - no_from_top - 1] = val;
361            Ok(())
362        } else {
363            Err(InstructionResult::StackUnderflow)
364        }
365    }
366}
367
368#[cfg(feature = "serde")]
369impl<'de> serde::Deserialize<'de> for Stack {
370    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
371    where
372        D: serde::Deserializer<'de>,
373    {
374        let mut data = Vec::<U256>::deserialize(deserializer)?;
375        if data.len() > STACK_LIMIT {
376            return Err(serde::de::Error::custom(std::format!(
377                "stack size exceeds limit: {} > {}",
378                data.len(),
379                STACK_LIMIT
380            )));
381        }
382        data.reserve(STACK_LIMIT - data.len());
383        Ok(Self { data })
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::*;
390
391    fn run(f: impl FnOnce(&mut Stack)) {
392        let mut stack = Stack::new();
393        // fill capacity with non-zero values
394        unsafe {
395            stack.data.set_len(STACK_LIMIT);
396            stack.data.fill(U256::MAX);
397            stack.data.set_len(0);
398        }
399        f(&mut stack);
400    }
401
402    #[test]
403    fn push_slices() {
404        // no-op
405        run(|stack| {
406            stack.push_slice(b"").unwrap();
407            assert_eq!(stack.data, []);
408        });
409
410        // one word
411        run(|stack| {
412            stack.push_slice(&[42]).unwrap();
413            assert_eq!(stack.data, [U256::from(42)]);
414        });
415
416        let n = 0x1111_2222_3333_4444_5555_6666_7777_8888_u128;
417        run(|stack| {
418            stack.push_slice(&n.to_be_bytes()).unwrap();
419            assert_eq!(stack.data, [U256::from(n)]);
420        });
421
422        // more than one word
423        run(|stack| {
424            let b = [U256::from(n).to_be_bytes::<32>(); 2].concat();
425            stack.push_slice(&b).unwrap();
426            assert_eq!(stack.data, [U256::from(n); 2]);
427        });
428
429        run(|stack| {
430            let b = [&[0; 32][..], &[42u8]].concat();
431            stack.push_slice(&b).unwrap();
432            assert_eq!(stack.data, [U256::ZERO, U256::from(42)]);
433        });
434
435        run(|stack| {
436            let b = [&[0; 32][..], &n.to_be_bytes()].concat();
437            stack.push_slice(&b).unwrap();
438            assert_eq!(stack.data, [U256::ZERO, U256::from(n)]);
439        });
440
441        run(|stack| {
442            let b = [&[0; 64][..], &n.to_be_bytes()].concat();
443            stack.push_slice(&b).unwrap();
444            assert_eq!(stack.data, [U256::ZERO, U256::ZERO, U256::from(n)]);
445        });
446    }
447}
revm_interpreter/interpreter/stack.rs

revm_interpreter/interpreter/
stack.rs
