Compare commits
1 Commits
cleanup/se
...
agent/bitt
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
4ce997995d |
213
tools/decomp-assist/jump_table_diff.py
Normal file
213
tools/decomp-assist/jump_table_diff.py
Normal file
@@ -0,0 +1,213 @@
|
||||
"""Compare relocated switch destinations after checking instructions with ctxdiff.
|
||||
|
||||
Usage: python jump_table_diff.py <unit> <function> [--table <reference-symbol>]
|
||||
Paths follow ctxdiff.py: build/43U/{src,obj}/<unit>.o. Requires pyelftools.
|
||||
Exit 0: all selected tables match (or no tables); 1: mismatch; 2: invalid or
|
||||
ambiguous input. This checks relative destinations, not behavioral equivalence.
|
||||
|
||||
Automatic selection covers local jumptable_* symbols whose R_PPC_ADDR32 entries
|
||||
all target the selected function. External callback tables/vtables are not
|
||||
covered. Source locations are inferred from corresponding function relocations,
|
||||
never from an assumption that both data sections have the same layout.
|
||||
"""
|
||||
|
||||
import argparse
|
||||
from dataclasses import dataclass
|
||||
from pathlib import Path
|
||||
import sys
|
||||
|
||||
from elftools.common.exceptions import ELFError
|
||||
from elftools.elf.elffile import ELFFile
|
||||
|
||||
|
||||
@dataclass(frozen=True)
|
||||
class Symbol:
|
||||
name: str
|
||||
section: object
|
||||
value: int
|
||||
size: int
|
||||
kind: str = "STT_OBJECT"
|
||||
|
||||
|
||||
@dataclass(frozen=True)
|
||||
class Relocation:
|
||||
offset: int
|
||||
kind: int
|
||||
symbol: int
|
||||
addend: int
|
||||
|
||||
|
||||
@dataclass
|
||||
class ObjectInfo:
|
||||
sections: dict
|
||||
symbols: list
|
||||
relocations: dict
|
||||
|
||||
def symbol(self, name):
|
||||
found = [s for s in self.symbols if s.name == name
|
||||
and isinstance(s.section, int) and s.size]
|
||||
if len(found) != 1:
|
||||
raise ValueError("expected one defined symbol: " + name)
|
||||
symbol = found[0]
|
||||
if (symbol.section not in self.sections or symbol.value < 0
|
||||
or symbol.size <= 0
|
||||
or symbol.value + symbol.size > self.sections[symbol.section][1]):
|
||||
raise ValueError("symbol is outside its section: " + name)
|
||||
return symbol
|
||||
|
||||
def location(self, relocation):
|
||||
if not 0 <= relocation.symbol < len(self.symbols):
|
||||
raise ValueError("relocation symbol index is out of range")
|
||||
symbol = self.symbols[relocation.symbol]
|
||||
if not isinstance(symbol.section, int):
|
||||
return None
|
||||
if symbol.section not in self.sections:
|
||||
raise ValueError("relocation symbol has an invalid section")
|
||||
return symbol.section, symbol.value + relocation.addend
|
||||
|
||||
def relocs(self, section):
|
||||
return self.relocations.get(section, {})
|
||||
|
||||
|
||||
def read_object(path):
|
||||
with open(path, "rb") as stream:
|
||||
elf = ELFFile(stream)
|
||||
if (elf.elfclass != 32 or elf.little_endian
|
||||
or elf["e_machine"] != "EM_PPC" or elf["e_type"] != "ET_REL"):
|
||||
raise ValueError("expected a relocatable big-endian ELF32 PowerPC object")
|
||||
symtab = elf.get_section_by_name(".symtab")
|
||||
if symtab is None:
|
||||
raise ValueError("object has no .symtab")
|
||||
symbols = [Symbol(s.name, s["st_shndx"], s["st_value"], s["st_size"],
|
||||
s["st_info"]["type"]) for s in symtab.iter_symbols()]
|
||||
sections = {}
|
||||
relocations = {}
|
||||
for index, section in enumerate(elf.iter_sections()):
|
||||
sections[index] = (section.name, section["sh_size"])
|
||||
if section["sh_type"] == "SHT_REL":
|
||||
raise ValueError("REL relocations are unsupported; expected RELA")
|
||||
if section["sh_type"] != "SHT_RELA":
|
||||
continue
|
||||
if elf.get_section(section["sh_link"]).name != ".symtab":
|
||||
raise ValueError("relocation uses a different symbol table")
|
||||
entries = relocations.setdefault(section["sh_info"], {})
|
||||
for r in section.iter_relocations():
|
||||
if r["r_offset"] in entries:
|
||||
raise ValueError("multiple relocations at the same offset")
|
||||
entries[r["r_offset"]] = Relocation(
|
||||
r["r_offset"], r["r_info_type"], r["r_info_sym"], r["r_addend"])
|
||||
return ObjectInfo(sections, symbols, relocations)
|
||||
|
||||
|
||||
def jump_target(obj, relocation, function):
|
||||
if relocation is None or relocation.kind != 1: # R_PPC_ADDR32
|
||||
return None
|
||||
location = obj.location(relocation)
|
||||
if location is None or location[0] != function.section:
|
||||
return None
|
||||
offset = location[1] - function.value
|
||||
if offset < 0 or offset >= function.size or offset % 4:
|
||||
return None
|
||||
return offset
|
||||
|
||||
|
||||
def reference_tables(obj, function, name=None):
|
||||
candidates = [obj.symbol(name)] if name else [
|
||||
s for s in obj.symbols if s.name.startswith("jumptable_") and s.size]
|
||||
result = []
|
||||
for table in candidates:
|
||||
if not isinstance(table.section, int) or table.size % 4:
|
||||
if name:
|
||||
raise ValueError("invalid reference table extent")
|
||||
continue
|
||||
section_size = obj.sections[table.section][1]
|
||||
if table.value < 0 or table.value + table.size > section_size:
|
||||
raise ValueError("reference table is outside its section")
|
||||
targets = [jump_target(obj, obj.relocs(table.section).get(offset), function)
|
||||
for offset in range(table.value, table.value + table.size, 4)]
|
||||
if targets and all(target is not None for target in targets):
|
||||
result.append((table, targets))
|
||||
elif name:
|
||||
raise ValueError("reference table does not target the selected function")
|
||||
return result
|
||||
|
||||
|
||||
def source_table_location(source, reference, source_fn, reference_fn, table):
|
||||
if source_fn.size != reference_fn.size:
|
||||
raise ValueError("function sizes differ; check ctxdiff before table matching")
|
||||
locations = set()
|
||||
for relocation in reference.relocs(reference_fn.section).values():
|
||||
if not reference_fn.value <= relocation.offset < reference_fn.value + reference_fn.size:
|
||||
continue
|
||||
if reference.location(relocation) != (table.section, table.value):
|
||||
continue
|
||||
offset = source_fn.value + relocation.offset - reference_fn.value
|
||||
other = source.relocs(source_fn.section).get(offset)
|
||||
if other is None or other.kind != relocation.kind:
|
||||
raise ValueError("table-reference relocations differ; check ctxdiff")
|
||||
location = source.location(other)
|
||||
if location is None:
|
||||
raise ValueError("source table reference is undefined")
|
||||
if source.sections[location[0]][0] != reference.sections[table.section][0]:
|
||||
raise ValueError("source table resolves to a different section")
|
||||
locations.add(location)
|
||||
if len(locations) != 1:
|
||||
raise ValueError("cannot infer one source table from function relocations")
|
||||
section, offset = next(iter(locations))
|
||||
sizes = {s.size for s in source.symbols if s.section == section
|
||||
and s.value == offset and s.size and s.kind != "STT_SECTION"}
|
||||
if len(sizes) != 1:
|
||||
raise ValueError("source table extent is missing or ambiguous")
|
||||
size = next(iter(sizes))
|
||||
if size % 4 or offset < 0 or offset + size > source.sections[section][1]:
|
||||
raise ValueError("invalid source table extent")
|
||||
return section, offset, size
|
||||
|
||||
|
||||
def compare_table(source, reference, source_fn, reference_fn, table, expected):
|
||||
section, offset, size = source_table_location(
|
||||
source, reference, source_fn, reference_fn, table)
|
||||
actual = [jump_target(source, source.relocs(section).get(i), source_fn)
|
||||
for i in range(offset, offset + size, 4)]
|
||||
differences = []
|
||||
for i in range(max(len(actual), len(expected))):
|
||||
src = actual[i] if i < len(actual) else None
|
||||
ref = expected[i] if i < len(expected) else None
|
||||
if i >= min(len(actual), len(expected)) or src != ref:
|
||||
differences.append((i, src, ref))
|
||||
return actual, differences
|
||||
|
||||
|
||||
def main(argv=None):
|
||||
parser = argparse.ArgumentParser(description=__doc__)
|
||||
parser.add_argument("unit", help="e.g. src/scene/sdChannelSelect/iplSDChannelSelect")
|
||||
parser.add_argument("function", help="exact function symbol used by ctxdiff")
|
||||
parser.add_argument("--table", help="optional exact reference jump-table symbol")
|
||||
args = parser.parse_args(argv)
|
||||
try:
|
||||
source = read_object(Path("build/43U/src") / (args.unit + ".o"))
|
||||
reference = read_object(Path("build/43U/obj") / (args.unit + ".o"))
|
||||
source_fn = source.symbol(args.function)
|
||||
reference_fn = reference.symbol(args.function)
|
||||
tables = reference_tables(reference, reference_fn, args.table)
|
||||
mismatch = False
|
||||
for table, expected in tables:
|
||||
actual, differences = compare_table(
|
||||
source, reference, source_fn, reference_fn, table, expected)
|
||||
matched = sum(a == b for a, b in zip(actual, expected))
|
||||
print("%s: %d/%d entries match (source=%d reference=%d)" %
|
||||
(table.name, matched, len(expected), len(actual), len(expected)))
|
||||
for index, src, ref in differences:
|
||||
src_text = "unresolved/missing" if src is None else "+0x%X" % src
|
||||
ref_text = "missing" if ref is None else "+0x%X" % ref
|
||||
print(" [%d] source %s; reference %s" % (index, src_text, ref_text))
|
||||
mismatch |= bool(differences)
|
||||
print("Compared %d jump table(s); instruction correctness requires ctxdiff." % len(tables))
|
||||
return 1 if mismatch else 0
|
||||
except (OSError, ValueError, ELFError) as error:
|
||||
print("ERROR: %s" % error, file=sys.stderr)
|
||||
return 2
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
sys.exit(main())
|
||||
159
tools/decomp-assist/test_jump_table_diff.py
Normal file
159
tools/decomp-assist/test_jump_table_diff.py
Normal file
@@ -0,0 +1,159 @@
|
||||
import contextlib
|
||||
from dataclasses import replace
|
||||
import io
|
||||
import unittest
|
||||
from unittest.mock import patch
|
||||
|
||||
import jump_table_diff as tool
|
||||
|
||||
|
||||
def fixture(entries=(0x10, 0x20, 0x30), function_offset=0x100,
|
||||
table_offset=0x40, source=False, section_ids=(1, 2)):
|
||||
text, data = section_ids
|
||||
symbols = [
|
||||
tool.Symbol("dispatch", text, function_offset, 0x80, "STT_FUNC"),
|
||||
tool.Symbol("@123" if source else "jumptable_test", data,
|
||||
table_offset, len(entries) * 4),
|
||||
]
|
||||
references = {
|
||||
text: {
|
||||
function_offset + 2: tool.Relocation(function_offset + 2, 6, 1, 0),
|
||||
function_offset + 6: tool.Relocation(function_offset + 6, 4, 1, 0),
|
||||
},
|
||||
data: {table_offset + i * 4: tool.Relocation(table_offset + i * 4, 1, 0, value)
|
||||
for i, value in enumerate(entries)},
|
||||
}
|
||||
return tool.ObjectInfo({text: (".text", 0x1000), data: (".data", 0x1000)},
|
||||
symbols, references)
|
||||
|
||||
|
||||
def compare(source, reference=None):
|
||||
reference = reference or fixture()
|
||||
src_fn = source.symbol("dispatch")
|
||||
ref_fn = reference.symbol("dispatch")
|
||||
table, expected = tool.reference_tables(reference, ref_fn, "jumptable_test")[0]
|
||||
return tool.compare_table(source, reference, src_fn, ref_fn, table, expected)
|
||||
|
||||
|
||||
class JumpTableTests(unittest.TestCase):
|
||||
def test_infers_shifted_source_table_and_function(self):
|
||||
source = fixture(source=True, function_offset=0x200, table_offset=0x90,
|
||||
section_ids=(3, 4))
|
||||
self.assertEqual(compare(source), ([0x10, 0x20, 0x30], []))
|
||||
|
||||
def test_detects_swapped_destinations_despite_same_function_size(self):
|
||||
actual, differences = compare(fixture((0x20, 0x10, 0x30), source=True))
|
||||
self.assertEqual(actual, [0x20, 0x10, 0x30])
|
||||
self.assertEqual(differences, [(0, 0x20, 0x10), (1, 0x10, 0x20)])
|
||||
|
||||
def test_section_relative_code_reference(self):
|
||||
source = fixture(source=True, table_offset=0x90)
|
||||
source.symbols.append(tool.Symbol("", 2, 0, 0, "STT_SECTION"))
|
||||
for offset, relocation in list(source.relocations[1].items()):
|
||||
source.relocations[1][offset] = replace(relocation, symbol=2, addend=0x90)
|
||||
self.assertEqual(compare(source)[1], [])
|
||||
|
||||
def test_section_relative_table_entries(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols.append(tool.Symbol("", 1, 0, 0, "STT_SECTION"))
|
||||
for offset, relocation in list(source.relocations[2].items()):
|
||||
source.relocations[2][offset] = replace(
|
||||
relocation, symbol=2, addend=0x100 + relocation.addend)
|
||||
self.assertEqual(compare(source)[1], [])
|
||||
|
||||
def test_missing_entry_is_mismatch(self):
|
||||
source = fixture(source=True)
|
||||
del source.relocations[2][0x44]
|
||||
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
|
||||
|
||||
def test_wrong_relocation_kind_is_mismatch(self):
|
||||
source = fixture(source=True)
|
||||
source.relocations[2][0x44] = replace(source.relocations[2][0x44], kind=10)
|
||||
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
|
||||
|
||||
def test_out_of_function_destination_is_mismatch(self):
|
||||
source = fixture(source=True)
|
||||
source.relocations[2][0x44] = replace(source.relocations[2][0x44], addend=0x80)
|
||||
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
|
||||
|
||||
def test_extra_source_entry_is_not_a_pass(self):
|
||||
self.assertEqual(compare(fixture((0x10, 0x20, 0x30, 0x40), source=True))[1],
|
||||
[(3, 0x40, None)])
|
||||
|
||||
def test_short_source_table_is_not_a_pass(self):
|
||||
self.assertEqual(compare(fixture((0x10, 0x20), source=True))[1],
|
||||
[(2, None, 0x30)])
|
||||
|
||||
def test_different_function_sizes_reject_inference(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols[0] = replace(source.symbols[0], size=0x84)
|
||||
with self.assertRaisesRegex(ValueError, "function sizes differ"):
|
||||
compare(source)
|
||||
|
||||
def test_disagreeing_code_references_reject_inference(self):
|
||||
source = fixture(source=True)
|
||||
source.relocations[1][0x106] = replace(source.relocations[1][0x106], addend=4)
|
||||
with self.assertRaisesRegex(ValueError, "infer one source table"):
|
||||
compare(source)
|
||||
|
||||
def test_missing_code_reference_rejects_inference(self):
|
||||
source = fixture(source=True)
|
||||
del source.relocations[1][0x106]
|
||||
with self.assertRaisesRegex(ValueError, "table-reference relocations differ"):
|
||||
compare(source)
|
||||
|
||||
def test_ambiguous_source_extent_rejects_inference(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols.append(tool.Symbol("alias", 2, 0x40, 16))
|
||||
with self.assertRaisesRegex(ValueError, "extent is missing or ambiguous"):
|
||||
compare(source)
|
||||
|
||||
def test_different_source_section_rejects_inference(self):
|
||||
source = fixture(source=True)
|
||||
source.sections[2] = (".rodata", 0x1000)
|
||||
with self.assertRaisesRegex(ValueError, "different section"):
|
||||
compare(source)
|
||||
|
||||
def test_undefined_source_reference_rejects_inference(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols[1] = replace(source.symbols[1], section="SHN_UNDEF")
|
||||
with self.assertRaisesRegex(ValueError, "reference is undefined"):
|
||||
compare(source)
|
||||
|
||||
def test_invalid_relocation_symbol_rejected(self):
|
||||
source = fixture(source=True)
|
||||
source.relocations[2][0x44] = replace(source.relocations[2][0x44], symbol=999)
|
||||
with self.assertRaisesRegex(ValueError, "symbol index is out of range"):
|
||||
compare(source)
|
||||
|
||||
def test_duplicate_function_rejected(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols.append(source.symbols[0])
|
||||
with self.assertRaisesRegex(ValueError, "one defined symbol"):
|
||||
compare(source)
|
||||
|
||||
def test_out_of_section_symbol_rejected(self):
|
||||
source = fixture(source=True)
|
||||
source.symbols[0] = replace(source.symbols[0], size=0x2000)
|
||||
with self.assertRaisesRegex(ValueError, "outside its section"):
|
||||
compare(source)
|
||||
|
||||
def test_unrelated_reference_table_is_not_selected(self):
|
||||
reference = fixture((0x80, 0x84, 0x88))
|
||||
self.assertEqual(tool.reference_tables(reference, reference.symbol("dispatch")), [])
|
||||
with self.assertRaisesRegex(ValueError, "does not target"):
|
||||
tool.reference_tables(reference, reference.symbol("dispatch"), "jumptable_test")
|
||||
|
||||
def test_cli_exit_codes(self):
|
||||
for source, expected_status in [(fixture(source=True), 0),
|
||||
(fixture((0x20, 0x10, 0x30), source=True), 1)]:
|
||||
with patch.object(tool, "read_object", side_effect=[source, fixture()]):
|
||||
with contextlib.redirect_stdout(io.StringIO()):
|
||||
self.assertEqual(tool.main(["unused", "dispatch"]), expected_status)
|
||||
with patch.object(tool, "read_object", side_effect=ValueError("bad object")):
|
||||
with contextlib.redirect_stderr(io.StringIO()):
|
||||
self.assertEqual(tool.main(["unused", "dispatch"]), 2)
|
||||
|
||||
|
||||
if __name__ == "__main__":
|
||||
unittest.main()
|
||||
Reference in New Issue
Block a user