revm_bytecode/legacy/
analysis.rs

1use super::JumpTable;
2use crate::opcode;
3use bitvec::{bitvec, order::Lsb0, vec::BitVec};
4use primitives::Bytes;
5use std::vec::Vec;
6
7/// Analyzes the bytecode to produce a jump table and potentially padded bytecode.
8///
9/// Prefer using [`Bytecode::new_legacy`](crate::Bytecode::new_legacy) instead.
10pub(crate) fn analyze_legacy(bytecode: Bytes) -> (JumpTable, Bytes) {
11    let mut jumps: BitVec<u8> = bitvec![u8, Lsb0; 0; bytecode.len()];
12    let range = bytecode.as_ptr_range();
13    let start = range.start;
14    let mut iterator = start;
15    let end = range.end;
16    let mut prev_byte: u8 = 0;
17    let mut last_byte: u8 = 0;
18
19    while iterator < end {
20        prev_byte = last_byte;
21        last_byte = unsafe { *iterator };
22        if last_byte == opcode::JUMPDEST {
23            // SAFETY: Jumps are max length of the code
24            unsafe { jumps.set_unchecked(iterator.offset_from_unsigned(start), true) }
25            iterator = unsafe { iterator.add(1) };
26        } else {
27            let push_offset = last_byte.wrapping_sub(opcode::PUSH1);
28            if push_offset < 32 {
29                // A trailing PUSH can advance the iterator past the end of the
30                // bytecode allocation; `wrapping_add` keeps that offset
31                // computation defined (the `< end` guard prevents any OOB read).
32                iterator = iterator.wrapping_add(push_offset as usize + 2);
33            } else {
34                // SAFETY: Iterator access range is checked in the while loop
35                iterator = unsafe { iterator.add(1) };
36            }
37        }
38    }
39
40    // Calculate padding needed:
41    // push_overflow: bytes needed for incomplete PUSH immediate data
42    let push_overflow = (iterator as usize) - (end as usize);
43    let mut padding = push_overflow;
44
45    if last_byte == opcode::STOP {
46        // DUPN/SWAPN/EXCHANGE have 1-byte immediates that aren't handled by the loop above,
47        // so we need extra padding to ensure safe execution.
48        padding += is_dupn_swapn_exchange(prev_byte) as usize;
49    } else {
50        // Add final STOP instruction and immediate for DUPN/SWAPN/EXCHANGE
51        padding += 1 + is_dupn_swapn_exchange(last_byte) as usize;
52    }
53
54    let bytecode = if padding > 0 {
55        let mut padded = Vec::with_capacity(bytecode.len() + padding);
56        padded.extend_from_slice(&bytecode);
57        padded.resize(padded.len() + padding, 0);
58        Bytes::from(padded)
59    } else {
60        bytecode
61    };
62
63    (JumpTable::new(jumps), bytecode)
64}
65
66/// Returns true if the opcode is DUPN, SWAPN, or EXCHANGE.
67const fn is_dupn_swapn_exchange(opcode: u8) -> bool {
68    opcode.wrapping_sub(opcode::DUPN) < 3
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_bytecode_ends_with_stop_no_padding_needed() {
77        let bytecode = vec![
78            opcode::PUSH1,
79            0x01,
80            opcode::PUSH1,
81            0x02,
82            opcode::ADD,
83            opcode::STOP,
84        ];
85        let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
86        assert_eq!(padded_bytecode.len(), bytecode.len());
87    }
88
89    #[test]
90    fn test_bytecode_ends_without_stop_requires_padding() {
91        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH1, 0x02, opcode::ADD];
92        let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
93        assert_eq!(padded_bytecode.len(), bytecode.len() + 1);
94    }
95
96    #[test]
97    fn test_bytecode_ends_with_push16_requires_17_bytes_padding() {
98        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH16];
99        let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
100        assert_eq!(padded_bytecode.len(), bytecode.len() + 17);
101    }
102
103    #[test]
104    fn test_bytecode_ends_with_push2_requires_2_bytes_padding() {
105        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH2, 0x02];
106        let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
107        assert_eq!(padded_bytecode.len(), bytecode.len() + 2);
108    }
109
110    #[test]
111    fn test_bytecode_with_jumpdest_at_start() {
112        let bytecode = vec![opcode::JUMPDEST, opcode::PUSH1, 0x01, opcode::STOP];
113        let (jump_table, _) = analyze_legacy(bytecode.into());
114        assert!(jump_table.is_valid(0)); // First byte should be a valid jumpdest
115    }
116
117    #[test]
118    fn test_bytecode_with_jumpdest_after_push() {
119        let bytecode = vec![opcode::PUSH1, 0x01, opcode::JUMPDEST, opcode::STOP];
120        let (jump_table, _) = analyze_legacy(bytecode.into());
121        assert!(jump_table.is_valid(2)); // JUMPDEST should be at position 2
122    }
123
124    #[test]
125    fn test_bytecode_with_multiple_jumpdests() {
126        let bytecode = vec![
127            opcode::JUMPDEST,
128            opcode::PUSH1,
129            0x01,
130            opcode::JUMPDEST,
131            opcode::STOP,
132        ];
133        let (jump_table, _) = analyze_legacy(bytecode.into());
134        assert!(jump_table.is_valid(0)); // First JUMPDEST
135        assert!(jump_table.is_valid(3)); // Second JUMPDEST
136    }
137
138    #[test]
139    fn test_bytecode_with_max_push32() {
140        let bytecode = vec![opcode::PUSH32];
141        let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
142        assert_eq!(padded_bytecode.len(), bytecode.len() + 33); // PUSH32 + 32 bytes + STOP
143    }
144
145    #[test]
146    fn test_truncated_pushes_are_padded_without_inbounds_pointer_advance() {
147        for push in opcode::PUSH1..=opcode::PUSH32 {
148            let bytecode = vec![push];
149            let (_, padded_bytecode) = analyze_legacy(bytecode.clone().into());
150            let push_immediate_len = (push - opcode::PUSH1 + 1) as usize;
151            assert_eq!(
152                padded_bytecode.len(),
153                bytecode.len() + push_immediate_len + 1
154            );
155        }
156    }
157
158    #[test]
159    fn test_bytecode_with_invalid_opcode() {
160        let bytecode = vec![0xFF, opcode::STOP]; // 0xFF is an invalid opcode
161        let (jump_table, _) = analyze_legacy(bytecode.into());
162        assert!(!jump_table.is_valid(0)); // Invalid opcode should not be a jumpdest
163    }
164
165    #[test]
166    fn test_bytecode_with_sequential_pushes() {
167        let bytecode = vec![
168            opcode::PUSH1,
169            0x01,
170            opcode::PUSH2,
171            0x02,
172            0x03,
173            opcode::PUSH4,
174            0x04,
175            0x05,
176            0x06,
177            0x07,
178            opcode::STOP,
179        ];
180        let (jump_table, padded_bytecode) = analyze_legacy(bytecode.clone().into());
181        assert_eq!(padded_bytecode.len(), bytecode.len());
182        assert!(!jump_table.is_valid(0)); // PUSH1
183        assert!(!jump_table.is_valid(2)); // PUSH2
184        assert!(!jump_table.is_valid(5)); // PUSH4
185    }
186
187    #[test]
188    fn test_bytecode_with_jumpdest_in_push_data() {
189        let bytecode = vec![
190            opcode::PUSH2,
191            opcode::JUMPDEST, // This should not be treated as a JUMPDEST
192            0x02,
193            opcode::STOP,
194        ];
195        let (jump_table, _) = analyze_legacy(bytecode.into());
196        assert!(!jump_table.is_valid(1)); // JUMPDEST in push data should not be valid
197    }
198
199    #[test]
200    fn test_bytecode_ends_with_immediate_opcode_and_stop_requires_padding() {
201        // For SWAPN/DUPN/EXCHANGE, the STOP (0x00) is consumed as the immediate operand,
202        // not as an actual STOP instruction, so padding is needed.
203        // [OPCODE]       -> [OPCODE, STOP, STOP] (3 bytes)
204        // [OPCODE, STOP] -> [OPCODE, STOP, STOP] (3 bytes)
205        for op in [opcode::SWAPN, opcode::DUPN, opcode::EXCHANGE] {
206            for bytecode in [vec![op], vec![op, opcode::STOP]] {
207                let (_, padded_bytecode) = analyze_legacy(bytecode.into());
208                assert_eq!(padded_bytecode.len(), 3);
209                assert_eq!(padded_bytecode[0], op);
210                assert_eq!(padded_bytecode[1], opcode::STOP);
211                assert_eq!(padded_bytecode[2], opcode::STOP);
212            }
213        }
214    }
215}
revm_bytecode/legacy/analysis.rs

revm_bytecode/legacy/
analysis.rs
