mirror of
https://github.com/RetroPortingToolKit/psxrecomp
synced 2026-10-28 10:59:16 -04:00
Matthew Stanley
80ff96780a
The overlay capture format DELIBERATELY appends one coherent guard instruction
past the end of a dirty-page run (overlay_capture.c write_json_window, `size
+= 4u`, pinned by runtime/tests/test_interpreter_perf_guards.py:47): a MIPS
branch sitting at the run's final word (...FFC) always executes its delay slot
in the next page (...000), and the shard must be able to emit and hash that
word. So a capture whose size is a page multiple PLUS 4 is a CORRECT capture --
N bytes of overlay plus one guard word. Measured: 36 of 36 Ape Escape
(SCUS-94423) vault records and 846 of 946 Tomba 2 (SCUS-94454) records are that
shape.
The recompiler was never taught the asymmetry: the guard word is a legal
DELAY-SLOT SOURCE but an ILLEGAL BLOCK LEADER, because the word after it does
not exist in the image. It had exactly one bound -- end_address() -- used both
to read words and to decide what is code.
MEASURED on Ape Escape, its own single-source vault at framework
v0.3.2-alpha-139-g1bf70960, 36 variants:
PSX_SHARD_RESULT ok=50 failed=17 skipped=32 capacity_fastpath=0
! [recompiler] overlay 0x80136000 crc 4BAB23C9: what(): cannot emit control
flow at 0x80138000: mandatory delay slot 0x80138004 is outside the input
image
+ 16 x [fragment] interior 0x801360.. @region 0x00136000, identical message
One root cause, seventeen shards. The whole region then falls back to the
dirty-RAM interpreter forever, and nothing at runtime says so.
Causal chain, every step read in source:
1. overlay_capture.c:349-361 appends the guard word; region 0x80136000 gets
size 0x2004, so the image is [0x80136000, 0x80138004).
2. compile_overlays.py make_psxexe wraps those bytes verbatim with text size
= len(data), so PS1Executable::end_address() = 0x80138004.
3. function_analysis.cpp in_exe / in_function admit 0x80138000 as ordinary
code, and the walk reaches it by fall-through from 0x80137FFC
(0x24022000, addiu -- not control flow), so func.end_addr becomes the
image end.
4. control_flow.cpp makes the final block end_addr = func.end_addr - 4 =
0x80138000: the block LEADER is the guard word.
5. control_flow.cpp's "Also check last instruction itself" promotion finds
0x80137FFC is not control flow and therefore promotes read_word(end_addr)
-- the guard word 0x1062005A, a beq -- to block.exit_instr, with
has_delay_slot = true and address == end_addr. THIS IS THE DEFECT.
6. code_generator.cpp computes delay_slot_addr = 0x80138004, read_word
returns nullopt, and it throws.
THE THROW AT STEP 6 IS CORRECT AND IS PRESERVED. Emitting a control transfer
without its architectural delay slot silently corrupts guest state, which is
what the code did before that throw was added. The gap is step 5.
Fix: give the image view two distinct bounds.
end_address() READ bound -- every byte the image supplies, so a
mandatory delay slot living at a guard word resolves.
analysis_end_address() ANALYSIS bound -- one past the last byte that may be
discovered, made a block leader, or made a block's
exit instruction.
read_word() keeps the READ bound. Discovery and block construction move to the
ANALYSIS bound: function_analysis.cpp in_exe / in_exe_p3 / add_forced_entry /
every hard_cap that used to be the image end / the jr-table producer_hi
defaults / the static jr-ra and JAL sweeps; control_flow.cpp gains
analysis_walk_hi(func) and uses it for cfg.function_end, alias entries,
add_boundary, the scan loop, the final block's end_addr and in_func;
code_generator.cpp's mid-function split pre-pass; main_psx.cpp seed admission
and the data-scan pointer promotion; analysis_db.cpp, main_toml.cpp,
main_cli.cpp target/seed admission. The clamp is applied only when it leaves a
non-empty walk, so a degenerate function starting at or past the bound keeps
failing closed rather than silently producing an empty CFG.
HOW THE BOUND IS DERIVED -- the producer STATES it; the recompiler is told.
The alternative was for the recompiler to infer the count from `size % 4096 ==
4`. That fits every capture the current writer has ever produced, but it is a
consumer guessing at a producer's intent, and this tree already has the
counter-example: 52 of the 946 SCUS-94454 records have residues from 112 to
3996 bytes (one not even 4-byte aligned) because they come from the STATIC
extractor, which records an exact file extent and appends no guard word. A rule
keyed to the page-run shape is a rule that shifts the moment a producer
changes.
So the count travels with the image, in a magic-tagged field in the otherwise
zero-filled tail of the 2048-byte PS-EXE header (exe_tag in ps1_exe_parser.h:
"PSXRGRD1" at 0x7E0, uint32 count at 0x7E8). Putting it in the header rather
than on the command line means every consumer gets it automatically and no
future invocation path can forget to pass it -- compile_overlays has three
make_psxexe sites and five recompiler spawn sites. An absent or malformed tag
means ZERO guard bytes, which is exactly what every genuine PS-X EXE is: the
BIOS and every retail main executable have no guard word, their analysis bound
equals their read bound, and their analysis is bit-for-bit unchanged.
Producer side:
overlay_capture.c writes "guard_bytes": 4|0 per region -- the writer
stating its own intent, additive to the v2 schema and
preserved through coverage_vault.py compaction.
compile_overlays.py capture_guard_bytes(): prefer that field; for captures
recorded before it existed, reconstruct the single
shape write_json_window can produce (page multiple + 4)
and return 0 for everything else, which is the
fail-closed answer -- an unrecognised guard word is
analysed as code and the step-6 throw still fires
loudly at generation time.
make_psxexe guard_bytes is keyword-only with NO default, so a new
call site is a TypeError, not a silently mis-analysed
shard. The count is threaded through
compile_fragment_batch / compile_interior_fragment /
generate_interior_fragment_static and into the fragment
fail-memo key (bumped to v3, so a memo recorded under
the old analysis cannot suppress a retry under the
corrected one).
SECOND-ORDER DEFECT FIXED IN THE SAME PASS. generate_ranges_manifest extends a
range by +4 for any block whose exit instruction IS its last word, so the
cloned delay slot joins the candidate CRC and the page-generation watch. That
extension was unclamped. Reachable TODAY, independent of the guard word: a
branch-likely opcode (0x14-0x17, RESERVED on the R3000A) as the image's very
last word is short-circuited by translate_basic_block into an inline RI raise
BEFORE any delay slot is read, so generation succeeds and the manifest claims 4
bytes past the image end. Measured on origin/master with a 28-byte synthetic
image: `R 80010000 20` for an image ending at 0x8001001C. The cache would then
validate the shard against bytes the shard never saw. Now clamped to the READ
bound -- not the analysis bound, because a guard word genuinely IS compiled in
when it serves as a delay slot and must participate in the CRC.
DEAD CODE, documented rather than trusted: basic_block.cpp's BasicBlockAnalyzer
bounds its walk correctly but nothing in the tree constructs it. It is still
compiled and still hashed into the codegen tag, so a change there invalidates
caches without moving an emitted byte. Its bounds move to the analysis bound
too -- wiring it up must not reintroduce this defect -- and a header comment now
says where the live walker actually is.
TESTS. Both registered, so ctest runs them and the configure-time
registration guard is satisfied.
recompiler/tests/test_overlay_guard_word_analysis_bound.py drives
psxrecomp-game over five synthetic images:
A tagged, 2 pages + guard word, last real word not control flow, guard word
IS a beq -- the measured Ape shape. Must generate; the guard word must not
be emitted as an instruction; the block must publish 0x80012000 for the
runtime to dispatch; no range may claim it.
B byte-for-byte the same payload with NO tag. Must still fail closed with
the mandatory-delay-slot diagnostic naming 0x80012000. A and B differ only
in the header tag, which proves the tag is what changed behaviour and that
the throw was not weakened.
B2 a misaligned declaration (6). Must be rejected and behave like B.
C tagged, with a real branch at the last analysable word. The guard word
must be emitted AS the delay slot and must be covered by the manifest.
D branch-likely as the final word. Generation must succeed and no range may
exceed the image end.
Against origin/master's psxrecomp-game the same file reports exactly the two
things this commit changes, and passes B, B2 and C:
FAIL: tagged guard word still fails generation: what(): cannot emit control
flow at 0x80012000: mandatory delay slot 0x80012004 is outside the
input image
FAIL: range [0x80010000,0x80010020) claims 4 byte(s) past the image end
0x8001001C
tools/tests/test_overlay_guard_bytes_declaration.py pins the producer half:
field precedence, the reconstruction table, rejection of nonsense
declarations, the tag's byte offsets, that make_psxexe with guard_bytes=0 is
byte-identical to the pre-fix wrapper, and that overlay_capture.c both appends
the guard word and now declares it.
MEASURED OUTCOME, Ape Escape, same vault, same flags, fresh cache:
before PSX_SHARD_RESULT ok=50 failed=17 skipped=32 capacity_fastpath=0
after PSX_SHARD_RESULT ok=31 failed=0 skipped=57 capacity_fastpath=0
ok falls because 19 isolated island fragment shards at 0x00136000 are no longer
needed once the region variant compiles as one shard. Coverage is what matters,
and it is measured from the DLL exports: 349 -> 361 unique func_XXXXXXXX
entries, ZERO lost, 12 gained -- 0x80136140, 0x8013614C, 0x80136154,
0x80136238, 0x801362D4, 0x801362DC, 0x801362F0, 0x80136324, 0x80136370,
0x80136400, 0x80136480, 0x80137950, all from the failure list. The other four
failing PCs were already served by a sibling variant's shard.
INERTNESS.
BIOS (SCPH1001, psxrecomp-bios --config bios/SCPH1001.toml): all four
generated artifacts BYTE-IDENTICAL, verified by sha256 rather than by exit
code, because tools/regen_bios.sh exits 0 on failure.
Tomba 2 main EXE (psxrecomp-game --config game.toml): all nine generated
artifacts BYTE-IDENTICAL, and the console log is identical too.
Tomba 2 overlays, 82 variants over 6 regions from its own vault: identical
result line (ok=98 failed=0 skipped=103) and identical shard identity set,
4901 unique func exports on both sides -- zero gained, zero lost. 97 of 98
range manifests are byte-identical. The one that differs is region
0x8010A000 variant A32DB188, size 0x2004, whose last function's range goes
from 0x218 to 0x214 bytes: its guard word (0x24840008, addiu) had been
emitted as an ordinary instruction and hashed, and now is not. That is
precisely the intended change and nothing else moved.
Bead beads-eio.3.100.
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
1051 lines
44 KiB
C++
1051 lines
44 KiB
C++
// analysis_db.cpp — see analysis_db.h for the two rules this file obeys.
|
|
|
|
#include "analysis_db.h"
|
|
|
|
#include <algorithm>
|
|
#include <cstring>
|
|
#include <fstream>
|
|
#include <queue>
|
|
#include <sstream>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
|
|
#include "fmt/format.h"
|
|
#include "function_analysis.h"
|
|
#include "mips_decoder.h"
|
|
|
|
// toml11 is header-only; used only to read an existing symbols.toml so that
|
|
// hand-applied names survive re-analysis.
|
|
#include "toml.hpp"
|
|
|
|
namespace PSXRecomp::Analysis {
|
|
|
|
namespace {
|
|
|
|
constexpr uint32_t kMmioLo = 0x1F801000;
|
|
constexpr uint32_t kMmioHi = 0x1F803000;
|
|
|
|
inline uint32_t norm(uint32_t a) { return a & 0x1FFFFFFF; }
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Register effect model
|
|
//
|
|
// Deliberately explicit rather than derived from DecodedInstruction's coarse
|
|
// is_load/is_alu flags: the signature pass needs to know *which* registers an
|
|
// instruction reads, and a wrong answer there silently corrupts every inferred
|
|
// prototype. Anything this table does not recognize contributes no reads and
|
|
// no writes, which is the conservative direction for read-before-write (it can
|
|
// only under-report arguments, never invent them).
|
|
// ---------------------------------------------------------------------------
|
|
struct RegEffect {
|
|
uint32_t reads = 0;
|
|
uint32_t writes = 0;
|
|
};
|
|
|
|
inline void add(uint32_t& mask, uint8_t r) {
|
|
if (r != 0) mask |= (1u << r);
|
|
}
|
|
|
|
RegEffect reg_effect(const DecodedInstruction& d) {
|
|
RegEffect e;
|
|
switch (d.opcode) {
|
|
case 0x00: // SPECIAL
|
|
switch (d.funct) {
|
|
case 0x00: case 0x02: case 0x03: // SLL/SRL/SRA
|
|
add(e.reads, d.rt); add(e.writes, d.rd); break;
|
|
case 0x04: case 0x06: case 0x07: // SLLV/SRLV/SRAV
|
|
add(e.reads, d.rt); add(e.reads, d.rs); add(e.writes, d.rd); break;
|
|
case 0x08: // JR
|
|
add(e.reads, d.rs); break;
|
|
case 0x09: // JALR
|
|
add(e.reads, d.rs); add(e.writes, d.rd); break;
|
|
case 0x0C: case 0x0D: // SYSCALL/BREAK
|
|
break;
|
|
case 0x10: case 0x12: // MFHI/MFLO
|
|
add(e.writes, d.rd); break;
|
|
case 0x11: case 0x13: // MTHI/MTLO
|
|
add(e.reads, d.rs); break;
|
|
case 0x18: case 0x19: case 0x1A: case 0x1B: // MULT/MULTU/DIV/DIVU
|
|
add(e.reads, d.rs); add(e.reads, d.rt); break;
|
|
case 0x20: case 0x21: case 0x22: case 0x23: // ADD/ADDU/SUB/SUBU
|
|
case 0x24: case 0x25: case 0x26: case 0x27: // AND/OR/XOR/NOR
|
|
case 0x2A: case 0x2B: // SLT/SLTU
|
|
add(e.reads, d.rs); add(e.reads, d.rt); add(e.writes, d.rd); break;
|
|
default: break;
|
|
}
|
|
break;
|
|
case 0x01: // REGIMM
|
|
add(e.reads, d.rs);
|
|
if (d.rt == 0x10 || d.rt == 0x11) add(e.writes, REG_RA); // BLTZAL/BGEZAL
|
|
break;
|
|
case 0x02: break; // J
|
|
case 0x03: add(e.writes, REG_RA); break; // JAL
|
|
case 0x04: case 0x05: // BEQ/BNE
|
|
add(e.reads, d.rs); add(e.reads, d.rt); break;
|
|
case 0x06: case 0x07: // BLEZ/BGTZ
|
|
add(e.reads, d.rs); break;
|
|
case 0x08: case 0x09: case 0x0A: case 0x0B: // ADDI/ADDIU/SLTI/SLTIU
|
|
case 0x0C: case 0x0D: case 0x0E: // ANDI/ORI/XORI
|
|
add(e.reads, d.rs); add(e.writes, d.rt); break;
|
|
case 0x0F: add(e.writes, d.rt); break; // LUI
|
|
case 0x10: // COP0
|
|
if (d.rs == 0x00) add(e.writes, d.rt); // MFC0
|
|
else if (d.rs == 0x04) add(e.reads, d.rt); // MTC0
|
|
break;
|
|
case 0x12: // COP2 / GTE
|
|
if (d.rs == 0x00 || d.rs == 0x02) add(e.writes, d.rt); // MFC2/CFC2
|
|
else if (d.rs == 0x04 || d.rs == 0x06) add(e.reads, d.rt); // MTC2/CTC2
|
|
break;
|
|
case 0x20: case 0x21: case 0x23: case 0x24: case 0x25: // LB/LH/LW/LBU/LHU
|
|
add(e.reads, d.rs); add(e.writes, d.rt); break;
|
|
case 0x22: case 0x26: // LWL/LWR: partial merge
|
|
add(e.reads, d.rs); add(e.reads, d.rt); add(e.writes, d.rt); break;
|
|
case 0x28: case 0x29: case 0x2A: case 0x2B: case 0x2E: // SB/SH/SWL/SW/SWR
|
|
add(e.reads, d.rs); add(e.reads, d.rt); break;
|
|
case 0x32: case 0x3A: // LWC2/SWC2
|
|
add(e.reads, d.rs); break;
|
|
default: break;
|
|
}
|
|
return e;
|
|
}
|
|
|
|
int mem_width(uint8_t opcode) {
|
|
switch (opcode) {
|
|
case 0x20: case 0x24: case 0x28: return 1;
|
|
case 0x21: case 0x25: case 0x29: return 2;
|
|
case 0x22: case 0x23: case 0x26: case 0x2A: case 0x2B: case 0x2E:
|
|
case 0x32: case 0x3A: return 4;
|
|
default: return 0;
|
|
}
|
|
}
|
|
|
|
bool is_store_op(uint8_t opcode) {
|
|
return opcode == 0x28 || opcode == 0x29 || opcode == 0x2A ||
|
|
opcode == 0x2B || opcode == 0x2E || opcode == 0x3A;
|
|
}
|
|
|
|
bool is_load_op(uint8_t opcode) {
|
|
return opcode == 0x20 || opcode == 0x21 || opcode == 0x22 ||
|
|
opcode == 0x23 || opcode == 0x24 || opcode == 0x25 ||
|
|
opcode == 0x26 || opcode == 0x32;
|
|
}
|
|
|
|
std::string classify_target(uint32_t target, uint32_t lo, uint32_t hi) {
|
|
uint32_t k = norm(target);
|
|
if (k >= norm(kMmioLo) && k < norm(kMmioHi)) return "mmio";
|
|
if (target >= lo && target < hi) return "image";
|
|
if (k < 0x00800000) return "ram";
|
|
return "other";
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Disassembly formatting
|
|
// ---------------------------------------------------------------------------
|
|
std::string format_instr(const DecodedInstruction& d,
|
|
const AnalysisDb* db) {
|
|
auto rn = [](uint8_t r) { return MipsDecoder::register_name(r); };
|
|
auto sym = [&](uint32_t a) -> std::string {
|
|
if (db) {
|
|
const FunctionRecord* f = db->find(a);
|
|
if (f) return fmt::format("0x{:08X} <{}>", a, f->name);
|
|
}
|
|
return fmt::format("0x{:08X}", a);
|
|
};
|
|
|
|
if (d.is_nop) return "nop";
|
|
const char* m = d.mnemonic ? d.mnemonic : "???";
|
|
std::string mn = m;
|
|
std::transform(mn.begin(), mn.end(), mn.begin(),
|
|
[](unsigned char c) { return std::tolower(c); });
|
|
|
|
switch (d.opcode) {
|
|
case 0x02: case 0x03: // J / JAL
|
|
return fmt::format("{:<8}{}", mn, sym(d.jump_target));
|
|
case 0x04: case 0x05: // BEQ/BNE
|
|
return fmt::format("{:<8}{}, {}, 0x{:08X}", mn, rn(d.rs), rn(d.rt),
|
|
d.branch_target);
|
|
case 0x06: case 0x07: // BLEZ/BGTZ
|
|
return fmt::format("{:<8}{}, 0x{:08X}", mn, rn(d.rs), d.branch_target);
|
|
case 0x01: // REGIMM
|
|
return fmt::format("{:<8}{}, 0x{:08X}", mn, rn(d.rs), d.branch_target);
|
|
case 0x0F: // LUI
|
|
return fmt::format("{:<8}{}, 0x{:04X}", mn, rn(d.rt), d.uimm16);
|
|
case 0x08: case 0x09: case 0x0A: case 0x0B:
|
|
return fmt::format("{:<8}{}, {}, {}", mn, rn(d.rt), rn(d.rs),
|
|
d.sign_ext_imm);
|
|
case 0x0C: case 0x0D: case 0x0E:
|
|
return fmt::format("{:<8}{}, {}, 0x{:04X}", mn, rn(d.rt), rn(d.rs),
|
|
d.uimm16);
|
|
default: break;
|
|
}
|
|
|
|
if (d.is_load || d.is_store)
|
|
return fmt::format("{:<8}{}, {}({})", mn, rn(d.rt), d.sign_ext_imm,
|
|
rn(d.rs));
|
|
|
|
if (d.opcode == 0x00) {
|
|
switch (d.funct) {
|
|
case 0x08: return fmt::format("{:<8}{}", mn, rn(d.rs));
|
|
case 0x09: return fmt::format("{:<8}{}, {}", mn, rn(d.rd), rn(d.rs));
|
|
case 0x00: case 0x02: case 0x03:
|
|
return fmt::format("{:<8}{}, {}, {}", mn, rn(d.rd), rn(d.rt),
|
|
(int)d.shamt);
|
|
case 0x0C: case 0x0D: return mn;
|
|
case 0x10: case 0x12: return fmt::format("{:<8}{}", mn, rn(d.rd));
|
|
case 0x11: case 0x13: return fmt::format("{:<8}{}", mn, rn(d.rs));
|
|
case 0x18: case 0x19: case 0x1A: case 0x1B:
|
|
return fmt::format("{:<8}{}, {}", mn, rn(d.rs), rn(d.rt));
|
|
default:
|
|
return fmt::format("{:<8}{}, {}, {}", mn, rn(d.rd), rn(d.rs),
|
|
rn(d.rt));
|
|
}
|
|
}
|
|
if (d.format == InstrFormat::UNKNOWN)
|
|
return fmt::format(".word 0x{:08X}", d.raw);
|
|
return fmt::format("{:<8}{}, {}, {}", mn, rn(d.rd), rn(d.rs), rn(d.rt));
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// General jump-table recovery
|
|
//
|
|
// function_analysis.cpp's resolve_exact_bounded_jump_table() is tried first and
|
|
// is authoritative when it fires. It accepts exactly one instruction schedule
|
|
// (`sltiu; beq; nop; sll; addu; lw; jr`) because a wrong table there emits
|
|
// wrong CODE. This recoverer exists because that is the wrong trade for a
|
|
// discovery tool: on a real title the far more common schedule puts the `sll`
|
|
// in the branch's delay slot and materializes the table base between the `sll`
|
|
// and the `addu`, which the strict form rejects outright — leaving every switch
|
|
// in the image reported as an unresolved indirect jump.
|
|
//
|
|
// So this walks the actual backward slice instead of matching a fixed window,
|
|
// and labels how it terminated: `guarded` (an sltiu bound on the index register
|
|
// was found — the count is proven) or `scanned` (no bound found; the table was
|
|
// walked until a word stopped looking like a code address). A `scanned` table
|
|
// is a hypothesis and is reported as such; it never silently reads as proven.
|
|
struct RecoveredTable {
|
|
uint32_t base = 0;
|
|
uint32_t count = 0;
|
|
std::vector<uint32_t> targets;
|
|
const char* method = "";
|
|
};
|
|
|
|
// Nearest preceding instruction that writes `reg`, searching back at most
|
|
// `window` instructions and never before `lo`. Returns false if none.
|
|
bool find_def(const PS1Executable& exe, uint32_t lo, uint32_t from_pc,
|
|
uint8_t reg, uint32_t window, DecodedInstruction& out) {
|
|
uint32_t limit = (from_pc > lo + window * 4) ? from_pc - window * 4 : lo;
|
|
for (uint32_t pc = from_pc; pc >= limit; pc -= 4) {
|
|
auto w = exe.read_word(pc);
|
|
if (!w.has_value()) break;
|
|
DecodedInstruction d = MipsDecoder::decode(*w, pc);
|
|
if (reg_effect(d).writes & (1u << reg)) { out = d; return true; }
|
|
if (pc < 4 || pc == limit) break;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// Constant value of `reg` at `at_pc`, if it comes from LUI or LUI+ADDIU.
|
|
bool const_value(const PS1Executable& exe, uint32_t lo, uint32_t at_pc,
|
|
uint8_t reg, uint32_t& out) {
|
|
DecodedInstruction d;
|
|
if (!find_def(exe, lo, at_pc, reg, 48, d)) return false;
|
|
if (d.opcode == 0x0F) { // LUI
|
|
out = static_cast<uint32_t>(d.uimm16) << 16;
|
|
return true;
|
|
}
|
|
if (d.opcode == 0x09) { // ADDIU rt, rs, imm
|
|
uint32_t hi = 0;
|
|
if (d.address < lo + 4) return false;
|
|
if (!const_value(exe, lo, d.address - 4, d.rs, hi)) return false;
|
|
out = hi + static_cast<uint32_t>(d.sign_ext_imm);
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool recover_jump_table(const PS1Executable& exe,
|
|
uint32_t f_start, uint32_t f_end,
|
|
uint32_t jr_pc, uint8_t jr_rs,
|
|
const std::unordered_map<uint32_t, size_t>& fn_index,
|
|
RecoveredTable& out) {
|
|
const uint32_t img_lo = exe.load_address();
|
|
const uint32_t img_hi = exe.analysis_end_address();
|
|
|
|
// jr $rD <- lw $rD, off($rB)
|
|
DecodedInstruction lw;
|
|
if (jr_pc < f_start + 4) return false;
|
|
if (!find_def(exe, f_start, jr_pc - 4, jr_rs, 8, lw)) return false;
|
|
if (lw.opcode != 0x23) return false; // must be LW
|
|
const int32_t lw_off = lw.sign_ext_imm;
|
|
const uint8_t base_reg = lw.rs;
|
|
|
|
// $rB <- addu $rB, <scaled index>, <table base>
|
|
DecodedInstruction addu;
|
|
if (lw.address < f_start + 4) return false;
|
|
if (!find_def(exe, f_start, lw.address - 4, base_reg, 8, addu)) return false;
|
|
if (!(addu.opcode == 0x00 && (addu.funct == 0x21 || addu.funct == 0x20)))
|
|
return false; // ADDU / ADD
|
|
|
|
// One operand is `sll rX, rIdx, 2`; the other is a materialized constant.
|
|
uint8_t index_reg = 0;
|
|
uint32_t table_base = 0;
|
|
bool have_base = false;
|
|
const uint8_t ops[2] = {addu.rs, addu.rt};
|
|
for (int k = 0; k < 2; ++k) {
|
|
DecodedInstruction d;
|
|
if (addu.address < f_start + 4) break;
|
|
if (!find_def(exe, f_start, addu.address - 4, ops[k], 16, d)) continue;
|
|
if (d.opcode == 0x00 && d.funct == 0x00 && d.shamt == 2) {
|
|
index_reg = d.rt; // SLL rd, rt, 2
|
|
}
|
|
}
|
|
for (int k = 0; k < 2; ++k) {
|
|
uint32_t v = 0;
|
|
if (addu.address < f_start + 4) break;
|
|
if (const_value(exe, f_start, addu.address - 4, ops[k], v)) {
|
|
table_base = v;
|
|
have_base = true;
|
|
}
|
|
}
|
|
if (!index_reg || !have_base) return false;
|
|
|
|
table_base += static_cast<uint32_t>(lw_off);
|
|
if ((table_base & 3u) || table_base < img_lo || table_base + 3 >= img_hi)
|
|
return false;
|
|
|
|
// Bound: nearest `sltiu/slti rX, rIdx, N` before the jr.
|
|
uint32_t count = 0;
|
|
const char* method = "scanned";
|
|
{
|
|
uint32_t limit = (jr_pc > f_start + 64 * 4) ? jr_pc - 64 * 4 : f_start;
|
|
for (uint32_t pc = jr_pc; pc >= limit; pc -= 4) {
|
|
auto w = exe.read_word(pc);
|
|
if (!w.has_value()) break;
|
|
DecodedInstruction d = MipsDecoder::decode(*w, pc);
|
|
if ((d.opcode == 0x0B || d.opcode == 0x0A) && d.rs == index_reg &&
|
|
d.uimm16 > 0 && d.uimm16 <= 4096) {
|
|
count = d.uimm16;
|
|
method = "guarded";
|
|
break;
|
|
}
|
|
if (pc < 4 || pc == limit) break;
|
|
}
|
|
}
|
|
|
|
auto plausible_target = [&](uint32_t t) {
|
|
if (t & 3u) return false;
|
|
if (t < img_lo || t + 3 >= img_hi) return false;
|
|
auto w = exe.read_word(t);
|
|
if (!w.has_value()) return false;
|
|
// A case label is either inside this function or a known function
|
|
// start; anything else is a coincidental word, not a target.
|
|
if (!(t >= f_start && t < f_end) && !fn_index.count(t)) return false;
|
|
return FunctionAnalyzer::is_valid_mips_word(*w);
|
|
};
|
|
|
|
if (count == 0) {
|
|
for (uint32_t k = 0; k < 256; ++k) {
|
|
auto w = exe.read_word(table_base + k * 4);
|
|
if (!w.has_value() || !plausible_target(*w)) break;
|
|
count = k + 1;
|
|
}
|
|
if (count < 2) return false; // a lone match is noise, not a table
|
|
}
|
|
|
|
for (uint32_t k = 0; k < count; ++k) {
|
|
auto w = exe.read_word(table_base + k * 4);
|
|
if (!w.has_value()) return false;
|
|
if (!plausible_target(*w)) {
|
|
// A guarded count that does not validate means the slice was
|
|
// misread. Report nothing rather than a half-right table.
|
|
if (method[0] == 'g') return false;
|
|
break;
|
|
}
|
|
out.targets.push_back(*w);
|
|
}
|
|
if (out.targets.size() < 2) return false;
|
|
|
|
out.base = table_base;
|
|
out.count = static_cast<uint32_t>(out.targets.size());
|
|
out.method = method;
|
|
return true;
|
|
}
|
|
|
|
// Resolve `jalr $rD` / `jr $rD` where $rD holds a statically-known function
|
|
// address: either materialized inline (lui/addiu) or loaded from a fixed
|
|
// address whose stored word is a known function start. This is the callback /
|
|
// dispatch-slot pattern, and it is the second largest indirect class after
|
|
// switches. Anything whose pointer comes from a struct field or a computed
|
|
// address stays unresolved — correctly, since static analysis cannot know it.
|
|
bool recover_indirect_call(const PS1Executable& exe, uint32_t f_start,
|
|
uint32_t call_pc, uint8_t reg,
|
|
const std::unordered_map<uint32_t, size_t>& fn_index,
|
|
uint32_t& target, const char*& how) {
|
|
if (call_pc < f_start + 4) return false;
|
|
DecodedInstruction def;
|
|
if (!find_def(exe, f_start, call_pc - 4, reg, 16, def)) return false;
|
|
|
|
// Materialized directly: lui + addiu naming a function.
|
|
if (def.opcode == 0x09 || def.opcode == 0x0F) {
|
|
uint32_t v = 0;
|
|
if (const_value(exe, f_start, def.address, reg, v) && fn_index.count(v)) {
|
|
target = v;
|
|
how = "immediate";
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
// Loaded from a statically-known address.
|
|
if (def.opcode == 0x23) { // LW rt, off(rB)
|
|
uint32_t base = 0;
|
|
if (def.address < f_start + 4) return false;
|
|
if (!const_value(exe, f_start, def.address - 4, def.rs, base))
|
|
return false;
|
|
uint32_t slot = base + static_cast<uint32_t>(def.sign_ext_imm);
|
|
auto w = exe.read_word(slot);
|
|
if (!w.has_value() || !fn_index.count(*w)) return false;
|
|
target = *w;
|
|
how = "static_slot";
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
std::string render_prototype(const FunctionRecord& f) {
|
|
std::string ret = (f.sig.returns_v0 || f.sig.returns_v1) ? "u32" : "void";
|
|
std::string args;
|
|
for (int i = 0; i < f.sig.arg_count; ++i) {
|
|
if (i) args += ", ";
|
|
args += fmt::format("u32 a{}", i);
|
|
}
|
|
if (args.empty()) args = "void";
|
|
return fmt::format("{} {}({})", ret, f.name, args);
|
|
}
|
|
|
|
} // namespace
|
|
|
|
const char* confidence_name(Confidence c) {
|
|
switch (c) {
|
|
case Confidence::Verified: return "verified";
|
|
case Confidence::High: return "high";
|
|
case Confidence::Medium: return "medium";
|
|
case Confidence::Low: return "low";
|
|
case Confidence::DataRegion: return "data";
|
|
}
|
|
return "low";
|
|
}
|
|
|
|
const char* edge_kind_name(CallEdge::Kind k) {
|
|
switch (k) {
|
|
case CallEdge::Kind::Direct: return "direct";
|
|
case CallEdge::Kind::JumpTable: return "jump_table";
|
|
case CallEdge::Kind::AddressTaken: return "address_taken";
|
|
case CallEdge::Kind::Indirect: return "indirect";
|
|
}
|
|
return "direct";
|
|
}
|
|
|
|
const FunctionRecord* AnalysisDb::find(uint32_t addr) const {
|
|
auto it = std::lower_bound(functions.begin(), functions.end(), addr,
|
|
[](const FunctionRecord& f, uint32_t v) { return f.addr < v; });
|
|
if (it != functions.end() && it->addr == addr) return &*it;
|
|
return nullptr;
|
|
}
|
|
|
|
const FunctionRecord* AnalysisDb::containing(uint32_t pc) const {
|
|
auto it = std::upper_bound(functions.begin(), functions.end(), pc,
|
|
[](uint32_t v, const FunctionRecord& f) { return v < f.addr; });
|
|
if (it == functions.begin()) return nullptr;
|
|
--it;
|
|
return (pc >= it->addr && pc < it->end) ? &*it : nullptr;
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// symbols.toml
|
|
// ---------------------------------------------------------------------------
|
|
bool load_symbols(const std::filesystem::path& path,
|
|
std::vector<SymbolEntry>& out,
|
|
std::string& error) {
|
|
out.clear();
|
|
if (path.empty()) return true;
|
|
std::error_code ec;
|
|
if (!std::filesystem::exists(path, ec)) return true; // absent is not an error
|
|
try {
|
|
const auto root = toml::parse(path.string());
|
|
if (!root.contains("func")) return true;
|
|
const auto& arr = toml::find(root, "func");
|
|
if (!arr.is_array()) return true;
|
|
for (const auto& e : arr.as_array()) {
|
|
SymbolEntry s;
|
|
if (!e.contains("pc")) continue;
|
|
s.pc = static_cast<uint32_t>(toml::find<std::int64_t>(e, "pc"));
|
|
s.name = e.contains("name") ? toml::find<std::string>(e, "name") : "";
|
|
if (s.name.empty()) continue;
|
|
if (e.contains("status")) s.status = toml::find<std::string>(e, "status");
|
|
if (e.contains("note")) s.note = toml::find<std::string>(e, "note");
|
|
if (e.contains("emit")) s.emit = toml::find<bool>(e, "emit");
|
|
out.push_back(s);
|
|
}
|
|
} catch (const std::exception& ex) {
|
|
error = fmt::format("symbols.toml parse failed: {}", ex.what());
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// Main build
|
|
// ---------------------------------------------------------------------------
|
|
AnalysisDb build_analysis_db(const PS1Executable& exe,
|
|
const std::string& image_name,
|
|
const Options& opts,
|
|
std::string& error) {
|
|
AnalysisDb db;
|
|
db.image_name = image_name;
|
|
db.load_address = exe.load_address();
|
|
db.entry_point = exe.entry_point();
|
|
db.initial_gp = exe.header.initial_gp;
|
|
db.image_size = exe.code_size();
|
|
|
|
const uint32_t lo = exe.load_address();
|
|
const uint32_t hi = exe.analysis_end_address();
|
|
|
|
auto read_w = [&](uint32_t a) -> uint32_t {
|
|
auto w = exe.read_word(a);
|
|
return w.has_value() ? *w : 0u;
|
|
};
|
|
auto in_image = [&](uint32_t a) { return a >= lo && a + 3 < hi; };
|
|
|
|
// ---- pass 1: boundaries ------------------------------------------------
|
|
FunctionAnalyzer analyzer(exe);
|
|
analyzer.add_forced_entry(exe.entry_point());
|
|
for (uint32_t a : opts.extra_entries) analyzer.add_forced_entry(a);
|
|
|
|
FunctionAnalysisResult ar;
|
|
if (opts.exact_entries) {
|
|
std::vector<uint32_t> entries{exe.entry_point()};
|
|
entries.insert(entries.end(), opts.extra_entries.begin(),
|
|
opts.extra_entries.end());
|
|
ar = analyzer.analyze_exact_entries(entries);
|
|
} else {
|
|
ar = analyzer.analyze();
|
|
}
|
|
|
|
db.functions.reserve(ar.functions.size());
|
|
for (const auto& f : ar.functions) {
|
|
FunctionRecord r;
|
|
r.addr = f.start_addr;
|
|
r.end = f.end_addr;
|
|
r.size = (f.end_addr > f.start_addr) ? (f.end_addr - f.start_addr) : 0;
|
|
r.instruction_count = r.size / 4;
|
|
r.name = fmt::format("func_{:08X}", f.start_addr);
|
|
r.has_prologue = f.has_prologue;
|
|
r.has_epilogue = f.has_epilogue;
|
|
r.is_data = f.is_data_section;
|
|
r.alias_of = f.alias_walk_lo;
|
|
r.sig.stack_frame = f.stack_frame_size;
|
|
db.functions.push_back(std::move(r));
|
|
}
|
|
std::sort(db.functions.begin(), db.functions.end(),
|
|
[](const FunctionRecord& a, const FunctionRecord& b) {
|
|
return a.addr < b.addr;
|
|
});
|
|
db.functions.erase(
|
|
std::unique(db.functions.begin(), db.functions.end(),
|
|
[](const FunctionRecord& a, const FunctionRecord& b) {
|
|
return a.addr == b.addr;
|
|
}),
|
|
db.functions.end());
|
|
|
|
std::unordered_map<uint32_t, size_t> index;
|
|
for (size_t i = 0; i < db.functions.size(); ++i)
|
|
index[db.functions[i].addr] = i;
|
|
|
|
auto containing_idx = [&](uint32_t pc) -> long {
|
|
auto it = std::upper_bound(db.functions.begin(), db.functions.end(), pc,
|
|
[](uint32_t v, const FunctionRecord& f) { return v < f.addr; });
|
|
if (it == db.functions.begin()) return -1;
|
|
--it;
|
|
if (pc >= it->addr && pc < it->end)
|
|
return static_cast<long>(it - db.functions.begin());
|
|
return -1;
|
|
};
|
|
|
|
// ---- pass 2: per-function decode, CFG, edges, refs, signature ----------
|
|
std::unordered_set<uint32_t> callee_set; // for in_degree
|
|
std::vector<std::unordered_set<uint32_t>> callers(db.functions.size());
|
|
std::vector<std::unordered_set<uint32_t>> callees(db.functions.size());
|
|
|
|
for (size_t fi = 0; fi < db.functions.size(); ++fi) {
|
|
FunctionRecord& f = db.functions[fi];
|
|
if (f.is_data || f.size == 0) continue;
|
|
|
|
// Block leaders: entry, every intra-range branch/jump target, and the
|
|
// instruction after each branch's delay slot.
|
|
std::set<uint32_t> leaders{f.addr};
|
|
std::vector<DecodedInstruction> code;
|
|
code.reserve(f.instruction_count);
|
|
for (uint32_t pc = f.addr; pc < f.end; pc += 4) {
|
|
if (!in_image(pc)) break;
|
|
DecodedInstruction d = MipsDecoder::decode(read_w(pc), pc);
|
|
if (d.format == InstrFormat::UNKNOWN) {
|
|
f.partial = true;
|
|
if (f.undecoded_pcs.size() < 64) f.undecoded_pcs.push_back(pc);
|
|
db.stats.undecoded_words++;
|
|
}
|
|
code.push_back(d);
|
|
}
|
|
for (const auto& d : code) {
|
|
if (d.is_branch) {
|
|
if (d.branch_target >= f.addr && d.branch_target < f.end)
|
|
leaders.insert(d.branch_target);
|
|
if (d.address + 8 < f.end) leaders.insert(d.address + 8);
|
|
} else if (d.opcode == 0x02) { // J
|
|
if (d.jump_target >= f.addr && d.jump_target < f.end)
|
|
leaders.insert(d.jump_target);
|
|
if (d.address + 8 < f.end) leaders.insert(d.address + 8);
|
|
} else if (d.is_jump) {
|
|
if (d.address + 8 < f.end) leaders.insert(d.address + 8);
|
|
}
|
|
}
|
|
f.block_leaders.assign(leaders.begin(), leaders.end());
|
|
|
|
// Terminal shape.
|
|
for (auto it = code.rbegin(); it != code.rend(); ++it) {
|
|
if (it->is_nop) continue;
|
|
if (it->is_jr_ra) { f.ends_jr_ra = true; }
|
|
break;
|
|
}
|
|
if (!f.ends_jr_ra) {
|
|
for (const auto& d : code) if (d.is_jr_ra) { f.ends_jr_ra = true; break; }
|
|
}
|
|
|
|
// Signature scan + edge/ref collection in one walk.
|
|
uint32_t defined = 0; // registers written so far
|
|
uint32_t arg_mask = 0;
|
|
bool saw_backward_branch = false;
|
|
uint32_t hi_val[32] = {0};
|
|
bool hi_ok[32] = {false};
|
|
|
|
for (size_t i = 0; i < code.size(); ++i) {
|
|
const DecodedInstruction& d = code[i];
|
|
if (leaders.count(d.address)) {
|
|
std::memset(hi_ok, 0, sizeof(hi_ok));
|
|
}
|
|
|
|
db.stats.total_instructions++;
|
|
if (d.mnemonic) db.stats.opcode_histogram[d.mnemonic]++;
|
|
|
|
RegEffect e = reg_effect(d);
|
|
for (uint8_t r = REG_A0; r <= REG_A3; ++r) {
|
|
if ((e.reads & (1u << r)) && !(defined & (1u << r)))
|
|
arg_mask |= (1u << (r - REG_A0));
|
|
}
|
|
if (e.reads & (1u << REG_GP)) f.sig.reads_gp = true;
|
|
if (e.writes & (1u << REG_V0)) f.sig.returns_v0 = true;
|
|
if (e.writes & (1u << REG_V1)) f.sig.returns_v1 = true;
|
|
defined |= e.writes;
|
|
|
|
if (d.is_branch && d.branch_target <= d.address)
|
|
saw_backward_branch = true;
|
|
if (d.opcode == 0x12) f.sig.uses_gte = true;
|
|
if (d.is_syscall) f.sig.uses_syscall = true;
|
|
if (d.is_break) f.sig.uses_break = true;
|
|
|
|
// Callee-saved: `sw sN/ra/fp, off($sp)` inside the frame.
|
|
if (d.opcode == 0x2B && d.rs == REG_SP) {
|
|
if ((d.rt >= REG_S0 && d.rt <= REG_S7) || d.rt == REG_FP ||
|
|
d.rt == REG_RA)
|
|
f.sig.saved_mask |= (1u << d.rt);
|
|
}
|
|
|
|
// --- constant tracking for data refs / address-taken ------------
|
|
if (d.opcode == 0x0F) { // LUI
|
|
hi_val[d.rt] = static_cast<uint32_t>(d.uimm16) << 16;
|
|
hi_ok[d.rt] = true;
|
|
} else {
|
|
uint32_t resolved = 0;
|
|
bool have = false;
|
|
bool materialize = false;
|
|
|
|
if (d.opcode == 0x09 && hi_ok[d.rs]) { // ADDIU rt, rs(hi), imm
|
|
resolved = hi_val[d.rs] + static_cast<uint32_t>(d.sign_ext_imm);
|
|
have = true;
|
|
materialize = true;
|
|
} else if ((is_load_op(d.opcode) || is_store_op(d.opcode))) {
|
|
if (hi_ok[d.rs]) {
|
|
resolved = hi_val[d.rs] +
|
|
static_cast<uint32_t>(d.sign_ext_imm);
|
|
have = true;
|
|
} else if (d.rs == REG_GP && db.initial_gp) {
|
|
resolved = db.initial_gp +
|
|
static_cast<uint32_t>(d.sign_ext_imm);
|
|
have = true;
|
|
}
|
|
}
|
|
|
|
if (have && opts.collect_data_refs) {
|
|
DataRef ref;
|
|
ref.from_func = f.addr;
|
|
ref.site_pc = d.address;
|
|
ref.target = resolved;
|
|
ref.is_write = is_store_op(d.opcode);
|
|
ref.width = static_cast<uint8_t>(mem_width(d.opcode));
|
|
ref.kind = materialize ? "addr"
|
|
: classify_target(resolved, lo, hi);
|
|
if (ref.kind == "mmio") f.sig.touches_mmio = true;
|
|
db.data_refs.push_back(std::move(ref));
|
|
}
|
|
if (materialize) {
|
|
auto ti = index.find(resolved);
|
|
if (ti != index.end()) {
|
|
db.functions[ti->second].address_taken = true;
|
|
db.edges.push_back({f.addr, d.address, resolved,
|
|
CallEdge::Kind::AddressTaken});
|
|
callers[ti->second].insert(f.addr);
|
|
callees[fi].insert(resolved);
|
|
}
|
|
}
|
|
|
|
// Invalidate any hi constant this instruction clobbers.
|
|
for (uint8_t r = 1; r < 32; ++r)
|
|
if ((e.writes & (1u << r)) && !(d.opcode == 0x09 && r == d.rt && hi_ok[d.rs]))
|
|
hi_ok[r] = false;
|
|
if (d.opcode == 0x09 && hi_ok[d.rs] && d.rt != d.rs)
|
|
hi_ok[d.rt] = false; // the sum is an address, not a hi part
|
|
}
|
|
|
|
// --- call edges --------------------------------------------------
|
|
if (d.opcode == 0x03) { // JAL
|
|
f.sig.is_leaf = false;
|
|
db.edges.push_back({f.addr, d.address, d.jump_target,
|
|
CallEdge::Kind::Direct});
|
|
db.stats.direct_edges++;
|
|
callees[fi].insert(d.jump_target);
|
|
auto ti = index.find(d.jump_target);
|
|
if (ti != index.end()) callers[ti->second].insert(f.addr);
|
|
} else if (d.opcode == 0x00 && d.funct == 0x09) { // JALR
|
|
f.sig.is_leaf = false;
|
|
}
|
|
}
|
|
|
|
f.sig.arg_mask = static_cast<uint8_t>(arg_mask);
|
|
f.sig.arg_count = 0;
|
|
for (int i = 0; i < 4; ++i) {
|
|
if (arg_mask & (1u << i)) f.sig.arg_count = i + 1;
|
|
}
|
|
f.sig.sig_confident = !saw_backward_branch && !f.partial;
|
|
}
|
|
|
|
// ---- pass 2.5: PSY-Q kernel dispatch thunks ---------------------------
|
|
// Shape: an immediate load of 0xA0/0xB0/0xC0 into some register, a `jr` on
|
|
// that register, and an immediate load of the call index into $t1. This is
|
|
// an exact pattern, not a heuristic, so a match is Verified — which matters
|
|
// because the generic rules score these stubs `low` (no prologue, no
|
|
// jr $ra) despite them being among the most-called code in any image.
|
|
for (auto& f : db.functions) {
|
|
if (f.is_data || f.size < 12 || f.size > 32) continue;
|
|
uint32_t table = 0, idx = 0, tbl_reg = 32;
|
|
bool have_jr = false;
|
|
for (uint32_t pc = f.addr; pc < f.end && pc < f.addr + 16; pc += 4) {
|
|
if (!in_image(pc)) break;
|
|
DecodedInstruction d = MipsDecoder::decode(read_w(pc), pc);
|
|
const bool imm_load = (d.opcode == 0x09 || d.opcode == 0x0D) &&
|
|
d.rs == REG_ZERO; // ADDIU/ORI rt, $zero, k
|
|
if (imm_load) {
|
|
if (d.uimm16 == 0xA0 || d.uimm16 == 0xB0 || d.uimm16 == 0xC0) {
|
|
table = d.uimm16;
|
|
tbl_reg = d.rt;
|
|
} else if (d.rt == 9) { // $t1 carries the index
|
|
idx = d.uimm16;
|
|
}
|
|
} else if (d.opcode == 0x00 && d.funct == 0x08 && d.rs == tbl_reg) {
|
|
have_jr = true;
|
|
}
|
|
}
|
|
if (!table || !have_jr) continue;
|
|
|
|
const char* nm = bios_call_name(table, idx);
|
|
f.bios_call = fmt::format("{:02X}:{:02X}{}{}", table, idx,
|
|
*nm ? " " : "", nm);
|
|
f.name = *nm ? fmt::format("bios_{:02X}_{:02X}_{}", table, idx, nm)
|
|
: fmt::format("bios_{:02X}_{:02X}", table, idx);
|
|
f.confidence = Confidence::Verified;
|
|
f.confidence_reason =
|
|
fmt::format("PSY-Q kernel dispatch thunk to {:02X}({:02X}h)",
|
|
table, idx);
|
|
f.sig.prototype = fmt::format("/* kernel {:02X}({:02X}h) */ {}",
|
|
table, idx, f.name);
|
|
}
|
|
|
|
// ---- pass 3: indirect sites + static jump-table recovery ---------------
|
|
for (size_t fi = 0; fi < db.functions.size(); ++fi) {
|
|
FunctionRecord& f = db.functions[fi];
|
|
if (f.is_data || f.size == 0) continue;
|
|
for (uint32_t pc = f.addr; pc < f.end; pc += 4) {
|
|
if (!in_image(pc)) break;
|
|
DecodedInstruction d = MipsDecoder::decode(read_w(pc), pc);
|
|
const bool is_jr = (d.opcode == 0x00 && d.funct == 0x08);
|
|
const bool is_jalr = (d.opcode == 0x00 && d.funct == 0x09);
|
|
if (!is_jr && !is_jalr) continue;
|
|
if (is_jr && d.rs == REG_RA) continue; // ordinary return
|
|
|
|
IndirectSite site;
|
|
site.from_func = f.addr;
|
|
site.pc = pc;
|
|
site.reg = d.rs;
|
|
site.kind = is_jr ? "jr" : "jalr";
|
|
site.classification = "unresolved";
|
|
|
|
// The `jr` inside a recognized kernel thunk IS the dispatch — its
|
|
// target is the A0/B0/C0 vector, which pass 2.5 already identified
|
|
// exactly. Leaving it in the unresolved bucket would inflate the
|
|
// coverage gap with the one class of indirect transfer the tool
|
|
// understands best.
|
|
if (!f.bios_call.empty()) {
|
|
site.classification = fmt::format("bios_dispatch:{}", f.bios_call);
|
|
db.indirect.push_back(std::move(site));
|
|
continue;
|
|
}
|
|
|
|
if (is_jr && opts.resolve_jump_tables) {
|
|
// The emitter's proven form first; the general slice walk only
|
|
// if it declines. Provenance is kept in `classification` so a
|
|
// consumer can tell a proven table from an inferred one.
|
|
ExactJumpTable table;
|
|
if (resolve_exact_bounded_jump_table(exe, f.addr, f.end, pc,
|
|
d.rs, table) &&
|
|
table.table_base && table.table_count) {
|
|
site.classification = "jump_table:proven";
|
|
site.table_base = table.table_base;
|
|
site.table_count = table.table_count;
|
|
for (const auto& t : table.targets)
|
|
site.targets.push_back(t.second);
|
|
} else {
|
|
RecoveredTable rt;
|
|
if (recover_jump_table(exe, f.addr, f.end, pc, d.rs, index,
|
|
rt)) {
|
|
site.classification =
|
|
fmt::format("jump_table:{}", rt.method);
|
|
site.table_base = rt.base;
|
|
site.table_count = rt.count;
|
|
site.targets = rt.targets;
|
|
}
|
|
}
|
|
|
|
if (!site.targets.empty()) {
|
|
for (uint32_t t : site.targets) {
|
|
if (t >= f.addr && t < f.end) {
|
|
// Intra-function switch case: control flow, not a
|
|
// call. It becomes a block leader instead of an edge.
|
|
f.block_leaders.push_back(t);
|
|
continue;
|
|
}
|
|
db.edges.push_back({f.addr, pc, t,
|
|
CallEdge::Kind::JumpTable});
|
|
callees[fi].insert(t);
|
|
auto ti = index.find(t);
|
|
if (ti != index.end()) callers[ti->second].insert(f.addr);
|
|
}
|
|
std::sort(f.block_leaders.begin(), f.block_leaders.end());
|
|
f.block_leaders.erase(
|
|
std::unique(f.block_leaders.begin(), f.block_leaders.end()),
|
|
f.block_leaders.end());
|
|
db.stats.jump_tables_resolved++;
|
|
db.stats.jump_table_targets +=
|
|
static_cast<uint32_t>(site.targets.size());
|
|
}
|
|
}
|
|
|
|
if (site.classification == "unresolved") {
|
|
uint32_t t = 0;
|
|
const char* how = "";
|
|
if (recover_indirect_call(exe, f.addr, pc, d.rs, index, t, how)) {
|
|
site.classification = fmt::format("call_ptr:{}", how);
|
|
site.targets.push_back(t);
|
|
db.edges.push_back({f.addr, pc, t,
|
|
CallEdge::Kind::Indirect});
|
|
callees[fi].insert(t);
|
|
auto ti = index.find(t);
|
|
if (ti != index.end()) callers[ti->second].insert(f.addr);
|
|
}
|
|
}
|
|
|
|
if (site.classification == "unresolved") {
|
|
f.unresolved_indirect++;
|
|
db.stats.indirect_unresolved++;
|
|
uint32_t ctx_lo = (pc >= f.addr + 64) ? pc - 64 : f.addr;
|
|
site.context = disassemble_range(exe, ctx_lo, pc + 8, nullptr);
|
|
}
|
|
db.indirect.push_back(std::move(site));
|
|
}
|
|
}
|
|
|
|
// ---- pass 4: pointer tables in data -----------------------------------
|
|
// A run of >=2 consecutive 4-aligned words each naming a distinct known
|
|
// function start is treated as a dispatch table. A single isolated word is
|
|
// NOT: at this density a lone match is as likely to be a coincidental
|
|
// integer, and a false function pointer is worse than a missing one.
|
|
{
|
|
uint32_t run_start = 0;
|
|
std::vector<uint32_t> run;
|
|
auto flush = [&]() {
|
|
if (run.size() >= 2) {
|
|
for (size_t k = 0; k < run.size(); ++k) {
|
|
auto ti = index.find(run[k]);
|
|
if (ti == index.end()) continue;
|
|
db.functions[ti->second].address_taken = true;
|
|
db.edges.push_back({0,
|
|
run_start + static_cast<uint32_t>(k * 4),
|
|
run[k], CallEdge::Kind::AddressTaken});
|
|
}
|
|
}
|
|
run.clear();
|
|
};
|
|
for (uint32_t a = lo; a + 3 < hi; a += 4) {
|
|
uint32_t w = read_w(a);
|
|
if (index.count(w)) {
|
|
if (run.empty()) run_start = a;
|
|
run.push_back(w);
|
|
} else {
|
|
flush();
|
|
}
|
|
}
|
|
flush();
|
|
}
|
|
|
|
// ---- pass 5: reachability from the EXE entry point ---------------------
|
|
{
|
|
std::unordered_map<uint32_t, std::vector<uint32_t>> succ;
|
|
// Every edge kind here is statically proven — an Indirect edge only
|
|
// exists when the pointer's value was resolved — so all of them carry
|
|
// reachability. Nothing is reached "because the runtime saw it".
|
|
for (const auto& e : db.edges)
|
|
succ[e.from_func].push_back(e.to_addr);
|
|
long ei = containing_idx(db.entry_point);
|
|
std::queue<uint32_t> q;
|
|
std::unordered_set<uint32_t> seen;
|
|
if (ei >= 0) {
|
|
q.push(db.functions[ei].addr);
|
|
seen.insert(db.functions[ei].addr);
|
|
}
|
|
// Pointer-table edges have from_func == 0 (no owning function); seed
|
|
// their targets so a table-only-reachable handler is not called an
|
|
// orphan.
|
|
for (const auto& e : db.edges) {
|
|
if (e.from_func == 0 && seen.insert(e.to_addr).second)
|
|
q.push(e.to_addr);
|
|
}
|
|
while (!q.empty()) {
|
|
uint32_t cur = q.front(); q.pop();
|
|
auto it = succ.find(cur);
|
|
if (it == succ.end()) continue;
|
|
for (uint32_t nx : it->second)
|
|
if (index.count(nx) && seen.insert(nx).second) q.push(nx);
|
|
}
|
|
for (auto& f : db.functions) f.reachable = seen.count(f.addr) > 0;
|
|
}
|
|
|
|
// ---- pass 6: degrees ---------------------------------------------------
|
|
for (size_t i = 0; i < db.functions.size(); ++i) {
|
|
db.functions[i].in_degree =
|
|
static_cast<uint32_t>(callers[i].size());
|
|
db.functions[i].out_degree =
|
|
static_cast<uint32_t>(callees[i].size());
|
|
}
|
|
|
|
// ---- pass 7: symbols ---------------------------------------------------
|
|
if (!opts.symbols_toml.empty()) {
|
|
std::vector<SymbolEntry> syms;
|
|
std::string serr;
|
|
if (!load_symbols(opts.symbols_toml, syms, serr)) {
|
|
error = serr;
|
|
return db;
|
|
}
|
|
for (const auto& s : syms) {
|
|
auto it = index.find(s.pc);
|
|
if (it == index.end()) continue;
|
|
FunctionRecord& f = db.functions[it->second];
|
|
f.name = s.name;
|
|
f.user_named = true;
|
|
f.status = s.status;
|
|
f.note = s.note;
|
|
}
|
|
}
|
|
|
|
// ---- pass 8: confidence + prototypes ----------------------------------
|
|
for (auto& f : db.functions) {
|
|
if (!f.bios_call.empty()) continue; // pass 2.5 already decided
|
|
if (f.is_data) {
|
|
f.confidence = Confidence::DataRegion;
|
|
f.confidence_reason = "classified as data";
|
|
} else if (f.partial) {
|
|
f.confidence = Confidence::Low;
|
|
f.confidence_reason = fmt::format(
|
|
"{} word(s) did not decode", f.undecoded_pcs.size());
|
|
} else if (f.has_prologue && f.has_epilogue && f.ends_jr_ra &&
|
|
f.reachable && f.in_degree > 0) {
|
|
f.confidence = Confidence::Verified;
|
|
f.confidence_reason =
|
|
"prologue + epilogue + jr $ra, called from reachable code";
|
|
} else if (f.ends_jr_ra && f.reachable) {
|
|
f.confidence = Confidence::High;
|
|
f.confidence_reason = "jr $ra exit, reachable from entry";
|
|
} else if (f.has_prologue || f.address_taken) {
|
|
f.confidence = Confidence::Medium;
|
|
f.confidence_reason = f.address_taken
|
|
? "address taken but no call-graph path from entry"
|
|
: "prologue-shaped, no proven call path";
|
|
} else {
|
|
f.confidence = Confidence::Low;
|
|
f.confidence_reason = f.reachable
|
|
? "reachable but no prologue and no jr $ra exit"
|
|
: "no prologue, no jr $ra exit, unreachable from entry";
|
|
}
|
|
f.sig.prototype = render_prototype(f);
|
|
}
|
|
|
|
// ---- stats -------------------------------------------------------------
|
|
db.stats.total_functions = static_cast<uint32_t>(db.functions.size());
|
|
db.stats.bytes_image = hi - lo;
|
|
for (const auto& f : db.functions) {
|
|
db.stats.confidence_counts[static_cast<int>(f.confidence)]++;
|
|
if (f.reachable) db.stats.reachable_functions++;
|
|
else db.stats.orphan_functions++;
|
|
if (f.user_named) db.stats.named_functions++;
|
|
if (f.partial) db.stats.partial_functions++;
|
|
if (!f.is_data) db.stats.bytes_covered += f.size;
|
|
}
|
|
|
|
std::sort(db.edges.begin(), db.edges.end(),
|
|
[](const CallEdge& a, const CallEdge& b) {
|
|
if (a.from_func != b.from_func) return a.from_func < b.from_func;
|
|
return a.site_pc < b.site_pc;
|
|
});
|
|
std::sort(db.data_refs.begin(), db.data_refs.end(),
|
|
[](const DataRef& a, const DataRef& b) {
|
|
return a.site_pc < b.site_pc;
|
|
});
|
|
std::sort(db.indirect.begin(), db.indirect.end(),
|
|
[](const IndirectSite& a, const IndirectSite& b) {
|
|
return a.pc < b.pc;
|
|
});
|
|
return db;
|
|
}
|
|
|
|
std::vector<std::string> disassemble_range(const PS1Executable& exe,
|
|
uint32_t lo, uint32_t hi,
|
|
const AnalysisDb* db) {
|
|
std::vector<std::string> out;
|
|
for (uint32_t pc = lo; pc < hi; pc += 4) {
|
|
auto w = exe.read_word(pc);
|
|
if (!w.has_value()) break;
|
|
DecodedInstruction d = MipsDecoder::decode(*w, pc);
|
|
out.push_back(fmt::format("{:08X} {:08X} {}", pc, *w,
|
|
format_instr(d, db)));
|
|
}
|
|
return out;
|
|
}
|
|
|
|
} // namespace PSXRecomp::Analysis
|