use crate::isa::{self, Decoder, Insn, ItState, Mem, Operand, Reg};
const NOP_T1: u16 = 0xBF00;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub enum XrefKind {
Call,
Branch,
LiteralPool,
PcRelativeAddress,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub struct Xref {
pub at: usize,
pub kind: XrefKind,
pub via: Option<&'static str>,
}
pub fn xrefs(image: &[u8], target: u32) -> Vec<Xref> {
xrefs_with(isa::Target::Union, image, target)
}
pub fn xrefs_with(profile: isa::Target, image: &[u8], target: u32) -> Vec<Xref> {
let want = target & !1;
let mut out: Vec<Xref> = Vec::new();
let mut d = Decoder::at(image, 0, 0).target(profile);
loop {
let at = d.pos();
if at + 2 > image.len() {
break;
}
let insn = match d.next() {
Some(i) => i,
None => {
Decoder::skip(&mut d, 2);
continue;
}
};
if let Some(kind) = xref_kind(&insn, want) {
out.push(Xref {
at,
kind,
via: Some(insn.mnemonic),
});
}
}
let mut p = 0usize;
while p + 4 <= image.len() {
if crate::read_u32(image, p) & !1 == want {
out.push(Xref {
at: p,
kind: XrefKind::LiteralPool,
via: None,
});
}
p += 4;
}
out.sort_by_key(|x| (x.at, x.kind));
out
}
fn xref_kind(insn: &Insn, want: u32) -> Option<XrefKind> {
if insn
.operands
.as_slice()
.any(|o| matches!(o, Operand::Mem(_)))
{
return None;
}
if insn.branch_target()? & !1 != want {
return None;
}
if insn.is_call() {
Some(XrefKind::Call)
} else if insn.is_branch() {
Some(XrefKind::Branch)
} else {
Some(XrefKind::PcRelativeAddress)
}
}
pub fn function_start(image: &[u8], addr: usize, max_scan: usize) -> Option<usize> {
function_start_with(isa::Target::Union, image, addr, max_scan)
}
pub fn function_start_with(
_target: isa::Target,
image: &[u8],
addr: usize,
max_scan: usize,
) -> Option<usize> {
let addr = addr & !1;
let lo = addr.saturating_sub(max_scan);
let mut p = addr;
loop {
if is_prologue(image, p) {
return Some(p);
}
if p < 2 || p.saturating_sub(lo) < 2 {
return None;
}
p -= 2;
}
}
fn is_prologue(image: &[u8], at: usize) -> bool {
let hw1 = match crate::try_read_u16(image, at) {
Some(h) => h,
None => return false,
};
if hw1 & 0xFF00 == 0xB500 {
return true;
}
if hw1 == 0xE92D {
return matches!(crate::try_read_u16(image, at + 2), Some(hw2) if hw2 & 0x4000 != 0);
}
if hw1 == 0xF84D {
return crate::try_read_u16(image, at + 2) == Some(0xED04);
}
false
}
pub fn literal_value(image: &[u8], at: usize) -> Option<u32> {
literal_value_with(isa::Target::Union, image, at)
}
pub fn literal_value_with(target: isa::Target, image: &[u8], at: usize) -> Option<u32> {
let insn = isa::decode_at_with(image, at, at as u32, target)?;
if insn.mnemonic != "ldr" {
return None;
}
let literal_form = insn
.operands
.as_slice()
.any(|o| matches!(o, Operand::Mem(Mem { base, index: None, .. }) if base == Reg::PC));
let pool = insn.operands.as_slice().find_map(|o| match o {
Operand::Target(t) => Some(t),
_ => None,
});
match (literal_form, pool) {
(true, Some(pool)) => crate::try_read_u32(image, pool as usize),
_ => None,
}
}
pub fn nop_fill(image: &mut [u8], at: usize, len: usize) {
assert!(
at % 2 == 0,
"nop_fill offset {at} is odd; Thumb instructions are halfword aligned"
);
assert!(
len % 2 == 0,
"nop_fill length {len} is odd; there is no 1-byte Thumb instruction"
);
assert!(
at + len <= image.len(),
"nop_fill range {at}..{} is past the end of a {}-byte image",
at + len,
image.len()
);
for hw in image[at..at + len].chunks_exact_mut(2) {
hw.copy_from_slice(&NOP_T1.to_le_bytes());
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct Reach {
pub insns: Vec<usize>,
pub end: usize,
pub unresolved: Vec<usize>,
pub complete: bool,
}
pub fn reachable(image: &[u8], entry: usize, limit: usize) -> Reach {
reachable_with(isa::Target::Union, image, entry, limit)
}
pub fn reachable_with(target: isa::Target, image: &[u8], entry: usize, limit: usize) -> Reach {
let mut out = Reach {
complete: true,
..Reach::default()
};
let mut visited: std::collections::BTreeSet<usize> = std::collections::BTreeSet::new();
let mut work: Vec<(usize, ItState)> = vec![(entry & !1, ItState::INACTIVE)];
while let Some((at, it)) = work.pop() {
if !visited.insert(at) {
continue;
}
if visited.len() > limit {
out.complete = false;
break;
}
let insn = match isa::decode_at_with(image, at, at as u32, target) {
Some(i) => i,
None => {
out.complete = false;
continue;
}
};
let i = out.insns.binary_search(&at).unwrap_or_else(|i| i);
out.insns.insert(i, at);
out.end = out.end.max(at + insn.len());
let next_it = if insn.mnemonic.starts_with("it") {
isa::it_state_from(u16::from_le_bytes([image[at], image[at + 1]]))
} else {
it.advance()
};
let mut push = |t: usize, state: ItState, out: &mut Reach| {
if t.checked_add(2).map_or(false, |end| end <= image.len()) {
work.push((t, state));
} else {
out.complete = false;
}
};
let conditional = insn.cond.is_some()
|| it.current().is_some()
|| matches!(insn.mnemonic, "cbz" | "cbnz" | "chka");
if insn.is_branch() && !insn.is_call() {
let has_mem = insn
.operands
.as_slice()
.any(|o| matches!(o, Operand::Mem(_)));
match insn.branch_target() {
Some(t) if !has_mem => push(t as usize & !1, ItState::INACTIVE, &mut out),
_ => {
let i = out.unresolved.binary_search(&at).unwrap_or_else(|i| i);
out.unresolved.insert(i, at);
}
}
}
if !insn.is_branch() || insn.is_call() || conditional {
push(at + insn.len(), next_it, &mut out);
}
}
out
}
pub fn veneer(at: usize, target: u32) -> Option<[u8; 8]> {
if at % 4 != 0 {
return None;
}
let hw1: u16 = 0xF8DF;
let hw2: u16 = 0xF000;
let mut out = [0u8; 8];
out[0..2].copy_from_slice(&hw1.to_le_bytes());
out[2..4].copy_from_slice(&hw2.to_le_bytes());
out[4..8].copy_from_slice(&(target | 1).to_le_bytes());
Some(out)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{encode_bl, find_bl_sites, Asm};
#[test]
fn function_start_near_the_top_of_memory_terminates() {
let image = vec![0u8; 0x20];
assert_eq!(function_start(&image, usize::MAX, 0), None);
assert_eq!(function_start(&image, usize::MAX, 64), None);
assert_eq!(function_start(&image, usize::MAX - 1, 0), None);
}
#[test]
fn reachable_with_a_branch_target_near_the_top_is_not_a_panic() {
let mut asm = Asm::new();
let bytes = crate::encode_b_wide(0, 0x00FF_FFFE).expect("b.w encodes");
asm.raw16(u16::from_le_bytes([bytes[0], bytes[1]]));
asm.raw16(u16::from_le_bytes([bytes[2], bytes[3]]));
let image = asm.finish().expect("assembles");
let r = reachable(&image, 0, 16);
assert!(
!r.complete,
"a target past the image leaves the walk incomplete"
);
}
fn live(len: usize) -> Vec<u8> {
vec![0x00; len]
}
#[test]
fn free_space_does_not_round_up_out_of_the_run() {
let mut image = live(0x40);
for b in &mut image[0x12..0x22] {
*b = 0xFF;
}
assert_eq!(crate::find_free_space(&image, 16, 1, 0), Some(0x12));
assert_eq!((0x12 + 3) & !3, 0x14, "what the naive repair computes");
assert!(image[0x22] != 0xFF && image[0x23] != 0xFF);
assert_eq!(crate::find_free_space(&image, 16, 4, 0), None);
assert_eq!(crate::find_free_space(&image, 14, 4, 0), Some(0x14));
assert_eq!(crate::find_free_space(&image, 6, 4, 0x1C), Some(0x1C));
assert_eq!(crate::find_free_space(&image, 7, 4, 0x1C), None);
}
#[test]
fn free_space_honours_every_alignment() {
let mut image = live(0x80);
for b in &mut image[0x21..0x51] {
*b = 0xFF;
}
assert_eq!(crate::find_free_space(&image, 8, 1, 0), Some(0x21));
assert_eq!(crate::find_free_space(&image, 8, 2, 0), Some(0x22));
assert_eq!(crate::find_free_space(&image, 8, 4, 0), Some(0x24));
assert_eq!(crate::find_free_space(&image, 8, 16, 0), Some(0x30));
assert_eq!(crate::find_free_space(&image, 0x11, 16, 0x31), Some(0x40));
assert_eq!(crate::find_free_space(&image, 0x12, 16, 0x31), None);
}
#[test]
fn free_space_finds_a_run_at_the_very_end_of_the_image() {
let mut image = live(0x20);
for b in &mut image[0x18..0x20] {
*b = 0xFF;
}
assert_eq!(crate::find_free_space(&image, 8, 4, 0), Some(0x18));
assert_eq!(crate::find_free_space(&image, 8, 8, 0), Some(0x18));
assert_eq!(crate::find_free_space(&image, 9, 1, 0), None);
let free = vec![0xFFu8; 0x20];
assert_eq!(crate::find_free_space(&free, 0x20, 4, 0), Some(0));
assert_eq!(crate::find_free_space(&free, 0x20, 4, 4), None);
assert_eq!(crate::find_free_space(&free, 0x1C, 4, 4), Some(4));
assert_eq!(crate::find_free_space(&free, 0, 16, 0x11), Some(0x20));
assert_eq!(crate::find_free_space(&free, 0, 1, 0x64), Some(0x20));
assert_eq!(
crate::find(&free, crate::Needle::FreeRun { len: 0, align: 1 }, 0x64),
Some(0x20)
);
assert_eq!(crate::find_free_space(&free, 1, 1, 0x64), None);
}
#[test]
#[should_panic(expected = "alignment must be at least 1 byte")]
fn free_space_rejects_a_zero_alignment() {
crate::find_free_space(&[0xFF; 4], 1, 0, 0);
}
#[test]
fn free_space_gives_asm_finish_the_alignment_it_documents() {
let mut a = Asm::new();
a.ldr_lit(0, 0xDEAD_BEEF);
a.bx(0);
let code = a.finish().unwrap();
let mut image = live(0x100);
for b in &mut image[0x32..0x80] {
*b = 0xFF;
}
let aligned = crate::find_free_space(&image, code.len(), 4, 0).unwrap();
let unaligned = crate::find_free_space(&image, code.len(), 1, 0).unwrap();
assert_eq!((aligned, unaligned), (0x34, 0x32));
assert_eq!(aligned % 4, 0);
let at = aligned;
crate::write(&mut image, at, &code);
assert_eq!(literal_value(&image, at), Some(0xDEAD_BEEF));
let mut skewed = live(0x100);
crate::write(&mut skewed, unaligned, &code);
assert_ne!(literal_value(&skewed, unaligned), Some(0xDEAD_BEEF));
}
#[test]
fn xrefs_finds_every_kind_of_reference() {
let mut image = live(0x80);
crate::write(&mut image, 0x00, &encode_bl(0x00, 0x40).unwrap());
crate::write(&mut image, 0x04, &crate::encode_b_wide(0x04, 0x40).unwrap());
crate::write(
&mut image,
0x08,
&(0xA000u16 | ((0x40 - 0x0C) / 4)).to_le_bytes(),
);
crate::write(&mut image, 0x0C, &(0xE000u16 | 0x18).to_le_bytes());
crate::write(&mut image, 0x10, &(0xD000u16 | 0x16).to_le_bytes());
nop_fill(&mut image, 0x12, 0x0E);
crate::write(&mut image, 0x20, &0x41u32.to_le_bytes());
crate::write(&mut image, 0x40, &0xB510u16.to_le_bytes());
let refs = xrefs(&image, 0x40);
let seen: Vec<(usize, XrefKind, Option<&str>)> =
refs.iter().map(|x| (x.at, x.kind, x.via)).collect();
assert_eq!(
seen,
vec![
(0x00, XrefKind::Call, Some("bl")),
(0x04, XrefKind::Branch, Some("b")),
(0x08, XrefKind::PcRelativeAddress, Some("adr")),
(0x0C, XrefKind::Branch, Some("b")),
(0x10, XrefKind::Branch, Some("b")),
(0x20, XrefKind::LiteralPool, None),
]
);
assert_eq!(xrefs(&image, 0x41), refs);
assert_eq!(xrefs(&image, 0x44), vec![]);
}
#[test]
fn xrefs_resynchronises_past_an_undefined_encoding() {
let mut image = live(0x80);
crate::write(&mut image, 0x00, &[0x70, 0xf8, 0x00, 0x00]);
crate::write(&mut image, 0x04, &encode_bl(0x04, 0x40).unwrap());
assert_eq!(
isa::decode_at_with(&image, 0x00, 0, isa::Target::Union),
None,
"the test vector must be undecodable, or it proves nothing"
);
assert_eq!(
xrefs(&image, 0x40),
vec![Xref {
at: 0x04,
kind: XrefKind::Call,
via: Some("bl"),
}]
);
}
#[test]
fn every_target_carrying_encoding_is_a_branch_a_call_or_an_adr() {
fn check(insn: &Insn) -> bool {
let has_mem = insn
.operands
.as_slice()
.any(|o| matches!(o, Operand::Mem(_)));
let target = match insn.branch_target() {
Some(t) if !has_mem => t,
_ => return false,
};
assert!(
matches!(insn.mnemonic, "b" | "bl" | "blx" | "cbz" | "cbnz" | "adr"),
"{insn} ({}) carries a target with no memory operand",
insn.encoding
);
let kind = xref_kind(insn, target & !1);
let want = if insn.is_call() {
XrefKind::Call
} else if insn.is_branch() {
XrefKind::Branch
} else {
XrefKind::PcRelativeAddress
};
assert_eq!(kind, Some(want), "{insn}");
true
}
let mut seen = 0usize;
for hw in 0x0000u16..=0xFFFF {
if isa::insn_len(hw) != 2 {
continue;
}
if let Some(insn) =
isa::decode_at_with(&hw.to_le_bytes(), 0, 0x1000, isa::Target::Union)
{
seen += usize::from(check(&insn));
}
}
for hw1 in 0xE800u16..=0xFFFF {
for hw2 in [
0x0000u16, 0x0004, 0x00ff, 0x0f0f, 0x1234, 0x4000, 0x8000, 0xc000, 0xed04, 0xf000,
0xfff0, 0xffff,
] {
let [a, b] = hw1.to_le_bytes();
let [c, d] = hw2.to_le_bytes();
if let Some(insn) =
isa::decode_at_with(&[a, b, c, d], 0, 0x1000, isa::Target::Union)
{
seen += usize::from(check(&insn));
}
}
}
assert!(seen > 4_000, "only {seen} target-carrying encodings swept");
}
#[test]
fn xrefs_rejects_the_phantom_bl_that_find_bl_sites_reports() {
let mut image = live(0x2000);
crate::write(&mut image, 0x10, &[0xD0, 0xE8, 0x01, 0xF0]);
crate::write(&mut image, 0x14, &[0xD0, 0xF8, 0x04, 0x00]);
crate::write(&mut image, 0x100, &0x11B7u32.to_le_bytes());
let phantom = 0x12;
assert_eq!(crate::decode_bl(&image, phantom), Some(0x11B6));
assert!(
find_bl_sites(&image, 0x11B6).contains(&phantom),
"find_bl_sites must report the phantom — that is the bug"
);
let refs = xrefs(&image, 0x11B6);
assert!(
!refs.iter().any(|x| x.at == phantom),
"xrefs must not report a reference at {phantom:#x}: {refs:?}"
);
assert_eq!(
refs,
vec![Xref {
at: 0x100,
kind: XrefKind::LiteralPool,
via: None,
}]
);
assert_eq!(
isa::disassemble(&image, 0x10, 0x10, 2),
["00000010: tbb [r0, r1]", "00000014: ldr.w r0, [r0, #4]"]
);
}
#[test]
fn xrefs_does_not_mistake_a_pool_address_for_a_destination() {
let mut image = live(0x40);
crate::write(&mut image, 0x00, &0x4801u16.to_le_bytes());
crate::write(&mut image, 0x08, &0x1234u32.to_le_bytes());
crate::write(&mut image, 0x0C, &0x08u32.to_le_bytes());
assert_eq!(
xrefs(&image, 0x08),
vec![Xref {
at: 0x0C,
kind: XrefKind::LiteralPool,
via: None,
}]
);
assert_eq!(
xrefs(&image, 0x1234),
vec![Xref {
at: 0x08,
kind: XrefKind::LiteralPool,
via: None,
}]
);
}
#[test]
fn function_start_finds_each_prologue_form() {
let narrow = [0x10u8, 0xB5, 0x01, 0x20, 0x70, 0x47];
assert_eq!(function_start(&narrow, 4, 16), Some(0));
assert_eq!(function_start(&narrow, 5, 16), Some(0));
assert_eq!(function_start(&narrow, 0, 16), Some(0));
let wide = [0x2Du8, 0xE9, 0xF0, 0x41, 0x70, 0x47];
assert_eq!(function_start(&wide, 4, 16), Some(0));
let no_lr = [0x2Du8, 0xE9, 0xF0, 0x01, 0x70, 0x47];
assert_eq!(function_start(&no_lr, 4, 16), None);
let t3 = [0x4Du8, 0xF8, 0x04, 0xED, 0x70, 0x47];
assert_eq!(function_start(&t3, 4, 16), Some(0));
}
#[test]
fn function_start_respects_max_scan_and_the_image_start() {
let mut image = live(0x14);
crate::write(&mut image, 0, &0xB510u16.to_le_bytes());
nop_fill(&mut image, 2, 0x12);
assert_eq!(function_start(&image, 0x12, 0x12), Some(0));
assert_eq!(function_start(&image, 0x12, 0x10), None);
assert_eq!(function_start(&image, 0x12, 0), None);
assert_eq!(function_start(&image, 0x00, 0), Some(0));
let no_prologue = live(0x10);
assert_eq!(function_start(&no_prologue, 0x0E, usize::MAX), None);
assert_eq!(function_start(&image, 0x1000, 0x10), None);
assert_eq!(function_start(&image, 0x20, 0x20), Some(0));
}
#[test]
fn function_start_is_a_heuristic_and_can_land_mid_instruction() {
let mut image = live(0x20);
crate::write(&mut image, 0x00, &0xB510u16.to_le_bytes());
crate::write(&mut image, 0x02, &[0xC0, 0xE9, 0x0B, 0xB5]);
crate::write(&mut image, 0x06, &0x4770u16.to_le_bytes());
assert_eq!(
isa::disassemble(&image, 0x02, 0x02, 1),
["00000002: strd r11, r5, [r0, #44]"]
);
assert_eq!(
function_start(&image, 0x06, 0x10),
Some(0x04),
"documented behaviour: the nearest halfword-aligned match, whatever \
it is a halfword of"
);
assert_eq!(function_start(&image, 0x02, 0x10), Some(0x00));
let leaf = [0x01u8, 0x20, 0x70, 0x47]; assert_eq!(function_start(&leaf, 0x02, 0x10), None);
}
#[test]
fn literal_value_resolves_align_pc_4_from_either_parity() {
let mut image = live(0x20);
crate::write(&mut image, 0x00, &0x4801u16.to_le_bytes());
crate::write(&mut image, 0x02, &0x4801u16.to_le_bytes());
crate::write(&mut image, 0x08, &0xDEAD_BEEFu32.to_le_bytes());
assert_eq!(literal_value(&image, 0x00), Some(0xDEAD_BEEF));
assert_eq!(literal_value(&image, 0x02), Some(0xDEAD_BEEF));
assert_ne!(0x02 + 4 + 4, 0x08, "the arithmetic everyone gets wrong");
crate::write(&mut image, 0x0C, &0x1234_5678u32.to_le_bytes());
crate::write(&mut image, 0x10, &[0x5F, 0xF8, 0x08, 0x10]);
assert_eq!(literal_value(&image, 0x10), Some(0x1234_5678));
}
#[test]
fn literal_value_refuses_what_it_cannot_answer() {
let mut short = live(0x08);
crate::write(&mut short, 0x04, &0x4801u16.to_le_bytes());
assert_eq!(literal_value(&short, 0x04), None);
let mut other = live(0x10);
crate::write(&mut other, 0x00, &0x4770u16.to_le_bytes()); crate::write(&mut other, 0x02, &0x6801u16.to_le_bytes()); crate::write(&mut other, 0x04, &0xA001u16.to_le_bytes()); assert_eq!(literal_value(&other, 0x00), None);
assert_eq!(literal_value(&other, 0x02), None, "base is r0, not pc");
assert_eq!(literal_value(&other, 0x04), None, "adr loads nothing");
let mut byte = live(0x10);
crate::write(&mut byte, 0x00, &[0x9F, 0xF8, 0x04, 0x00]);
assert_eq!(
isa::decode_at(&byte, 0).map(|i| i.mnemonic),
Some("ldrb"),
"the fixture really is a byte load"
);
assert_eq!(literal_value(&byte, 0x00), None);
let mut data = live(0x10);
crate::write(&mut data, 0x00, &[0x70, 0xF8, 0x00, 0x00]);
assert_eq!(
isa::decode_at(&data, 0),
None,
"the fixture must not decode"
);
assert_eq!(literal_value(&data, 0x00), None);
assert_eq!(literal_value(&data, 0x10), None);
}
#[test]
fn nop_fill_round_trips_through_the_decoder() {
let mut image = live(0x10);
nop_fill(&mut image, 0x04, 0x08);
assert_eq!(&image[0x00..0x04], &[0, 0, 0, 0]);
assert_eq!(&image[0x0C..0x10], &[0, 0, 0, 0]);
let decoded: Vec<String> = Decoder::at(&image, 0x04, 0x04)
.take(4)
.map(|i| i.to_string())
.collect();
assert_eq!(decoded, ["nop", "nop", "nop", "nop"]);
assert_eq!(
isa::decode_at(&image, 0).map(|i| i.to_string()),
Some("movs r0, r0".to_string())
);
assert!(isa::decode_at(&image, 0).unwrap().sets_flags);
assert!(!isa::decode_at(&image, 4).unwrap().sets_flags);
let before = image.clone();
nop_fill(&mut image, 0x06, 0);
assert_eq!(image, before);
}
#[test]
#[should_panic(expected = "there is no 1-byte Thumb instruction")]
fn nop_fill_refuses_an_odd_length() {
nop_fill(&mut live(0x10), 0x04, 0x03);
}
#[test]
#[should_panic(expected = "halfword aligned")]
fn nop_fill_refuses_an_odd_offset() {
nop_fill(&mut live(0x10), 0x03, 0x04);
}
#[test]
#[should_panic(expected = "past the end")]
fn nop_fill_refuses_to_run_off_the_end() {
nop_fill(&mut live(0x10), 0x0C, 0x08);
}
#[test]
fn reachable_follows_both_arms_and_stops_at_returns() {
let image = [0x08, 0xB1, 0x01, 0x20, 0x70, 0x47, 0x00, 0x20, 0x70, 0x47];
let r = reachable(&image, 0, 64);
assert!(r.complete);
assert_eq!(r.insns, vec![0, 2, 4, 6, 8]);
assert_eq!(r.end, 10);
assert_eq!(r.unresolved, vec![4, 8], "the two `bx lr` returns");
}
#[test]
fn reachable_does_not_follow_calls_but_does_resume_after_them() {
let mut image = live(0x40);
crate::write(&mut image, 0x00, &0xB500u16.to_le_bytes());
crate::write(&mut image, 0x02, &encode_bl(0x02, 0x20).unwrap());
crate::write(&mut image, 0x06, &0xBD00u16.to_le_bytes());
crate::write(&mut image, 0x20, &0x4770u16.to_le_bytes());
let r = reachable(&image, 0, 64);
assert!(r.complete);
assert_eq!(r.insns, vec![0x00, 0x02, 0x06]);
assert_eq!(r.end, 0x08);
assert_eq!(r.unresolved, vec![0x06]);
assert_eq!(reachable(&image, 0x20, 64).insns, vec![0x20]);
}
#[test]
fn reachable_reports_an_unconditional_branch_as_leaving() {
let mut image = live(0x20);
crate::write(&mut image, 0x00, &(0xE000u16 | 0x02).to_le_bytes());
nop_fill(&mut image, 0x02, 0x06);
crate::write(&mut image, 0x08, &0x4770u16.to_le_bytes());
let r = reachable(&image, 0, 64);
assert!(r.complete);
assert_eq!(
r.insns,
vec![0x00, 0x08],
"the skipped nops are not reached"
);
assert_eq!(r.unresolved, vec![0x08]);
}
#[test]
fn reachable_is_honest_about_running_out_of_road() {
let image = [0x00u8, 0xBF, 0x00, 0xBF, 0x00, 0xBF, 0x70, 0x47];
assert!(reachable(&image, 0, 4).complete);
let clipped = reachable(&image, 0, 2);
assert!(!clipped.complete);
assert!(clipped.insns.len() <= 3);
let bad = [0x01u8, 0x20, 0x70, 0xF8, 0x00, 0x00];
let r = reachable(&bad, 0, 64);
assert!(!r.complete, "an undefined encoding must not pass silently");
assert_eq!(r.insns, vec![0]);
}
#[test]
fn reachable_walks_a_loop_once_and_terminates() {
let image = [0x01u8, 0x20, 0xFD, 0xE7];
assert_eq!(
isa::decode_at(&image, 2).and_then(|i| i.branch_target()),
Some(0),
"the fixture must branch back to the top"
);
let r = reachable(&image, 0, 64);
assert!(r.complete, "a loop is not a reason to give up");
assert_eq!(r.insns, vec![0, 2], "each instruction once, not twice");
assert_eq!(r.end, 4);
assert_eq!(r.unresolved, vec![], "the back edge is resolved");
let diamond = [0x10u8, 0xB1, 0x01, 0x20, 0x00, 0xE0, 0x00, 0xBF, 0x70, 0x47];
assert_eq!(
isa::decode_at(&diamond, 0).and_then(|i| i.branch_target()),
Some(8),
"both arms must join at 0x08"
);
let r = reachable(&diamond, 0, 64);
assert!(r.complete);
assert_eq!(r.insns, vec![0, 2, 4, 8], "0x06 is never reached");
assert_eq!(r.unresolved, vec![8]);
}
#[test]
fn reachable_is_incomplete_when_an_edge_leaves_the_image() {
let cut = [0x01u8, 0x20]; let r = reachable(&cut, 0, 64);
assert!(!r.complete, "the fall-through leaves the image");
assert_eq!(r.insns, vec![0]);
assert_eq!(r.end, 2);
assert_eq!(
r.unresolved,
vec![],
"not an unresolved branch — an absent one"
);
let far = [0xFFu8, 0xE3];
assert_eq!(
isa::decode_at(&far, 0).and_then(|i| i.branch_target()),
Some(0x802)
);
let r = reachable(&far, 0, 64);
assert!(!r.complete);
assert_eq!(r.insns, vec![0]);
assert_eq!(r.unresolved, vec![]);
}
#[test]
fn reachable_does_not_walk_into_a_veneers_literal() {
let mut image = live(0x20);
crate::write(&mut image, 0x00, &veneer(0x00, 0x1234).unwrap());
let r = reachable(&image, 0, 64);
assert!(r.complete);
assert_eq!(r.insns, vec![0x00]);
assert_eq!(r.end, 0x04, "the literal is data, not an instruction");
assert_eq!(r.unresolved, vec![0x00]);
}
#[test]
fn veneer_reaches_where_no_branch_encoding_can() {
let far = 0x0200_0000u32; assert_eq!(encode_bl(0x10, far), None);
assert_eq!(crate::encode_b_wide(0x10, far), None);
let mut image = live(0x20);
let stub = veneer(0x10, far).unwrap();
crate::write(&mut image, 0x10, &stub);
let insn = isa::decode_at(&image, 0x10).unwrap();
assert_eq!(insn.mnemonic, "ldr");
assert!(insn.is_branch() && insn.writes_pc());
assert_eq!(insn.branch_target(), Some(0x14), "the pool word's address");
assert_eq!(literal_value(&image, 0x10), Some(far | 1));
assert_eq!(crate::read_u32(&image, 0x14) & 1, 1);
assert_eq!(veneer(0x10, far | 1), Some(stub));
assert!(encode_bl(0x00, 0x10).is_some());
}
#[test]
fn veneer_refuses_a_placement_align_pc_4_would_break() {
assert_eq!(veneer(0x02, 0x1234), None);
assert_eq!(veneer(0x06, 0x1234), None);
assert!(veneer(0x04, 0x1234).is_some());
assert!(veneer(0x00, 0x1234).is_some());
let mut image = live(0x40);
for b in &mut image[0x22..0x40] {
*b = 0xFF;
}
let at = crate::find_free_space(&image, 8, 4, 0).unwrap();
assert_eq!(at, 0x24);
assert!(veneer(at, 0x1234).is_some());
}
#[test]
fn a_return_made_conditional_by_an_enclosing_it_block_still_falls_through() {
let image = [0x08, 0xBF, 0x70, 0x47, 0x01, 0x20, 0x70, 0x47];
let r = reachable(&image, 0, 64);
assert!(r.complete, "nothing here is indeterminate");
assert_eq!(r.insns, vec![0, 2, 4, 6], "the fall-through arm is live");
assert_eq!(r.end, 8);
assert_eq!(r.unresolved, vec![2, 6], "both returns are indirect edges");
}
#[test]
fn an_unconditional_return_ends_the_path() {
let image = [0x70, 0x47, 0x01, 0x20, 0x70, 0x47];
let r = reachable(&image, 0, 64);
assert_eq!(r.insns, vec![0], "control leaves at the first instruction");
assert_eq!(r.end, 2);
assert_eq!(r.unresolved, vec![0]);
}
#[test]
fn it_state_expires_and_the_next_return_is_unconditional_again() {
let image = [0x04, 0xBF, 0x70, 0x47, 0x70, 0x47, 0x70, 0x47, 0x01, 0x20];
let r = reachable(&image, 0, 64);
assert_eq!(
r.insns,
vec![0, 2, 4, 6],
"offset 8 is past the last return"
);
assert_eq!(r.end, 8);
assert_eq!(r.unresolved, vec![2, 4, 6]);
}
#[test]
fn xrefs_reaches_a_branch_in_the_final_halfword() {
let mut image = live(0x80);
let at = image.len() - 2;
crate::write(&mut image, at, &(0xE000u16 | 0x7DF).to_le_bytes());
let found = xrefs(&image, 0x40);
assert_eq!(found.len(), 1, "the last halfword is inside the image");
assert_eq!(found[0].at, at);
assert_eq!(found[0].kind, XrefKind::Branch);
}
#[test]
fn xrefs_finds_a_stored_pointer_in_the_last_word_of_the_image() {
let mut image = live(0x40);
let at = image.len() - 4;
crate::write(&mut image, at, &0x41u32.to_le_bytes());
let found = xrefs(&image, 0x40);
assert!(
found
.iter()
.any(|x| x.at == at && x.kind == XrefKind::LiteralPool),
"a pointer in the final word must be reported: {found:?}"
);
}
#[test]
fn both_xref_scans_cover_the_whole_image_not_a_fraction_of_it() {
let mut image = live(0x400);
let branch_at = 0x300;
let bl = crate::encode_bl(branch_at, 0x40).expect("in range");
crate::write(&mut image, branch_at, &bl);
let pointer_at = 0x380;
crate::write(&mut image, pointer_at, &0x41u32.to_le_bytes());
let found = xrefs(&image, 0x40);
assert!(
found
.iter()
.any(|x| x.at == branch_at && x.kind == XrefKind::Call),
"the call at {branch_at:#x} is past the half-way point: {found:?}"
);
assert!(
found
.iter()
.any(|x| x.at == pointer_at && x.kind == XrefKind::LiteralPool),
"the pointer at {pointer_at:#x} is past the quarter-way point: {found:?}"
);
}
}