#!/usr/bin/env python3
"""Thread one proved x86-64 direct branch in a named ELF function."""

import argparse
from dataclasses import dataclass
from hashlib import sha256
import json
import mmap
import os
from pathlib import Path
import re
import shutil
import struct
import subprocess
import tempfile


FORMAT = "graalc-elf-jump-threading-v1"
BLOCK = 1024 * 1024
ELF_HEADER = struct.Struct("<16sHHIQQQIHHHHHH")
SECTION_HEADER = struct.Struct("<IIQQQQIIQQ")
PROGRAM_HEADER = struct.Struct("<IIQQQQQQ")
SYMBOL = struct.Struct("<IBBHQQ")
FDE = re.compile(r"([a-f0-9]+) [a-f0-9]+ [a-f0-9]+ FDE .* pc=([a-f0-9]+)\.\.([a-f0-9]+)")
CIE = re.compile(r"([a-f0-9]+) [a-f0-9]+ [a-f0-9]+ CIE \"([^\"]*)\"")
INSTRUCTION = re.compile(r"\s*([0-9a-f]+):\t([0-9a-f ]+)\t(.+)")


def require(condition, message):
    if not condition:
        raise ValueError(message)


def tool(name, *args):
    result = subprocess.run([name, *args], capture_output=True, check=True, text=True,
                            env={**os.environ, "LC_ALL": "C"})
    require(not result.stderr.strip(), f"{name}: {result.stderr.strip()}")
    return result.stdout


def overlaps(start, end, other_start, other_end):
    return start < other_end and other_start < end


@dataclass(frozen=True)
class Section:
    name_index: int
    kind: int
    flags: int
    address: int
    offset: int
    size: int
    link: int
    info: int
    align: int
    entry_size: int


class Elf:
    def __init__(self, path, data):
        self.path = path
        self.data = data
        ident, kind, machine, version, _, p_off, s_off, _, h_size, p_size, p_count, s_size, s_count, names = ELF_HEADER.unpack_from(data)
        require(ident[:7] == b"\x7fELF\x02\x01\x01" and kind in (2, 3) and machine == 62
                and version == 1 and h_size == ELF_HEADER.size,
                "expected a little-endian x86-64 ELF executable")
        require(p_size == PROGRAM_HEADER.size and s_size == SECTION_HEADER.size
                and p_count and 0 < names < s_count, "unsupported ELF header tables")
        require(p_off + p_count * p_size <= len(data) and s_off + s_count * s_size <= len(data),
                "truncated ELF header tables")
        self.sections = [Section(*SECTION_HEADER.unpack_from(data, s_off + i * s_size))
                         for i in range(s_count)]
        self.segments = [PROGRAM_HEADER.unpack_from(data, p_off + i * p_size)
                         for i in range(p_count)]
        for s in self.sections:
            if s.kind != 8:  # SHT_NOBITS has no file contents.
                require(s.offset + s.size <= len(data), "truncated ELF section")
        self.names = self.sections[names]
        self.symbols = self.read_symbols()

    def read_string(self, section, index):
        require(section.kind == 3 and index < section.size, "invalid ELF string table")
        start = section.offset + index
        end = self.data.find(b"\0", start, section.offset + section.size)
        require(end >= 0, "unterminated ELF string")
        return self.data[start:end].decode("utf-8", errors="surrogateescape")

    def read_symbols(self):
        symbols = set()
        for section in self.sections:
            if section.kind not in (2, 11):  # SHT_SYMTAB, SHT_DYNSYM
                continue
            require(section.entry_size == SYMBOL.size and section.size % SYMBOL.size == 0
                    and section.link < len(self.sections), "invalid ELF symbol table")
            for pos in range(section.offset, section.offset + section.size, SYMBOL.size):
                name, info, _, index, address, size = SYMBOL.unpack_from(self.data, pos)
                if 0 < index < len(self.sections):
                    symbols.add((self.read_string(self.sections[section.link], name),
                                 info & 15, index, address, size))
        return symbols

    def scope(self, name):
        matches = {(index, start, size) for symbol, kind, index, start, size in self.symbols
                   if symbol == name and kind == 2 and 0 < size <= BLOCK}
        require(len(matches) == 1, "expected one sized STT_FUNC symbol of at most 1 MiB")
        index, start, size = matches.pop()
        end = start + size
        section = self.sections[index]
        require(self.read_string(self.names, section.name_index) == ".text" and section.kind == 1
                and section.flags & 7 == 6 and section.address <= start
                and end <= section.address + section.size, "symbol is outside read-only executable .text")
        offset = section.offset + start - section.address
        loads = [(flags, pos, address, count, mem_size)
                 for kind, flags, pos, address, _, count, mem_size, _ in self.segments
                 if kind == 1 and overlaps(start, end, address, address + mem_size)]
        require(len(loads) == 1, "ambiguous ELF load mapping")
        flags, pos, address, count, _ = loads[0]
        require(flags == 5 and address <= start and end <= address + count
                and pos + start - address == offset, "symbol is outside a file-backed R-X segment")
        for _, _, i, addr, length in self.symbols:
            if i != index:
                continue
            if addr == start and length in (0, size):
                continue  # Same-address aliases are fine.
            require(not (start < addr < end or (length and overlaps(start, end, addr, addr + length))),
                    "different ELF symbol overlaps the requested function")
        self.check_relocations(start, end)
        return start, end, offset

    def check_relocations(self, start, end):
        for section in self.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", self.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 not in (4, 9):
                continue
            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", self.data, pos)
                # Conservatively include up to a 16-byte x86-64 relocation write.
                require(not overlaps(start, end, address, address + 16),
                        "a relocation can write the requested function")

    def instructions(self, start, end, offset):
        listing = tool("objdump", "-d", "-z", "-w", "--insn-width=16", "-j", ".text",
                       f"--start-address={start}", f"--stop-address={end}", str(self.path))
        position = start
        instructions = {}
        for line in listing.splitlines():
            m = INSTRUCTION.fullmatch(line)
            if not m:
                continue
            address = int(m[1], 16)
            raw = bytes.fromhex(m[2])
            require(address == position and "(bad)" not in m[3] and
                    not m[3].lstrip().startswith("."), "symbol is not entirely decoded instructions")
            require(1 <= len(raw) <= 15 and self.data[offset + address - start:offset + address - start + len(raw)] == raw,
                    "objdump decoding differs from ELF bytes")
            position += len(raw)
            instructions[address] = raw
        require(position == end, "objdump did not decode the exact symbol extent")
        return instructions


def cfi_scopes(path, start, end):
    frames = []
    cies = {}
    frame = None
    section = ""
    for line in tool("readelf", "-W", "--debug-dump=frames-interp", str(path)).splitlines():
        heading = re.fullmatch(r"Contents of the (\.\w+) section:", line)
        if heading:
            section = heading[1]
            frame = None
        if section not in (".eh_frame", ".debug_frame"):
            continue
        if m := CIE.match(line):
            cies[(section, int(m[1], 16))] = m[2]
            frame = None
        elif m := FDE.fullmatch(line):
            low, high = int(m[2], 16), int(m[3], 16)
            cie = re.search(r"cie=([a-f0-9]+) ", line)
            require(cie is not None, "cannot resolve unwind CIE")
            if overlaps(start, end, low, high):
                frame = {"section": section, "fde": int(m[1], 16), "low": low, "high": high,
                         "augmentation": cies.get((section, int(cie[1], 16))), "rows": []}
                frames.append(frame)
            else:
                frame = None
        elif " FDE " in line or " CIE " in line:
            raise ValueError("unrecognized readelf unwind record")
        elif frame and (m := re.match(r"([a-f0-9]+)\s+(\S.*)", line)):
            frame["rows"].append((int(m[1], 16), m[2].split()))
    return frames


def cfi_witness(frames, pcs):
    by_section = {}
    for section in {f["section"] for f in frames}:
        records = [f for f in frames if f["section"] == section
                   and any(f["low"] <= pc < f["high"] for pc in pcs)]
        if not records:
            continue
        require(len(records) == 1, "ambiguous or different unwind records")
        frame = records[0]
        require(frame["augmentation"] in ("", "zR"), "unwind record has auxiliary semantics")
        require(all(frame["low"] <= pc < frame["high"] for pc in pcs), "branch crosses an unwind range")
        # Even if identical rules are restated, require the same row to avoid
        # relying on a partial interpretation of DWARF expressions.
        rows = sorted(row[0] for row in frame["rows"])
        require(not any(min(pcs) < row <= max(pcs) for row in rows), "branch crosses an unwind row")
        by_section[section] = frame["fde"]
    return by_section


def jump(raw):
    if len(raw) == 2 and raw[0] == 0xEB:
        return 1
    if len(raw) == 5 and raw[0] == 0xE9:
        return 1
    return 0


def source_branch(raw):
    if len(raw) == 2 and 0x70 <= raw[0] <= 0x7F:
        return 1
    if len(raw) == 6 and raw[0] == 0x0F and 0x80 <= raw[1] <= 0x8F:
        return 2
    return jump(raw)


def branch_target(address, raw, width):
    return address + len(raw) + int.from_bytes(raw[width:], "little", signed=True)


def branch_condition(raw, width):
    return None if jump(raw) else raw[width - 1] & 15


def condition_holds(code, flags):
    carry, parity, zero, sign, overflow = (bool(flags & (1 << index)) for index in range(5))
    value = (overflow, carry, zero, carry or zero, sign, parity,
             sign != overflow, zero or sign != overflow)[code >> 1]
    return value != bool(code & 1)


def forwarded_target(origin, from_width, via, middle):
    if jump(middle):
        return branch_target(via, middle, 1)
    mid_width = source_branch(middle)
    if not mid_width or jump(origin):
        return None
    source_code = branch_condition(origin, from_width)
    middle_code = branch_condition(middle, mid_width)
    possible = {condition_holds(middle_code, state) for state in range(32)
                if condition_holds(source_code, state)}
    if possible == {True}:
        return branch_target(via, middle, mid_width)
    if possible == {False}:
        return via + len(middle)
    return None


def inspect(path, symbol):
    with path.open("rb") as file, mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_READ) as data:
        elf = Elf(path, data)
        start, end, offset = elf.scope(symbol)
        instructions = elf.instructions(start, end, offset)
        frames = cfi_scopes(path, start, end)
        candidates = []
        for address, raw in instructions.items():
            width = source_branch(raw)
            if not width:
                continue
            via = branch_target(address, raw, width)
            middle = instructions.get(via, b"")
            target = forwarded_target(raw, width, via, middle)
            if target not in instructions or len({address, via, target}) != 3:
                continue
            try:
                new = raw[:width] + (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 (ValueError, OverflowError):
                continue
            candidates.append({"address": address, "file_offset": offset + address - start,
                               "via": via, "target": target, "original_bytes": raw.hex(),
                               "via_bytes": middle.hex(), "replacement_bytes": new.hex(),
                               "unwind_records": unwind})
        return {"format": FORMAT, "symbol": symbol, "scope": [start, end],
                "original_sha256": sha256(data).hexdigest()}, candidates


def verify_bytes(original, optimized, patch):
    offset = patch["file_offset"]
    old = bytes.fromhex(patch["original_bytes"])
    new = bytes.fromhex(patch["replacement_bytes"])
    with original.open("rb") as src, optimized.open("rb") as dst:
        source_hash, output_hash = sha256(), sha256()

        def same(length):
            while length:
                step = min(BLOCK, length)
                left, right = src.read(step), dst.read(step)
                require(len(left) == step and left == right, "binary differs outside the certified patch")
                source_hash.update(left)
                output_hash.update(right)
                length -= step
        require(original.stat().st_size == optimized.stat().st_size, "binary changed size")
        same(offset)
        require(src.read(len(old)) == old and dst.read(len(new)) == new, "patch bytes do not match")
        source_hash.update(old)
        output_hash.update(new)
        same(original.stat().st_size - offset - len(old))
        require(not src.read(1) and not dst.read(1), "binary changed during verification")
    return source_hash.hexdigest(), output_hash.hexdigest()


def select(candidates, address):
    selected = [patch for patch in candidates if address is None or patch["address"] == address]
    require(len(selected) == 1, "expected one patch. Use inspect and pass one candidate address")
    return selected[0]


def rewrite(source, output, certificate, header, patch):
    require(len({source.resolve(), output.resolve(), certificate.resolve()}) == 3,
            "input, output and certificate must be different files")
    require(not output.exists() and not certificate.exists(), "output and certificate must be new files")
    with tempfile.TemporaryDirectory(dir=output.parent, prefix=".elf-rewrite-") as staging:
        staged = Path(staging) / "binary"
        shutil.copyfile(source, staged)
        with staged.open("r+b") as binary:
            binary.seek(patch["file_offset"])
            binary.write(bytes.fromhex(patch["replacement_bytes"]))
        source_digest, output_digest = verify_bytes(source, staged, patch)
        require(source_digest == header["original_sha256"], "input changed after inspection")
        staged.chmod(source.stat().st_mode & 0o777)
        cert = {**header, "optimized_sha256": output_digest, "patch": patch}
        with certificate.open("x") as report:
            json.dump(cert, report, indent=2)
            report.write("\n")
        try:
            os.link(staged, output)
        except OSError:
            certificate.unlink()
            raise


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    modes = parser.add_subparsers(dest="command", required=True)
    for name in ("inspect", "rewrite"):
        mode = modes.add_parser(name)
        mode.add_argument("input", type=Path)
        mode.add_argument("--symbol", required=True)
        if name == "rewrite":
            mode.add_argument("--address", type=lambda text: int(text, 0))
            mode.add_argument("--output", type=Path, required=True)
            mode.add_argument("--certificate", type=Path, required=True)
    mode = modes.add_parser("verify")
    mode.add_argument("input", type=Path)
    mode.add_argument("output", type=Path)
    mode.add_argument("certificate", type=Path)
    args = parser.parse_args()

    try:
        if args.command == "verify":
            cert = json.loads(args.certificate.read_text())
            header, candidates = inspect(args.input, cert["symbol"])
            patch = select(candidates, cert["patch"]["address"])
            source_digest, output_digest = verify_bytes(args.input, args.output, patch)
            require(source_digest == header["original_sha256"], "input changed after inspection")
            expected = {**header, "optimized_sha256": output_digest, "patch": patch}
            require(cert == expected, "certificate does not match the checked ELF pair")
            print("Checked x86-64 branch stuttering and exact byte diff.")
        else:
            header, candidates = inspect(args.input, args.symbol)
            if args.command == "inspect":
                print(json.dumps({**header, "candidates": candidates}, indent=2))
            else:
                patch = select(candidates, args.address)
                rewrite(args.input, args.output, args.certificate, header, patch)
    except (KeyError, TypeError, ValueError, OSError, struct.error, subprocess.CalledProcessError) as exc:
        parser.exit(1, f"optimize-aot-elf: {exc}\n")


if __name__ == "__main__":
    main()
