642d5a256791
pseudo.rs
//! A small, honest pseudo-C lifter. It works at register level (no type recovery), turns each
//! basic block into C-like statements, and structures the control-flow graph into `if`/`else`
//! and `while` using dominators and post-dominators, falling back to labels and `goto` where the
//! graph isn't structured. Calls get resolved names and arguments from the calling convention;
//! string literals are inlined.
use crate::decode::{ArmConsts, Cond, Flow, Insn, Kind, MemOp, Mode, Op, Shift, canonical_reg};
use crate::image::Image;
use crate::program::{Function, Program};
use craft_anything_formats::Format;
use serde::Serialize;
use std::collections::{BTreeMap, BTreeSet};
/// Blocks above this are listed linearly with labels instead of being structured.
const MAX_STRUCTURED_BLOCKS: usize = 1500;
const MAX_DEPTH: usize = 64;
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct Pseudo {
pub signature: String,
pub text: String,
/// Names of everything called.
pub calls: Vec<String>,
/// String literals used.
pub strings: Vec<String>,
pub gotos: usize,
/// Instructions shown as `__asm(...)` because the lifter has no rule for them.
pub asm_fallbacks: usize,
/// True when the control flow was fully structured (no gotos, no linear fallback).
pub structured: bool,
pub limitations: Vec<(String, String)>,
}
#[derive(Debug, Clone)]
struct Line {
indent: usize,
text: String,
label: Option<u64>,
loop_end: bool,
}
struct BlockCode {
stmts: Vec<String>,
cond: Option<String>,
/// Condition is for the taken edge; `taken` is its target.
taken: Option<u64>,
}
/// Source expression and read-dependencies for an assignment that may be folded into a later call.
struct InlineExpr {
idx: usize,
expr: String,
deps: Vec<String>,
/// The memory the expression reads, if any: a later store that may overlap it changes the
/// value, so the expression can't move past that store.
mem: Option<MemOp>,
}
/// Latest assignment to a register or outgoing stack slot in the current basic block.
/// While `inline` is `Some`, its RHS can be folded straight into a call and its statement removed;
/// if a source dependency changes before the call, `inline` clears to `None` so the statement stays
/// emitted and the call receives the assigned target name (`rsi`, `stack_20`, etc.).
struct PendingAssign {
target: String,
inline: Option<InlineExpr>,
}
/// Clear `inline` on pending assignments that read any canonical register overwritten in `written`,
/// keeping the target slot registered so callers still pass the preserved register or stack slot.
fn invalidate_dependents<K: Ord>(map: &mut BTreeMap<K, PendingAssign>, written: &[String]) {
if written.is_empty() {
return;
}
for assign in map.values_mut() {
if assign.inline.as_ref().is_some_and(|e| e.deps.iter().any(|r| written.contains(r))) {
assign.inline = None;
}
}
}
/// Registers that can be distinguished from static addresses in this function and block.
#[derive(Clone, Copy)]
struct FrameBases {
stack: bool,
pointer: Option<&'static str>,
}
/// An A64 stack adjustment by an immediate preserves the stack base. A new value from
/// another register can point into static storage, including in a later block.
fn replaces_a64_stack(i: &Insn) -> bool {
if !i.writes.iter().any(|r| r == "sp") {
return false;
}
match (i.kind, i.ops.as_slice()) {
(Kind::Add | Kind::Sub | Kind::Mov, [Op::Reg(dst), Op::Reg(src), Op::Imm(_)]) if dst == "sp" && src == "sp" => false,
// Scalar LDR/STR and pair writebacks have an immediate offset. Vector structure
// loads and stores can take their increment from a register.
(Kind::Load | Kind::Store, [_, Op::Mem(m)]) if m.base.as_deref() == Some("sp") && (i.mnemonic.starts_with("ldr") || i.mnemonic.starts_with("str")) => {
false
}
(Kind::StorePair | Kind::LoadPair, [_, _, Op::Mem(m)]) if m.base.as_deref() == Some("sp") => false,
_ => true,
}
}
/// Keep the x86 stack distinct from static data only while stack writes preserve its base.
fn replaces_x86_stack(i: &Insn) -> bool {
if !i.writes.iter().any(|r| r == "rsp") {
return false;
}
match (i.kind, i.ops.as_slice()) {
(Kind::Add | Kind::Sub, [Op::Reg(dst), Op::Imm(_)]) if dst == "rsp" => false,
(Kind::Lea, [Op::Reg(dst), Op::Mem(m)]) if dst == "rsp" && m.base.as_deref() == Some("rsp") && m.index.is_none() && m.seg.is_none() => false,
_ => true,
}
}
/// Clear `inline` on pending assignments whose expression reads memory that a write to `written`
/// may overlap. `None` is a write whose bytes aren't known, which may overlap any read.
fn invalidate_memory_readers(map: &mut BTreeMap<String, PendingAssign>, written: Option<&MemOp>, frame: FrameBases) {
for assign in map.values_mut() {
if assign.inline.as_ref().and_then(|e| e.mem.as_ref()).is_some_and(|read| written.is_none_or(|w| may_overlap(read, w, frame))) {
assign.inline = None;
}
}
}
/// Clear `inline` on Win64 outgoing stack arguments (`[rsp+off]`, eight bytes) that a write to
/// `written` may change, so the call passes the slot as it is and the store that set it stays.
fn invalidate_stack_slots(slots: &mut BTreeMap<i64, PendingAssign>, written: Option<&MemOp>, frame: FrameBases) {
if let Some(w) = written
&& w.base.as_deref() == Some("rsp")
&& w.index.is_none()
&& w.seg.is_none()
&& w.addr.is_none()
&& w.size > 0
{
let first = w.disp.saturating_sub(7);
let last = w.disp.saturating_add(i64::from(w.size) - 1);
for (_, assign) in slots.range_mut(first..=last) {
assign.inline = None;
}
return;
}
for (&off, assign) in slots.iter_mut() {
let slot = MemOp { base: Some("rsp".into()), index: None, index_shift: None, scale: 1, disp: off, size: 8, addr: None, seg: None };
if written.is_none_or(|w| may_overlap(&slot, w, frame)) {
assign.inline = None;
}
}
}
/// Size of an A64 data register in bytes.
fn reg_width(o: Option<&Op>) -> u8 {
match o {
Some(Op::Reg(r)) => match r.as_bytes().first() {
Some(b'x') => 8,
Some(b'w') => 4,
Some(b'q') => 16,
Some(b'd') => 8,
Some(b's') if r != "sp" => 4,
Some(b'h') => 2,
Some(b'b') => 1,
_ => 0,
},
_ => 0,
}
}
/// Memory width and sign extension of a scalar A64 load.
fn scalar_load(i: &Insn) -> (u8, bool) {
match i.mnemonic.as_str() {
"ldrb" | "ldurb" | "ldarb" => (1, false),
"ldrh" | "ldurh" | "ldarh" => (2, false),
"ldrsb" | "ldursb" => (1, true),
"ldrsh" | "ldursh" => (2, true),
"ldrsw" | "ldursw" => (4, true),
_ => (reg_width(i.ops.first()), false),
}
}
/// Memory footprint used to check whether a pending argument survives a write.
fn accessed(mode: Mode, i: &Insn, m: &MemOp) -> MemOp {
let pair_width = |start: usize| {
let (a, b) = (reg_width(i.ops.get(start)), reg_width(i.ops.get(start + 1)));
if a == 0 || b == 0 { 0 } else { a + b }
};
let size = match (m.size, mode, i.kind) {
(0, Mode::A64, Kind::Store) if matches!(i.mnemonic.as_str(), "stxp" | "stlxp") => pair_width(1),
(0, Mode::A64, Kind::Store) if matches!(i.mnemonic.as_str(), "stxr" | "stxrb" | "stxrh" | "stlxr" | "stlxrb" | "stlxrh") => reg_width(i.ops.get(1)),
(0, Mode::A64, Kind::Load) => scalar_load(i).0,
(0, Mode::A64, Kind::Store) => reg_width(i.ops.first()),
(0, Mode::A64, Kind::LoadPair | Kind::StorePair) => pair_width(0),
(s, ..) => s,
};
let addr = if mode == Mode::A64 && matches!(i.kind, Kind::Load | Kind::Store) && matches!(i.ops.get(1), Some(Op::Mem(_))) {
m.addr.or_else(|| i.refs.first().copied())
} else {
m.addr
};
MemOp { size, addr, ..m.clone() }
}
/// Whether two memory operands can share a byte. Without a known overlap they are assumed to:
/// only the same absolute address range, or the same segment, base and index with displacements
/// far enough apart, are told apart, and an unindexed, unsegmented frame slot never overlaps an
/// absolute address. An access of unknown width (0) may reach any byte from its start on.
fn may_overlap(a: &MemOp, b: &MemOp, frame: FrameBases) -> bool {
// A segment base (`fs:[rax]`) moves the address by an amount that isn't known here.
if a.seg != b.seg {
return true;
}
let ends_by = |x: i64, m: &MemOp, y: i64| m.size != 0 && x.saturating_add(i64::from(m.size)) <= y;
let apart = |x: i64, y: i64| ends_by(x, a, y) || ends_by(y, b, x);
let is_frame = |m: &MemOp| {
m.addr.is_none()
&& m.index.is_none()
&& m.seg.is_none()
&& m.base.as_deref().is_some_and(|r| frame.stack && (matches!(r, "rsp" | "esp" | "sp") || Some(r) == frame.pointer))
};
match (a.addr, b.addr) {
(Some(x), Some(y)) => !apart(x as i64, y as i64),
(Some(_), None) => !is_frame(b),
(None, Some(_)) => !is_frame(a),
(None, None) => {
let same = |p: &Option<String>, q: &Option<String>| p.as_deref().map(canonical_reg) == q.as_deref().map(canonical_reg);
// The scale and extension only matter with an index.
let same_index = same(&a.index, &b.index) && (a.index.is_none() || (a.scale == b.scale && a.index_shift == b.index_shift));
if same(&a.base, &b.base) && same_index { !apart(a.disp, b.disp) } else { true }
}
}
}
struct Lifter<'a> {
img: &'a Image,
prog: &'a Program,
names: &'a dyn Fn(u64) -> Option<String>,
mode: Mode,
arg_regs: &'static [&'static str],
/// Win64: calls take arguments 5+ from the stack at `[rsp+0x20]`, `[rsp+0x28]`, โฆ
win64: bool,
/// Jump targets that leave the function (tail calls).
tail_calls: &'a [u64],
ret_reg: String,
calls: BTreeSet<String>,
strings: Vec<String>,
asm_fallbacks: usize,
}
fn escape(s: &str) -> String {
let mut out = String::new();
for (i, c) in s.chars().enumerate() {
if i >= 120 {
out.push_str("...");
break;
}
match c {
'"' => out.push_str("\\\""),
'\\' => out.push_str("\\\\"),
'\n' => out.push_str("\\n"),
'\r' => out.push_str("\\r"),
'\t' => out.push_str("\\t"),
c if c.is_control() => out.push_str(&format!("\\x{:02x}", c as u32)),
c => out.push(c),
}
}
out
}
/// True when `op` is the AArch64 zero register (`wzr` or `xzr`).
fn is_zero_reg(op: Option<&Op>) -> bool {
matches!(op, Some(Op::Reg(r)) if matches!(r.as_str(), "wzr" | "xzr"))
}
fn ty(size: u8) -> &'static str {
match size {
1 => "uint8_t",
2 => "uint16_t",
4 => "uint32_t",
8 => "uint64_t",
16 => "uint128_t",
_ => "void",
}
}
/// Dereference a scalar load with its encoded width and sign extension.
fn scalar_deref(mode: Mode, i: &Insn, addr: &str) -> String {
let word = matches!(i.ops.first(), Some(Op::Reg(r)) if r.starts_with('w'));
let ty = match mode {
Mode::A32 | Mode::T32 => "uint32_t",
Mode::A64 => {
let (width, signed) = scalar_load(i);
let name = ty(width);
if signed {
name.trim_start_matches('u')
} else if width == 0 {
"uint64_t"
} else {
name
}
}
_ => "uint64_t",
};
// Writing W zeroes the high half of X even for a sign-extending load.
let cast = if word && ty.starts_with("int") { "(uint32_t)" } else { "" };
format!("{cast}*({ty}*){addr}")
}
/// A shifted or extended register as C: the shift's signedness and width are spelled out, since
/// registers have no types here.
fn shifted(reg: &str, shift: Shift, n: u8) -> String {
let bits: u8 = if reg.starts_with('w') { 32 } else { 64 };
// (the extension, the 64-bit type it widens to before a shift)
let (cast, wide) = match shift {
Shift::Lsl => return format!("({reg} << {n})"),
Shift::Lsr => return format!("((uint{bits}_t){reg} >> {n})"),
Shift::Asr => return format!("((int{bits}_t){reg} >> {n})"),
Shift::Ror => {
return match bits.checked_sub(n) {
Some(back) if n > 0 && back > 0 => format!("((uint{bits}_t){reg} >> {n} | (uint{bits}_t){reg} << {back})"),
_ => reg.to_string(),
};
}
Shift::Uxtb => ("uint8_t", "uint64_t"),
Shift::Uxth => ("uint16_t", "uint64_t"),
Shift::Uxtw => ("uint32_t", "uint64_t"),
Shift::Uxtx => ("uint64_t", "uint64_t"),
Shift::Sxtb => ("int8_t", "int64_t"),
Shift::Sxth => ("int16_t", "int64_t"),
Shift::Sxtw => ("int32_t", "int64_t"),
Shift::Sxtx => ("int64_t", "int64_t"),
};
// Extend, then widen before shifting, so the shift can't lose the bits C's narrower type would drop.
match n {
0 => format!("({cast}){reg}"),
_ if cast == wide => format!("(({wide}){reg} << {n})"),
_ => format!("(({wide})({cast}){reg} << {n})"),
}
}
fn imm(v: i64) -> String {
if (-16..=16).contains(&v) {
v.to_string()
} else if v < 0 {
format!("-{:#x}", v.unsigned_abs())
} else {
format!("{v:#x}")
}
}
impl Lifter<'_> {
fn addr_name(&self, a: u64) -> Option<String> {
(self.names)(a).or_else(|| self.prog.name_at(a))
}
/// Inline a string literal at `a`, slicing by byte offset for UTF-8 and 2-byte code-unit offset
/// for UTF-16LE while rejecting misaligned interior addresses.
fn string_lit(&mut self, a: u64) -> Option<String> {
let s = self.prog.string_at(a)?;
let off = usize::try_from(a.checked_sub(s.addr)?).ok()?;
let text = match s.encoding {
craft_anything_formats::strings::Encoding::Ascii | craft_anything_formats::strings::Encoding::Utf8 => {
let tail = s.text.get(off..)?;
if off > 0 && tail.is_empty() {
return None;
}
tail.to_string()
}
craft_anything_formats::strings::Encoding::Utf16le => {
if off == 0 {
s.text.clone()
} else {
if !off.is_multiple_of(2) {
return None;
}
let units: Vec<u16> = s.text.encode_utf16().collect();
let tail = units.get(off / 2..)?;
if tail.is_empty() {
return None;
}
String::from_utf16(tail).ok()?
}
}
};
if !self.strings.contains(&text) && self.strings.len() < 256 {
self.strings.push(text.clone());
}
Some(format!("\"{}\"", escape(&text)))
}
/// `&thing` for an address-of.
fn address_of(&mut self, a: u64) -> String {
if let Some(s) = self.string_lit(a) {
return s;
}
match self.addr_name(a) {
Some(n) => format!("&{n}"),
None => {
if self.img.is_exec(a) {
format!("sub_{a:x}")
} else {
format!("&data_{a:x}")
}
}
}
}
/// The address arithmetic of a memory operand, without dereferencing it.
fn mem_addr(&mut self, m: &MemOp) -> String {
if let Some(a) = m.addr {
return self.address_of(a);
}
let mut parts = Vec::new();
if let Some(b) = &m.base {
parts.push(b.clone());
}
if let Some(i) = &m.index {
parts.push(self.index_expr(i, m));
}
if m.disp != 0 || parts.is_empty() {
parts.push(imm(m.disp));
}
parts.join(" + ").replace("+ -", "- ")
}
fn mem(&mut self, m: &MemOp) -> String {
if let Some(seg) = &m.seg {
return format!("{seg}:[{}]", self.mem_addr(m));
}
if let Some(a) = m.addr {
if let Some(n) = self.addr_name(a) {
return n;
}
return format!("*({}*){a:#x}", ty(m.size));
}
let frame = matches!(m.base.as_deref(), Some("rbp" | "ebp" | "bp" | "x29"));
let stack = matches!(m.base.as_deref(), Some("rsp" | "esp" | "sp"));
if m.index.is_none() && (frame || stack) {
let prefix = if frame { if m.disp < 0 { "var" } else { "arg" } } else { "stack" };
return format!("{prefix}_{:x}", m.disp.unsigned_abs());
}
let mut parts = Vec::new();
if let Some(b) = &m.base {
parts.push(b.clone());
}
if let Some(i) = &m.index {
parts.push(self.index_expr(i, m));
}
if m.disp != 0 || parts.is_empty() {
parts.push(imm(m.disp));
}
format!("*({}*)({})", ty(m.size), parts.join(" + ").replace("+ -", "- "))
}
/// An index register as it enters the address: extended when the instruction extends it
/// (`[x1, w2, sxtw #2]`), scaled when the encoding only says a scale (x86), plain otherwise.
fn index_expr(&mut self, index: &str, m: &MemOp) -> String {
match m.index_shift {
Some(s) => shifted(index, s.shift, s.amount),
None if m.scale > 1 => format!("{index} * {}", m.scale),
None => index.to_string(),
}
}
fn op(&mut self, o: &Op) -> String {
match o {
Op::Reg(r) => r.clone(),
Op::Imm(v) => imm(*v),
Op::Mem(m) => self.mem(m),
Op::Addr(a) => self.address_of(*a),
Op::Shifted { reg, shift, amount } => shifted(reg, *shift, *amount),
}
}
fn call_name(&self, i: &Insn) -> String {
match i.flow {
Flow::Call { target } => self.addr_name(target).unwrap_or_else(|| format!("sub_{target:x}")),
Flow::IndirectCall { slot: Some(s) } => {
self.prog.import_slots.get(&s).map(|x| x.name.clone()).or_else(|| self.addr_name(s)).unwrap_or_else(|| format!("(*{s:#x})"))
}
_ => match i.ops.first() {
Some(Op::Reg(r)) => format!("(*{r})"),
Some(Op::Mem(m)) => {
let m = m.clone();
let mut tmp = Lifter {
img: self.img,
prog: self.prog,
names: self.names,
mode: self.mode,
arg_regs: self.arg_regs,
win64: self.win64,
tail_calls: self.tail_calls,
ret_reg: String::new(),
calls: BTreeSet::new(),
strings: Vec::new(),
asm_fallbacks: 0,
};
format!("(*{})", tmp.mem(&m))
}
_ => "(*unknown)".into(),
},
}
}
/// Register arguments of a call: up to the last argument register assigned in this block (at
/// least `min`). Assignments whose dependencies stay intact are folded into the call; invalidated
/// ones keep their emitted statement and pass the register name itself.
fn reg_args(&self, defs: &BTreeMap<String, PendingAssign>, dead: &mut BTreeSet<usize>, min: usize) -> Vec<String> {
let n = self.arg_regs.iter().rposition(|r| defs.contains_key(*r)).map(|p| p + 1).unwrap_or(0).max(min).min(self.arg_regs.len());
self.arg_regs
.iter()
.take(n)
.map(|r| match defs.get(*r) {
Some(assign) => match &assign.inline {
Some(def) => {
dead.insert(def.idx);
def.expr.clone()
}
None => assign.target.clone(),
},
None => (*r).to_string(),
})
.collect()
}
/// Statements for one block plus its branch condition.
fn block(&mut self, insns: &[Insn], entry_or_exit: bool, stack_is_frame: bool) -> BlockCode {
let mut stmts: Vec<String> = Vec::new();
// canonical reg โ pending assignment of its latest value in this block
let mut defs: BTreeMap<String, PendingAssign> = BTreeMap::new();
// canonical reg โ (statement index, value) while that assignment is a plain constant,
// so a following MOVK can fold with it
let mut consts: BTreeMap<String, (usize, u64)> = BTreeMap::new();
let mut pushes: Vec<String> = Vec::new();
let mut flag_src: Option<&Insn> = None;
let mut cond = None;
let mut taken = None;
let mut dead: BTreeSet<usize> = BTreeSet::new();
// Win64 outgoing stack arguments stored in this block: rsp offset โ pending assignment.
let mut stack_args: BTreeMap<i64, PendingAssign> = BTreeMap::new();
// A split argument may be initialized high half first, before its low-address store.
let mut written_slots = BTreeSet::new();
// Registers assigned in this block whose assignment a later read took out of `defs`:
// still set here, so a memory-indirect call's base among them is still an argument.
let mut read_after_set: BTreeSet<String> = BTreeSet::new();
let mut frame = FrameBases { stack: stack_is_frame, pointer: None };
for (k, i) in insns.iter().enumerate() {
if i.writes.iter().any(|r| matches!(r.as_str(), "rbp" | "x29")) {
frame.pointer = match (i.kind, i.ops.as_slice()) {
(Kind::Mov, [Op::Reg(dst), Op::Reg(src)]) if i.mnemonic == "mov" && dst == "rbp" && src == "rsp" => Some("rbp"),
(Kind::Add | Kind::Mov, [Op::Reg(dst), Op::Reg(src), Op::Imm(_)]) if dst == "x29" && src == "sp" => Some("x29"),
_ => None,
};
}
let exclusive_memory = self.mode == Mode::A64
&& matches!(
i.mnemonic.as_str(),
"ldxr"
| "ldxrb"
| "ldxrh"
| "ldaxr"
| "ldaxrb"
| "ldaxrh"
| "ldxp"
| "ldaxp"
| "stxr"
| "stxrb"
| "stxrh"
| "stlxr"
| "stlxrb"
| "stlxrh"
| "stxp"
| "stlxp"
);
// The constant a MOVK is about to fold with, before its own read of the destination
// hides the assignment (the read-removal below is what makes the pair two statements).
let insert_dst = (self.mode == Mode::A64 && i.kind == Kind::Insert)
.then(|| i.ops.first().and_then(|o| if let Op::Reg(r) = o { Some(canonical_reg(r)) } else { None }))
.flatten();
let insert_src = insert_dst.as_ref().and_then(|r| consts.get(r).copied());
// A register read by a later instruction (including an indirect call's target,
// address base/index, or pointer-authentication modifier) keeps its assignment
// instead of being folded away as a call argument.
//
// The base of a memory-indirect call (`call [rdi + 16]`) is usually the object the
// callee is reached through, so an argument register there still counts as an
// argument: it is passed by name and its assignment stays visible. A register target,
// an index or a modifier only addresses the callee.
let call_base = match (&i.flow, i.ops.first()) {
(Flow::IndirectCall { .. }, Some(Op::Mem(m))) => m.base.as_deref().map(canonical_reg),
_ => None,
};
for r in &i.reads {
consts.remove(r);
if call_base.as_ref() == Some(r) {
if let Some(base) = defs.get_mut(r) {
base.inline = None;
continue;
}
if read_after_set.contains(r) {
defs.insert(r.clone(), PendingAssign { target: r.clone(), inline: None });
continue;
}
}
if defs.remove(r).is_some() {
read_after_set.insert(r.clone());
}
}
for w in &i.writes {
read_after_set.remove(w);
}
// A memory write moves no load past it that may read the bytes it writes, and an
// outgoing stack argument it may change no longer folds to the value stored before it.
let mem_op = |o: &Op| if let Op::Mem(m) = o { Some(accessed(self.mode, i, m)) } else { None };
let written: Option<Option<MemOp>> = match i.kind {
Kind::Store | Kind::StorePair => i.ops.iter().find_map(mem_op).map(Some),
Kind::Mov
| Kind::Add
| Kind::Sub
| Kind::And
| Kind::Or
| Kind::Xor
| Kind::Inc
| Kind::Dec
| Kind::Not
| Kind::Neg
| Kind::Shl
| Kind::Shr
| Kind::Sar => i.ops.first().and_then(mem_op).map(Some),
// An instruction the lifter doesn't model (A32 `strb`, x86 `stosb`) may write its
// memory operand at a width that isn't known, or memory it doesn't name at all.
Kind::Other if self.mode.is_x86() => match (i.mnemonic.split_ascii_whitespace().next_back(), i.ops.as_slice()) {
(Some("bts" | "btr" | "btc"), [Op::Mem(_), Op::Reg(_)]) => Some(None),
(Some("movdir64b"), [Op::Reg(base), Op::Mem(_)]) if self.mode == Mode::X64 && canonical_reg(base) != *base => Some(None),
(Some("movdir64b"), [Op::Reg(base), Op::Mem(_)]) => {
Some(Some(MemOp { base: Some(base.clone()), index: None, index_shift: None, scale: 1, disp: 0, size: 64, addr: None, seg: None }))
}
_ => Some(i.ops.iter().find_map(mem_op).map(|m| MemOp { size: 0, ..m })),
},
Kind::Other => Some(i.ops.iter().find_map(mem_op).map(|m| MemOp { size: 0, ..m })),
_ => None,
};
let mut prior_slot_write = false;
if let Some(w) = &written {
if self.win64
&& let Some(w) = w
&& w.base.as_deref() == Some("rsp")
&& w.index.is_none()
&& w.seg.is_none()
&& w.size > 0
{
let first = (w.disp & !7).max(0x20);
let last = w.disp.saturating_add(i64::from(w.size) - 1) & !7;
for slot in (first..=last).step_by(8) {
if !written_slots.insert(slot) && slot == w.disp {
prior_slot_write = true;
}
}
}
invalidate_memory_readers(&mut defs, w.as_ref(), frame);
invalidate_stack_slots(&mut stack_args, w.as_ref(), frame);
}
// AArch64 page loads and import-slot loads are shown through what uses them.
if i.kind == Kind::Adrp
|| (self.mode == Mode::A64
&& !exclusive_memory
&& i.kind == Kind::Load
&& i.refs.first().is_some_and(|r| self.prog.import_slots.contains_key(r)))
{
// The skipped instruction still overwrites its destination: no constant,
// assignment, or pending expression reading it survives.
invalidate_dependents(&mut defs, &i.writes);
invalidate_dependents(&mut stack_args, &i.writes);
for w in &i.writes {
defs.remove(w);
consts.remove(w);
}
if i.writes.iter().any(|w| w == "rsp") {
stack_args.clear();
written_slots.clear();
}
continue;
}
let d = i.ops.first().map(|o| self.op(o));
let s = i.ops.get(1).map(|o| self.op(o));
let t = i.ops.get(2).map(|o| self.op(o));
let mut stmt: Option<String> = None;
// set when this statement leaves its destination holding a known constant
let mut const_def: Option<(String, u64)> = None;
// A store's first operand is the register it reads (`str r1, [r4]`), not a destination:
// recording it would fold the store's own statement away as that register's value.
let dest_reg = match (i.kind, i.ops.first()) {
(Kind::Store | Kind::StorePair, _) => None,
(_, Some(Op::Reg(r))) => Some(canonical_reg(r)),
_ => None,
};
// The memory this instruction's value comes from (a load, or an operation with a memory
// source); `lea` only computes an address. A PC-relative literal load names its fixed
// address as an `Addr` operand.
let read_mem = match i.kind {
Kind::Lea | Kind::Store | Kind::StorePair => None,
_ => i.ops.iter().skip(1).find_map(|o| match o {
Op::Mem(m) => Some(accessed(self.mode, i, m)),
&Op::Addr(a) if i.kind == Kind::Load => Some(accessed(
self.mode,
i,
&MemOp { base: None, index: None, index_shift: None, scale: 0, disp: 0, size: 0, addr: Some(a), seg: None },
)),
_ => None,
}),
};
let frame_reg = |r: &str| matches!(canonical_reg(r).as_str(), "rsp" | "rbp" | "sp" | "x29" | "x30");
match (i.kind, &i.flow) {
// Keep the exclusive monitor and unrepresented SIMD pair operands in assembly.
_ if exclusive_memory || (i.kind == Kind::StorePair && !matches!(i.ops.first(), Some(Op::Reg(_)))) => {
self.asm_fallbacks += 1;
stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
}
(_, Flow::Call { .. } | Flow::IndirectCall { .. }) => {
let name = self.call_name(i);
if self.calls.len() < 512 {
self.calls.insert(name.trim_start_matches("(*").trim_end_matches(')').to_string());
}
let args = if self.mode == Mode::X32 || self.mode == Mode::X16 {
let a = pushes.iter().rev().cloned().collect();
pushes.clear();
a
} else {
// Win64 calls into imports: contiguous stores at [rsp+0x20], [rsp+0x28], โฆ
// are arguments 5, 6, โฆ
let import: Option<&str> = match i.flow {
Flow::IndirectCall { slot: Some(s) } => self.prog.import_slots.get(&s).map(|si| si.name.as_str()),
Flow::Call { target } => self
.prog
.import_slots
.get(&target)
.map(|si| si.name.as_str())
.or_else(|| self.prog.functions.get(&target).and_then(|f| f.thunk_of.as_deref())),
_ => None,
};
let mut stack = Vec::new();
if self.win64 && import.is_some() {
let mut off = 0x20i64;
while let Some(arg) = stack_args.get(&off) {
match &arg.inline {
Some(def) => {
dead.insert(def.idx);
stack.push(def.expr.clone());
}
None => stack.push(arg.target.clone()),
}
off += 8;
}
}
// A known library function shows all its register arguments, even ones set
// outside this block (they read as the register itself).
let known = import.and_then(crate::arity::import_arity).unwrap_or(0);
let mut a = self.reg_args(&defs, &mut dead, if stack.is_empty() { known } else { known.max(4) });
a.extend(stack);
a
};
stack_args.clear();
written_slots.clear();
let uses_ret = insns
.get(k + 1..)
.unwrap_or(&[])
.iter()
.take(6)
.take_while(|n| !matches!(n.flow, Flow::Call { .. } | Flow::IndirectCall { .. }))
.find_map(|n| {
let r = n.reads.iter().any(|x| *x == self.ret_canon());
let w = n.writes.iter().any(|x| *x == self.ret_canon());
if r {
Some(true)
} else if w {
Some(false)
} else {
None
}
});
let call = format!("{name}({})", args.join(", "));
stmt = Some(if uses_ret == Some(true) { format!("{} = {call};", self.ret_reg_name()) } else { format!("{call};") });
// Calls clobber argument registers.
defs.clear();
read_after_set.clear();
consts.clear();
}
(_, Flow::Return) => {
stmt = Some(if self.ret_reg.is_empty() { "return;".into() } else { format!("return {};", self.ret_reg) });
}
(_, Flow::Jump { target }) if self.tail_calls.contains(target) => {
// A jump out of the function is a tail call: it returns what the callee returns.
let name = self.addr_name(*target).unwrap_or_else(|| format!("sub_{target:x}"));
if self.calls.len() < 512 {
self.calls.insert(name.clone());
}
let args = self.reg_args(&defs, &mut dead, 0);
stmt = Some(format!("return {name}({}); /* tail call */", args.join(", ")));
}
(_, Flow::Jump { .. } | Flow::Cond { .. } | Flow::Stop) => {
if let Flow::Cond { target } = i.flow {
cond = Some(self.condition(i.cond.as_ref(), flag_src));
taken = Some(target);
}
if matches!(i.flow, Flow::Stop) {
stmt = Some(if i.mnemonic.starts_with("int3") || i.mnemonic == "brk" {
"__debugbreak();".into()
} else {
"__halt(); /* stops here */".into()
});
}
}
(_, Flow::IndirectJump { slot }) => {
let import = slot.and_then(|s| self.prog.import_slots.get(&s)).map(|si| si.name.clone());
stmt = Some(match import {
// A jump through an import slot (an x86 `jmp [slot]` or ARM `ldr pc` GOT
// thunk) is a tail call: it passes the block's argument registers and is
// recorded like any other call.
Some(name) => {
if self.calls.len() < 512 {
self.calls.insert(name.clone());
}
let args = self.reg_args(&defs, &mut dead, crate::arity::import_arity(&name).unwrap_or(0));
format!("return {name}({}); /* tail call */", args.join(", "))
}
None => format!("goto *{}; /* computed jump */", d.clone().unwrap_or_default()),
});
}
(Kind::Nop | Kind::Leave, _) => {}
(Kind::Push, _) => {
let v = d.clone().unwrap_or_default();
if !(entry_or_exit && matches!(i.ops.first(), Some(Op::Reg(_)))) {
pushes.push(v);
}
}
(Kind::Pop, _) => {
if !entry_or_exit {
stmt = Some(format!("{} = pop();", d.clone().unwrap_or_default()));
}
}
(Kind::Cmp | Kind::Test, _) => flag_src = Some(i),
(Kind::Mov | Kind::MovSx | Kind::MovZx, _) if i.ops.len() >= 2 => {
let (dd, ss) = (d.clone().unwrap_or_default(), s.clone().unwrap_or_default());
let zero_dst = self.mode == Mode::A64 && is_zero_reg(i.ops.first());
if (frame_reg(&dd) && dest_reg.is_some()) || dd == ss || zero_dst {
// frame setup (mov rbp, rsp / mov x29, sp) or discarded write to wzr/xzr
} else {
stmt = Some(format!("{dd} = {ss};"));
}
// A register set to a plain immediate holds a constant a MOVK can fold with
// (a W register's constant lives in the low 32 bits).
if !zero_dst && let (Some(Op::Reg(r)), Some(Op::Imm(v))) = (i.ops.first(), i.ops.get(1)) {
let value = if r.starts_with('w') { u64::from(*v as u32) } else { *v as u64 };
const_def = Some((canonical_reg(r), value));
}
}
(Kind::Insert, _) => match (i.ops.get(1), i.ops.get(2)) {
(Some(Op::Imm(v)), Some(Op::Imm(keep))) => {
let dd = d.clone().unwrap_or_default();
// A MOVZ (or an earlier folded MOVK) beside this MOVK is one constant:
// fold the pair into a single assignment.
if let (Some((idx, base)), Some(dr)) = (insert_src, dest_reg.as_ref())
&& !dead.contains(&idx)
{
let combined = (base & (*keep as u64)) | (*v as u64);
dead.insert(idx);
stmt = Some(format!("{dd} = {};", imm(combined as i64)));
const_def = Some((dr.clone(), combined));
} else {
stmt = Some(format!("{dd} = ({dd} & {:#x}) | {:#x};", *keep as u64, *v as u64));
}
}
_ => {
self.asm_fallbacks += 1;
stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
}
},
(Kind::Lea, _) => {
let e = match i.ops.get(1) {
Some(Op::Mem(m)) => match m.addr {
Some(a) => self.address_of(a),
None => {
let frame = matches!(m.base.as_deref(), Some("rbp" | "ebp" | "rsp" | "esp" | "x29" | "sp")) && m.index.is_none();
if frame { format!("&{}", self.mem(m)) } else { self.mem_addr(m) }
}
},
_ => s.clone().unwrap_or_default(),
};
stmt = Some(format!("{} = {e};", d.clone().unwrap_or_default()));
}
(Kind::Adrp | Kind::Adr, _) => {
let e = match i.ops.get(1) {
Some(Op::Addr(a)) if i.kind == Kind::Adr => self.address_of(*a),
Some(Op::Addr(a)) => format!("{a:#x} /* page */"),
_ => s.clone().unwrap_or_default(),
};
stmt = Some(format!("{} = {e};", d.clone().unwrap_or_default()));
}
(Kind::Add | Kind::Sub | Kind::And | Kind::Or | Kind::Xor | Kind::Shl | Kind::Shr | Kind::Sar | Kind::Mul, _) => {
let sym = match i.kind {
Kind::Add => "+",
Kind::Sub => "-",
Kind::And => "&",
Kind::Or => "|",
Kind::Xor => "^",
Kind::Shl => "<<",
Kind::Shr | Kind::Sar => ">>",
_ => "*",
};
let dd = d.clone().unwrap_or_default();
if i.sets_flags {
flag_src = Some(i);
}
if dest_reg.as_deref().is_some_and(frame_reg) && matches!(i.kind, Kind::Add | Kind::Sub) {
// stack frame adjustment
} else if self.mode == Mode::A64 && is_zero_reg(i.ops.first()) {
// discarded write to wzr/xzr (e.g. `cmn` = `adds xzr, โฆ`); flags are kept above
} else if i.kind == Kind::Xor && i.ops.len() == 2 && i.ops.first() == i.ops.get(1) {
stmt = Some(format!("{dd} = 0;"));
} else if self.mode == Mode::A64 && i.kind == Kind::Add && i.refs.first().is_some_and(|r| self.prog.string_at(*r).is_some()) {
let r = i.refs.first().copied().unwrap_or(0);
let lit = self.address_of(r);
stmt = Some(format!("{dd} = {lit};"));
} else if let Some(t) = t.clone() {
let ss = s.clone().unwrap_or_default();
stmt = Some(if ss == dd { format!("{dd} {sym}= {t};") } else { format!("{dd} = {ss} {sym} {t};") });
} else if let Some(ss) = s.clone() {
stmt = Some(format!("{dd} {sym}= {ss};"));
} else {
stmt = Some(format!("{dd} = {dd} {sym} ...; /* {} */", i.text()));
}
if self.mode.is_x86() && i.ops.len() == 1 && i.kind == Kind::Mul {
stmt = Some(format!("rdx:rax = rax * {dd};"));
}
}
(Kind::Inc, _) => {
flag_src = Some(i);
stmt = Some(format!("{}++;", d.clone().unwrap_or_default()));
}
(Kind::Dec, _) => {
flag_src = Some(i);
stmt = Some(format!("{}--;", d.clone().unwrap_or_default()));
}
(Kind::Not, _) => stmt = Some(format!("{0} = ~{0};", d.clone().unwrap_or_default())),
(Kind::Neg, _) => stmt = Some(format!("{0} = -{0};", d.clone().unwrap_or_default())),
(Kind::Load, _) if i.ops.len() >= 2 => {
let e = match i.refs.first() {
Some(&r) => self.addr_name(r).unwrap_or_else(|| scalar_deref(self.mode, i, &format!("{r:#x}"))),
None if self.mode == Mode::A64
&& scalar_load(i).0 < reg_width(i.ops.first())
&& let Some(Op::Mem(m)) = i.ops.get(1) =>
{
scalar_deref(self.mode, i, &format!("({})", self.mem_addr(m)))
}
None => s.clone().unwrap_or_default(),
};
let e = if e.starts_with("&") && i.refs.is_empty() { e.trim_start_matches('&').to_string() } else { e };
stmt = Some(format!("{} = {};", d.clone().unwrap_or_default(), e.trim_start_matches("&")));
}
(Kind::Store, _) if i.ops.len() >= 2 => {
let target = match i.refs.first() {
Some(&r) => self.addr_name(r).unwrap_or_else(|| format!("*(uint64_t*){r:#x}")),
None => s.clone().unwrap_or_default(),
};
stmt = Some(format!("{} = {};", target.trim_start_matches('&'), d.clone().unwrap_or_default()));
}
(Kind::LoadPair | Kind::StorePair, _) => {
let all_frame = i.ops.iter().take(2).all(|o| matches!(o, Op::Reg(r) if frame_reg(r)));
let stack_pair = matches!(i.ops.get(2), Some(Op::Mem(m)) if m.base.as_deref() == Some("sp") && m.index.is_none());
let frame_save = i.kind == Kind::StorePair
&& i.mnemonic == "stp"
&& matches!(i.ops.as_slice(), [Op::Reg(fp), Op::Reg(lr), _] if fp == "x29" && lr == "x30")
&& matches!(i.ops.get(2), Some(Op::Mem(m)) if m.disp < 0)
&& i.writes.iter().any(|r| r == "sp");
if !(entry_or_exit && all_frame && stack_pair && frame.stack && (i.kind == Kind::LoadPair || frame_save)) {
let (a, b) = (d.clone().unwrap_or_default(), s.clone().unwrap_or_default());
if i.kind == Kind::LoadPair {
let m = t.clone().unwrap_or_default();
stmt = Some(format!("{a} = {m}[0]; {b} = {m}[1];"));
} else if let Some(Op::Mem(m)) = i.ops.get(2) {
if m.base.as_ref().is_some_and(|base| i.writes.contains(base)) {
self.asm_fallbacks += 1;
stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
} else {
let elem = ty(reg_width(i.ops.first()));
let base = m.addr.map(|addr| format!("{addr:#x}")).unwrap_or_else(|| self.mem_addr(m));
let ptr = format!("(({elem}*)({base}))");
stmt = Some(format!("{ptr}[0] = {a}; {ptr}[1] = {b};"));
}
}
}
}
_ => {
if i.sets_flags {
flag_src = Some(i);
}
self.asm_fallbacks += 1;
stmt = Some(format!("__asm(\"{}\");", escape(&i.text())));
}
}
// Writing a register invalidates earlier pending expressions that read it (before
// recording this instruction's own new pending expression). For calls, arguments were
// already consumed above so post-call register clobbers still invalidate surviving slots.
invalidate_dependents(&mut defs, &i.writes);
invalidate_dependents(&mut stack_args, &i.writes);
if let Some(st) = stmt {
stmts.push(st);
if self.win64
&& matches!(i.kind, Kind::Mov | Kind::Store)
&& let Some(Op::Mem(m)) = i.ops.first()
&& m.base.as_deref() == Some("rsp")
&& m.index.is_none()
&& m.seg.is_none()
&& m.disp >= 0x20
&& m.disp % 8 == 0
&& let Some((lhs, rhs)) = stmts.last().and_then(|l| l.split_once(" = "))
{
let target = lhs.trim().to_string();
let v = rhs.trim_end_matches(';').to_string();
let inline = (m.size == 8 || (m.size > 0 && m.size < 8 && !prior_slot_write)).then(|| InlineExpr {
idx: stmts.len() - 1,
expr: v,
deps: i.reads.clone(),
mem: None,
});
stack_args.insert(m.disp, PendingAssign { target, inline });
}
if let Some(r) = &dest_reg {
let expr = stmts.last().and_then(|l| l.split_once(" = ").map(|(_, e)| e.trim_end_matches(';').to_string()));
match expr {
Some(e) if !e.contains(';') && !matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) => {
let deps = if const_def.is_some() { Vec::new() } else { i.reads.clone() };
defs.insert(
r.clone(),
PendingAssign { target: r.clone(), inline: Some(InlineExpr { idx: stmts.len() - 1, expr: e, deps, mem: read_mem.clone() }) },
);
}
_ => {
defs.remove(r);
}
}
match const_def {
Some((cr, v)) if cr == *r => {
consts.insert(r.clone(), (stmts.len() - 1, v));
}
_ => {
consts.remove(r);
}
}
}
for w in &i.writes {
if dest_reg.as_ref() != Some(w) {
defs.remove(w);
consts.remove(w);
}
}
} else {
for w in &i.writes {
defs.remove(w);
consts.remove(w);
}
}
// Moving the stack pointer shifts every slot: forget the pending stack arguments.
if i.writes.iter().any(|w| w == "rsp") {
stack_args.clear();
written_slots.clear();
}
}
let stmts = stmts.into_iter().enumerate().filter(|(i, _)| !dead.contains(i)).map(|(_, s)| s).collect();
BlockCode { stmts, cond, taken }
}
fn ret_canon(&self) -> String {
match self.mode {
Mode::A64 => "x0".into(),
Mode::A32 | Mode::T32 => "r0".into(),
_ => "rax".into(),
}
}
fn ret_reg_name(&self) -> String {
if self.ret_reg.is_empty() { self.ret_canon() } else { self.ret_reg.clone() }
}
fn condition(&mut self, c: Option<&Cond>, src: Option<&Insn>) -> String {
let Some(c) = c else { return "/* condition */ flags".into() };
match c {
Cond::RegZero(r) => return format!("{r} == 0"),
Cond::RegNonZero(r) => return format!("{r} != 0"),
Cond::BitClear(r, b) => return format!("(({r} >> {b}) & 1) == 0"),
Cond::BitSet(r, b) => return format!("(({r} >> {b}) & 1) != 0"),
_ => {}
}
let opstr = match c {
Cond::Sign => Some("<"),
Cond::NotSign => Some(">="),
other => other.op(),
};
let Some(src) = src else { return format!("/* {c:?} */ flags") };
let zero_dst = self.mode == Mode::A64 && is_zero_reg(src.ops.first());
let a = src.ops.first().map(|o| self.op(o)).unwrap_or_default();
// ARM compare/test/cmn aliases encode the zero register first.
let (a, b) = if self.mode == Mode::A64 && (matches!(src.kind, Kind::Cmp | Kind::Test) || (src.kind == Kind::Add && zero_dst)) {
(src.ops.get(1).map(|o| self.op(o)).unwrap_or_default(), src.ops.get(2).map(|o| self.op(o)).unwrap_or_default())
} else {
(a, src.ops.get(1).map(|o| self.op(o)).unwrap_or_default())
};
let Some(op) = opstr else { return format!("/* {c:?} after {} */ flags", src.mnemonic) };
let unsigned = if c.unsigned() { " /* unsigned */" } else { "" };
match src.kind {
Kind::Cmp => {
if matches!(c, Cond::Sign | Cond::NotSign) {
format!("{a} - {b} {op} 0")
} else {
format!("{a} {op} {b}{unsigned}")
}
}
Kind::Test => {
if a == b || b.is_empty() {
format!("{a} {op} 0{unsigned}")
} else {
format!("({a} & {b}) {op} 0")
}
}
Kind::Add if zero_dst => format!("({a} + {b}) {op} 0{unsigned}"),
_ => format!("{a} {op} 0{unsigned}"),
}
}
}
fn cond_negate_text(c: &str) -> String {
for (a, b) in [(" == ", " != "), (" != ", " == "), (" <= ", " > "), (" >= ", " < "), (" < ", " >= "), (" > ", " <= ")] {
if let Some((l, r)) = c.split_once(a)
&& !r.contains(" == ")
&& !r.contains(" != ")
&& !l.contains(" == ")
{
return format!("{l}{b}{r}");
}
}
format!("!({c})")
}
/// Bitset-backed dominator sets.
fn dominators(n: usize, entry: usize, preds: &[Vec<usize>]) -> Vec<Vec<u64>> {
let words = n.div_ceil(64);
let full = vec![u64::MAX; words];
let mut dom: Vec<Vec<u64>> = vec![full; n];
if let Some(d) = dom.get_mut(entry) {
*d = vec![0; words];
set(d, entry);
}
let mut changed = true;
let mut rounds = 0;
while changed && rounds < 200 {
changed = false;
rounds += 1;
for b in 0..n {
if b == entry {
continue;
}
let mut new = vec![u64::MAX; words];
let mut any = false;
for &p in preds.get(b).map(Vec::as_slice).unwrap_or(&[]) {
if let Some(pd) = dom.get(p) {
any = true;
for (x, y) in new.iter_mut().zip(pd) {
*x &= *y;
}
}
}
if !any {
new = vec![0; words];
}
set(&mut new, b);
if dom.get(b) != Some(&new) {
if let Some(d) = dom.get_mut(b) {
*d = new;
}
changed = true;
}
}
}
dom
}
fn set(v: &mut [u64], i: usize) {
if let Some(w) = v.get_mut(i / 64) {
*w |= 1 << (i % 64);
}
}
fn has(v: &[u64], i: usize) -> bool {
v.get(i / 64).is_some_and(|w| w & (1 << (i % 64)) != 0)
}
fn count(v: &[u64]) -> u32 {
v.iter().map(|w| w.count_ones()).sum()
}
/// Immediate (post-)dominator: the strict dominator with the largest dominator set.
fn immediate(sets: &[Vec<u64>], n: usize, b: usize) -> Option<usize> {
let s = sets.get(b)?;
if count(s) as usize >= n && n > 1 {
return None; // unreachable / never reaches exit: set stayed full
}
(0..n).filter(|&d| d != b && has(s, d)).max_by_key(|&d| sets.get(d).map(|x| count(x)).unwrap_or(0))
}
struct Graph {
starts: Vec<u64>,
succs: Vec<Vec<usize>>,
idom: Vec<Option<usize>>,
ipdom: Vec<Option<usize>>,
dom: Vec<Vec<u64>>,
/// header โ (loop body, follow)
loops: BTreeMap<usize, (BTreeSet<usize>, Option<usize>)>,
}
fn build_graph(f: &Function) -> Graph {
let n = f.blocks.len();
let starts: Vec<u64> = f.blocks.iter().map(|b| b.start).collect();
let index: BTreeMap<u64, usize> = starts.iter().enumerate().map(|(i, s)| (*s, i)).collect();
let succs: Vec<Vec<usize>> = f.blocks.iter().map(|b| b.succs.iter().filter_map(|s| index.get(s).copied()).collect()).collect();
let mut preds = vec![Vec::new(); n];
for (i, ss) in succs.iter().enumerate() {
for &s in ss {
if let Some(p) = preds.get_mut(s) {
p.push(i);
}
}
}
let entry = index.get(&f.entry).copied().unwrap_or(0);
let dom = dominators(n, entry, &preds);
// Post-dominators: reverse graph with a virtual exit (index n).
let mut rpreds: Vec<Vec<usize>> = succs.clone();
for (i, ss) in succs.iter().enumerate() {
if ss.is_empty()
&& let Some(r) = rpreds.get_mut(i)
{
r.push(n);
}
}
rpreds.push(Vec::new());
let pdom = dominators(n + 1, n, &rpreds);
let idom = (0..n).map(|b| immediate(&dom, n, b)).collect();
let ipdom = (0..n).map(|b| immediate(&pdom, n + 1, b).filter(|&d| d < n)).collect();
// Natural loops from back edges u โ h where h dominates u.
let mut loops: BTreeMap<usize, (BTreeSet<usize>, Option<usize>)> = BTreeMap::new();
for (u, ss) in succs.iter().enumerate() {
for &h in ss {
if dom.get(u).is_some_and(|d| has(d, h)) {
let body = &mut loops.entry(h).or_insert_with(|| (BTreeSet::from([h]), None)).0;
let mut stack = vec![u];
while let Some(x) = stack.pop() {
if body.insert(x) {
for &p in preds.get(x).map(Vec::as_slice).unwrap_or(&[]) {
stack.push(p);
}
}
}
}
}
}
let ipd: Vec<Option<usize>> = (0..n).map(|b| immediate(&pdom, n + 1, b).filter(|&d| d < n)).collect();
for (h, (body, follow)) in loops.iter_mut() {
let exits: BTreeSet<usize> = body.iter().flat_map(|&b| succs.get(b).cloned().unwrap_or_default()).filter(|s| !body.contains(s)).collect();
*follow = ipd
.get(*h)
.copied()
.flatten()
.filter(|p| !body.contains(p))
.or_else(|| exits.iter().min_by_key(|&&e| starts.get(e).copied().unwrap_or(0)).copied());
}
Graph { starts, succs, idom, ipdom, dom, loops }
}
enum Edge {
Continue,
Break,
To(usize),
}
struct Emitter<'a> {
g: &'a Graph,
code: &'a [BlockCode],
emitted: Vec<bool>,
lines: Vec<Line>,
labels: BTreeSet<u64>,
gotos: usize,
loop_stack: Vec<(usize, Option<usize>)>,
pending_label: Option<u64>,
}
impl Emitter<'_> {
fn push(&mut self, indent: usize, text: impl Into<String>) {
let label = self.pending_label.take();
self.lines.push(Line { indent, text: text.into(), label, loop_end: false });
}
fn edge(&self, to: usize) -> Edge {
if let Some(&(h, follow)) = self.loop_stack.last() {
if to == h {
return Edge::Continue;
}
if Some(to) == follow {
return Edge::Break;
}
}
Edge::To(to)
}
fn goto(&mut self, indent: usize, b: usize) {
let s = self.g.starts.get(b).copied().unwrap_or(0);
self.labels.insert(s);
self.gotos += 1;
self.push(indent, format!("goto label_{s:x};"));
}
fn in_current_loop(&self, b: usize) -> bool {
match self.loop_stack.last() {
Some((h, _)) => self.g.loops.get(h).is_some_and(|(body, _)| body.contains(&b)),
None => true,
}
}
/// Emit from block `b` until `stop`.
fn region(&mut self, mut b: Option<usize>, stop: Option<usize>, indent: usize, depth: usize) {
while let Some(cur) = b {
if Some(cur) == stop {
return;
}
if depth > MAX_DEPTH || indent > MAX_DEPTH {
self.goto(indent, cur);
return;
}
if !self.in_current_loop(cur) {
// Leaving the loop other than through its follow.
self.goto(indent, cur);
return;
}
if self.emitted.get(cur).copied().unwrap_or(true) {
let tiny_exit = self.g.succs.get(cur).is_some_and(|s| s.is_empty()) && self.code.get(cur).is_some_and(|c| c.stmts.len() <= 4);
if tiny_exit {
for st in self.code.get(cur).map(|c| c.stmts.clone()).unwrap_or_default() {
self.push(indent, st);
}
} else {
self.goto(indent, cur);
}
return;
}
let is_header = self.g.loops.contains_key(&cur) && self.loop_stack.last().map(|(h, _)| *h) != Some(cur);
if is_header {
let follow = self.g.loops.get(&cur).and_then(|(_, f)| *f);
self.push(indent, "while (true) {");
self.loop_stack.push((cur, follow));
self.body(cur, indent + 1, depth + 1);
self.loop_stack.pop();
// drop a trailing continue
if self.lines.last().is_some_and(|l| l.text == "continue;" && l.indent == indent + 1) {
self.lines.pop();
}
self.lines.push(Line { indent, text: "}".into(), label: None, loop_end: true });
b = follow;
continue;
}
b = self.body(cur, indent, depth);
}
}
/// Emit one block and its branch; returns where straight-line emission continues.
fn body(&mut self, cur: usize, indent: usize, depth: usize) -> Option<usize> {
if let Some(e) = self.emitted.get_mut(cur) {
*e = true;
}
let start = self.g.starts.get(cur).copied().unwrap_or(0);
let first_line = self.lines.len();
let (stmts, cond, taken) = match self.code.get(cur) {
Some(c) => (c.stmts.clone(), c.cond.clone(), c.taken),
None => (Vec::new(), None, None),
};
for s in stmts {
self.push(indent, s);
}
if let Some(l) = self.lines.get_mut(first_line) {
l.label = Some(start);
} else {
self.pending_label = Some(start);
}
let succs = self.g.succs.get(cur).cloned().unwrap_or_default();
match succs.as_slice() {
[] => None,
[s] => match self.edge(*s) {
Edge::Continue => {
self.push(indent, "continue;");
None
}
Edge::Break => {
self.push(indent, "break;");
None
}
Edge::To(t) => Some(t),
},
_ => {
let taken_idx = taken.and_then(|t| self.g.starts.iter().position(|s| *s == t));
let Some(t) = taken_idx.filter(|t| succs.contains(t)) else {
// switch / multiway: one case per target
let selector = match self.lines.last() {
Some(l) if l.text.starts_with("goto *") && l.label.is_none() => {
let sel = l.text.trim_start_matches("goto *").split(';').next().unwrap_or("").to_string();
self.lines.pop();
sel
}
_ => "/* computed */".to_string(),
};
self.push(indent, format!("switch ({selector}) {{"));
for s in succs {
let st = self.g.starts.get(s).copied().unwrap_or(0);
self.push(indent + 1, format!("case_{st:x}:"));
match self.edge(s) {
Edge::Continue => self.push(indent + 2, "continue;"),
Edge::Break => self.push(indent + 2, "break;"),
Edge::To(x) => {
if self.emitted.get(x).copied().unwrap_or(true) {
self.goto(indent + 2, x);
} else {
let join = self.g.ipdom.get(cur).copied().flatten();
self.region(Some(x), join, indent + 2, depth + 1);
if !self.lines.last().is_some_and(|l| l.text.starts_with("return") || l.text.starts_with("goto ")) {
self.push(indent + 2, "break;");
}
}
}
}
}
self.push(indent, "}");
return self.g.ipdom.get(cur).copied().flatten().filter(|j| !self.emitted.get(*j).copied().unwrap_or(true));
};
let f = succs.iter().copied().find(|s| *s != t).unwrap_or(t);
let cond = cond.unwrap_or_else(|| "/* condition */ flags".into());
let join =
self.g.ipdom.get(cur).copied().flatten().filter(|j| self.in_current_loop(*j) || self.loop_stack.last().and_then(|(_, f)| *f) == Some(*j));
let arm = |me: &mut Self, x: usize, ind: usize| -> bool {
// returns true when something was emitted
match me.edge(x) {
Edge::Continue => {
me.push(ind, "continue;");
true
}
Edge::Break => {
me.push(ind, "break;");
true
}
Edge::To(y) => {
if Some(y) == join {
false
} else {
let before = me.lines.len();
me.region(Some(y), join, ind, depth + 1);
me.lines.len() > before
}
}
}
};
let jumpy = |e: &Edge| matches!(e, Edge::Continue | Edge::Break);
let (et, ef) = (self.edge(t), self.edge(f));
if jumpy(&et) && jumpy(&ef) {
let word = |e: &Edge| if matches!(e, Edge::Break) { "break;" } else { "continue;" };
if matches!(et, Edge::Break) {
self.push(indent, format!("if ({cond}) {}", word(&et)));
self.push(indent, word(&ef));
} else {
self.push(indent, format!("if ({}) {}", cond_negate_text(&cond), word(&ef)));
self.push(indent, word(&et));
}
return None;
}
let t_empty = matches!(self.edge(t), Edge::To(y) if Some(y) == join);
let f_empty = matches!(self.edge(f), Edge::To(y) if Some(y) == join);
if t_empty && f_empty {
// both go to the join: nothing to branch on
} else if t_empty {
self.push(indent, format!("if ({}) {{", cond_negate_text(&cond)));
arm(self, f, indent + 1);
self.push(indent, "}");
} else if f_empty {
self.push(indent, format!("if ({cond}) {{"));
arm(self, t, indent + 1);
self.push(indent, "}");
} else {
self.push(indent, format!("if ({cond}) {{"));
arm(self, t, indent + 1);
self.push(indent, "} else {");
arm(self, f, indent + 1);
self.push(indent, "}");
}
match join {
Some(j) => match self.edge(j) {
Edge::Continue => None,
Edge::Break => {
self.push(indent, "break;");
None
}
Edge::To(j) => Some(j),
},
None => None,
}
}
}
}
}
fn simplify(lines: &mut Vec<Line>) {
// `} else {` directly followed by `}` โ `}`; `if (c) {` directly followed by `}` โ nothing.
let mut changed = true;
while changed {
changed = false;
let mut i = 0;
while i + 1 < lines.len() {
let (Some(a), Some(b)) = (lines.get(i), lines.get(i + 1)) else { break };
if b.text == "}" && a.indent == b.indent && a.label.is_none() && b.label.is_none() && !b.loop_end {
if a.text == "} else {" {
lines.remove(i);
changed = true;
continue;
}
if a.text.starts_with("if (") && a.text.ends_with(") {") {
lines.drain(i..i + 2);
changed = true;
continue;
}
}
i += 1;
}
}
// `if (c) { break; }` โ `if (c) break;`
let mut out: Vec<Line> = Vec::with_capacity(lines.len());
let mut i = 0;
while i < lines.len() {
if let (Some(a), Some(b), Some(c)) = (lines.get(i), lines.get(i + 1), lines.get(i + 2))
&& a.text.starts_with("if (")
&& a.text.ends_with(") {")
&& matches!(b.text.as_str(), "break;" | "continue;" | "return;")
&& c.text == "}"
&& c.indent == a.indent
&& b.label.is_none()
{
let head = a.text.trim_end_matches(" {");
out.push(Line { indent: a.indent, text: format!("{head} {}", b.text), label: a.label, loop_end: false });
i += 3;
continue;
}
if let Some(l) = lines.get(i) {
out.push(l.clone());
}
i += 1;
}
*lines = out;
}
/// Lift `f` to pseudo-C. `names` resolves user-given names (annotations) first.
pub fn lift(img: &Image, prog: &Program, f: &Function, names: &dyn Fn(u64) -> Option<String>) -> Pseudo {
let mode = prog.mode;
let arg_regs: &'static [&'static str] = match mode {
Mode::X64 if img.bin.format == Format::Pe => &["rcx", "rdx", "r8", "r9"],
Mode::X64 => &["rdi", "rsi", "rdx", "rcx", "r8", "r9"],
Mode::A64 => &["x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7"],
Mode::A32 | Mode::T32 => &["r0", "r1", "r2", "r3"],
_ => &[],
};
let mut limitations: Vec<(String, String)> = vec![
("register_level".into(), "variables are machine registers and stack slots; types are not recovered".into()),
("calling_convention_assumed".into(), format!("call arguments follow the usual {} convention and may be wrong for unusual functions", mode.name())),
("conditions_from_flags".into(), "branch conditions are rebuilt from the last compare and may be approximate".into()),
];
// Decode every block.
let mut per_block: Vec<Vec<Insn>> = Vec::new();
for b in &f.blocks {
let mut v = Vec::new();
let mut consts = ArmConsts::default();
let mut a = b.start;
while a < b.end && v.len() < 20_000 {
let Some(mut i) = img.decode(a, true) else { break };
if mode == Mode::A64 {
consts.apply(&mut i);
}
a = i.end();
v.push(i);
}
per_block.push(v);
}
// Return register: the widest name written to the return register anywhere.
let ret_canon = if mode == Mode::A64 {
"x0"
} else if matches!(mode, Mode::A32 | Mode::T32) {
"r0"
} else {
"rax"
};
let mut ret_reg = String::new();
'outer: for v in per_block.iter().rev() {
for i in v.iter().rev() {
if matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) {
ret_reg = ret_canon.into();
break 'outer;
}
if i.writes.iter().any(|w| w == ret_canon)
&& let Some(Op::Reg(r)) = i.ops.first()
{
ret_reg = r.clone();
break 'outer;
}
}
}
// Parameters: argument registers read before written in the entry block.
let mut params = Vec::new();
if let Some(entry_block) = f.blocks.iter().position(|b| b.start == f.entry).and_then(|i| per_block.get(i)) {
let mut written: BTreeSet<String> = BTreeSet::new();
for i in entry_block {
if matches!(i.flow, Flow::Call { .. } | Flow::IndirectCall { .. }) {
break;
}
for r in &i.reads {
if arg_regs.contains(&r.as_str()) && !written.contains(r) && !params.contains(r) {
params.push(r.clone());
}
}
written.extend(i.writes.iter().cloned());
}
}
params.sort_by_key(|p| arg_regs.iter().position(|r| r == p).unwrap_or(99));
let name = names(f.entry).unwrap_or_else(|| f.name.clone());
let ret_ty = if ret_reg.is_empty() {
"void"
} else if ret_reg.starts_with('e') || ret_reg.starts_with('w') {
"int32_t"
} else {
"int64_t"
};
let signature = format!("{ret_ty} {name}({})", params.iter().map(|p| format!("int64_t {p}")).collect::<Vec<_>>().join(", "));
let win64 = mode == Mode::X64 && img.bin.format == Format::Pe;
let mut lifter =
Lifter { img, prog, names, mode, arg_regs, win64, tail_calls: &f.tail_calls, ret_reg, calls: BTreeSet::new(), strings: Vec::new(), asm_fallbacks: 0 };
let n = f.blocks.len();
let stack_is_frame = match mode {
Mode::A64 => !per_block.iter().flatten().any(replaces_a64_stack),
Mode::X64 => !per_block.iter().flatten().any(replaces_x86_stack),
_ => true,
};
let codes: Vec<BlockCode> = per_block
.iter()
.zip(&f.blocks)
.map(|(v, b)| {
let edge = b.start == f.entry || b.succs.is_empty();
lifter.block(v, edge, stack_is_frame)
})
.collect();
let structured_ok = n <= MAX_STRUCTURED_BLOCKS;
let graph = if structured_ok {
build_graph(f)
} else {
Graph { starts: f.blocks.iter().map(|b| b.start).collect(), succs: vec![], idom: vec![], ipdom: vec![], dom: vec![], loops: BTreeMap::new() }
};
let mut emitter = Emitter {
g: &graph,
code: &codes,
emitted: vec![false; n],
lines: Vec::new(),
labels: BTreeSet::new(),
gotos: 0,
loop_stack: Vec::new(),
pending_label: None,
};
if structured_ok {
let entry = graph.starts.iter().position(|s| *s == f.entry).unwrap_or(0);
emitter.region(Some(entry), None, 1, 0);
// Anything unreachable from the entry (e.g. only via unresolved jumps) goes after.
for i in 0..n {
if !emitter.emitted.get(i).copied().unwrap_or(true) {
emitter.region(Some(i), None, 1, 0);
}
}
} else {
limitations.push(("not_structured".into(), format!("{n} blocks is above the structuring limit; shown as labelled blocks with gotos")));
for (i, b) in f.blocks.iter().enumerate() {
let first = emitter.lines.len();
for s in codes.get(i).map(|c| c.stmts.clone()).unwrap_or_default() {
emitter.push(1, s);
}
if let Some(c) = codes.get(i)
&& let (Some(cond), Some(t)) = (&c.cond, c.taken)
{
emitter.labels.insert(t);
emitter.gotos += 1;
emitter.push(1, format!("if ({cond}) goto label_{t:x};"));
}
if emitter.lines.len() == first {
emitter.push(1, ";");
}
if let Some(l) = emitter.lines.get_mut(first) {
l.label = Some(b.start);
}
emitter.labels.insert(b.start);
}
}
let _ = (&graph.idom, &graph.dom);
if emitter.pending_label.is_some() {
emitter.push(1, ";");
}
let mut lines = std::mem::take(&mut emitter.lines);
simplify(&mut lines);
let mut text = format!("{signature}\n{{\n");
for l in &lines {
if let Some(lab) = l.label
&& emitter.labels.contains(&lab)
{
text.push_str(&format!("label_{lab:x}:\n"));
}
let _ = l.loop_end;
text.push_str(&" ".repeat(l.indent));
text.push_str(&l.text);
text.push('\n');
}
text.push_str("}\n");
if emitter.gotos > 0 {
limitations.push(("unstructured_flow".into(), format!("{} gotos remain where the control flow isn't a simple if/loop", emitter.gotos)));
}
if lifter.asm_fallbacks > 0 {
limitations.push(("inline_asm".into(), format!("{} instructions have no C rule and are shown as __asm(...)", lifter.asm_fallbacks)));
}
if f.unresolved_indirect_jumps > 0 {
limitations.push(("indirect_jumps_unresolved".into(), "some indirect jumps were not resolved, so code may be missing".into()));
}
if f.truncated {
limitations.push(("function_truncated".into(), "the function hit the instruction limit; the end is missing".into()));
}
Pseudo {
signature,
text,
calls: lifter.calls.into_iter().collect(),
strings: lifter.strings,
gotos: emitter.gotos,
asm_fallbacks: lifter.asm_fallbacks,
structured: structured_ok && emitter.gotos == 0,
limitations,
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::NoControl;
use crate::program::Limits;
use craft_anything_testkit as tk;
use std::sync::Arc;
/// The eight-byte slots straddling the write are the only ones that lose their values.
#[test]
fn fixed_stack_writes_invalidate_only_intersecting_slots() {
let mut slots = (0..10_000)
.map(|offset| {
let expr = InlineExpr { idx: 0, expr: String::new(), deps: Vec::new(), mem: None };
(offset, PendingAssign { target: String::new(), inline: Some(expr) })
})
.collect::<BTreeMap<_, _>>();
let write = MemOp { base: Some("rsp".into()), index: None, index_shift: None, scale: 1, disp: 32, size: 4, addr: None, seg: None };
invalidate_stack_slots(&mut slots, Some(&write), FrameBases { stack: true, pointer: None });
let invalid: Vec<_> = slots.iter().filter(|(_, assign)| assign.inline.is_none()).map(|(&off, _)| off).collect();
assert_eq!(invalid, (25..=35).collect::<Vec<_>>());
}
fn setup(bytes: Vec<u8>) -> (Image, Program) {
let img = Image::parse(Arc::from(bytes)).unwrap();
let p = Program::analyze(&img, &Limits::default(), &NoControl).unwrap();
(img, p)
}
#[test]
fn calls_into_known_imports_show_their_arguments() {
// pe64 reuses the System V code, so nothing loads rcx before `puts`: Win64's first argument
// register. The call still has its one argument, shown as the register.
let (img, p) = setup(tk::pe64());
let none = |_: u64| None;
let entry = img.bin.entry.unwrap();
let f = p.functions.get(&entry).unwrap();
let text = lift(&img, &p, f, &none).text;
assert!(text.contains("puts(rcx)"), "{text}");
assert!(!text.contains("puts()"), "{text}");
}
/// `sub w9, w9, w9, lsl #3` came out as `w9 -= w9;`: the shift of a register operand was dropped.
#[test]
fn aarch64_shifted_operands_keep_their_shift() {
// add w9, w10, w9, lsr #31; sub w9, w9, w9, lsl #3; add x0, x1, x2, asr #4;
// add x3, x1, w2, sxtw #2; add x4, x1, w2, uxtw; orr x5, x1, x2, ror #8; ret
let words = [0x0b49_7d49u32, 0x4b09_0d29, 0x8b82_1020, 0x8b22_c823, 0x8b22_4024, 0xaac2_2025, 0xd65f_03c0];
let bytes: Vec<u8> = words.iter().flat_map(|w| w.to_le_bytes()).collect();
let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
let p = lift(&image, &program, program.functions.get(&0x1000).unwrap(), &|_| None);
for want in [
"w9 = w10 + ((uint32_t)w9 >> 31);",
"w9 -= (w9 << 3);",
"x0 = x1 + ((int64_t)x2 >> 4);",
"x3 = x1 + ((int64_t)(int32_t)w2 << 2);",
"x4 = x1 + (uint32_t)w2;",
"x5 = x1 | ((uint64_t)x2 >> 8 | (uint64_t)x2 << 56);",
] {
assert!(p.text.contains(want), "{want}\n{}", p.text);
}
assert!(!p.text.contains("w9 -= w9;"), "{}", p.text);
}
#[test]
fn main_and_helper_read_like_c() {
let (elf, _) = tk::elf64(tk::ElfArch::X86_64, true);
let (img, p) = setup(elf);
let none = |_: u64| None;
let main = lift(&img, &p, p.function_by_name("main").unwrap(), &none);
assert!(main.text.contains("puts(\"Hello, Craft!\")"), "{}", main.text);
assert!(main.text.contains("helper(5)"), "{}", main.text);
assert!(main.calls.contains(&"dispatch".to_string()));
assert_eq!(main.strings, vec![tk::HELLO.to_string()]);
let helper = lift(&img, &p, p.function_by_name("helper").unwrap(), &none);
assert!(helper.text.contains("while (true)"), "{}", helper.text);
assert!(helper.text.contains("if (edi"), "{}", helper.text);
assert!(helper.signature.contains("edi") || helper.signature.contains("rdi"), "{}", helper.signature);
assert!(helper.structured, "{}", helper.text);
let renamed = |a: u64| (a == p.function_by_name("helper").unwrap().entry).then(|| "sum_to".to_string());
let main2 = lift(&img, &p, p.function_by_name("main").unwrap(), &renamed);
assert!(main2.text.contains("sum_to(5)"), "{}", main2.text);
let d = lift(&img, &p, p.function_by_name("dispatch").unwrap(), &none);
assert!(d.text.contains("return"), "{}", d.text);
}
#[test]
fn win64_stack_args_and_tail_call() {
// main, patched: six arguments to the `puts` import (four in registers, two on the
// stack), then a tail jump to `helper`.
let mut pe = tk::pe64();
let code: [u8; 58] = [
0x48, 0x83, 0xec, 0x68, // sub rsp, 0x68
0x48, 0xc7, 0x44, 0x24, 0x28, 0x07, 0x00, 0x00, 0x00, // mov qword [rsp+0x28], 7
0xc7, 0x44, 0x24, 0x20, 0x05, 0x00, 0x00, 0x00, // mov dword [rsp+0x20], 5
0x41, 0xb9, 0x04, 0x00, 0x00, 0x00, // mov r9d, 4
0x41, 0xb8, 0x03, 0x00, 0x00, 0x00, // mov r8d, 3
0xba, 0x02, 0x00, 0x00, 0x00, // mov edx, 2
0xb9, 0x01, 0x00, 0x00, 0x00, // mov ecx, 1
0xff, 0x15, 0x2f, 0x11, 0x00, 0x00, // call [rip+0x112f] (the puts IAT slot)
0x48, 0x83, 0xc4, 0x68, // add rsp, 0x68
0xe9, 0x06, 0x00, 0x00, 0x00, // jmp helper
];
pe[0x400..0x400 + code.len()].copy_from_slice(&code);
let (img, p) = setup(pe);
let main = p.functions.get(&(tk::PE_BASE + tk::PE_TEXT_RVA)).unwrap();
let out = lift(&img, &p, main, &|_| None);
assert!(out.text.contains("puts(1, 2, 3, 4, 5, 7);"), "{}", out.text);
assert!(!out.text.contains("stack_20"), "{}", out.text);
assert!(out.text.contains("return helper();"), "{}", out.text);
assert!(out.calls.contains(&"helper".to_string()));
}
#[test]
fn aarch64_lifts() {
let (elf, _) = tk::elf64(tk::ElfArch::Aarch64, true);
let (img, p) = setup(elf);
let none = |_: u64| None;
let main = lift(&img, &p, p.function_by_name("main").unwrap(), &none);
assert!(main.text.contains("puts(\"Hello, Craft!\")"), "{}", main.text);
let helper = lift(&img, &p, p.function_by_name("helper").unwrap(), &none);
assert!(helper.text.contains("w0 == 0") || helper.text.contains("w0 != 0"), "{}", helper.text);
}
fn lift_a64(words: &[u32]) -> Pseudo {
let bytes: Vec<u8> = words.iter().flat_map(|w| w.to_le_bytes()).collect();
let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
let f = program.functions.get(&0x1000).unwrap();
lift(&image, &program, f, &|_| None)
}
/// `mov w9, #0x2493` followed by `movk w9, #0x9249, lsl #16` read as two statements, not
/// one constant (R3.11).
#[test]
fn aarch64_movz_movk_pairs_fold_into_one_constant() {
// mov w9, #0x2493; movk w9, #0x9249, lsl #16
let p = lift_a64(&[0x5284_9269, 0x72b2_4929, 0xd65f_03c0]);
assert!(p.text.contains("w9 = 0x92492493;"), "{}", p.text);
assert!(!p.text.contains("(w9 & "), "{}", p.text);
// mov x10, #0x1122; movk ร4: the whole 64-bit constant, one statement
let p = lift_a64(&[0xd282_244a, 0xf2a6_688a, 0xf2ca_acca, 0xf2ee_f10a, 0xd65f_03c0]);
assert!(p.text.contains("x10 = 0x7788556633441122;"), "{}", p.text);
assert!(!p.text.contains("(x10 & "), "{}", p.text);
// A W pair over a MOVN keeps its inverted low half
let p = lift_a64(&[0x1280_000d, 0x72b2_492d, 0xd65f_03c0]);
assert!(p.text.contains("w13 = 0x9249ffff;"), "{}", p.text);
// A read between the pair keeps both statements
let p = lift_a64(&[0xd284_926e, 0x8b0e_01cf, 0xf2b2_492e, 0xd65f_03c0]);
assert!(p.text.contains("x14 = 0x2493;"), "{}", p.text);
assert!(p.text.contains("x15 = x14 + x14;"), "{}", p.text);
assert!(p.text.contains("x14 = (x14 & 0xffffffff0000ffff) | 0x92490000;"), "{}", p.text);
// A page load between the pair overwrites the register: the MOVK folds with nothing
let p = lift_a64(&[0xd284_9269, 0x9000_0009, 0xf2b2_4929, 0xd65f_03c0]);
assert!(p.text.contains("x9 = 0x2493;"), "{}", p.text);
assert!(p.text.contains("x9 = (x9 & 0xffffffff0000ffff) | 0x92490000;"), "{}", p.text);
assert!(!p.text.contains("x9 = 0x92492493;"), "{}", p.text);
}
/// `ldr w0, [x1, w2, sxtw #2]` read the index as the plain register, so the address lost
/// the sign extension (R3.11).
#[test]
fn aarch64_extended_memory_indices_keep_the_extension() {
// ldr w0, [x1, w2, sxtw #2]; ldr x6, [x7, x8, lsl #3]; ldr x24, [x25, w26, uxtw];
// ldr x15, [x16, x17]; str w9, [x10, w11, sxtw #2]; ret
let words = [0xb862_d820u32, 0xf868_78e6, 0xf87a_4b38, 0xf871_6a0f, 0xb82b_d949, 0xd65f_03c0];
let p = lift_a64(&words);
for want in [
"w0 = *(void*)(x1 + ((int64_t)(int32_t)w2 << 2));",
"x6 = *(void*)(x7 + (x8 << 3));",
"x24 = *(void*)(x25 + (uint32_t)w26);",
"x15 = *(void*)(x16 + x17);",
"*(void*)(x10 + ((int64_t)(int32_t)w11 << 2)) = w9;",
] {
assert!(p.text.contains(want), "{want}\n{}", p.text);
}
assert!(!p.text.contains("*(void*)(x1 + x2)"), "{}", p.text);
assert!(!p.text.contains("*(void*)(x10 + x11)"), "{}", p.text);
}
/// `mov x19, x0` came out as `x19 = xzr;`: the zero register of its ORR form was taken as the value.
#[test]
fn aarch64_moves_copy_the_source_not_the_zero_register() {
// mov x19, x0; mov w1, w2; mov w0, #0xff00ff00; ret
let p = lift_a64(&[0xaa00_03f3, 0x2a02_03e1, 0x3208_9fe0, 0xd65f_03c0]);
assert!(p.text.contains("x19 = x0;") && p.text.contains("w1 = w2;"), "{}", p.text);
assert!(p.text.contains("w0 = 0xff00ff00;"), "{}", p.text);
assert!(!p.text.contains("zr"), "{}", p.text);
}
#[test]
fn every_function_of_damaged_inputs_lifts_without_panicking() {
let (elf, _) = tk::elf64(tk::ElfArch::X86_64, false);
for m in tk::mutations(&elf).into_iter().step_by(3) {
if let Ok(img) = Image::parse(Arc::from(m))
&& let Ok(p) = Program::analyze(&img, &Limits::default(), &NoControl)
{
for f in p.functions.values() {
let _ = lift(&img, &p, f, &|_| None);
}
}
}
for seed in 0..12 {
let raw = Image::raw(Arc::from(tk::noise(seed, 2048)), craft_anything_formats::Arch::X86_64, 0x1000);
if let Ok(p) = Program::analyze(&raw, &Limits::default(), &NoControl) {
for f in p.functions.values().take(50) {
let _ = lift(&raw, &p, f, &|_| None);
}
}
}
}
#[test]
fn arm32_calls_keep_their_return_value_in_r0() {
use craft_anything_formats::Arch;
fn words(ws: &[u32]) -> Vec<u8> {
ws.iter().flat_map(|w| w.to_le_bytes()).collect()
}
fn arm_elf(code: &[u8], thumb: bool) -> Vec<u8> {
let mut b = vec![0u8; 0x100];
b[0..7].copy_from_slice(b"\x7fELF\x01\x01\x01");
for (o, v) in [(16, 2u16), (18, 40), (40, 52), (42, 32), (44, 1)] {
b[o..o + 2].copy_from_slice(&v.to_le_bytes());
}
let n = code.len() as u32;
for (o, v) in [(20, 1u32), (24, 0x1000 | u32::from(thumb)), (28, 52), (36, 0x0500_0000), (52, 1)] {
b[o..o + 4].copy_from_slice(&v.to_le_bytes());
}
for (o, v) in [(56, 0x100u32), (60, 0x1000), (64, 0x1000), (68, n), (72, n), (76, 5), (80, 0x100)] {
b[o..o + 4].copy_from_slice(&v.to_le_bytes());
}
b.extend_from_slice(code);
b
}
fn lift_entry(image: Image) -> String {
let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
let f = program.functions.get(&0x1000).unwrap();
lift(&image, &program, f, &|_| None).text
}
let call_ret = words(&[0xe92d_4010, 0xeb00_0001, 0xe8bd_8010, 0xe320_f000, 0xe3a0_0007, 0xe12f_ff1e]);
let used_call = words(&[0xe92d_4010, 0xeb00_0002, 0xe280_1001, 0xe1a0_0001, 0xe8bd_8010, 0xe3a0_0007, 0xe12f_ff1e]);
let leaf = words(&[0xe3a0_0007, 0xe12f_ff1e]);
let ar = lift_entry(Image::raw(Arc::from(call_ret.clone()), Arch::Arm, 0x1000));
let au = lift_entry(Image::raw(Arc::from(used_call), Arch::Arm, 0x1000));
let al = lift_entry(Image::raw(Arc::from(leaf), Arch::Arm, 0x1000));
let ae = lift_entry(Image::parse(Arc::from(arm_elf(&call_ret, false))).unwrap());
let tr = lift_entry(Image::parse(Arc::from(arm_elf(&[0x10, 0xb5, 0x98, 0x47, 0x10, 0xbd], true))).unwrap());
assert!(ar.contains("return r0;") && !ar.contains("rax"), "{ar}");
assert!(ae.contains("return r0;") && !ae.contains("rax"), "{ae}");
assert!(tr.contains("return r0;") && !tr.contains("rax"), "{tr}");
assert!(au.contains("r0 = sub_1014();") && au.contains("r1 = r0 + 1;") && au.contains("return r0;"), "{au}");
assert!(al.contains("r0 = 7;") && al.contains("return r0;") && !al.contains("rax"), "{al}");
}
/// #277: ARM32 loads and stores came out as `r0 = 0;` and `0 = r0;`.
#[test]
fn arm32_loads_and_stores_keep_their_addresses() {
use craft_anything_formats::Arch;
let lift_words = |ws: &[u32]| {
let bytes: Vec<u8> = ws.iter().flat_map(|w| w.to_le_bytes()).collect();
let image = Image::raw(Arc::from(bytes), Arch::Arm, 0x1000);
let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
let f = program.functions.get(&0x1000).unwrap();
lift(&image, &program, f, &|_| None)
};
// ldr r0, [r1, #4]; str r0, [r2]; bx lr
let p = lift_words(&[0xe591_0004, 0xe582_0000, 0xe12f_ff1e]);
assert!(p.text.contains("r0 = *(uint32_t*)(r1 + 4);") && p.text.contains("*(uint32_t*)(r2) = r0;"), "{}", p.text);
assert_eq!(p.asm_fallbacks, 0);
// ldr r0, [r1, #-8]
let p = lift_words(&[0xe511_0008, 0xe12f_ff1e]);
assert!(p.text.contains("r0 = *(uint32_t*)(r1 - 8);"), "{}", p.text);
// ldr r0, [r1], #4 also moves r1, which no statement here says: it's shown as written.
let p = lift_words(&[0xe491_0004, 0xe12f_ff1e]);
assert!(p.text.contains("__asm(") && !p.text.contains("r0 = 0;") && p.asm_fallbacks == 1, "{}", p.text);
let i = crate::decode::decode(Mode::A32, &0xe591_0004u32.to_le_bytes(), 0x1000, false).unwrap();
assert!(i.reads.contains(&"r1".to_string()) && i.writes == ["r0"], "{i:?}");
}
/// `movk w9, #0x9249, lsl #16` came out as `w9 = 0x92490000;`, losing the low half set just
/// before, and `mov w0, #-1` (MOVN) as `w0 = 0;`.
#[test]
fn aarch64_move_wide_immediates_keep_their_value() {
// mov w9, #0x2493; movk w9, #0x9249, lsl #16; mov w0, #-1; ret
let bytes: Vec<u8> = [0x5284_9269u32, 0x72b2_4929, 0x1280_0000, 0xd65f_03c0].iter().flat_map(|w| w.to_le_bytes()).collect();
let image = Image::raw(Arc::from(bytes), craft_anything_formats::Arch::Aarch64, 0x1000);
let program = Program::analyze(&image, &Limits::default(), &NoControl).unwrap();
let p = lift(&image, &program, program.functions.get(&0x1000).unwrap(), &|_| None);
// The pair folds into one constant, whose low half is the MOVZ's
assert!(p.text.contains("w9 = 0x92492493;"), "{}", p.text);
assert!(!p.text.contains("w9 = 0x92490000;"), "{}", p.text);
assert!(p.text.contains("w0 = -1;") && !p.text.contains("w0 = 0;"), "{}", p.text);
assert_eq!(p.asm_fallbacks, 0, "{}", p.text);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (โO on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.