ethrex-common 29.0.0

use std::collections::BTreeMap;
use std::sync::{Arc, LazyLock};

use bytes::{BufMut, Bytes};
use ethereum_types::{H256, U256};
use ethrex_crypto::{Crypto, NativeCrypto};
use ethrex_trie::Trie;
use rustc_hash::FxHashMap;
use serde::{Deserialize, Serialize};

use ethrex_rlp::{
    decode::RLPDecode,
    encode::RLPEncode,
    error::RLPDecodeError,
    structs::{Decoder, Encoder},
};

use super::GenesisAccount;
use crate::constants::{EMPTY_KECCAK_HASH, EMPTY_TRIE_HASH};

/// Shared empty jumpdest bitmap. `Code::default()` and any bytecode without a
/// `JUMPDEST` clone this (a refcount bump) instead of allocating a fresh empty
/// `Arc` header each time. This matters because the per-tx `Code::default()`
/// placeholder and every EOA / empty-code load would otherwise each allocate.
static EMPTY_JUMPDESTS: LazyLock<Arc<[u8]>> = LazyLock::new(|| Arc::from(Vec::new()));

/// Trailing STOP bytes appended to every bytecode so the dispatch loop can read
/// the next opcode without a bounds check. 33 is the widest single-opcode advance
/// (PUSH32: 1 opcode byte + 32 immediate bytes), so `pc` can never step past the
/// padding regardless of which opcode sits at the last real byte.
pub const BYTECODE_PADDING: usize = 33;

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Code {
    // hash is only used for bytecodes stored in the DB, either for reading it from the DB
    // or with the CODEHASH opcode, which needs an account address as argument and
    // thus only accessed persisted bytecodes.
    // We use a bogus H256::zero() value for initcodes as there is no way for the VM or
    // endpoints to access that hash, saving one expensive Keccak hash.
    pub hash: H256,
    /// bytecode padded with 33 zeroes (STOP opcodes, due to PUSH32) to avoid checks on the hot path.
    bytecode: Bytes,
    /// The real bytecode length, needed for some opcodes, `bytecode` is padded with 33 STOPs to avoid checked adds on hot loop.
    bytecode_len: usize,
    /// One bit per bytecode byte, set when that offset holds a `JUMPDEST` that is not
    /// part of a `PUSH` immediate. Costs `ceil(len / 8)` bytes regardless of how dense
    /// the jump destinations are, and validating a jump is a bit test rather than a
    /// search.
    ///
    /// Bytecode with no jump destination stores a zero-length bitmap ([`EMPTY_JUMPDESTS`])
    /// rather than an all-zero one, so this is not always `ceil(len / 8)` bytes long;
    /// [`Code::is_valid_jumpdest`] reads a missing byte as "no jump destination".
    //
    // `Arc<[u8]>` so cloning `Code` (hot: every message-call resolves and clones
    // the callee's code) is a refcount bump instead of deep-copying the bitmap.
    // Serializes via serde's `rc` feature (enabled workspace-wide).
    jumpdests: Arc<[u8]>,
}

impl Code {
    // SAFETY: hash will be stored as-is, so it either needs to match
    // the real code hash (i.e. it was precomputed and we're reusing)
    // or never be read (e.g. for initcode).
    //
    // `code` is the logical, unpadded bytecode; `BYTECODE_PADDING` STOP bytes are
    // appended internally by `from_parts_unchecked`.
    pub fn from_bytecode_unchecked(code: Bytes, hash: H256) -> Self {
        let jumpdests = Self::compute_jumpdests(&code);
        Self::from_parts_unchecked(hash, &code, jumpdests)
    }

    /// `code` is the logical, unpadded bytecode; `BYTECODE_PADDING` STOP bytes are
    /// appended internally by `from_parts_unchecked`.
    pub fn from_bytecode(code: Bytes, crypto: &dyn Crypto) -> Self {
        let jumpdests = Self::compute_jumpdests(&code);
        let hash = H256(crypto.keccak256(code.as_ref()));
        Self::from_parts_unchecked(hash, &code, jumpdests)
    }

    /// Builds a `Code` from precomputed parts. The caller must guarantee `hash`
    /// and `jumpdests` correspond to `code`; neither is recomputed or validated.
    ///
    /// `code` is the logical, unpadded bytecode: this function appends
    /// `BYTECODE_PADDING` STOP bytes and records the original length in
    /// `bytecode_len`. Never pass a pre-padded buffer, or the logical length and
    /// every `JUMPDEST`/`PUSH` offset derived from it would be wrong.
    pub fn from_parts_unchecked(hash: H256, code: &[u8], jumpdests: Arc<[u8]>) -> Self {
        let bytecode_len = code.len();
        let mut padded_code = Vec::with_capacity(bytecode_len + BYTECODE_PADDING);
        padded_code.extend_from_slice(code);
        padded_code.extend_from_slice(&[0u8; BYTECODE_PADDING]);
        Self {
            hash,
            bytecode: Bytes::from_owner(padded_code),
            bytecode_len,
            jumpdests,
        }
    }

    /// Builds the [`Code::jumpdests`] bitmap: the bit of every `JUMPDEST` that is not a
    /// `PUSH` immediate.
    ///
    /// On aarch64, and on x86_64 with SSSE3, this runs without a data-dependent branch
    /// (see `by_block`), because a scan that branches on each opcode stalls on every
    /// misprediction, and random bytecode mispredicts on most bytes. execution-specs#3631
    /// builds such initcode on purpose. Other targets are mostly the zkVM guests, which
    /// have no branch predictor and would only pay for the extra instructions, so they
    /// keep the plain scan (`jumpdests_by_opcode`).
    pub fn compute_jumpdests(code: &[u8]) -> Arc<[u8]> {
        let mut bitmap = vec![0u8; code.len().div_ceil(8)];
        #[cfg(any(
            target_arch = "aarch64",
            all(target_arch = "x86_64", target_feature = "ssse3")
        ))]
        let any = by_block::jumpdests(code, &mut bitmap);
        #[cfg(not(any(
            target_arch = "aarch64",
            all(target_arch = "x86_64", target_feature = "ssse3")
        )))]
        let any = jumpdests_by_opcode(code, &mut bitmap);
        // Share the single empty bitmap for jumpless bytecode (very common: EOAs,
        // tiny contracts) so we don't allocate for an all-zero map; `is_valid_jumpdest`
        // reads a missing byte as "no jump destination".
        if any {
            Arc::from(bitmap)
        } else {
            EMPTY_JUMPDESTS.clone()
        }
    }

    /// Whether `offset` is a valid jump destination, i.e. it holds a `JUMPDEST` that is
    /// not part of a `PUSH` immediate. Offsets past the bytecode are not valid.
    #[inline]
    pub fn is_valid_jumpdest(&self, offset: usize) -> bool {
        self.jumpdests
            .get(offset / 8)
            .is_some_and(|byte| byte & (1 << (offset % 8)) != 0)
    }

    /// The raw [`Code::jumpdests`] bitmap, for persisting it alongside the bytecode.
    #[inline]
    pub fn jumpdests(&self) -> &[u8] {
        &self.jumpdests
    }

    #[inline]
    pub fn code(&self) -> &[u8] {
        self.bytecode.get(..self.bytecode_len).unwrap_or_default()
    }

    #[inline]
    pub fn code_bytes(&self) -> Bytes {
        self.bytecode.slice(..self.bytecode_len)
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.bytecode_len
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.bytecode_len == 0
    }

    /// Returns the padded bytecode buffer (real code + [`BYTECODE_PADDING`] trailing
    /// STOPs) used by the opcode dispatch loop to read opcodes without bounds checks.
    /// Use [`Code::code`] for the real, unpadded bytecode.
    #[inline]
    pub fn dispatch_buf(&self) -> &[u8] {
        &self.bytecode
    }

    /// Estimates the size of the Code struct in bytes
    /// (including stack size and heap allocation).
    ///
    /// Note: an estimate. It ignores allocator overhead and the `Arc`/`Bytes` control
    /// blocks, so it slightly under-counts, and a shared allocation is attributed in
    /// full to every entry holding it.
    ///
    /// # Returns
    ///
    /// usize - Estimated size in bytes
    pub fn size(&self) -> usize {
        let hash_size = size_of::<H256>();
        let bytes_size = size_of::<Bytes>() + self.bytecode.len();
        let bitmap_size = size_of::<Arc<[u8]>>() + self.jumpdests.len();
        hash_size + bytes_size + bitmap_size
    }
}

// Opcodes the jump destination analysis needs. The vm module defines them too, but
// depending on it here would be circular.
const OP_JUMPDEST: u8 = 0x5B;
const OP_PUSH1: u8 = 0x60;
const OP_PUSH32: u8 = 0x7F;

/// Fills `bitmap` for `code` one opcode at a time and returns whether any bit is set.
///
/// The bits of a byte are accumulated in a register and written once the scan leaves
/// that byte, which the monotonic `i` makes safe. Reading the bitmap back inside the
/// loop instead would turn each `JUMPDEST` into a read-modify-write, and indexing it
/// would put a bounds-check panic path in the loop body, which inhibits optimization
/// of every iteration rather than only the ones that find a destination.
#[cfg_attr(
    any(
        target_arch = "aarch64",
        all(target_arch = "x86_64", target_feature = "ssse3")
    ),
    allow(dead_code)
)]
fn jumpdests_by_opcode(code: &[u8], bitmap: &mut [u8]) -> bool {
    let mut any = false;
    let mut current_byte = usize::MAX;
    let mut bits = 0u8;
    let mut i = 0;
    while i < code.len() {
        match code[i] {
            OP_JUMPDEST => {
                if i / 8 != current_byte {
                    if let Some(byte) = bitmap.get_mut(current_byte) {
                        *byte = bits;
                    }
                    current_byte = i / 8;
                    bits = 0;
                }
                bits |= 1 << (i % 8);
                any = true;
            }
            // PUSH1..PUSH32 are followed by 1..32 immediate bytes.
            c @ OP_PUSH1..=OP_PUSH32 => i += usize::from(c - OP_PUSH1) + 1,
            _ => (),
        }
        i += 1;
    }
    if let Some(byte) = bitmap.get_mut(current_byte) {
        *byte = bits;
    }
    any
}

/// The jump destination analysis without a data-dependent branch, 64 bytes at a time.
///
/// Whether a byte is an opcode depends on every `PUSH` before it, so the natural scan
/// branches on each opcode, and on random bytecode that branch mispredicts on most bytes.
/// Here the work per block is the same whatever its bytes are:
///
/// 1. In each 16-byte group, the walks from all 16 bytes, each as if its byte were an
///    opcode, advance at once until they leave the group (see [`group_walks`]).
/// 2. The real walk enters the block where the previous block's walk left it. Where it
///    leaves a group is where it enters the next one, so four dependent loads pick the
///    walk of each group, and give where the walk enters the next block.
#[cfg(any(
    target_arch = "aarch64",
    all(target_arch = "x86_64", target_feature = "ssse3")
))]
mod by_block {
    use super::{OP_JUMPDEST, OP_PUSH1};
    use lanes::Lanes;

    /// Bytes per block, one `u64` of bitmap.
    const BLOCK: usize = 64;
    /// Bytes per group, one SIMD register.
    const GROUP: usize = 16;

    /// Fills `bitmap` for `code` and returns whether any bit is set.
    pub(super) fn jumpdests(code: &[u8], bitmap: &mut [u8]) -> bool {
        let mut walks = Walks::new();
        let (blocks, tail) = code.as_chunks::<BLOCK>();
        let mut carry = 0;
        let mut any = 0;
        // A full block fills exactly one 8-byte word of the bitmap.
        for (block, word) in blocks.iter().zip(bitmap.as_chunks_mut::<8>().0) {
            let valid = block_jumpdests(block, &mut carry, &mut walks);
            *word = valid.to_le_bytes();
            any |= valid;
        }
        if !tail.is_empty() {
            // Zeros are STOPs, which are neither destinations nor PUSHes.
            let mut padded = [0; BLOCK];
            padded[..tail.len()].copy_from_slice(tail);
            let valid = block_jumpdests(&padded, &mut carry, &mut walks);
            let rest = &mut bitmap[blocks.len() * 8..];
            rest.copy_from_slice(&valid.to_le_bytes()[..rest.len()]);
            any |= valid;
        }
        any != 0
    }

    /// The walks of one block's bytes (see [`group_walks`]), by position in the block:
    /// where each leaves its group, and which bytes of the group it lands on, the lower
    /// 8 in `low_stops` and the upper 8 in `high_stops`.
    ///
    /// Positions from 64 on stand for the next block: they lead to themselves and land on
    /// nothing, so a walk that has left the block stays where it is.
    struct Walks {
        exits: [u8; 2 * BLOCK],
        low_stops: [u8; 2 * BLOCK],
        high_stops: [u8; 2 * BLOCK],
    }

    impl Walks {
        fn new() -> Self {
            Self {
                exits: core::array::from_fn(|i| i as u8),
                low_stops: [0; 2 * BLOCK],
                high_stops: [0; 2 * BLOCK],
            }
        }
    }

    /// The valid jump destinations of one block, bit `i` for byte `i`.
    ///
    /// `carry` is how many leading bytes of the block are immediates of a `PUSH` in the
    /// previous block, and is updated for the next one.
    #[inline(always)]
    fn block_jumpdests(block: &[u8; BLOCK], carry: &mut usize, walks: &mut Walks) -> u64 {
        let groups = block.as_chunks::<GROUP>().0;
        let groups: [Lanes; BLOCK / GROUP] = core::array::from_fn(|g| Lanes::load(&groups[g]));
        let jumpdests = Lanes::bits(groups.map(|bytes| bytes.eq(Lanes::splat(OP_JUMPDEST))));
        for (g, bytes) in groups.into_iter().enumerate() {
            let (exits, low_stops, high_stops) = group_walks(bytes);
            // From here on, positions are relative to the block instead of the group.
            let exits = exits.add(Lanes::splat((g * GROUP) as u8));
            exits.store(&mut walks.exits.as_chunks_mut::<GROUP>().0[g]);
            low_stops.store(&mut walks.low_stops.as_chunks_mut::<GROUP>().0[g]);
            high_stops.store(&mut walks.high_stops.as_chunks_mut::<GROUP>().0[g]);
        }
        let mut at = *carry;
        let mut opcodes = 0;
        for _ in 0..BLOCK / GROUP {
            // At most 96, 32 immediates past the block; the modulo drops the bounds checks.
            let i = at % (2 * BLOCK);
            let stops = u64::from(walks.low_stops[i]) | (u64::from(walks.high_stops[i]) << 8);
            // Past the block there are no stops, so the shift only matters inside it.
            let group_start = i & (BLOCK - GROUP);
            opcodes |= stops << group_start;
            at = usize::from(walks.exits[i]);
        }
        // Each load moves the walk past at least one more group, so it is now past the
        // block, by as many bytes as the next block starts with immediates.
        *carry = at - BLOCK;
        jumpdests & opcodes
    }

    /// For each byte of a 16-byte group, the walk that starts if that byte is an opcode,
    /// up to where it leaves the group: the position it leaves to, relative to the group
    /// (16 to 48), and the bytes it lands on, bits 0 to 7 in the first mask and bits 8 to
    /// 15 in the second.
    ///
    /// All 16 walks advance together by pointer doubling: each round, a walk that is still
    /// in the group takes as many steps again by continuing with the walk of the byte it
    /// is at, which a table lookup of every lane (TBL on aarch64, PSHUFB on x86_64) reads.
    /// A step moves at least one byte, so four rounds (16 steps) take every walk out of
    /// the group.
    #[inline(always)]
    fn group_walks(bytes: Lanes) -> (Lanes, Lanes, Lanes) {
        const POSITIONS_PLUS_ONE: [u8; GROUP] =
            [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
        const LOW_POSITION_BITS: [u8; GROUP] =
            [1, 2, 4, 8, 16, 32, 64, 128, 0, 0, 0, 0, 0, 0, 0, 0];
        const HIGH_POSITION_BITS: [u8; GROUP] =
            [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 4, 8, 16, 32, 64, 128];
        // PUSH1..PUSH32 are exactly the bytes 0b011x_xxxx, with `byte - PUSH1 + 1`
        // immediates.
        let is_push = bytes.and(Lanes::splat(0xE0)).eq(Lanes::splat(OP_PUSH1));
        let immediates = is_push.and(bytes.sub(Lanes::splat(OP_PUSH1 - 1)));
        // One step, past the opcode and its immediates.
        let mut exits = Lanes::load(&POSITIONS_PLUS_ONE).add(immediates);
        let mut low_stops = Lanes::load(&LOW_POSITION_BITS);
        let mut high_stops = Lanes::load(&HIGH_POSITION_BITS);
        // The lookups read zero for a walk that has left the group, so its stops stay as
        // they are, and `max` keeps its exit, while a walk still inside moves ahead.
        // Stops in the lower 8 bytes are a walk's first 8 at most, so the last round can
        // skip them.
        for round in 0..4 {
            if round < 3 {
                low_stops = low_stops.or(low_stops.lookup(exits));
            }
            high_stops = high_stops.or(high_stops.lookup(exits));
            exits = exits.max(exits.lookup(exits));
        }
        (exits, low_stops, high_stops)
    }

    #[cfg(target_arch = "aarch64")]
    mod lanes {
        use core::arch::aarch64::*;

        /// 16 bytes in a NEON register.
        #[derive(Clone, Copy)]
        pub(super) struct Lanes(uint8x16_t);

        // SAFETY (every `unsafe` below): NEON is part of the aarch64 baseline, and the
        // loads and stores go through a reference to exactly 16 bytes, with no alignment
        // requirement.
        impl Lanes {
            #[inline(always)]
            pub(super) fn load(bytes: &[u8; 16]) -> Self {
                unsafe { Self(vld1q_u8(bytes.as_ptr())) }
            }

            #[inline(always)]
            pub(super) fn store(self, out: &mut [u8; 16]) {
                unsafe { vst1q_u8(out.as_mut_ptr(), self.0) }
            }

            #[inline(always)]
            pub(super) fn splat(byte: u8) -> Self {
                unsafe { Self(vdupq_n_u8(byte)) }
            }

            #[inline(always)]
            pub(super) fn and(self, other: Self) -> Self {
                unsafe { Self(vandq_u8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn or(self, other: Self) -> Self {
                unsafe { Self(vorrq_u8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn add(self, other: Self) -> Self {
                unsafe { Self(vaddq_u8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn sub(self, other: Self) -> Self {
                unsafe { Self(vsubq_u8(self.0, other.0)) }
            }

            /// All ones in the lanes that are equal, zero in the others.
            #[inline(always)]
            pub(super) fn eq(self, other: Self) -> Self {
                unsafe { Self(vceqq_u8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn max(self, other: Self) -> Self {
                unsafe { Self(vmaxq_u8(self.0, other.0)) }
            }

            /// Lane `i` of `self` for each lane `i` of `indices` below 16, zero for the rest.
            #[inline(always)]
            pub(super) fn lookup(self, indices: Self) -> Self {
                unsafe { Self(vqtbl1q_u8(self.0, indices.0)) }
            }

            /// The top bit of every lane of four registers of all-ones or zero lanes.
            ///
            /// NEON has no instruction that gathers one bit per byte, so each lane keeps
            /// the bit of its position within 8 bytes, and three rounds of pairwise adds
            /// pack them into one `u64`.
            #[inline(always)]
            pub(super) fn bits(masks: [Self; 4]) -> u64 {
                unsafe {
                    let position_bits = vreinterpretq_u8_u64(vdupq_n_u64(0x8040_2010_0804_0201));
                    let [a, b, c, d] = masks.map(|m| vandq_u8(m.0, position_bits));
                    let quarters = vpaddq_u8(vpaddq_u8(a, b), vpaddq_u8(c, d));
                    vgetq_lane_u64::<0>(vreinterpretq_u64_u8(vpaddq_u8(quarters, quarters)))
                }
            }
        }
    }

    #[cfg(target_arch = "x86_64")]
    mod lanes {
        use core::arch::x86_64::*;

        /// 16 bytes in an SSE register.
        #[derive(Clone, Copy)]
        pub(super) struct Lanes(__m128i);

        // SAFETY (every `unsafe` below): SSE2 is part of the x86_64 baseline, SSSE3 is
        // enabled for this build (see the `cfg` on `by_block`), and the loads and stores
        // go through a reference to exactly 16 bytes, with no alignment requirement.
        impl Lanes {
            #[inline(always)]
            pub(super) fn load(bytes: &[u8; 16]) -> Self {
                unsafe { Self(_mm_loadu_si128(bytes.as_ptr().cast())) }
            }

            #[inline(always)]
            pub(super) fn store(self, out: &mut [u8; 16]) {
                unsafe { _mm_storeu_si128(out.as_mut_ptr().cast(), self.0) }
            }

            #[inline(always)]
            pub(super) fn splat(byte: u8) -> Self {
                unsafe { Self(_mm_set1_epi8(byte as i8)) }
            }

            #[inline(always)]
            pub(super) fn and(self, other: Self) -> Self {
                unsafe { Self(_mm_and_si128(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn or(self, other: Self) -> Self {
                unsafe { Self(_mm_or_si128(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn add(self, other: Self) -> Self {
                unsafe { Self(_mm_add_epi8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn sub(self, other: Self) -> Self {
                unsafe { Self(_mm_sub_epi8(self.0, other.0)) }
            }

            /// All ones in the lanes that are equal, zero in the others.
            #[inline(always)]
            pub(super) fn eq(self, other: Self) -> Self {
                unsafe { Self(_mm_cmpeq_epi8(self.0, other.0)) }
            }

            #[inline(always)]
            pub(super) fn max(self, other: Self) -> Self {
                unsafe { Self(_mm_max_epu8(self.0, other.0)) }
            }

            /// Lane `i` of `self` for each lane `i` of `indices` below 16, zero for the rest
            /// up to 143.
            #[inline(always)]
            pub(super) fn lookup(self, indices: Self) -> Self {
                // PSHUFB zeroes the lanes whose index has its top bit set and otherwise
                // uses the index's low 4 bits. Adding 0x70 sets the top bit of 16..=143
                // and keeps the low 4 bits of 0..=15.
                unsafe {
                    let indices = _mm_add_epi8(indices.0, _mm_set1_epi8(0x70));
                    Self(_mm_shuffle_epi8(self.0, indices))
                }
            }

            /// The top bit of every lane of four registers of all-ones or zero lanes.
            #[inline(always)]
            pub(super) fn bits(masks: [Self; 4]) -> u64 {
                masks.iter().enumerate().fold(0, |bits, (i, m)| {
                    let lanes = unsafe { _mm_movemask_epi8(m.0) } as u16;
                    bits | (u64::from(lanes) << (16 * i))
                })
            }
        }
    }
}

/// Serde shadow for [`Code`]. Stores the *logical* (unpadded) bytecode so the
/// padding is never part of the serialized form. Deserialization re-pads through
/// [`Code::from_parts_unchecked`], which keeps the dispatch-loop invariant (every
/// `Code` is padded with [`BYTECODE_PADDING`] trailing STOPs) sound regardless of
/// where the bytes came from. Deserializing the padded buffer directly would
/// otherwise let unpadded input through and cause OOB reads during execution.
/// The jump destinations are deliberately absent: they are a pure function of the
/// bytecode, so carrying them would put a derived value in the wire format of everything
/// that embeds a `Code` (notably `AccountUpdate`, which the L2 rollup store persists with
/// bincode) and couple that format to how they happen to be represented.
/// Wire form of [`Code`]. Jump destinations are recomputed from `code` on
/// deserialize, never read from here — but the `jump_targets` field is kept so
/// the layout stays byte-identical to the pre-bitmap `Code` serialization.
/// `Code` is embedded in `AccountUpdate`, which is persisted with bincode (a
/// non-self-describing, positional codec) in the L2 rollup store; dropping the
/// field would shift every following field and make existing rows undecodable.
/// It is always serialized empty and ignored on read.
#[derive(Serialize, Deserialize)]
struct CodeSerde {
    hash: H256,
    code: Bytes,
    jump_targets: Arc<[u32]>,
}

impl Serialize for Code {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        CodeSerde {
            hash: self.hash,
            code: self.code_bytes(),
            jump_targets: Arc::from([]),
        }
        .serialize(serializer)
    }
}

impl<'de> Deserialize<'de> for Code {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        // `jump_targets` is read only to consume its bytes (layout compatibility);
        // the bitmap is always recomputed from `code`.
        let CodeSerde {
            hash,
            code,
            jump_targets: _,
        } = CodeSerde::deserialize(deserializer)?;
        Ok(Self::from_parts_unchecked(
            hash,
            &code,
            Self::compute_jumpdests(&code),
        ))
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct CodeMetadata {
    pub length: u64,
}

#[derive(Clone, Default, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Account {
    pub info: AccountInfo,
    pub code: Code,
    pub storage: FxHashMap<H256, U256>,
}

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize, Eq, Hash)]
pub struct AccountInfo {
    pub code_hash: H256,
    pub balance: U256,
    pub nonce: u64,
}

#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct AccountState {
    pub nonce: u64,
    pub balance: U256,
    pub storage_root: H256,
    pub code_hash: H256,
}

/// A slim codec for an [`AccountState`].
///
/// The slim codec will optimize both the [storage root](AccountState::storage_root) and the
/// [code hash](AccountState::code_hash)'s encoding so that it does not take space when empty.
///
/// The correct way to use it is to wrap the [`AccountState`] and encode it using this codec, and
/// not to store the codec as a field in a struct.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct AccountStateSlimCodec(pub AccountState);

impl Default for AccountInfo {
    fn default() -> Self {
        Self {
            code_hash: *EMPTY_KECCAK_HASH,
            balance: Default::default(),
            nonce: Default::default(),
        }
    }
}

impl Default for AccountState {
    fn default() -> Self {
        Self {
            nonce: Default::default(),
            balance: Default::default(),
            storage_root: *EMPTY_TRIE_HASH,
            code_hash: *EMPTY_KECCAK_HASH,
        }
    }
}

impl Default for Code {
    fn default() -> Self {
        Self {
            bytecode: Bytes::from_static(&[0u8; BYTECODE_PADDING]),
            bytecode_len: 0,
            hash: *EMPTY_KECCAK_HASH,
            jumpdests: EMPTY_JUMPDESTS.clone(),
        }
    }
}

impl From<GenesisAccount> for Account {
    fn from(genesis: GenesisAccount) -> Self {
        let code = Code::from_bytecode(genesis.code, &NativeCrypto);
        Self {
            info: AccountInfo {
                code_hash: code.hash,
                balance: genesis.balance,
                nonce: genesis.nonce,
            },
            code,
            storage: genesis
                .storage
                .iter()
                .map(|(k, v)| (H256(k.to_big_endian()), *v))
                .collect(),
        }
    }
}

pub fn code_hash(code: &Bytes, crypto: &dyn Crypto) -> H256 {
    H256(crypto.keccak256(code.as_ref()))
}

/// EIP-7702 delegation designation: an EOA whose code is `0xef0100 || address`.
/// See <https://eips.ethereum.org/EIPS/eip-7702>.
pub const EIP7702_DELEGATION_PREFIX: [u8; 3] = [0xef, 0x01, 0x00];
/// Total byte length of an EIP-7702 delegation designation: 3-byte prefix
/// plus the 20-byte target address.
pub const EIP7702_DELEGATED_CODE_LEN: usize = 23;

/// Returns true iff `code` is a valid EIP-7702 delegation designation
/// (exactly 23 bytes, prefixed with `0xef0100`).
pub fn is_eip7702_delegation(code: &[u8]) -> bool {
    code.len() == EIP7702_DELEGATED_CODE_LEN && code.starts_with(&EIP7702_DELEGATION_PREFIX)
}

impl RLPEncode for AccountInfo {
    fn encode(&self, buf: &mut dyn bytes::BufMut) {
        Encoder::new(buf)
            .encode_field(&self.code_hash)
            .encode_field(&self.balance)
            .encode_field(&self.nonce)
            .finish();
    }
}

impl RLPDecode for AccountInfo {
    fn decode_unfinished(rlp: &[u8]) -> Result<(AccountInfo, &[u8]), RLPDecodeError> {
        let decoder = Decoder::new(rlp)?;
        let (code_hash, decoder) = decoder.decode_field("code_hash")?;
        let (balance, decoder) = decoder.decode_field("balance")?;
        let (nonce, decoder) = decoder.decode_field("nonce")?;
        let account_info = AccountInfo {
            code_hash,
            balance,
            nonce,
        };
        Ok((account_info, decoder.finish()?))
    }
}

impl RLPEncode for AccountState {
    fn encode(&self, buf: &mut dyn bytes::BufMut) {
        Encoder::new(buf)
            .encode_field(&self.nonce)
            .encode_field(&self.balance)
            .encode_field(&self.storage_root)
            .encode_field(&self.code_hash)
            .finish();
    }
}

impl RLPDecode for AccountState {
    fn decode_unfinished(rlp: &[u8]) -> Result<(AccountState, &[u8]), RLPDecodeError> {
        let decoder = Decoder::new(rlp)?;
        let (nonce, decoder) = decoder.decode_field("nonce")?;
        let (balance, decoder) = decoder.decode_field("balance")?;
        let (storage_root, decoder) = decoder.decode_field("storage_root")?;
        let (code_hash, decoder) = decoder.decode_field("code_hash")?;
        let state = AccountState {
            nonce,
            balance,
            storage_root,
            code_hash,
        };
        Ok((state, decoder.finish()?))
    }
}

impl RLPEncode for AccountStateSlimCodec {
    fn encode(&self, buf: &mut dyn BufMut) {
        struct StorageRootCodec<'a>(&'a H256);
        impl RLPEncode for StorageRootCodec<'_> {
            fn encode(&self, buf: &mut dyn BufMut) {
                let data = if *self.0 != *EMPTY_TRIE_HASH {
                    self.0.as_bytes()
                } else {
                    &[]
                };

                data.encode(buf);
            }
        }

        struct CodeHashCodec<'a>(&'a H256);
        impl RLPEncode for CodeHashCodec<'_> {
            fn encode(&self, buf: &mut dyn BufMut) {
                let data = if *self.0 != *EMPTY_KECCAK_HASH {
                    self.0.as_bytes()
                } else {
                    &[]
                };

                data.encode(buf);
            }
        }

        Encoder::new(buf)
            .encode_field(&self.0.nonce)
            .encode_field(&self.0.balance)
            .encode_field(&StorageRootCodec(&self.0.storage_root))
            .encode_field(&CodeHashCodec(&self.0.code_hash))
            .finish();
    }
}

impl RLPDecode for AccountStateSlimCodec {
    fn decode_unfinished(rlp: &[u8]) -> Result<(Self, &[u8]), RLPDecodeError> {
        struct StorageRootCodec(H256);
        impl RLPDecode for StorageRootCodec {
            fn decode_unfinished(mut rlp: &[u8]) -> Result<(Self, &[u8]), RLPDecodeError> {
                let value = match rlp.split_off_first() {
                    Some(0x80) => *EMPTY_TRIE_HASH,
                    Some(0xA0) => {
                        let data;
                        (data, rlp) = rlp
                            .split_first_chunk::<32>()
                            .ok_or(RLPDecodeError::InvalidLength)?;
                        H256(*data)
                    }
                    _ => return Err(RLPDecodeError::InvalidLength),
                };

                Ok((Self(value), rlp))
            }
        }

        struct CodeHashCodec(H256);
        impl RLPDecode for CodeHashCodec {
            fn decode_unfinished(mut rlp: &[u8]) -> Result<(Self, &[u8]), RLPDecodeError> {
                let value = match rlp.split_off_first() {
                    Some(0x80) => *EMPTY_KECCAK_HASH,
                    Some(0xA0) => {
                        let data;
                        (data, rlp) = rlp
                            .split_first_chunk::<32>()
                            .ok_or(RLPDecodeError::InvalidLength)?;
                        H256(*data)
                    }
                    _ => return Err(RLPDecodeError::InvalidLength),
                };

                Ok((Self(value), rlp))
            }
        }

        let decoder = Decoder::new(rlp)?;
        let (nonce, decoder) = decoder.decode_field("nonce")?;
        let (balance, decoder) = decoder.decode_field("balance")?;
        let (StorageRootCodec(storage_root), decoder) = decoder.decode_field("storage_root")?;
        let (CodeHashCodec(code_hash), decoder) = decoder.decode_field("code_hash")?;

        Ok((
            Self(AccountState {
                nonce,
                balance,
                storage_root,
                code_hash,
            }),
            decoder.finish()?,
        ))
    }
}

pub fn compute_storage_root(storage: &BTreeMap<U256, U256>, crypto: &dyn Crypto) -> H256 {
    let iter = storage.iter().filter_map(|(k, v)| {
        (!v.is_zero()).then_some((
            crypto.keccak256(&k.to_big_endian()).to_vec(),
            v.encode_to_vec(),
        ))
    });
    Trie::compute_hash_from_unsorted_iter(iter, crypto)
}

impl From<&GenesisAccount> for AccountState {
    fn from(value: &GenesisAccount) -> Self {
        AccountState {
            nonce: value.nonce,
            balance: value.balance,
            storage_root: compute_storage_root(&value.storage, &NativeCrypto),
            code_hash: code_hash(&value.code, &NativeCrypto),
        }
    }
}

impl Account {
    pub fn new(balance: U256, code: Code, nonce: u64, storage: FxHashMap<H256, U256>) -> Self {
        Self {
            info: AccountInfo {
                balance,
                code_hash: code.hash,
                nonce,
            },
            code,
            storage,
        }
    }
}

impl AccountInfo {
    pub fn is_empty(&self) -> bool {
        self.balance.is_zero() && self.nonce == 0 && self.code_hash == *EMPTY_KECCAK_HASH
    }
}

#[cfg(test)]
mod test {
    use std::str::FromStr;

    use super::*;

    // Pre-bitmap on-wire layout of `Code`: `{hash, code, jump_targets}`. `AccountUpdate`
    // embeds `Code` and is persisted with bincode (positional) in the L2 rollup store,
    // so a row written before the bitmap change carries a non-empty `jump_targets`.
    #[derive(serde::Serialize)]
    struct OldCodeSerde {
        hash: H256,
        code: Bytes,
        jump_targets: Vec<u32>,
    }

    // `Code` is never persisted alone — it sits inside `AccountUpdate`, which has fields
    // AFTER `code`. These wrappers mirror that: a field following the code. A standalone
    // `Code` would tolerate trailing bytes, hiding the bug; only an embedded field
    // exposes the positional shift.
    #[derive(serde::Serialize)]
    struct OldWrap {
        code: OldCodeSerde,
        tail: u64,
    }
    #[derive(serde::Deserialize)]
    struct NewWrap {
        code: Code,
        tail: u64,
    }

    // A row serialized under the old three-field layout must still decode with the field
    // following `code` intact: the current `Code` deserializer reads and discards
    // `jump_targets`, keeping the layout aligned. Without the retained field, bincode
    // reads `tail` from the `jump_targets` bytes and every following field is corrupt —
    // exactly the `store_account_updates_by_block_number` break.
    #[test]
    fn embedded_code_decodes_an_old_layout_bincode_row() {
        // PUSH1 0x00 JUMPDEST STOP — offset 2 is a real JUMPDEST, offset 1 a PUSH immediate.
        let bytecode = Bytes::from(vec![0x60, 0x00, 0x5b, 0x00]);
        let hash = H256::from_low_u64_be(0xabc);
        const SENTINEL: u64 = 0x0123_4567_89ab_cdef;
        let old = OldWrap {
            code: OldCodeSerde {
                hash,
                code: bytecode.clone(),
                jump_targets: vec![2], // non-empty, as an old row would hold
            },
            tail: SENTINEL,
        };
        let bytes = bincode::serialize(&old).expect("serialize old layout");

        let decoded: NewWrap = bincode::deserialize(&bytes).expect("decode old row under new Code");
        assert_eq!(decoded.code.hash, hash);
        assert_eq!(decoded.code.code_bytes(), bytecode);
        // The field after `code` must survive — this is what breaks if the layout shifts.
        assert_eq!(
            decoded.tail, SENTINEL,
            "field after Code corrupted by layout shift"
        );
        // Jump destinations recomputed from code, not read from the row.
        assert!(decoded.code.is_valid_jumpdest(2));
        assert!(!decoded.code.is_valid_jumpdest(1));
    }

    #[test]
    fn test_code_hash() {
        let empty_code = Bytes::new();
        let hash = code_hash(&empty_code, &NativeCrypto);
        assert_eq!(
            hash,
            H256::from_str("c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470")
                .unwrap()
        )
    }

    #[test]
    fn test_is_eip7702_delegation_valid() {
        // 0xef0100 || 20-byte address
        let mut code = Vec::with_capacity(23);
        code.extend_from_slice(&EIP7702_DELEGATION_PREFIX);
        code.extend_from_slice(&[0x42; 20]);
        assert!(is_eip7702_delegation(&code));
    }

    #[test]
    fn test_is_eip7702_delegation_rejects_empty() {
        assert!(!is_eip7702_delegation(&[]));
    }

    #[test]
    fn test_is_eip7702_delegation_rejects_short() {
        // Prefix only, no address.
        assert!(!is_eip7702_delegation(&EIP7702_DELEGATION_PREFIX));
    }

    #[test]
    fn test_is_eip7702_delegation_rejects_long() {
        // Correct prefix but 24 bytes total.
        let mut code = Vec::with_capacity(24);
        code.extend_from_slice(&EIP7702_DELEGATION_PREFIX);
        code.extend_from_slice(&[0x42; 21]);
        assert!(!is_eip7702_delegation(&code));
    }

    #[test]
    fn test_is_eip7702_delegation_rejects_wrong_prefix() {
        // Right length, wrong magic.
        let mut code = Vec::with_capacity(23);
        code.extend_from_slice(&[0xef, 0x01, 0x01]); // off by one in the last prefix byte
        code.extend_from_slice(&[0x42; 20]);
        assert!(!is_eip7702_delegation(&code));
    }

    #[test]
    fn test_is_eip7702_delegation_rejects_arbitrary_contract_code() {
        // Real contract code starting with anything else.
        let code = vec![0x60, 0x60, 0x60, 0x40, 0x52 /* ... */];
        assert!(!is_eip7702_delegation(&code));
    }

    // On these targets `compute_jumpdests` runs `by_block`, so the scan it replaces only
    // runs here, as the reference: both must give the same bitmap.
    #[cfg(any(
        target_arch = "aarch64",
        all(target_arch = "x86_64", target_feature = "ssse3")
    ))]
    mod by_block_against_the_scan {
        use super::*;

        fn assert_same_jumpdests(code: &[u8]) {
            let mut want = vec![0; code.len().div_ceil(8)];
            let mut got = want.clone();
            let want_any = jumpdests_by_opcode(code, &mut want);
            let got_any = by_block::jumpdests(code, &mut got);
            assert_eq!((got_any, got), (want_any, want), "code {code:02x?}");
        }

        /// One or two bytes at every offset of codes whose lengths straddle the 16-byte
        /// groups and 64-byte blocks, so every PUSH below crosses each boundary, and is cut
        /// short by the end of the code.
        #[test]
        fn matches_around_group_and_block_boundaries() {
            // STOP, JUMPDEST, the shortest PUSHes, the ones that fill a group with their
            // immediates or come a byte short or over, and the longest ones.
            const BYTES: [u8; 9] = [
                0x00,
                OP_JUMPDEST,
                OP_PUSH1,
                OP_PUSH1 + 1,
                OP_PUSH1 + 14,
                OP_PUSH1 + 15,
                OP_PUSH1 + 16,
                OP_PUSH32 - 1,
                OP_PUSH32,
            ];
            let lengths = [
                1, 15, 16, 17, 31, 32, 33, 63, 64, 65, 96, 127, 128, 129, 193,
            ];
            // A JUMPDEST filler exposes any immediate taken for an opcode or the other way
            // round. A PUSH1 filler makes where each block's walk starts depend on every
            // byte before it.
            for filler in [OP_JUMPDEST, OP_PUSH1] {
                for len in lengths {
                    for at in 0..len {
                        for first in BYTES {
                            for second in [None].into_iter().chain(BYTES.map(Some)) {
                                let mut code = vec![filler; len];
                                code[at] = first;
                                if let (Some(second), Some(byte)) = (second, code.get_mut(at + 1)) {
                                    *byte = second;
                                }
                                assert_same_jumpdests(&code);
                            }
                        }
                    }
                }
            }
        }

        /// Random code up to 4 KiB long, over byte mixes that make the scan's branches
        /// unpredictable.
        #[test]
        fn matches_on_random_code() {
            // xorshift64, so every run checks the same inputs.
            let mut state = 0x9E37_79B9_7F4A_7C15_u64;
            let mut next = move || {
                state ^= state << 13;
                state ^= state >> 7;
                state ^= state << 17;
                state
            };
            let jumpdest_and_pushes: Vec<u8> = std::iter::once(OP_JUMPDEST)
                .chain(OP_PUSH1..=OP_PUSH32)
                .collect();
            let all_bytes: Vec<u8> = (0..=u8::MAX).collect();
            let mixes: [&[u8]; 4] = [
                &[0x00, OP_JUMPDEST, OP_PUSH1],
                &[OP_JUMPDEST, OP_PUSH1, OP_PUSH1 + 1],
                &jumpdest_and_pushes,
                &all_bytes,
            ];
            for mix in mixes {
                for _ in 0..200 {
                    let len = (next() % 4096) as usize;
                    let code: Vec<u8> = (0..len)
                        .map(|_| mix[(next() % mix.len() as u64) as usize])
                        .collect();
                    assert_same_jumpdests(&code);
                }
            }
        }
    }
}