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#[cfg(target_arch = "aarch64")]
8mod aarch64;
9#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
10mod x86;
11
12/// Analyzes the original bytecode to produce a jump table.
13#[inline]
14pub(crate) fn analyze_legacy(bytecode: &[u8]) -> JumpTable {
15    let mut jumps: BitVec<u8> = bitvec![u8, Lsb0; 0; bytecode.len()];
16    let table = jumps.as_raw_mut_slice();
17    let pc = analyze_simd(bytecode, table);
18    analyze_scalar(bytecode, table, pc);
19    JumpTable::new(jumps)
20}
21
22/// Marks the jump destinations of `code` from the instruction at `pc` on.
23///
24/// `pc` must be zero or the first instruction after an already analyzed prefix.
25#[inline]
26fn analyze_scalar(code: &[u8], table: &mut [u8], pc: usize) {
27    let range = code.as_ptr_range();
28    let start = range.start;
29    // A PUSH from the prefix can run past the end, so `wrapping_add` keeps this defined.
30    let mut iterator = start.wrapping_add(pc);
31    let end = range.end;
32
33    while iterator < end {
34        let last_byte = unsafe { *iterator };
35        if last_byte == opcode::JUMPDEST {
36            // SAFETY: Jumps are max length of the code.
37            let offset = unsafe { iterator.offset_from_unsigned(start) };
38            // SAFETY: `table` has a bit for each byte of `code`.
39            unsafe { *table.get_unchecked_mut(offset / 8) |= 1 << (offset % 8) };
40            iterator = unsafe { iterator.add(1) };
41        } else {
42            let push_offset = last_byte.wrapping_sub(opcode::PUSH1);
43            if push_offset < 32 {
44                // A trailing PUSH can advance past the bytecode allocation.
45                // `wrapping_add` keeps that offset computation defined.
46                iterator = iterator.wrapping_add(push_offset as usize + 2);
47            } else {
48                // SAFETY: Iterator access range is checked in the while loop.
49                iterator = unsafe { iterator.add(1) };
50            }
51        }
52    }
53}
54
55/// Marks the jump destinations of complete SIMD blocks and returns the offset of the first
56/// instruction after them.
57#[inline]
58fn analyze_simd(code: &[u8], table: &mut [u8]) -> usize {
59    if code.len() < 16 {
60        return 0;
61    }
62    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
63    {
64        x86::analyze(code, table)
65    }
66    #[cfg(target_arch = "aarch64")]
67    {
68        aarch64::analyze(code, table)
69    }
70    #[cfg(not(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64")))]
71    {
72        let _ = table;
73        0
74    }
75}
76
77/// A SIMD kernel that analyzes blocks of [`Self::LEN`] bytes.
78#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
79trait Kernel {
80    /// Jump destination bits of a block, one per byte.
81    type Bits: Into<u128>;
82
83    /// Offset of the first instruction in a block.
84    type Entry: Entry;
85
86    /// Block length in bytes.
87    const LEN: usize = 8 * core::mem::size_of::<Self::Bits>();
88
89    /// Returns the JUMPDEST bits of the block at `ptr` that start an instruction, and moves
90    /// `entry` to the next block.
91    unsafe fn block(ptr: *const u8, entry: &mut Self::Entry) -> Self::Bits;
92}
93
94/// Analyzes complete blocks with `K` from the block at `pc`, entered at `entry`, and returns
95/// the next block and its entry.
96///
97/// # Safety
98///
99/// The CPU must support the kernel's target features, and `table` must have a bit for each byte
100/// of `code`.
101#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
102#[inline(always)]
103unsafe fn analyze_blocks<K: Kernel>(
104    code: &[u8],
105    table: &mut [u8],
106    (mut pc, entry): (usize, usize),
107) -> (usize, usize) {
108    let mut entry = unsafe { K::Entry::new(entry) };
109    while pc + K::LEN <= code.len() {
110        // SAFETY: the block and its bits are in bounds.
111        unsafe {
112            let bits = K::block(code.as_ptr().add(pc), &mut entry)
113                .into()
114                .to_le_bytes();
115            let dst = table.as_mut_ptr().add(pc / 8);
116            core::ptr::copy_nonoverlapping(bits.as_ptr(), dst, K::LEN / 8);
117        }
118        pc += K::LEN;
119    }
120    (pc, unsafe { entry.offset() })
121}
122
123/// A kernel's representation of the offset of the first instruction in a block.
124#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
125trait Entry: Copy {
126    /// Converts an offset, at most 32, to an entry.
127    unsafe fn new(offset: usize) -> Self;
128
129    /// Converts the entry to an offset.
130    unsafe fn offset(self) -> usize;
131}
132
133/// Every opcode below this, including `0x80..` as signed bytes, is one byte long.
134#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
135const PUSHX: i8 = opcode::PUSH1 as i8 - 1;
136
137/// Subtracted from `max(opcode, PUSH1 - 1)` to get the length of an instruction.
138#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
139const END_OFFSET: u8 = opcode::PUSH1 - 2;
140
141/// Returns lanes counting up from `start`, restarting every `period` lanes.
142#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
143const fn lanes<const N: usize>(period: usize, start: u8) -> [u8; N] {
144    let mut lanes = [0; N];
145    let mut i = 0;
146    while i < N {
147        lanes[i] = start.wrapping_add((i % period) as u8);
148        i += 1;
149    }
150    lanes
151}
152
153/// Returns the JUMPDEST bits of a block without PUSH opcodes, clearing those the previous block's
154/// PUSH covers, and moves `entry` to the next block.
155#[cfg(any(target_arch = "x86", target_arch = "x86_64", target_arch = "aarch64"))]
156#[inline(always)]
157unsafe fn uncarried<E: Entry>(jumpdests: u64, entry: &mut E) -> u64 {
158    let carried = unsafe { entry.offset() };
159    *entry = unsafe { E::new(0) };
160    // At most 32, so the shifts never overflow.
161    jumpdests >> carried << carried
162}
163
164/// Maximum PUSH immediate length plus a terminating STOP.
165const PADDING: usize = 33;
166
167/// Appends zero padding unless the bytecode already ends with 33 zeros.
168pub(crate) fn pad_legacy(bytecode: Bytes) -> Bytes {
169    if bytecode.is_empty() {
170        return Bytes::from_static(&[opcode::STOP]);
171    }
172    if bytecode.ends_with(&[0; PADDING]) {
173        return bytecode;
174    }
175
176    let padded_len = bytecode.len() + PADDING;
177    match bytecode.0.try_into_mut() {
178        Ok(mut bytecode) => {
179            bytecode.resize(padded_len, 0);
180            bytecode.freeze().into()
181        }
182        Err(bytecode) => {
183            let mut padded = Vec::with_capacity(padded_len);
184            padded.extend_from_slice(&bytecode);
185            padded.resize(padded_len, 0);
186            padded.into()
187        }
188    }
189}
190
191#[cfg(test)]
192mod tests {
193    use super::*;
194    use crate::opcode::OpCode;
195    use rand::{rngs::StdRng, RngExt, SeedableRng};
196    use std::vec;
197
198    /// Returns the jump table of `code`, one instruction at a time.
199    fn reference(code: &[u8]) -> Vec<u8> {
200        let mut table = vec![0; code.len().div_ceil(8)];
201        let mut pc = 0;
202        while pc < code.len() {
203            let last = code[pc];
204            if last == opcode::JUMPDEST {
205                table[pc / 8] |= 1 << (pc % 8);
206            }
207            let opcode = OpCode::new_or_unknown(last);
208            pc += 1 + if opcode.is_push() {
209                opcode.info().immediate_size() as usize
210            } else {
211                0
212            };
213        }
214        table
215    }
216
217    /// Returns random bytecode of `len` bytes, drawn from one of several opcode mixes.
218    fn random_code(rng: &mut StdRng, len: usize) -> Vec<u8> {
219        const DENSE: &[u8] = &[
220            opcode::PUSH1,
221            opcode::PUSH1,
222            opcode::PUSH2,
223            opcode::PUSH4,
224            opcode::PUSH32,
225            opcode::JUMPDEST,
226            opcode::JUMPDEST,
227            opcode::STOP,
228            opcode::ADD,
229            opcode::DUPN,
230            0x80,
231            0xff,
232        ];
233        let kind = rng.random_range(0..6);
234        let mut code = Vec::with_capacity(len);
235        while code.len() < len {
236            let byte = match kind {
237                0 => rng.random(),
238                1 => DENSE[rng.random_range(0..DENSE.len())],
239                // No PUSH opcodes.
240                2 => match rng.random() {
241                    opcode::PUSH1..=opcode::PUSH32 => opcode::JUMPDEST,
242                    byte => byte,
243                },
244                3 => [opcode::PUSH1, opcode::JUMPDEST, opcode::ADD][rng.random_range(0..3)],
245                // Rare PUSH opcodes.
246                4 => match rng.random_range(0..64) {
247                    0 => rng.random_range(opcode::PUSH1..=opcode::PUSH32),
248                    1..8 => opcode::JUMPDEST,
249                    _ => opcode::ADD,
250                },
251                // Instructions with random immediates.
252                _ => {
253                    let byte = rng.random();
254                    code.push(byte);
255                    if (opcode::PUSH1..=opcode::PUSH32).contains(&byte) {
256                        for _ in 0..=byte - opcode::PUSH1 {
257                            code.push(rng.random());
258                        }
259                    }
260                    continue;
261                }
262            };
263            code.push(byte);
264        }
265        code.truncate(len);
266        code
267    }
268
269    /// Checks that `simd`, followed by the scalar loop, matches [`reference`] on bytecode ending
270    /// in PUSH instructions, and on random bytecode.
271    pub(super) fn check_simd(simd: impl Fn(&[u8], &mut [u8]) -> usize) {
272        let check = |code: &[u8]| {
273            let mut table = vec![0; code.len().div_ceil(8)];
274            let pc = simd(code, &mut table);
275            analyze_scalar(code, &mut table, pc);
276            assert_eq!(table, reference(code), "{}", primitives::hex::encode(code));
277        };
278
279        // Every PUSH near the end, followed by different instruction endings.
280        let endings: [&[u8]; 4] = [
281            &[],
282            &[opcode::STOP],
283            &[opcode::DUPN],
284            &[opcode::DUPN, opcode::STOP],
285        ];
286        for len in 16usize..160 {
287            for at in len.saturating_sub(40)..len {
288                for push in opcode::PUSH1..=opcode::PUSH32 {
289                    for ending in endings.into_iter().filter(|ending| at + ending.len() < len) {
290                        let mut code = vec![opcode::JUMPDEST; len];
291                        code[at] = push;
292                        code[len - ending.len()..].copy_from_slice(ending);
293                        check(&code);
294                    }
295                }
296            }
297        }
298
299        let mut rng = StdRng::seed_from_u64(0);
300        for i in 0..600 {
301            let len = if i < 400 {
302                i
303            } else {
304                rng.random_range(400..5000)
305            };
306            for _ in 0..8 {
307                check(&random_code(&mut rng, len));
308            }
309        }
310    }
311
312    #[test]
313    fn test_simd_matches_reference() {
314        check_simd(analyze_simd);
315    }
316
317    #[test]
318    fn test_scalar_matches_reference() {
319        check_simd(|_, _| 0);
320    }
321
322    #[test]
323    fn test_bytecode_ends_with_stop_still_padded() {
324        let bytecode = vec![
325            opcode::PUSH1,
326            0x01,
327            opcode::PUSH1,
328            0x02,
329            opcode::ADD,
330            opcode::STOP,
331        ];
332        let padded_bytecode = pad_legacy(bytecode.clone().into());
333        assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
334    }
335
336    #[test]
337    fn test_bytecode_ends_without_stop_requires_padding() {
338        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH1, 0x02, opcode::ADD];
339        let padded_bytecode = pad_legacy(bytecode.clone().into());
340        assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
341    }
342
343    #[test]
344    fn test_bytecode_ends_with_push16() {
345        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH16];
346        let padded_bytecode = pad_legacy(bytecode.clone().into());
347        assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
348    }
349
350    #[test]
351    fn test_bytecode_ends_with_push2() {
352        let bytecode = vec![opcode::PUSH1, 0x01, opcode::PUSH2, 0x02];
353        let padded_bytecode = pad_legacy(bytecode.clone().into());
354        assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
355    }
356
357    #[test]
358    fn test_bytecode_with_jumpdest_at_start() {
359        let bytecode = vec![opcode::JUMPDEST, opcode::PUSH1, 0x01, opcode::STOP];
360        let jump_table = analyze_legacy(&bytecode);
361        assert!(jump_table.is_valid(0)); // First byte should be a valid jumpdest
362    }
363
364    #[test]
365    fn test_bytecode_with_jumpdest_after_push() {
366        let bytecode = vec![opcode::PUSH1, 0x01, opcode::JUMPDEST, opcode::STOP];
367        let jump_table = analyze_legacy(&bytecode);
368        assert!(jump_table.is_valid(2)); // JUMPDEST should be at position 2
369    }
370
371    #[test]
372    fn test_bytecode_with_multiple_jumpdests() {
373        let bytecode = vec![
374            opcode::JUMPDEST,
375            opcode::PUSH1,
376            0x01,
377            opcode::JUMPDEST,
378            opcode::STOP,
379        ];
380        let jump_table = analyze_legacy(&bytecode);
381        assert!(jump_table.is_valid(0)); // First JUMPDEST
382        assert!(jump_table.is_valid(3)); // Second JUMPDEST
383    }
384
385    #[test]
386    fn test_bytecode_with_max_push32() {
387        let bytecode = vec![opcode::PUSH32];
388        let padded_bytecode = pad_legacy(bytecode.clone().into());
389        assert_eq!(padded_bytecode.len(), bytecode.len() + 33); // PUSH32 + 32 bytes + STOP
390    }
391
392    #[test]
393    fn test_truncated_pushes_are_padded_without_inbounds_pointer_advance() {
394        for push in opcode::PUSH1..=opcode::PUSH32 {
395            let bytecode = vec![push];
396            let padded_bytecode = pad_legacy(bytecode.clone().into());
397            let push_immediate_len = (push - opcode::PUSH1 + 1) as usize;
398            assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
399            assert!(padded_bytecode.len() > bytecode.len() + push_immediate_len);
400        }
401    }
402
403    #[test]
404    fn test_bytecode_with_invalid_opcode() {
405        let bytecode = vec![0xFF, opcode::STOP]; // 0xFF is an invalid opcode
406        let jump_table = analyze_legacy(&bytecode);
407        assert!(!jump_table.is_valid(0)); // Invalid opcode should not be a jumpdest
408    }
409
410    #[test]
411    fn test_bytecode_with_sequential_pushes() {
412        let bytecode = vec![
413            opcode::PUSH1,
414            0x01,
415            opcode::PUSH2,
416            0x02,
417            0x03,
418            opcode::PUSH4,
419            0x04,
420            0x05,
421            0x06,
422            0x07,
423            opcode::STOP,
424        ];
425        let jump_table = analyze_legacy(&bytecode);
426        let padded_bytecode = pad_legacy(bytecode.clone().into());
427        assert_eq!(padded_bytecode.len(), bytecode.len() + 33);
428        assert!(!jump_table.is_valid(0)); // PUSH1
429        assert!(!jump_table.is_valid(2)); // PUSH2
430        assert!(!jump_table.is_valid(5)); // PUSH4
431    }
432
433    #[test]
434    fn test_bytecode_with_jumpdest_in_push_data() {
435        let bytecode = vec![
436            opcode::PUSH2,
437            opcode::JUMPDEST, // This should not be treated as a JUMPDEST
438            0x02,
439            opcode::STOP,
440        ];
441        let jump_table = analyze_legacy(&bytecode);
442        assert!(!jump_table.is_valid(1)); // JUMPDEST in push data should not be valid
443    }
444
445    #[test]
446    fn test_bytecode_ends_with_immediate_opcode_and_stop_requires_padding() {
447        // For SWAPN/DUPN/EXCHANGE, the STOP (0x00) is consumed as the immediate operand,
448        // not as an actual STOP instruction, so padding is needed.
449        // The fixed padding supplies both the immediate and a terminating STOP.
450        for op in [opcode::SWAPN, opcode::DUPN, opcode::EXCHANGE] {
451            for bytecode in [vec![op], vec![op, opcode::STOP]] {
452                let original_len = bytecode.len();
453                let padded_bytecode = pad_legacy(bytecode.into());
454                assert_eq!(padded_bytecode.len(), original_len + 33);
455                assert_eq!(padded_bytecode[0], op);
456                assert_eq!(padded_bytecode[1], opcode::STOP);
457                assert_eq!(padded_bytecode[2], opcode::STOP);
458            }
459        }
460    }
461
462    #[test]
463    fn padding_zero_suffix_boundary() {
464        for len in [1, 32, 33, 34, 65] {
465            let raw = Bytes::from(vec![0; len]);
466            let padded = pad_legacy(raw.clone());
467            if len >= 33 {
468                assert_eq!(padded.len(), len);
469                assert_eq!(padded.as_ptr(), raw.as_ptr());
470            } else {
471                assert_eq!(padded.len(), len + 33);
472            }
473            assert!(padded.iter().all(|&byte| byte == 0));
474        }
475
476        // Every byte of the suffix must be zero to skip padding.
477        for nonzero in 0..33 {
478            let mut raw = vec![0; 33];
479            raw[nonzero] = opcode::JUMPDEST;
480            let padded = pad_legacy(raw.clone().into());
481            assert_eq!(padded.len(), 66);
482            assert_eq!(&padded[..33], &raw);
483            assert_eq!(&padded[33..], &[0; 33]);
484        }
485    }
486
487    #[test]
488    fn padding_reuses_owned_capacity() {
489        let mut raw = Vec::with_capacity(34);
490        raw.push(opcode::PUSH32);
491        let raw = Bytes::from(raw);
492        let ptr = raw.as_ptr();
493        let padded = pad_legacy(raw);
494        assert_eq!(padded.as_ptr(), ptr);
495        assert_eq!(padded.len(), 34);
496        assert_eq!(&padded[1..], &[0; 33]);
497    }
498
499    #[test]
500    fn padding_releases_shared_input() {
501        let raw = Bytes::copy_from_slice(&[opcode::PUSH32]);
502        let padded = pad_legacy(raw.clone());
503        assert!(raw.is_unique());
504        assert_ne!(padded.as_ptr(), raw.as_ptr());
505        assert_eq!(&raw[..], &[opcode::PUSH32]);
506        assert_eq!(padded.len(), 34);
507        assert_eq!(&padded[1..], &[0; 33]);
508    }
509}
revm_bytecode/legacy/analysis.rs

revm_bytecode/legacy/
analysis.rs
