#!/usr/bin/env python3
"""Thread verified direct branches throughout an x86-64 executable."""

import argparse
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from hashlib import sha256
import json
import mmap
import os
from pathlib import Path
import runpy
import shutil
import struct
import subprocess
import sys
import tempfile


PROOF = runpy.run_path(str(Path(__file__).with_name("optimize-aot-elf")))
Elf = PROOF["Elf"]
require = PROOF["require"]
overlaps = PROOF["overlaps"]
instruction = PROOF["INSTRUCTION"]
branch_target = PROOF["branch_target"]
source_branch = PROOF["source_branch"]
jump = PROOF["jump"]
forwarded_target = PROOF["forwarded_target"]
cfi_scopes = PROOF["cfi_scopes"]
cfi_witness = PROOF["cfi_witness"]
tool = PROOF["tool"]
BLOCK = PROOF["BLOCK"]
FORMAT = "graalc-elf-wide-branch-threading-v1"


def relocation_sites(elf):
    sites = []
    for section in elf.sections:
        kind = section.kind
        require(kind != 19, "packed ELF relocations are unsupported")
        if kind == 6:  # SHT_DYNAMIC
            require(section.entry_size == 16 and section.size % 16 == 0, "invalid dynamic table")
            for pos in range(section.offset, section.offset + section.size, 16):
                tag, value = struct.unpack_from("<qQ", elf.data, pos)
                require(tag not in (22, 35, 36, 37) and not (tag == 30 and value & 4),
                        "ELF has text relocations or unsupported packed relocations")
        if kind in (4, 9):  # SHT_RELA or SHT_REL.
            width = 24 if kind == 4 else 16
            require(section.entry_size == width and section.size % width == 0,
                    "invalid ELF relocation table")
            for pos in range(section.offset, section.offset + section.size, width):
                address, _ = struct.unpack_from("<QQ", elf.data, pos)
                sites.append(address)
    return sorted(set(sites))


def symbol_scopes(elf, text_index, counts, method_ranges):
    text = elf.sections[text_index]
    groups = defaultdict(list)
    for symbol, kind, index, address, size in elf.symbols:
        if index == text_index:
            groups[address].append((symbol, kind, size))
    for start, end in method_ranges:
        groups[start].append((f"svm-method@{start:#x}", 2, end - start))
    starts = sorted(groups)
    sites = relocation_sites(elf)
    previous_end = 0
    for i, start in enumerate(starts):
        entries = groups[start]
        sized = sorted({(symbol, size) for symbol, kind, size in entries if kind == 2 and size})
        if sized:
            counts["sized_function_starts"] += 1
            symbol, size = sized[0]
            end = start + size
            offset = text.offset + start - text.address
            next_start = starts[i + 1] if i + 1 < len(starts) else end
            if previous_end > start or next_start < end or any(length not in (0, size)
                                                               for _, _, length in entries):
                counts["overlapping_symbol_scopes"] += 1
            elif size > BLOCK or not text.address <= start < end <= text.address + text.size:
                counts["unsupported_symbol_extents"] += 1
            else:
                loads = [(flags, pos, address, count)
                         for kind, flags, pos, address, _, count, mem_size, _ in elf.segments
                         if kind == 1 and overlaps(start, end, address, address + mem_size)]
                if len(loads) == 1:
                    flags, pos, address, count = loads[0]
                    mapped = (flags == 5 and address <= start and end <= address + count
                              and pos + start - address == offset)
                else:
                    mapped = False
                if not mapped:
                    counts["non_executable_or_ambiguous_scopes"] += 1
                # Match the single-function tool's conservative relocation width.
                elif bisect_left(sites, end) != bisect_right(sites, start - 16):
                    counts["relocated_scopes"] += 1
                else:
                    yield symbol, start, end, offset
        previous_end = max(previous_end, *(start + size for _, _, size in entries))


def overlapping_frames(frames, scopes):
    ordered = sorted(frames, key=lambda frame: frame["low"])
    active = []
    next_index = 0
    for _, start, end, _ in scopes:
        active = [frame for frame in active if frame["high"] > start]
        while next_index < len(ordered) and ordered[next_index]["low"] < end:
            frame = ordered[next_index]
            if frame["high"] > start:
                active.append(frame)
            next_index += 1
        yield active


def reachable_instructions(start, decoded, terminals):
    pending = [start]
    reached = set()
    while pending:
        address = pending.pop()
        if address in reached or address not in decoded:
            continue
        reached.add(address)
        raw = decoded[address]
        width = source_branch(raw)
        if width:
            pending.append(branch_target(address, raw, width))
            if jump(raw):
                continue
        if address not in terminals:
            pending.append(address + len(raw))
    return reached


def is_terminal(assembly):
    # All exact short/near Jcc and JMP opcodes are handled separately. Stop
    # on unsupported transfers, especially indirect jumps into jump tables.
    decoder_prefixes = {"rep", "repz", "repnz", "repne", "data16", "addr32",
                        "bnd", "lock", "notrack", "cs", "ds"}
    for word in assembly.split():
        if word not in decoder_prefixes and not word.startswith("rex"):
            return (word.startswith(("j", "ret", "lret", "iret", "loop", "int", "sysret"))
                    or word in {"hlt", "ud0", "ud1", "ud2", "xabort", "xbegin", "sysexit"})
    return True


def function_candidates(scope, decoded, terminals, frames, counts):
    symbol, start, end, offset = scope
    reached = reachable_instructions(start, decoded, terminals)
    counts["reachable_instruction_bytes"] += sum(len(decoded[address]) for address in reached)
    for address in sorted(reached):
        raw = decoded[address]
        width = source_branch(raw)
        if not width:
            continue
        via = branch_target(address, raw, width)
        middle = decoded.get(via, b"")
        target = forwarded_target(raw, width, via, middle)
        if target not in reached or len({address, via, target}) != 3:
            continue
        try:
            new_disp = (target - address - len(raw)).to_bytes(len(raw) - width, "little", signed=True)
            unwind = cfi_witness(frames, (address, address + len(raw) - 1, via,
                                          via + len(middle) - 1, target))
        except (OverflowError, ValueError):
            continue
        yield {"symbol": symbol, "scope": [start, end], "address": address,
               "file_offset": offset + address - start, "via": via, "target": target,
               "original_bytes": raw.hex(), "via_bytes": middle.hex(),
               "replacement_bytes": (raw[:width] + new_disp).hex(), "unwind_records": unwind}


def decode_scopes(elf, scopes, frames, counts):
    """Use one streaming objdump pass, keeping only one function's instructions."""
    state = iter(zip(scopes, overlapping_frames(frames, scopes)))
    scope, frame_set = next(state, (None, None))
    if scope is None:
        return
    position = scope[1]
    decoded = {}
    terminals = set()
    command = ["objdump", "-d", "-z", "-w", "--insn-width=16", "-j", ".text", str(elf.path)]
    with tempfile.TemporaryFile(mode="w+") as errors, subprocess.Popen(
            command, stdout=subprocess.PIPE, stderr=errors, text=True, errors="surrogateescape",
            env={**os.environ, "LC_ALL": "C"}) as proc:
        for line in proc.stdout:
            match = instruction.fullmatch(line.rstrip("\n"))
            if not match or scope is None:
                continue
            address = int(match[1], 16)
            while scope is not None and address >= scope[2]:
                if position == scope[2]:
                    counts["decoded_function_scopes"] += 1
                    counts["decoded_scope_bytes"] += scope[2] - scope[1]
                    yield from function_candidates(scope, decoded, terminals, frame_set, counts)
                else:
                    counts["unverified_instruction_scopes"] += 1
                scope, frame_set = next(state, (None, None))
                if scope is not None:
                    position = scope[1]
                    decoded = {}
                    terminals = set()
            if scope is None or address < scope[1] or position is None:
                continue
            raw = bytes.fromhex(match[2])
            file_offset = scope[3] + address - scope[1]
            if (address != position or not 1 <= len(raw) <= 15 or address + len(raw) > scope[2]
                    or "(bad)" in match[3] or match[3].lstrip().startswith(".")
                    or elf.data[file_offset:file_offset + len(raw)] != raw):
                position = None
                continue
            decoded[address] = raw
            if not source_branch(raw) and is_terminal(match[3]):
                terminals.add(address)
            position += len(raw)
        status = proc.wait()
        errors.seek(0)
        warnings = errors.read().strip()
        require(status == 0 and not warnings, f"objdump failed: {warnings or status}")
    if scope is not None:
        if position == scope[2]:
            counts["decoded_function_scopes"] += 1
            counts["decoded_scope_bytes"] += scope[2] - scope[1]
            yield from function_candidates(scope, decoded, terminals, frame_set, counts)
        else:
            counts["unverified_instruction_scopes"] += 1
        counts["unverified_instruction_scopes"] += sum(1 for _ in state)


def pinned_svm_ranges(path, digest, text):
    extractor = Path(__file__).with_name("svm-method-map")
    recovered = json.loads(tool(sys.executable, str(extractor), str(path)))
    require(recovered["original_sha256"] == digest,
            "Native Image method table does not match the input ELF")
    ranges = []
    previous_end = text.address
    for entry in recovered["functions"]:
        start, end = entry["start"], entry["end"]
        require(type(start) is int and type(end) is int
                and previous_end <= start < end <= text.address + text.size,
                "invalid or overlapping Native Image method bounds")
        ranges.append((start, end))
        previous_end = end
    require(ranges, "Native Image method table is empty")
    return ranges


def inspect(path, native_image_methods):
    with path.open("rb") as file, mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_READ) as data:
        elf = Elf(path, data)
        indices = [index for index, section in enumerate(elf.sections)
                   if elf.read_string(elf.names, section.name_index) == ".text"]
        require(len(indices) == 1, "expected one .text section")
        section = elf.sections[indices[0]]
        require(section.kind == 1 and section.flags & 7 == 6 and section.size > 0,
                "expected a nonempty read-only executable .text section")
        digest = sha256(data).hexdigest()
        methods = pinned_svm_ranges(path, digest, section) if native_image_methods else []
        counts = Counter()
        scopes = list(symbol_scopes(elf, indices[0], counts, methods))
        counts["native_image_method_extents"] = len(methods)
        counts["eligible_function_scopes"] = len(scopes)
        counts["text_bytes"] = section.size
        counts["eligible_scope_bytes"] = sum(end - start for _, start, end, _ in scopes)
        frames = cfi_scopes(path, section.address, section.address + section.size) if scopes else []
        sources, protected = set(), set()
        accepted = []
        for patch in decode_scopes(elf, scopes, frames, counts):
            counts["candidate_branches"] += 1
            origin, via, target = (patch[key] for key in ("address", "via", "target"))
            # Keep every proof's witness instructions unmodified by all other proofs.
            if origin in protected or via in sources or target in sources:
                counts["dependent_branches_skipped"] += 1
                continue
            sources.add(origin)
            protected.update((via, target))
            accepted.append(patch)
        counts["rewritten_branches"] = len(accepted)
        counts["rewritten_function_scopes"] = len({tuple(patch["scope"]) for patch in accepted})
        return {"format": FORMAT, "original_sha256": digest,
                "scope_source": "symbols+native-image" if native_image_methods else "symbols",
                "coverage": dict(counts), "patches": sorted(accepted, key=lambda p: p["file_offset"])}


def verified_hashes(original, rewritten, patches):
    with original.open("rb") as src, rewritten.open("rb") as dst:
        length = os.fstat(src.fileno()).st_size
        require(os.fstat(dst.fileno()).st_size == length, "binary changed size")
        source_hash, output_hash = sha256(), sha256()

        def same(remaining):
            while remaining:
                step = min(remaining, BLOCK)
                mine, theirs = src.read(step), dst.read(step)
                require(len(mine) == step and mine == theirs, "binary differs outside the certified patches")
                source_hash.update(mine)
                output_hash.update(theirs)
                remaining -= step

        position = 0
        for patch in patches:
            offset = patch["file_offset"]
            old = bytes.fromhex(patch["original_bytes"])
            new = bytes.fromhex(patch["replacement_bytes"])
            require(position <= offset and offset + len(old) <= length and len(old) == len(new),
                    "patches overlap, change width, or cross the end of file")
            same(offset - position)
            require(src.read(len(old)) == old and dst.read(len(new)) == new, "incorrect certified patch")
            source_hash.update(old)
            output_hash.update(new)
            position = offset + len(old)
        same(length - position)
        require(not src.read(1) and not dst.read(1), "binary changed during verification")
    return source_hash.hexdigest(), output_hash.hexdigest()


def complete_certificate(original, rewritten, evidence):
    input_hash, output_hash = verified_hashes(original, rewritten, evidence["patches"])
    require(input_hash == evidence["original_sha256"], "original ELF changed after inspection")
    return {**evidence, "optimized_sha256": output_hash}


def rewrite(original, output, certificate, native_image_methods):
    require(len({original.resolve(), output.resolve(), certificate.resolve()}) == 3,
            "input, output, and certificate must be distinct files")
    require(not os.path.lexists(output) and not os.path.lexists(certificate),
            "output and certificate must be new files")
    evidence = inspect(original, native_image_methods)
    require(evidence["patches"], f"no certified branch rewrites for coverage {evidence['coverage']}")
    with tempfile.TemporaryDirectory(dir=output.parent, prefix=".elf-wide-") as temp:
        staged = Path(temp) / "output"
        shutil.copyfile(original, staged)
        with staged.open("r+b") as file:
            for patch in evidence["patches"]:
                file.seek(patch["file_offset"])
                file.write(bytes.fromhex(patch["replacement_bytes"]))
        manifest = complete_certificate(original, staged, evidence)
        staged.chmod(original.stat().st_mode & 0o777)
        with certificate.open("x") as file:
            json.dump(manifest, file, indent=2, sort_keys=True)
            file.write("\n")
        try:
            os.link(staged, output)
        except OSError:
            certificate.unlink()
            raise
    return manifest["coverage"]


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    commands = parser.add_subparsers(dest="command", required=True)
    for name in ("inspect", "rewrite", "verify"):
        cmd = commands.add_parser(name)
        cmd.add_argument("original", type=Path)
        cmd.add_argument("--native-image-methods", action="store_true",
                         help="also recover exact method ranges from the pinned Native Image ELF")
        if name != "inspect":
            cmd.add_argument("output", type=Path)
            cmd.add_argument("certificate", type=Path)
    args = parser.parse_args()
    try:
        if args.command == "inspect":
            report = inspect(args.original, args.native_image_methods)
        elif args.command == "rewrite":
            report = rewrite(args.original, args.output, args.certificate, args.native_image_methods)
        else:
            certificate = json.loads(args.certificate.read_text())
            evidence = inspect(args.original, args.native_image_methods)
            report = complete_certificate(args.original, args.output, evidence)
            require(report == certificate, "certificate does not match the independently checked pair")
            report = report["coverage"]
        print(json.dumps(report, indent=2, sort_keys=True))
    except (ValueError, KeyError, TypeError, OSError, struct.error, subprocess.SubprocessError) as error:
        parser.exit(1, f"optimize-elf-layout: {error}\n")


if __name__ == "__main__":
    main()
