Skip to main content

axcbpf/
translate.rs

1//! Safe x86_64 classic-BPF machine-code translation.
2//!
3//! The translator emits a self-contained SysV x86_64 function with the ABI
4//! `extern "C" fn(data: *const u8, len: u32) -> u32`. Input loads, arithmetic,
5//! scratch accesses, forward branches, and returns are emitted directly; no
6//! helper call or address-bearing relocation is needed. The publisher only
7//! has to copy the immutable bytes into an executable W^X mapping.
8
9use alloc::vec::Vec;
10use core::fmt;
11
12use crate::{Input, Instruction, LoadWidth, SCRATCH_WORDS, VerifyError, opcode};
13
14/// Maximum bytes in one translated x86_64 image.
15pub const MAX_CODE_IMAGE_BYTES: usize = 256 * 1024;
16
17/// Input ABI used by emitted loads.
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub enum InputProfile {
20    /// Byte, halfword, and word loads in big-endian order.
21    BigEndianBytes,
22    /// Aligned native-endian word loads.
23    ///
24    /// Alignment is part of the logical input contract: absolute offsets are
25    /// verified at translation time and indirect offsets at execution time.
26    /// An adapter may additionally admit only a four-byte-aligned snapshot
27    /// base, while host reference adapters intentionally do not infer this
28    /// contract from an incidental slice address.
29    NativeAlignedWords,
30}
31
32/// Input adapter for [`InputProfile::NativeAlignedWords`] reference tests.
33pub struct NativeWordInput<'a> {
34    bytes: &'a [u8],
35}
36
37impl<'a> NativeWordInput<'a> {
38    /// Wraps an immutable native-word input buffer.
39    ///
40    /// The reference model checks logical offsets, not the address of the
41    /// Rust slice. This keeps it equivalent to the JIT's pre-pointer-add
42    /// offset check; adapters whose snapshot contract requires four-byte base
43    /// alignment can enforce that separately with [`Self::new_aligned`].
44    pub const fn new(bytes: &'a [u8]) -> Self {
45        Self { bytes }
46    }
47
48    /// Wraps a native-word input only when its base address is four-byte
49    /// aligned.
50    ///
51    /// [`NativeWordInput::new`] deliberately keeps the logical-offset
52    /// contract independent from an incidental Rust slice address. Adapters
53    /// whose native snapshot ABI includes a physical base-alignment
54    /// precondition can use this constructor at that boundary instead of
55    /// silently losing that part of the contract.
56    pub fn new_aligned(bytes: &'a [u8]) -> Option<Self> {
57        let input = Self::new(bytes);
58        input.base_is_aligned().then_some(input)
59    }
60
61    /// Returns whether the wrapped byte view starts at a four-byte boundary.
62    ///
63    /// This is intentionally separate from the logical offset checks in
64    /// [`Input::load`]. x86_64 permits unaligned byte-addressed loads, while
65    /// some native-word adapters may require the stronger base-address rule.
66    pub fn base_is_aligned(&self) -> bool {
67        (self.bytes.as_ptr() as usize) & 3 == 0
68    }
69}
70
71impl Input for NativeWordInput<'_> {
72    fn len(&self) -> u32 {
73        u32::try_from(self.bytes.len()).unwrap_or(u32::MAX)
74    }
75
76    fn load(&self, offset: u32, width: LoadWidth) -> Option<u32> {
77        if matches!(width, LoadWidth::Word) && offset % 4 != 0 {
78            return None;
79        }
80        let bytes = self.bytes.get(crate::program::input_range(
81            self.bytes.len(),
82            offset,
83            width,
84        )?)?;
85        match width {
86            LoadWidth::Byte => Some(u32::from(bytes[0])),
87            LoadWidth::Half => Some(u32::from(u16::from_ne_bytes([bytes[0], bytes[1]]))),
88            LoadWidth::Word => Some(u32::from_ne_bytes([bytes[0], bytes[1], bytes[2], bytes[3]])),
89        }
90    }
91}
92
93/// A call site that a publisher may resolve after image placement.
94///
95/// The current direct emitter never produces one. The type remains part of
96/// the image contract so future non-inline input policies can fail explicitly
97/// without changing the image ownership boundary.
98#[derive(Clone, Copy, Debug, Eq, PartialEq)]
99#[allow(missing_docs)]
100pub enum ExternalCall {
101    InputLoad { width: LoadWidth },
102    InputLength,
103}
104
105/// The kind of an image relocation.
106#[derive(Clone, Copy, Debug, Eq, PartialEq)]
107#[allow(missing_docs)]
108pub enum RelocationKind {
109    ExternalCall(ExternalCall),
110}
111
112/// A relocation in an immutable [`CodeImage`].
113#[derive(Clone, Copy, Debug, Eq, PartialEq)]
114#[allow(missing_docs)]
115pub struct Relocation {
116    pub offset: u32,
117    pub kind: RelocationKind,
118}
119
120/// Maps one source instruction to emitted machine bytes.
121#[derive(Clone, Copy, Debug, Eq, PartialEq)]
122#[allow(missing_docs)]
123pub struct InstructionMap {
124    pub source_pc: u32,
125    pub offset: u32,
126    pub len: u32,
127}
128
129#[derive(Clone, Copy, Debug, Eq, PartialEq)]
130struct BranchSite {
131    source_pc: u32,
132    true_pc: u32,
133    false_pc: u32,
134    true_disp: u32,
135    false_disp: u32,
136}
137
138/// Failure found by the independent translation validator.
139#[derive(Clone, Copy, Debug, Eq, PartialEq)]
140#[non_exhaustive]
141#[allow(missing_docs)]
142pub enum ImageValidationError {
143    NoMemory,
144    Empty,
145    TooLong {
146        length: usize,
147    },
148    UnsupportedOpcode {
149        pc: usize,
150        code: u16,
151    },
152    ImmediateDivisionByZero {
153        pc: usize,
154    },
155    ImmediateShiftOutOfRange {
156        pc: usize,
157        shift: u32,
158    },
159    ScratchOutOfRange {
160        pc: usize,
161        index: u32,
162    },
163    ScratchUninitialized {
164        pc: usize,
165        index: u32,
166    },
167    JumpOutOfRange {
168        pc: usize,
169    },
170    MissingFinalReturn,
171    InvalidEntry {
172        entry: u32,
173    },
174    InvalidBoundary {
175        index: usize,
176    },
177    BoundaryOutOfBounds {
178        index: usize,
179    },
180    InvalidRecordLength {
181        index: usize,
182        len: u32,
183    },
184    SourceMapMismatch {
185        index: usize,
186    },
187    MissingBranchSite {
188        pc: usize,
189    },
190    BranchSiteMismatch {
191        pc: usize,
192    },
193    BranchOutOfBounds {
194        pc: usize,
195    },
196    IndirectControlFlow,
197    RelocationOutOfBounds {
198        index: usize,
199    },
200    UnexpectedRelocation {
201        index: usize,
202    },
203    ImageTooLarge {
204        size: usize,
205    },
206    ProfileUnsupported {
207        pc: usize,
208        code: u16,
209    },
210    /// The immutable native image contains an instruction outside the
211    /// restricted x86_64 subset emitted by this crate.
212    NativeDecode {
213        offset: usize,
214    },
215    /// A decoded native instruction does not implement the source operation
216    /// at this program counter.
217    NativeSemanticMismatch {
218        pc: usize,
219        offset: usize,
220    },
221    /// A native direct branch does not target the source block or runtime
222    /// failure/epilogue block required by the source program.
223    NativeTargetMismatch {
224        pc: usize,
225    },
226    /// Native bytes remain after the independently validated epilogue.
227    NativeTrailingBytes {
228        offset: usize,
229    },
230}
231
232impl fmt::Display for ImageValidationError {
233    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
234        match self {
235            Self::NoMemory => formatter.write_str("translation validation allocation failed"),
236            Self::Empty => formatter.write_str("translated image is empty"),
237            Self::TooLong { length } => {
238                write!(formatter, "translated program has {length} instructions")
239            }
240            Self::UnsupportedOpcode { pc, code } => {
241                write!(formatter, "unsupported opcode {code:#x} at {pc}")
242            }
243            Self::ImmediateDivisionByZero { pc } => {
244                write!(formatter, "zero immediate divisor at {pc}")
245            }
246            Self::ImmediateShiftOutOfRange { pc, shift } => {
247                write!(formatter, "shift {shift} out of range at {pc}")
248            }
249            Self::ScratchOutOfRange { pc, index } => {
250                write!(formatter, "scratch {index} out of range at {pc}")
251            }
252            Self::ScratchUninitialized { pc, index } => {
253                write!(formatter, "scratch {index} uninitialized at {pc}")
254            }
255            Self::JumpOutOfRange { pc } => write!(formatter, "jump out of range at {pc}"),
256            Self::MissingFinalReturn => {
257                formatter.write_str("translated source has no final return")
258            }
259            Self::InvalidEntry { entry } => write!(formatter, "invalid entry offset {entry}"),
260            Self::InvalidBoundary { index } => write!(formatter, "invalid boundary {index}"),
261            Self::BoundaryOutOfBounds { index } => {
262                write!(formatter, "boundary {index} out of bounds at {index}")
263            }
264            Self::InvalidRecordLength { index, len } => {
265                write!(formatter, "invalid emitted length {len} at {index}")
266            }
267            Self::SourceMapMismatch { index } => {
268                write!(formatter, "source map mismatch at {index}")
269            }
270            Self::MissingBranchSite { pc } => write!(formatter, "missing branch metadata at {pc}"),
271            Self::BranchSiteMismatch { pc } => {
272                write!(formatter, "branch metadata mismatch at {pc}")
273            }
274            Self::BranchOutOfBounds { pc } => {
275                write!(formatter, "branch target out of bounds at {pc}")
276            }
277            Self::IndirectControlFlow => {
278                formatter.write_str("indirect control flow in translated image")
279            }
280            Self::RelocationOutOfBounds { index } => {
281                write!(formatter, "relocation {index} out of bounds")
282            }
283            Self::UnexpectedRelocation { index } => {
284                write!(formatter, "unexpected relocation {index}")
285            }
286            Self::ImageTooLarge { size } => write!(formatter, "translated image is {size} bytes"),
287            Self::ProfileUnsupported { pc, code } => {
288                write!(
289                    formatter,
290                    "opcode {code:#x} is unavailable for the input profile at {pc}"
291                )
292            }
293            Self::NativeDecode { offset } => {
294                write!(formatter, "unsupported native instruction at byte {offset}")
295            }
296            Self::NativeSemanticMismatch { pc, offset } => {
297                write!(
298                    formatter,
299                    "native lowering mismatch at source {pc}, byte {offset}"
300                )
301            }
302            Self::NativeTargetMismatch { pc } => {
303                write!(formatter, "native branch target mismatch at source {pc}")
304            }
305            Self::NativeTrailingBytes { offset } => {
306                write!(formatter, "native trailing bytes at byte {offset}")
307            }
308        }
309    }
310}
311
312/// Failure while translating a verified program.
313#[derive(Clone, Copy, Debug, Eq, PartialEq)]
314#[non_exhaustive]
315#[allow(missing_docs)]
316pub enum TranslationError {
317    UnsupportedOpcode { pc: usize, code: u16 },
318    InvalidSource(VerifyError),
319    NoMemory,
320    ImageTooLarge,
321    InvalidImage(ImageValidationError),
322    ProfileUnsupported { pc: usize, code: u16 },
323}
324
325impl fmt::Display for TranslationError {
326    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
327        match self {
328            Self::UnsupportedOpcode { pc, code } => {
329                write!(formatter, "unsupported opcode {code:#x} at {pc}")
330            }
331            Self::InvalidSource(error) => write!(formatter, "invalid translation source: {error}"),
332            Self::NoMemory => formatter.write_str("translation allocation failed"),
333            Self::ImageTooLarge => formatter.write_str("translation image is too large"),
334            Self::InvalidImage(error) => {
335                write!(formatter, "translation validator rejected image: {error}")
336            }
337            Self::ProfileUnsupported { pc, code } => {
338                write!(
339                    formatter,
340                    "opcode {code:#x} is unavailable for the input profile at {pc}"
341                )
342            }
343        }
344    }
345}
346
347/// Immutable native x86_64 bytes and translation metadata.
348#[derive(Debug)]
349pub struct CodeImage {
350    bytes: Vec<u8>,
351    relocations: Vec<Relocation>,
352    entry: u32,
353    boundaries: Vec<u32>,
354    instruction_map: Vec<InstructionMap>,
355    source: Vec<Instruction>,
356    branches: Vec<BranchSite>,
357    profile: InputProfile,
358}
359
360impl CodeImage {
361    /// Returns immutable executable bytes. The first byte is the function
362    /// entry and the bytes are suitable for a W^X publisher to copy.
363    pub fn bytes(&self) -> &[u8] {
364        &self.bytes
365    }
366
367    /// Returns the native entry offset.
368    pub const fn entry_offset(&self) -> u32 {
369        self.entry
370    }
371
372    /// Returns source boundaries including the terminal code length.
373    pub fn instruction_boundaries(&self) -> &[u32] {
374        &self.boundaries
375    }
376
377    /// Returns source-to-native instruction mappings.
378    pub fn instruction_map(&self) -> &[InstructionMap] {
379        &self.instruction_map
380    }
381
382    /// Returns relocations. Direct images always return an empty slice.
383    pub fn relocations(&self) -> &[Relocation] {
384        &self.relocations
385    }
386
387    /// Returns the input ABI profile used by native load emission.
388    pub const fn profile(&self) -> InputProfile {
389        self.profile
390    }
391
392    /// Returns the number of translated source instructions.
393    pub fn len(&self) -> usize {
394        self.source.len()
395    }
396
397    /// Returns whether the source program is empty.
398    pub fn is_empty(&self) -> bool {
399        self.source.is_empty()
400    }
401
402    /// Returns the exact native byte length.
403    pub fn image_size(&self) -> usize {
404        self.bytes.len()
405    }
406
407    /// Returns the page-rounded size required by a publisher.
408    pub fn page_aligned_size(&self, page_size: usize) -> Option<usize> {
409        if page_size == 0 {
410            return None;
411        }
412        self.bytes
413            .len()
414            .checked_add(page_size - 1)
415            .map(|size| size / page_size * page_size)
416    }
417
418    /// Returns owned bytes and publisher metadata.
419    pub fn into_parts(self) -> (Vec<u8>, Vec<Relocation>, u32, Vec<u32>, Vec<InstructionMap>) {
420        (
421            self.bytes,
422            self.relocations,
423            self.entry,
424            self.boundaries,
425            self.instruction_map,
426        )
427    }
428
429    /// Returns owned native bytes.
430    pub fn into_bytes(self) -> Vec<u8> {
431        self.bytes
432    }
433
434    /// Independently validates native code, source map, branches and relocations.
435    pub fn validate(&self) -> Result<(), ImageValidationError> {
436        let layout = crate::translation_validate::validate_translation_layout(
437            &self.bytes,
438            &self.source,
439            self.profile,
440        )?;
441        validate_image(self, &layout)
442    }
443
444    /// Evaluates a second safe reference model from the immutable source copy.
445    pub fn evaluate<I: Input + ?Sized>(&self, input: &I) -> u32 {
446        evaluate_source(&self.source, input)
447    }
448}
449
450pub(crate) fn translate_program(
451    source: &[Instruction],
452    profile: InputProfile,
453) -> Result<CodeImage, TranslationError> {
454    validate_profile(source, profile)?;
455    validate_source(source).map_err(TranslationError::InvalidSource)?;
456    for (pc, instruction) in source.iter().copied().enumerate() {
457        if !is_supported(instruction.code) {
458            return Err(TranslationError::UnsupportedOpcode {
459                pc,
460                code: instruction.code,
461            });
462        }
463    }
464
465    let mut assembler = Assembler::new(source.len()).map_err(|_| TranslationError::NoMemory)?;
466    assembler.emit_prologue(profile);
467    let mut map = Vec::new();
468    map.try_reserve_exact(source.len())
469        .map_err(|_| TranslationError::NoMemory)?;
470    let mut boundaries = Vec::new();
471    boundaries
472        .try_reserve_exact(source.len() + 2)
473        .map_err(|_| TranslationError::NoMemory)?;
474    // Source byte maps start after the ABI prologue.  Keeping the prologue
475    // outside source instruction zero prevents a source map consumer from
476    // attributing saved-register or argument setup bytes to user cBPF.
477    boundaries
478        .push(u32::try_from(assembler.bytes.len()).map_err(|_| TranslationError::ImageTooLarge)?);
479
480    for (pc, instruction) in source.iter().copied().enumerate() {
481        let start = assembler.bytes.len();
482        assembler.emit_instruction(pc, instruction, profile);
483        let end = assembler.bytes.len();
484        boundaries.push(u32::try_from(end).map_err(|_| TranslationError::ImageTooLarge)?);
485        map.push(InstructionMap {
486            source_pc: pc as u32,
487            offset: u32::try_from(start).map_err(|_| TranslationError::ImageTooLarge)?,
488            len: u32::try_from(end - start).map_err(|_| TranslationError::ImageTooLarge)?,
489        });
490    }
491
492    let failure = assembler.bytes.len();
493    assembler.emit_zero_return();
494    let epilogue = assembler.bytes.len();
495    assembler.emit_epilogue();
496    assembler.resolve(source.len(), &map, failure, epilogue)?;
497    if assembler.bytes.len() > MAX_CODE_IMAGE_BYTES {
498        return Err(TranslationError::ImageTooLarge);
499    }
500    boundaries
501        .push(u32::try_from(assembler.bytes.len()).map_err(|_| TranslationError::ImageTooLarge)?);
502
503    let mut owned_source = Vec::new();
504    owned_source
505        .try_reserve_exact(source.len())
506        .map_err(|_| TranslationError::NoMemory)?;
507    owned_source.extend_from_slice(source);
508    let image = CodeImage {
509        bytes: assembler.bytes,
510        relocations: Vec::new(),
511        entry: 0,
512        boundaries,
513        instruction_map: map,
514        source: owned_source,
515        branches: assembler.branches,
516        profile,
517    };
518    image.validate().map_err(TranslationError::InvalidImage)?;
519    Ok(image)
520}
521
522struct Assembler {
523    bytes: Vec<u8>,
524    patches: Vec<Patch>,
525    branches: Vec<BranchSite>,
526}
527
528#[derive(Clone, Copy)]
529struct Patch {
530    disp: usize,
531    target: Target,
532}
533
534#[derive(Clone, Copy)]
535enum Target {
536    Pc(usize),
537    Failure,
538    Epilogue,
539}
540
541impl Assembler {
542    fn new(source_len: usize) -> Result<Self, alloc::collections::TryReserveError> {
543        let mut bytes = Vec::new();
544        let byte_capacity = source_len
545            .checked_mul(128)
546            .and_then(|size| size.checked_add(64))
547            .unwrap_or(usize::MAX);
548        bytes.try_reserve_exact(byte_capacity)?;
549        let mut patches = Vec::new();
550        patches.try_reserve_exact(source_len.saturating_mul(8))?;
551        let mut branches = Vec::new();
552        branches.try_reserve_exact(source_len)?;
553        Ok(Self {
554            bytes,
555            patches,
556            branches,
557        })
558    }
559
560    fn emit_prologue(&mut self, profile: InputProfile) {
561        self.bytes.extend_from_slice(&[
562            0x55, // push rbp
563            0x41, 0x54, // push r12
564            0x41, 0x55, // push r13
565            0x41, 0x56, // push r14
566            0x41, 0x57, // push r15
567            0x48, 0x89, 0xe5, // mov rbp,rsp
568            0x48, 0x83, 0xec, 0x40, // sub rsp,64
569        ]);
570        match profile {
571            InputProfile::BigEndianBytes | InputProfile::NativeAlignedWords => {
572                self.bytes.extend_from_slice(&[
573                    0x49, 0x89, 0xfc, // mov r12,rdi (data)
574                    0x41, 0x89, 0xf5, // mov r13d,esi (len)
575                ]);
576            }
577        }
578        self.bytes.extend_from_slice(&[
579            0x31, 0xc0, // xor eax,eax
580            0x31, 0xc9, // xor ecx,ecx
581        ]);
582    }
583
584    fn emit_instruction(&mut self, pc: usize, i: Instruction, profile: InputProfile) {
585        match i.code {
586            opcode::LD_IMM => self.mov_eax_imm(i.k),
587            opcode::LD_W_ABS => self.emit_abs_load(i.k, LoadWidth::Word, profile),
588            opcode::LD_H_ABS => self.emit_abs_load(i.k, LoadWidth::Half, profile),
589            opcode::LD_B_ABS => self.emit_abs_load(i.k, LoadWidth::Byte, profile),
590            opcode::LD_W_IND => self.emit_ind_load(i.k, LoadWidth::Word, profile),
591            opcode::LD_H_IND => self.emit_ind_load(i.k, LoadWidth::Half, profile),
592            opcode::LD_B_IND => self.emit_ind_load(i.k, LoadWidth::Byte, profile),
593            opcode::LD_MEM => self.load_scratch(i.k, false),
594            opcode::LD_LEN => self.bytes.extend_from_slice(&[0x44, 0x89, 0xe8]),
595            opcode::LDX_IMM => self.mov_ecx_imm(i.k),
596            opcode::LDX_MEM => self.load_scratch(i.k, true),
597            opcode::LDX_LEN => self.bytes.extend_from_slice(&[0x44, 0x89, 0xe9]),
598            opcode::LDX_B_MSH => {
599                // BPF_LDX | BPF_B | BPF_MSH writes only X.  Load the nibble
600                // directly into ECX so the accumulator survives unchanged.
601                self.emit_abs_load_to_x(i.k, profile);
602                self.bytes
603                    .extend_from_slice(&[0x83, 0xe1, 0x0f, 0xc1, 0xe1, 0x02]);
604            }
605            opcode::ST => self.store_scratch(i.k, false),
606            opcode::STX => self.store_scratch(i.k, true),
607            opcode::ALU_ADD_K => self.bin_imm(0x05, i.k),
608            opcode::ALU_ADD_X => self.bytes.extend_from_slice(&[0x01, 0xc8]),
609            opcode::ALU_SUB_K => self.bin_imm(0x2d, i.k),
610            opcode::ALU_SUB_X => self.bytes.extend_from_slice(&[0x29, 0xc8]),
611            opcode::ALU_MUL_K => self.imul_imm(i.k),
612            opcode::ALU_MUL_X => self.bytes.extend_from_slice(&[0x0f, 0xaf, 0xc1]),
613            opcode::ALU_DIV_K => self.div_imm(i.k, false),
614            opcode::ALU_DIV_X => self.div_x(false),
615            opcode::ALU_OR_K => self.bin_imm(0x0d, i.k),
616            opcode::ALU_OR_X => self.bytes.extend_from_slice(&[0x09, 0xc8]),
617            opcode::ALU_AND_K => self.bin_imm(0x25, i.k),
618            opcode::ALU_AND_X => self.bytes.extend_from_slice(&[0x21, 0xc8]),
619            opcode::ALU_LSH_K => self.shift_imm(0xc1, 0xe0, i.k as u8),
620            opcode::ALU_LSH_X => self.shift_x(0xd3, 0xe0),
621            opcode::ALU_RSH_K => self.shift_imm(0xc1, 0xe8, i.k as u8),
622            opcode::ALU_RSH_X => self.shift_x(0xd3, 0xe8),
623            opcode::ALU_NEG => self.bytes.extend_from_slice(&[0xf7, 0xd8]),
624            opcode::ALU_MOD_K => self.div_imm(i.k, true),
625            opcode::ALU_MOD_X => self.div_x(true),
626            opcode::ALU_XOR_K => self.bin_imm(0x35, i.k),
627            opcode::ALU_XOR_X => self.bytes.extend_from_slice(&[0x31, 0xc8]),
628            opcode::JMP_JA => {
629                let target = pc + 1 + i.k as usize;
630                let disp = self.emit_jump(Target::Pc(target));
631                self.branches.push(BranchSite {
632                    source_pc: pc as u32,
633                    true_pc: target as u32,
634                    false_pc: target as u32,
635                    true_disp: disp as u32,
636                    false_disp: disp as u32,
637                });
638            }
639            opcode::JMP_JEQ_K => self.emit_conditional(0x84, i.k, i, false, pc),
640            opcode::JMP_JEQ_X => self.emit_conditional(0x84, 0, i, true, pc),
641            opcode::JMP_JGT_K => self.emit_conditional(0x87, i.k, i, false, pc),
642            opcode::JMP_JGT_X => self.emit_conditional(0x87, 0, i, true, pc),
643            opcode::JMP_JGE_K => self.emit_conditional(0x83, i.k, i, false, pc),
644            opcode::JMP_JGE_X => self.emit_conditional(0x83, 0, i, true, pc),
645            opcode::JMP_JSET_K => self.emit_conditional(0x85, i.k, i, false, pc),
646            opcode::JMP_JSET_X => self.emit_conditional(0x85, 0, i, true, pc),
647            opcode::RET_K => {
648                self.mov_eax_imm(i.k);
649                self.emit_jump(Target::Epilogue);
650            }
651            opcode::RET_A => {
652                self.emit_jump(Target::Epilogue);
653            }
654            opcode::MISC_TAX => self.bytes.extend_from_slice(&[0x89, 0xc1]),
655            opcode::MISC_TXA => self.bytes.extend_from_slice(&[0x89, 0xc8]),
656            _ => {}
657        }
658    }
659
660    fn emit_abs_load(&mut self, offset: u32, width: LoadWidth, profile: InputProfile) {
661        self.mov_r14d_imm(offset);
662        self.emit_bounds(width);
663        self.add_r14_r12();
664        self.emit_speculation_barrier();
665        self.emit_load_r14(width, profile);
666    }
667
668    fn emit_abs_load_to_x(&mut self, offset: u32, profile: InputProfile) {
669        self.mov_r14d_imm(offset);
670        self.emit_bounds(LoadWidth::Byte);
671        self.add_r14_r12();
672        self.emit_speculation_barrier();
673        self.emit_load_r14_to_x(profile);
674    }
675
676    fn emit_ind_load(&mut self, offset: u32, width: LoadWidth, profile: InputProfile) {
677        self.bytes.extend_from_slice(&[0x41, 0x89, 0xce]); // mov r14d,ecx
678        self.bytes.extend_from_slice(&[0x41, 0x81, 0xc6]);
679        self.u32(offset);
680        self.jcc(0x82, Target::Failure); // add carry
681        self.emit_bounds_ind(width, profile);
682        self.add_r14_r12();
683        self.emit_speculation_barrier();
684        self.emit_load_r14(width, profile);
685    }
686
687    fn emit_speculation_barrier(&mut self) {
688        // x86_64 LFENCE is the same architectural speculation-stop used by
689        // Linux's x86 barrier_nospec() sequence.  Keep it immediately before
690        // the packet dereference, after all bounds and pointer-overflow checks.
691        self.bytes.extend_from_slice(&[0x0f, 0xae, 0xe8]);
692    }
693
694    fn emit_bounds(&mut self, width: LoadWidth) {
695        self.cmp_r13_imm(width_bytes(width) as u8);
696        self.jcc(0x82, Target::Failure);
697        self.bytes.extend_from_slice(&[0x45, 0x89, 0xef]); // mov r15d,r13d
698        self.sub_r15_imm(width_bytes(width) as u8);
699        self.bytes.extend_from_slice(&[0x45, 0x39, 0xf7]); // cmp r15d,r14d
700        self.jcc(0x82, Target::Failure);
701    }
702
703    fn emit_bounds_ind(&mut self, width: LoadWidth, profile: InputProfile) {
704        self.cmp_r13_imm(width_bytes(width) as u8);
705        self.jcc(0x82, Target::Failure);
706        self.bytes.extend_from_slice(&[0x45, 0x89, 0xef]);
707        self.sub_r15_imm(width_bytes(width) as u8);
708        self.bytes.extend_from_slice(&[0x45, 0x39, 0xf7]);
709        self.jcc(0x82, Target::Failure);
710        if matches!(profile, InputProfile::NativeAlignedWords) && matches!(width, LoadWidth::Word) {
711            self.bytes.extend_from_slice(&[0x41, 0xf6, 0xc6, 0x03]);
712            self.jcc(0x85, Target::Failure);
713        }
714    }
715
716    fn add_r14_r12(&mut self) {
717        self.bytes.extend_from_slice(&[0x4d, 0x01, 0xe6]);
718        self.jcc(0x82, Target::Failure);
719    }
720
721    fn emit_load_r14(&mut self, width: LoadWidth, profile: InputProfile) {
722        match width {
723            LoadWidth::Byte => self.bytes.extend_from_slice(&[0x41, 0x0f, 0xb6, 0x06]),
724            LoadWidth::Half => {
725                self.bytes
726                    // MOVZX r14d, word ptr [r14].  Omitting 0x66 is
727                    // intentional: the operand-size override would write
728                    // only r14w and leave the previous accumulator's high
729                    // sixteen bits in EAX when the result is consumed.
730                    .extend_from_slice(&[0x41, 0x0f, 0xb7, 0x06]);
731                if matches!(profile, InputProfile::BigEndianBytes) {
732                    self.bytes.extend_from_slice(&[0x66, 0xc1, 0xc0, 0x08]);
733                }
734            }
735            LoadWidth::Word => {
736                self.bytes.extend_from_slice(&[0x41, 0x8b, 0x06]);
737                if matches!(profile, InputProfile::BigEndianBytes) {
738                    self.bytes.extend_from_slice(&[0x0f, 0xc8]);
739                }
740            }
741        }
742    }
743
744    fn emit_load_r14_to_x(&mut self, _profile: InputProfile) {
745        // MOVZX ecx, byte ptr [r14].  The byte profile is the only one that
746        // reaches this helper (NativeAlignedWords rejects LDX_B_MSH).
747        self.bytes.extend_from_slice(&[0x41, 0x0f, 0xb6, 0x0e]);
748    }
749
750    fn load_scratch(&mut self, index: u32, into_x: bool) {
751        let disp = scratch_disp(index);
752        self.bytes.push(0x8b);
753        self.bytes.push(if into_x { 0x4d } else { 0x45 });
754        self.bytes.push(disp);
755    }
756
757    fn store_scratch(&mut self, index: u32, from_x: bool) {
758        let disp = scratch_disp(index);
759        self.bytes.push(0x89);
760        self.bytes.push(if from_x { 0x4d } else { 0x45 });
761        self.bytes.push(disp);
762    }
763
764    fn bin_imm(&mut self, opcode: u8, immediate: u32) {
765        self.bytes.push(opcode);
766        self.u32(immediate);
767    }
768    fn imul_imm(&mut self, immediate: u32) {
769        self.bytes.extend_from_slice(&[0x69, 0xc0]);
770        self.u32(immediate);
771    }
772
773    fn div_imm(&mut self, immediate: u32, remainder: bool) {
774        self.mov_r14d_imm(immediate);
775        self.bytes
776            .extend_from_slice(&[0x31, 0xd2, 0x41, 0xf7, 0xf6]);
777        if remainder {
778            self.bytes.extend_from_slice(&[0x89, 0xd0]);
779        }
780    }
781
782    fn div_x(&mut self, remainder: bool) {
783        self.bytes.extend_from_slice(&[0x85, 0xc9]);
784        self.jcc(0x84, Target::Failure);
785        self.bytes.extend_from_slice(&[0x31, 0xd2, 0xf7, 0xf1]);
786        if remainder {
787            self.bytes.extend_from_slice(&[0x89, 0xd0]);
788        }
789    }
790
791    fn shift_imm(&mut self, opcode: u8, modrm: u8, count: u8) {
792        self.bytes.extend_from_slice(&[opcode, modrm, count]);
793    }
794
795    fn shift_x(&mut self, opcode: u8, modrm: u8) {
796        self.bytes.extend_from_slice(&[
797            0x41, 0x89, 0xce, 0x41, 0x83, 0xe6, 0x1f, 0x41, 0x89, 0xcf, 0x44, 0x89, 0xf1, opcode,
798            modrm, 0x44, 0x89, 0xf9,
799        ]);
800    }
801
802    fn emit_conditional(
803        &mut self,
804        condition: u8,
805        immediate: u32,
806        i: Instruction,
807        x_source: bool,
808        pc: usize,
809    ) {
810        if x_source && condition == 0x85 {
811            self.bytes.extend_from_slice(&[0x85, 0xc8]);
812        } else if x_source {
813            self.bytes.extend_from_slice(&[0x39, 0xc8]);
814        } else if condition == 0x85 {
815            self.bytes.push(0xa9);
816            self.u32(immediate);
817        } else {
818            self.bytes.push(0x3d);
819            self.u32(immediate);
820        }
821        let true_disp = self.jcc(condition, Target::Pc(pc + 1 + usize::from(i.jt)));
822        let false_disp = self.emit_jump(Target::Pc(pc + 1 + usize::from(i.jf)));
823        self.branches.push(BranchSite {
824            source_pc: pc as u32,
825            true_pc: (pc + 1 + usize::from(i.jt)) as u32,
826            false_pc: (pc + 1 + usize::from(i.jf)) as u32,
827            true_disp: true_disp as u32,
828            false_disp: false_disp as u32,
829        });
830    }
831
832    fn emit_jump(&mut self, target: Target) -> usize {
833        self.bytes.push(0xe9);
834        let disp = self.bytes.len();
835        self.u32(0);
836        self.patches.push(Patch { disp, target });
837        disp
838    }
839
840    fn jcc(&mut self, condition: u8, target: Target) -> usize {
841        self.bytes.extend_from_slice(&[0x0f, condition]);
842        let disp = self.bytes.len();
843        self.u32(0);
844        self.patches.push(Patch { disp, target });
845        disp
846    }
847
848    fn emit_zero_return(&mut self) {
849        self.bytes.extend_from_slice(&[0x31, 0xc0]);
850        self.emit_jump(Target::Epilogue);
851    }
852
853    fn emit_epilogue(&mut self) {
854        self.bytes.extend_from_slice(&[
855            0x48, 0x83, 0xc4, 0x40, 0x41, 0x5f, 0x41, 0x5e, 0x41, 0x5d, 0x41, 0x5c, 0x5d, 0xc3,
856        ]);
857    }
858
859    fn resolve(
860        &mut self,
861        count: usize,
862        map: &[InstructionMap],
863        failure: usize,
864        epilogue: usize,
865    ) -> Result<(), TranslationError> {
866        for patch in self.patches.iter().copied() {
867            let target = match patch.target {
868                Target::Pc(pc) => map
869                    .get(pc)
870                    .map(|entry| entry.offset as usize)
871                    .ok_or(TranslationError::ImageTooLarge)?,
872                Target::Failure => failure,
873                Target::Epilogue => epilogue,
874            };
875            let base = patch.disp + 4;
876            let displacement =
877                i64::try_from(target).unwrap_or(i64::MAX) - i64::try_from(base).unwrap_or(i64::MAX);
878            let displacement =
879                i32::try_from(displacement).map_err(|_| TranslationError::ImageTooLarge)?;
880            self.bytes[patch.disp..patch.disp + 4].copy_from_slice(&displacement.to_le_bytes());
881        }
882        for branch in &mut self.branches {
883            let true_target = map
884                .get(branch.true_pc as usize)
885                .ok_or(TranslationError::ImageTooLarge)?
886                .offset;
887            let false_target = map
888                .get(branch.false_pc as usize)
889                .ok_or(TranslationError::ImageTooLarge)?
890                .offset;
891            if !patch_matches(&self.bytes, branch.true_disp as usize, true_target as usize)
892                || !patch_matches(
893                    &self.bytes,
894                    branch.false_disp as usize,
895                    false_target as usize,
896                )
897            {
898                return Err(TranslationError::ImageTooLarge);
899            }
900        }
901        if count != map.len() {
902            return Err(TranslationError::ImageTooLarge);
903        }
904        Ok(())
905    }
906
907    fn u32(&mut self, value: u32) {
908        self.bytes.extend_from_slice(&value.to_le_bytes());
909    }
910    fn mov_eax_imm(&mut self, value: u32) {
911        self.bytes.push(0xb8);
912        self.u32(value);
913    }
914    fn mov_ecx_imm(&mut self, value: u32) {
915        self.bytes.push(0xb9);
916        self.u32(value);
917    }
918    fn mov_r14d_imm(&mut self, value: u32) {
919        self.bytes.extend_from_slice(&[0x41, 0xbe]);
920        self.u32(value);
921    }
922    fn cmp_r13_imm(&mut self, value: u8) {
923        self.bytes.extend_from_slice(&[0x41, 0x83, 0xfd, value]);
924    }
925    fn sub_r15_imm(&mut self, value: u8) {
926        self.bytes.extend_from_slice(&[0x41, 0x83, 0xef, value]);
927    }
928}
929
930fn validate_image(
931    image: &CodeImage,
932    layout: &crate::translation_validate::TranslationLayout,
933) -> Result<(), ImageValidationError> {
934    if image.source.is_empty() {
935        return Err(ImageValidationError::Empty);
936    }
937    if image.source.len() > crate::MAX_INSTRUCTIONS {
938        return Err(ImageValidationError::TooLong {
939            length: image.source.len(),
940        });
941    }
942    if image.entry != 0 {
943        return Err(ImageValidationError::InvalidEntry { entry: image.entry });
944    }
945    if image.bytes.len() > MAX_CODE_IMAGE_BYTES {
946        return Err(ImageValidationError::ImageTooLarge {
947            size: image.bytes.len(),
948        });
949    }
950    validate_profile_image(&image.source, image.profile)?;
951    if let Some((index, relocation)) = image.relocations.iter().enumerate().next() {
952        if usize::try_from(relocation.offset)
953            .ok()
954            .and_then(|offset| offset.checked_add(4))
955            .filter(|end| *end <= image.bytes.len())
956            .is_none()
957        {
958            return Err(ImageValidationError::RelocationOutOfBounds { index });
959        }
960        return Err(ImageValidationError::UnexpectedRelocation { index });
961    }
962    if image.instruction_map.len() != image.source.len()
963        || image.boundaries.len() != image.source.len() + 2
964    {
965        return Err(ImageValidationError::SourceMapMismatch {
966            index: image.instruction_map.len(),
967        });
968    }
969    if image
970        .boundaries
971        .first()
972        .copied()
973        .and_then(|bound| usize::try_from(bound).ok())
974        .filter(|bound| *bound > image.entry as usize && *bound <= image.bytes.len())
975        .is_none()
976        || image
977            .boundaries
978            .last()
979            .copied()
980            .and_then(|bound| usize::try_from(bound).ok())
981            .filter(|bound| *bound == image.bytes.len())
982            .is_none()
983    {
984        return Err(ImageValidationError::BoundaryOutOfBounds { index: 0 });
985    }
986    if image
987        .boundaries
988        .windows(2)
989        .any(|window| window[0] >= window[1])
990    {
991        return Err(ImageValidationError::InvalidBoundary { index: 0 });
992    }
993    for (pc, ((map, source), bounds)) in image
994        .instruction_map
995        .iter()
996        .zip(&image.source)
997        .zip(image.boundaries.windows(2).take(image.source.len()))
998        .enumerate()
999    {
1000        if map.source_pc != pc as u32
1001            || map.offset != bounds[0]
1002            || map.offset != layout.source_offsets[pc]
1003            || map.len != bounds[1].saturating_sub(bounds[0])
1004            || map.len == 0
1005        {
1006            return Err(ImageValidationError::SourceMapMismatch { index: pc });
1007        }
1008        let end = usize::try_from(bounds[1])
1009            .map_err(|_| ImageValidationError::BoundaryOutOfBounds { index: pc })?;
1010        if end > image.bytes.len() {
1011            return Err(ImageValidationError::BoundaryOutOfBounds { index: pc });
1012        }
1013        validate_source_instruction(pc, *source)?;
1014    }
1015    validate_source(&image.source).map_err(map_verify_error)?;
1016    for branch in &image.branches {
1017        let Some(source) = image.source.get(branch.source_pc as usize) else {
1018            return Err(ImageValidationError::MissingBranchSite {
1019                pc: branch.source_pc as usize,
1020            });
1021        };
1022        let Some(map) = image.instruction_map.get(branch.source_pc as usize) else {
1023            return Err(ImageValidationError::MissingBranchSite {
1024                pc: branch.source_pc as usize,
1025            });
1026        };
1027        let true_offset = image
1028            .instruction_map
1029            .get(branch.true_pc as usize)
1030            .ok_or(ImageValidationError::BranchOutOfBounds {
1031                pc: branch.source_pc as usize,
1032            })?
1033            .offset;
1034        let false_offset = image
1035            .instruction_map
1036            .get(branch.false_pc as usize)
1037            .ok_or(ImageValidationError::BranchOutOfBounds {
1038                pc: branch.source_pc as usize,
1039            })?
1040            .offset;
1041        let direct_branch_opcode = if source.code == opcode::JMP_JA {
1042            branch.true_disp >= 1
1043                && image.bytes.get(branch.true_disp as usize - 1).copied() == Some(0xe9)
1044        } else {
1045            let expected_condition = match source.code {
1046                opcode::JMP_JEQ_K | opcode::JMP_JEQ_X => 0x84,
1047                opcode::JMP_JGT_K | opcode::JMP_JGT_X => 0x87,
1048                opcode::JMP_JGE_K | opcode::JMP_JGE_X => 0x83,
1049                opcode::JMP_JSET_K | opcode::JMP_JSET_X => 0x85,
1050                _ => 0,
1051            };
1052            branch.true_disp >= 2
1053                && image.bytes.get(branch.true_disp as usize - 2) == Some(&0x0f)
1054                && image.bytes.get(branch.true_disp as usize - 1) == Some(&expected_condition)
1055                && branch.false_disp >= 1
1056                && image.bytes.get(branch.false_disp as usize - 1) == Some(&0xe9)
1057        };
1058        if source.code < opcode::JMP_JA
1059            || map.offset > branch.true_disp
1060            || !direct_branch_opcode
1061            || !patch_matches(
1062                &image.bytes,
1063                branch.true_disp as usize,
1064                true_offset as usize,
1065            )
1066            || !patch_matches(
1067                &image.bytes,
1068                branch.false_disp as usize,
1069                false_offset as usize,
1070            )
1071        {
1072            return Err(ImageValidationError::BranchSiteMismatch {
1073                pc: branch.source_pc as usize,
1074            });
1075        }
1076    }
1077    let expected_branches = image
1078        .source
1079        .iter()
1080        .filter(|instruction| is_jump(instruction.code))
1081        .count();
1082    if expected_branches != image.branches.len()
1083        || image.branches.iter().enumerate().any(|(index, branch)| {
1084            image
1085                .source
1086                .iter()
1087                .enumerate()
1088                .filter(|(_, instruction)| is_jump(instruction.code))
1089                .nth(index)
1090                .map(|(pc, _)| branch.source_pc as usize != pc)
1091                .unwrap_or(true)
1092        })
1093    {
1094        return Err(ImageValidationError::MissingBranchSite { pc: 0 });
1095    }
1096    Ok(())
1097}
1098
1099fn validate_profile(source: &[Instruction], profile: InputProfile) -> Result<(), TranslationError> {
1100    for (pc, instruction) in source.iter().copied().enumerate() {
1101        if let InputProfile::NativeAlignedWords = profile {
1102            match instruction.code {
1103                opcode::LD_W_ABS if instruction.k % 4 != 0 => {
1104                    return Err(TranslationError::ProfileUnsupported {
1105                        pc,
1106                        code: instruction.code,
1107                    });
1108                }
1109                opcode::LD_W_IND => {}
1110                opcode::LD_H_ABS
1111                | opcode::LD_B_ABS
1112                | opcode::LD_H_IND
1113                | opcode::LD_B_IND
1114                | opcode::LDX_B_MSH => {
1115                    return Err(TranslationError::ProfileUnsupported {
1116                        pc,
1117                        code: instruction.code,
1118                    });
1119                }
1120                _ => {}
1121            }
1122        }
1123    }
1124    Ok(())
1125}
1126
1127pub(crate) fn validate_profile_image(
1128    source: &[Instruction],
1129    profile: InputProfile,
1130) -> Result<(), ImageValidationError> {
1131    for (pc, instruction) in source.iter().copied().enumerate() {
1132        if let InputProfile::NativeAlignedWords = profile {
1133            match instruction.code {
1134                opcode::LD_W_ABS if instruction.k % 4 != 0 => {
1135                    return Err(ImageValidationError::ProfileUnsupported {
1136                        pc,
1137                        code: instruction.code,
1138                    });
1139                }
1140                opcode::LD_W_IND => {}
1141                opcode::LD_H_ABS
1142                | opcode::LD_B_ABS
1143                | opcode::LD_H_IND
1144                | opcode::LD_B_IND
1145                | opcode::LDX_B_MSH => {
1146                    return Err(ImageValidationError::ProfileUnsupported {
1147                        pc,
1148                        code: instruction.code,
1149                    });
1150                }
1151                _ => {}
1152            }
1153        }
1154    }
1155    Ok(())
1156}
1157
1158fn patch_matches(bytes: &[u8], disp: usize, target: usize) -> bool {
1159    let Some(raw) = bytes.get(disp..disp + 4) else {
1160        return false;
1161    };
1162    let displacement = i32::from_le_bytes([raw[0], raw[1], raw[2], raw[3]]) as i64;
1163    i64::try_from(disp + 4)
1164        .ok()
1165        .and_then(|base| base.checked_add(displacement))
1166        .map(|value| value == target as i64)
1167        .unwrap_or(false)
1168}
1169
1170fn scratch_disp(index: u32) -> u8 {
1171    (-(4_i32 * (index as i32 + 1))) as u8
1172}
1173
1174fn width_bytes(width: LoadWidth) -> usize {
1175    match width {
1176        LoadWidth::Byte => 1,
1177        LoadWidth::Half => 2,
1178        LoadWidth::Word => 4,
1179    }
1180}
1181
1182const fn is_jump(code: u16) -> bool {
1183    matches!(
1184        code,
1185        opcode::JMP_JA
1186            | opcode::JMP_JEQ_K
1187            | opcode::JMP_JEQ_X
1188            | opcode::JMP_JGT_K
1189            | opcode::JMP_JGT_X
1190            | opcode::JMP_JGE_K
1191            | opcode::JMP_JGE_X
1192            | opcode::JMP_JSET_K
1193            | opcode::JMP_JSET_X
1194    )
1195}
1196
1197fn validate_source_instruction(
1198    pc: usize,
1199    instruction: Instruction,
1200) -> Result<(), ImageValidationError> {
1201    if !is_supported(instruction.code) {
1202        return Err(ImageValidationError::UnsupportedOpcode {
1203            pc,
1204            code: instruction.code,
1205        });
1206    }
1207    match instruction.code {
1208        opcode::ALU_DIV_K | opcode::ALU_MOD_K if instruction.k == 0 => {
1209            Err(ImageValidationError::ImmediateDivisionByZero { pc })
1210        }
1211        opcode::ALU_LSH_K | opcode::ALU_RSH_K if instruction.k >= 32 => {
1212            Err(ImageValidationError::ImmediateShiftOutOfRange {
1213                pc,
1214                shift: instruction.k,
1215            })
1216        }
1217        opcode::LD_MEM | opcode::LDX_MEM | opcode::ST | opcode::STX
1218            if instruction.k >= SCRATCH_WORDS as u32 =>
1219        {
1220            Err(ImageValidationError::ScratchOutOfRange {
1221                pc,
1222                index: instruction.k,
1223            })
1224        }
1225        _ => Ok(()),
1226    }
1227}
1228
1229pub(crate) fn validate_source(instructions: &[Instruction]) -> Result<(), VerifyError> {
1230    if instructions.is_empty() {
1231        return Err(VerifyError::Empty);
1232    }
1233    if instructions.len() > crate::MAX_INSTRUCTIONS {
1234        return Err(VerifyError::TooLong {
1235            length: instructions.len(),
1236        });
1237    }
1238    for (pc, i) in instructions.iter().copied().enumerate() {
1239        if !is_supported(i.code) {
1240            return Err(VerifyError::UnsupportedOpcode { pc, code: i.code });
1241        }
1242        match i.code {
1243            opcode::ALU_DIV_K | opcode::ALU_MOD_K if i.k == 0 => {
1244                return Err(VerifyError::ImmediateDivisionByZero { pc });
1245            }
1246            opcode::ALU_LSH_K | opcode::ALU_RSH_K if i.k >= 32 => {
1247                return Err(VerifyError::ImmediateShiftOutOfRange { pc, shift: i.k });
1248            }
1249            opcode::LD_MEM | opcode::LDX_MEM | opcode::ST | opcode::STX
1250                if i.k >= SCRATCH_WORDS as u32 =>
1251            {
1252                return Err(VerifyError::ScratchOutOfRange { pc, index: i.k });
1253            }
1254            opcode::JMP_JA => {
1255                if pc
1256                    .checked_add(1)
1257                    .and_then(|next| next.checked_add(i.k as usize))
1258                    .filter(|target| *target < instructions.len())
1259                    .is_none()
1260                {
1261                    return Err(VerifyError::JumpOutOfRange { pc });
1262                }
1263            }
1264            opcode::JMP_JEQ_K
1265            | opcode::JMP_JEQ_X
1266            | opcode::JMP_JGT_K
1267            | opcode::JMP_JGT_X
1268            | opcode::JMP_JGE_K
1269            | opcode::JMP_JGE_X
1270            | opcode::JMP_JSET_K
1271            | opcode::JMP_JSET_X
1272                if pc + 1 + usize::from(i.jt) >= instructions.len()
1273                    || pc + 1 + usize::from(i.jf) >= instructions.len() =>
1274            {
1275                return Err(VerifyError::JumpOutOfRange { pc });
1276            }
1277            _ => {}
1278        }
1279    }
1280    if !matches!(
1281        instructions.last().map(|i| i.code),
1282        Some(opcode::RET_K | opcode::RET_A)
1283    ) {
1284        return Err(VerifyError::MissingFinalReturn);
1285    }
1286    let mut incoming = Vec::new();
1287    incoming
1288        .try_reserve_exact(instructions.len())
1289        .map_err(|_| VerifyError::NoMemory)?;
1290    incoming.resize(instructions.len(), None);
1291    incoming[0] = Some(0);
1292    for (pc, i) in instructions.iter().copied().enumerate() {
1293        let Some(mut initialized) = incoming[pc] else {
1294            continue;
1295        };
1296        match i.code {
1297            opcode::LD_MEM | opcode::LDX_MEM => {
1298                let bit = 1_u16 << i.k;
1299                if initialized & bit == 0 {
1300                    return Err(VerifyError::ScratchUninitialized { pc, index: i.k });
1301                }
1302            }
1303            opcode::ST | opcode::STX => initialized |= 1_u16 << i.k,
1304            _ => {}
1305        }
1306        match i.code {
1307            opcode::RET_K | opcode::RET_A => {}
1308            opcode::JMP_JA => merge(&mut incoming[pc + 1 + i.k as usize], initialized),
1309            opcode::JMP_JEQ_K
1310            | opcode::JMP_JEQ_X
1311            | opcode::JMP_JGT_K
1312            | opcode::JMP_JGT_X
1313            | opcode::JMP_JGE_K
1314            | opcode::JMP_JGE_X
1315            | opcode::JMP_JSET_K
1316            | opcode::JMP_JSET_X => {
1317                merge(&mut incoming[pc + 1 + usize::from(i.jt)], initialized);
1318                merge(&mut incoming[pc + 1 + usize::from(i.jf)], initialized);
1319            }
1320            _ => merge(&mut incoming[pc + 1], initialized),
1321        }
1322    }
1323    Ok(())
1324}
1325
1326fn merge(slot: &mut Option<u16>, incoming: u16) {
1327    *slot = Some(slot.map(|old| old & incoming).unwrap_or(incoming));
1328}
1329
1330pub(crate) fn map_verify_error(error: VerifyError) -> ImageValidationError {
1331    match error {
1332        VerifyError::Empty => ImageValidationError::Empty,
1333        VerifyError::TooLong { length } => ImageValidationError::TooLong { length },
1334        VerifyError::NoMemory => ImageValidationError::NoMemory,
1335        VerifyError::UnsupportedOpcode { pc, code } => {
1336            ImageValidationError::UnsupportedOpcode { pc, code }
1337        }
1338        VerifyError::ImmediateDivisionByZero { pc } => {
1339            ImageValidationError::ImmediateDivisionByZero { pc }
1340        }
1341        VerifyError::ImmediateShiftOutOfRange { pc, shift } => {
1342            ImageValidationError::ImmediateShiftOutOfRange { pc, shift }
1343        }
1344        VerifyError::ScratchOutOfRange { pc, index } => {
1345            ImageValidationError::ScratchOutOfRange { pc, index }
1346        }
1347        VerifyError::ScratchUninitialized { pc, index } => {
1348            ImageValidationError::ScratchUninitialized { pc, index }
1349        }
1350        VerifyError::JumpOutOfRange { pc } => ImageValidationError::JumpOutOfRange { pc },
1351        VerifyError::MissingFinalReturn => ImageValidationError::MissingFinalReturn,
1352    }
1353}
1354
1355fn evaluate_source<I: Input + ?Sized>(instructions: &[Instruction], input: &I) -> u32 {
1356    let mut a = 0_u32;
1357    let mut x = 0_u32;
1358    let mut scratch = [0_u32; SCRATCH_WORDS];
1359    let mut pc = 0_usize;
1360    let mut steps = 0;
1361    while steps < instructions.len() {
1362        let i = instructions[pc];
1363        steps += 1;
1364        match i.code {
1365            opcode::LD_IMM => a = i.k,
1366            opcode::LD_W_ABS | opcode::LD_H_ABS | opcode::LD_B_ABS => {
1367                let w = if i.code == opcode::LD_W_ABS {
1368                    LoadWidth::Word
1369                } else if i.code == opcode::LD_H_ABS {
1370                    LoadWidth::Half
1371                } else {
1372                    LoadWidth::Byte
1373                };
1374                let Some(v) = input.load(i.k, w) else {
1375                    return 0;
1376                };
1377                a = v;
1378            }
1379            opcode::LD_W_IND | opcode::LD_H_IND | opcode::LD_B_IND => {
1380                let Some(offset) = x.checked_add(i.k) else {
1381                    return 0;
1382                };
1383                let w = if i.code == opcode::LD_W_IND {
1384                    LoadWidth::Word
1385                } else if i.code == opcode::LD_H_IND {
1386                    LoadWidth::Half
1387                } else {
1388                    LoadWidth::Byte
1389                };
1390                let Some(v) = input.load(offset, w) else {
1391                    return 0;
1392                };
1393                a = v;
1394            }
1395            opcode::LD_MEM => a = scratch[i.k as usize],
1396            opcode::LD_LEN => a = input.len(),
1397            opcode::LDX_IMM => x = i.k,
1398            opcode::LDX_MEM => x = scratch[i.k as usize],
1399            opcode::LDX_LEN => x = input.len(),
1400            opcode::LDX_B_MSH => {
1401                let Some(v) = input.load(i.k, LoadWidth::Byte) else {
1402                    return 0;
1403                };
1404                x = (v & 0xf) << 2;
1405            }
1406            opcode::ST => scratch[i.k as usize] = a,
1407            opcode::STX => scratch[i.k as usize] = x,
1408            opcode::ALU_ADD_K => a = a.wrapping_add(i.k),
1409            opcode::ALU_ADD_X => a = a.wrapping_add(x),
1410            opcode::ALU_SUB_K => a = a.wrapping_sub(i.k),
1411            opcode::ALU_SUB_X => a = a.wrapping_sub(x),
1412            opcode::ALU_MUL_K => a = a.wrapping_mul(i.k),
1413            opcode::ALU_MUL_X => a = a.wrapping_mul(x),
1414            opcode::ALU_DIV_K => a /= i.k,
1415            opcode::ALU_DIV_X => {
1416                if x == 0 {
1417                    return 0;
1418                }
1419                a /= x;
1420            }
1421            opcode::ALU_OR_K => a |= i.k,
1422            opcode::ALU_OR_X => a |= x,
1423            opcode::ALU_AND_K => a &= i.k,
1424            opcode::ALU_AND_X => a &= x,
1425            opcode::ALU_LSH_K => a = a.wrapping_shl(i.k),
1426            opcode::ALU_LSH_X => a = a.wrapping_shl(x & 31),
1427            opcode::ALU_RSH_K => a = a.wrapping_shr(i.k),
1428            opcode::ALU_RSH_X => a = a.wrapping_shr(x & 31),
1429            opcode::ALU_NEG => a = a.wrapping_neg(),
1430            opcode::ALU_MOD_K => a %= i.k,
1431            opcode::ALU_MOD_X => {
1432                if x == 0 {
1433                    return 0;
1434                }
1435                a %= x;
1436            }
1437            opcode::ALU_XOR_K => a ^= i.k,
1438            opcode::ALU_XOR_X => a ^= x,
1439            opcode::JMP_JA => {
1440                pc += 1 + i.k as usize;
1441                continue;
1442            }
1443            opcode::JMP_JEQ_K
1444            | opcode::JMP_JEQ_X
1445            | opcode::JMP_JGT_K
1446            | opcode::JMP_JGT_X
1447            | opcode::JMP_JGE_K
1448            | opcode::JMP_JGE_X
1449            | opcode::JMP_JSET_K
1450            | opcode::JMP_JSET_X => {
1451                let o = if matches!(
1452                    i.code,
1453                    opcode::JMP_JEQ_X | opcode::JMP_JGT_X | opcode::JMP_JGE_X | opcode::JMP_JSET_X
1454                ) {
1455                    x
1456                } else {
1457                    i.k
1458                };
1459                let c = match i.code {
1460                    opcode::JMP_JEQ_K | opcode::JMP_JEQ_X => a == o,
1461                    opcode::JMP_JGT_K | opcode::JMP_JGT_X => a > o,
1462                    opcode::JMP_JGE_K | opcode::JMP_JGE_X => a >= o,
1463                    _ => a & o != 0,
1464                };
1465                pc += 1 + usize::from(if c { i.jt } else { i.jf });
1466                continue;
1467            }
1468            opcode::RET_K => return i.k,
1469            opcode::RET_A => return a,
1470            opcode::MISC_TAX => x = a,
1471            opcode::MISC_TXA => a = x,
1472            _ => return 0,
1473        }
1474        pc += 1;
1475    }
1476    0
1477}
1478
1479const fn is_supported(code: u16) -> bool {
1480    matches!(
1481        code,
1482        opcode::LD_IMM
1483            | opcode::LD_W_ABS
1484            | opcode::LD_H_ABS
1485            | opcode::LD_B_ABS
1486            | opcode::LD_W_IND
1487            | opcode::LD_H_IND
1488            | opcode::LD_B_IND
1489            | opcode::LD_MEM
1490            | opcode::LD_LEN
1491            | opcode::LDX_IMM
1492            | opcode::LDX_MEM
1493            | opcode::LDX_LEN
1494            | opcode::LDX_B_MSH
1495            | opcode::ST
1496            | opcode::STX
1497            | opcode::ALU_ADD_K
1498            | opcode::ALU_ADD_X
1499            | opcode::ALU_SUB_K
1500            | opcode::ALU_SUB_X
1501            | opcode::ALU_MUL_K
1502            | opcode::ALU_MUL_X
1503            | opcode::ALU_DIV_K
1504            | opcode::ALU_DIV_X
1505            | opcode::ALU_OR_K
1506            | opcode::ALU_OR_X
1507            | opcode::ALU_AND_K
1508            | opcode::ALU_AND_X
1509            | opcode::ALU_LSH_K
1510            | opcode::ALU_LSH_X
1511            | opcode::ALU_RSH_K
1512            | opcode::ALU_RSH_X
1513            | opcode::ALU_NEG
1514            | opcode::ALU_MOD_K
1515            | opcode::ALU_MOD_X
1516            | opcode::ALU_XOR_K
1517            | opcode::ALU_XOR_X
1518            | opcode::JMP_JA
1519            | opcode::JMP_JEQ_K
1520            | opcode::JMP_JEQ_X
1521            | opcode::JMP_JGT_K
1522            | opcode::JMP_JGT_X
1523            | opcode::JMP_JGE_K
1524            | opcode::JMP_JGE_X
1525            | opcode::JMP_JSET_K
1526            | opcode::JMP_JSET_X
1527            | opcode::RET_K
1528            | opcode::RET_A
1529            | opcode::MISC_TAX
1530            | opcode::MISC_TXA
1531    )
1532}