TP3/shell/tests/check_8086.py

#!/usr/bin/env python3
"""check_8086.py -- require that the emitted image contains no opcode the 8086
lacks, and that what replaced the two illegal ones is TP3's shape.

The bug
-------
`EmJcc` emitted `0F 8x rel16' and `EmSetcc` emitted `0F 9x' (SETcc).  Both are
386-and-later: on an 8086 the byte `0F' is not an opcode prefix at all, so
every conditional branch and every comparison *value* in every compiled program
was an illegal instruction on the machine TP3 targets.

Nothing in the build could see it, and each thing that might have failed is
worth naming:

  * it compiled, because the compiler only ever writes bytes;
  * FCML decoded it happily, because FCML's -m16 mode is 386 -- and FCML is
    this project's independent disassembler, so the one tool that could have
    objected was the one tool guaranteed to agree;
  * the .COM linked and its layout checked, because `0F 84 lo hi' is a
    perfectly well-formed 4-byte displacement field;
  * the runtime golden did not move, because the runtime emits no 0F;
  * and all 30 fixtures ran to the right answers under qemu-system-i386,
    whose lowest CPU model is 486.  There is no `-cpu 8086'.

That last one is why this file exists rather than a one-line change to the
harness.  The gap was invisible to the oracle, not absent.

Why the two regions are treated differently
------------------------------------------
The runtime's code region (bytes 0..code-end of the runtime blob) is pure
code, so it can be swept exhaustively and the sweep must complete.  That is a
hard guarantee: no 0F-prefixed instruction anywhere in the runtime.

The generated program's code region is NOT pure code -- inline string literals
are emitted into it, after the code, and a linear sweep desynchronises on them
and then reports an undefined opcode in the middle of a string.  t09_if is the
demonstration: the sweep decodes 16 real instructions and then dies at the
bytes `FE E9 0D 00', which are ASCII text, not code.  So a sweep of the
program region cannot answer "is this 8086-legal", and a check that believed it
would be worse than no check.

What is sound instead is to name the SITES rather than the boundaries.  Both
illegal opcodes were emitted in answer to exactly one thing -- the result of a
comparison -- and a comparison is always introduced by one of two sequences
this compiler emits and nothing else emits:

    3B C1      EmCmpAxCx,  CMP AX,CX
    3D lo hi   EmCmpAxi,   CMP AX,imm16

Every one of the seven EmJcc call sites and the single EmSetcc call site sits
immediately after one of those, which is checked by reading each site rather
than assumed (see the site table in Compiler.mod).  So this check asserts:

  A. the runtime's code region sweeps clean and holds no 0F-prefixed opcode;
  B. every `3B C1` in every fixture's code region is followed by one of exactly
     two 8086-legal shapes --
       B8 01 00  7X 01  48      a Boolean VALUE: MOV AX,1 ; Jcc +1 ; DEC AX
       7X 03  E9                a BRANCH:          Jcc +3 ; EJMP
     which are EmSetcc and EmJcc respectively;
  C. every `3D lo hi' is followed by the BRANCH shape, because all five
     EmCmpAxi sites are IF/WHILE/REPEAT/CASE tests;
  D. every condition nibble the compiler's two tables declare must appear at
     least once across the suite.

D is what stops the check being vacuous, and it is why t33_cmpops exists: when
this was first written, measuring the emitted nibbles showed `=', `<>' and
`<=' were never used in a comparison anywhere in the suite.  A check that only
requires "some condition was lowered" would have been satisfied by the three
that were covered.

The shapes in B and C are hand-derived from the original compiler, not read
back out of this compiler's output:

  TPSRC8 246-295   IF / WHILE / REPEAT are each
                     MOV AL,brnchop ; MOV AH,#$03 ; CALL eword
                     PUSH pc ; CALL ejump
                   i.e. a SHORT Jcc of displacement 3 stepping over a 3-byte
                   EJMP.  brnchop is the condition's own opcode, so the short
                   jump is taken straight to the target.

  TPSRC9 412-424   flgbool turns a comparison's flags into a value with
                     MOV AX,#0001 ; <Jcc> +1 ; DEC AX
                   AX stays 1 because the DEC was stepped over.

Both are `short Jcc ; one byte ; something`, which is why the displacement is
3 in one case and 1 in the other and why both are two instructions and a byte.

Usage: check_8086.py [-v]     (from shell/)
"""

import collections
import glob
import os
import re
import subprocess
import sys
import tempfile

HERE = os.path.dirname(os.path.abspath(__file__))
SHELL = os.path.dirname(HERE)
sys.path.insert(0, HERE)
import disasm16  # noqa: E402
# The image layout: where the header is, how big it is, and the load bias this
# file used to carry on its own account.  See tests/check_comimage.py, which
# asserts that every reader of a linked image gets these from one place.
import comimage  # noqa: E402

COMTEST = os.path.join(SHELL, "comtest")

# Declared by Compiler.mod, restated here rather than asked of the code under
# test, and cross-checked against what the suite emits.  These are the low
# nibbles of the `0F 9x' SETcc opcodes ParseCmp passes to EmSetcc:
#   = 94H  <> 95H  < 9CH  > 9FH  >= 9DH  <= 9EH
# EmSetcc's job is to answer "is this comparison true", so its Jcc is the
# comparison's OWN opcode and these keys are what appears in the image.
SETCC_NIBBLES = {0x4: "=", 0x5: "<>", 0xC: "<", 0xD: ">=", 0xE: "<=",
                 0xF: ">"}
# ... and of the `0F 8x' Jcc opcodes the seven EmJcc sites pass:
#   IF 84H  REPEAT 84H  CASE 85H  FOR 8CH (downto) / 8FH (to)
# EmJcc JUMPS TO the target while these are "taken when the condition is
# false" (IF's JZ is patched to the ELSE, so it must fire when the test
# failed), and the Jcc-over-EJMP shape steps over the EJMP when it is TAKEN.
# Those two things are opposite, so the byte in the image is the negation of
# the nibble declared here: the Jcc code's low bit IS the negation bit, and
# negating a condition is `n XOR 1' (JE/JNE are 74h/75h).  Hence the XOR below,
# and hence clause E is stated on the emitted byte rather than on these keys.
JCC_NIBBLES = {0x4: "IF / REPEAT", 0x5: "CASE", 0xC: "FOR downto",
               0xF: "FOR to"}


def negated(nib):
    """The Jcc nibble the image will carry for a site that declares `nib'."""
    return nib ^ 1

CMP_AX_CX = b"\x3b\xc1"  # EmCmpAxCx
CMP_AX_ZERO = b"\x3d\x00\x00"   # EmCmpAxi (0)


def probe_runtime():
    """(blob, code_end) from the existing rt_exec probe, so this check does
    not restate Runtime.RT_Size or where the code stops."""
    out = subprocess.run([sys.executable, os.path.join(HERE, "rt_exec.py"),
                          "--probe"], capture_output=True, text=True,
                         cwd=SHELL)
    if out.returncode != 0:
        sys.stderr.write(out.stdout + out.stderr)
        raise SystemExit("FAIL: rt_exec.py --probe failed")
    size = code_end = None
    for line in out.stdout.splitlines():
        if line.endswith("bytes") and size is None:
            size = int(line.split()[0])
        if line.startswith("code ends at"):
            code_end = int(line.split()[3])
    if size is None or code_end is None:
        raise SystemExit("FAIL: could not read the runtime size from the probe")
    # the probe prints a hex dump of the blob; rebuild it from the .COM-free
    # dump lines so this check needs no second source of the runtime bytes
    blob = bytearray()
    for line in out.stdout.splitlines():
        parts = line.split()
        # one offset word then 16 two-digit hex bytes
        if len(parts) == 17 and all(len(p) == 2 for p in parts[1:]):
            try:
                blob += bytes(int(p, 16) for p in parts[1:])
            except ValueError:
                pass
    return bytes(blob), code_end, size


def sweep(code, base=0):
    """Linear sweep.  Returns (instructions, offset_it_stopped_at_or_None).
    An instruction is (offset, opcode_byte, length)."""
    out = []
    pc = 0
    while pc < len(code):
        text, length = disasm16.decode(code[pc:], base + pc)
        if length == 0:
            return out, pc
        out.append((pc, code[pc], length))
        pc += length
    return out, None


def find_all(hay, needle, start=0):
    i = start
    while True:
        i = hay.find(needle, i)
        if i < 0:
            return
        yield i
        i += 1


def is_value_shape(nxt):
    """B8 01 00 7X 01 48 -- EmSetcc: MOV AX,#0001 ; Jcc +1 ; DEC AX"""
    return (len(nxt) >= 6 and nxt[0] == 0xB8 and nxt[1] == 0x01
            and nxt[2] == 0x00 and 0x70 <= nxt[3] <= 0x7F
            and nxt[4] == 0x01 and nxt[5] == 0x48)


def is_branch_shape(nxt):
    """7X 03 E9 -- EmJcc: Jcc +3, stepping over a 3-byte EJMP"""
    return (len(nxt) >= 3 and 0x70 <= nxt[0] <= 0x7F
            and nxt[1] == 0x03 and nxt[2] == 0xE9)


# Pascal relational operator -> the condition nibble the 8086 short Jcc must
# carry for that operator to be answered correctly.  `=' is JE (74h), and so
# on down the 70h..7Fh table.  Restated here, and checked against what
# Compiler.mod's ParseCmp table passes to EmSetcc, so the two cannot drift.
OP_NIBBLE = {"=": 0x4, "<>": 0x5, "<": 0xC, "<=": 0xE, ">": 0xF, ">=": 0xD}

# The fixture whose SOURCE ORDER of operators is compared against the order
# the compiler emitted them in.  This is the clause that catches a swap: the
# clauses above only ask "is this an 8086 shape", and a shape with the wrong
# nibble is still a shape.  It has to be a fixture whose every comparison is a
# value (so every one is an EmSetcc site, in source order) and which uses all
# six operators -- hence t33_cmpops, which exists partly for this.
ORDER_FIXTURE = "t33_cmpops"
RE_WRITELN_OP = re.compile(
    r"writeln\s*\(\s*\w+\s*(=|<>|<=|>=|<|>)\s*\w+\s*\)")

# H: for each fixture that HAS a branch, the multiset of conditions its branch
# sites declare, read off the .pas source by hand, with the reading spelled
# out in BRANCH_WHY so a later reader can check the reasoning rather than
# trust it.  Declared nibbles, i.e. before EmJcc's inversion, so 4 = IF/WHILE/
# REPEAT, 5 = CASE, C = FOR downto, F = FOR to.
BRANCH_SITES = {
    "t09_if":     [4, 4, 4],     # three `if ... then ... else'
    "t10_while":  [4, 4],        # two `while ... do'
    "t11_for":    [15, 12],      # one `for .. to' (F), one `for .. downto' (C)
    "t12_repeat": [4, 4],        # two `repeat .. until'
    "t15_label":  [4],           # one `if x < 5 then goto 1'
    "t22_case":   [5, 5],        # `case x of' with two arms, both fall to end
    "t30_forloop": [15],         # one `for .. to'
    "t32_forexit": [15, 4],      # one `for .. to' plus one `if .. exit'
}
BRANCH_WHY = {
    "t09_if":     "three `if' statements",
    "t10_while":  "two `while' loops",
    "t11_for":    "a `for .. to' and a `for .. downto'",
    "t12_repeat": "two `repeat .. until' loops",
    "t15_label":  "a single `if .. then goto'",
    "t22_case":   "a `case' with two arms, both falling through to `end'",
    "t30_forloop": "a single `for .. to'",
    "t32_forexit": "a `for .. to' and an `if .. exit'",
}


def source_operators(path):
    """The relational operators of every `writeln (x OP y)' in source order."""
    with open(path) as fh:
        text = fh.read()
    return [m.group(1) for m in RE_WRITELN_OP.finditer(text)]


def check_runtime_region(verbose):
    """A: the runtime's code region is pure code, so this is exhaustive."""
    blob, code_end, size = probe_runtime()
    if code_end > len(blob):
        return ["the probe says code ends at %d but only %d bytes were dumped"
                % (code_end, len(blob))]
    instrs, stopped = sweep(blob[:code_end])
    problems = []
    if stopped is not None:
        problems.append("the runtime's code region does not sweep clean: it "
                        "stops at offset %04X, so this check cannot claim to "
                        "have looked at everything" % stopped)
    bad = [(o, b) for (o, b, _) in instrs if b == 0x0F]
    for o, _ in bad:
        problems.append("runtime offset %04X is a 0F-prefixed opcode, which "
                        "does not exist on an 8086" % o)
    if verbose:
        print("runtime code region 0..%d: %d instructions swept%s"
              % (code_end, len(instrs),
                 "" if stopped is None else ", stopped at %04X" % stopped))
    return problems, dict(size=size, code_end=code_end,
                          ninstr=len(instrs), n0f=len(bad))


def program_code_region(img, rt_size):
    """(start, end) of the generated program's code region, both as IMAGE
    offsets, derived from the image rather than from a restated constant: the
    entry jump's displacement is the program's own answer for where the code
    begins, and hdrCS is `pc + LoadBias' with pc the end of the generated code,
    so hdrCS - LoadBias is where it stops.

    Where the header is gets two INDEPENDENT answers: rt_size is the runtime
    blob's size as the probe measured it, and comimage.find_header locates the
    header inside this file by its own self-consistency equation.  They are
    measurements of two different artefacts, so their agreement is evidence,
    and a .COM whose two disagree has no code region this checker can state --
    guessing one of them would be the restated constant this function exists
    to avoid."""
    hdr_probe = comimage.ENT_SZ + rt_size
    hdr_file = comimage.find_header(img)
    if hdr_file is None or hdr_file != hdr_probe:
        return None
    if len(img) < hdr_file + comimage.HDR_SZ:
        return None
    start = comimage.entry_target(img)
    if start is None:
        return None
    start %= 0x10000
    hdr_cs = int.from_bytes(img[hdr_file + 2:hdr_file + 4], "little")
    end = hdr_cs - comimage.LOAD_BIAS
    if not (start <= end <= len(img)):
        return None
    return start, end


def main(argv):
    verbose = "-v" in argv
    if not os.path.exists(COMTEST):
        print("FAIL: %s not built; run tests/run_com_tests.sh first" % COMTEST)
        return 1

    rt_problems, rt_info = check_runtime_region(verbose)
    problems = list(rt_problems)

    work = tempfile.mkdtemp(prefix="check8086.")
    try:
        fixtures = sorted(glob.glob(os.path.join(HERE, "fixtures", "*.pas")))
        paths = "\n".join(fixtures) + "\n"
        subprocess.run([COMTEST], input=paths.encode(), cwd=work,
                       stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL)

        val_nibbles = collections.Counter()   # EmSetcc sites
        br_nibbles = collections.Counter()   # EmJcc sites
        ncmp = nval = 0
        nlinked = 0
        ordered = 0
        ordered_cmps = 0
        pinned = []
        nbr_anchored = 0
        swept_fixtures = 0
        swept_bytes = 0
        missing = []

        for src in fixtures:
            name = os.path.basename(src)[:-4]
            com = os.path.join(work, name + ".COM")
            if not os.path.exists(com):
                continue                      # a fixture that errors by design
            with open(com, "rb") as fh:
                img = fh.read()
            region = program_code_region(img, rt_info["size"])
            if region is None:
                problems.append("%s: could not locate the code region "
                                "(entry jump, program header and hdrCS do not "
                                "agree)" % name)
                continue
            start, end = region
            code = img[start:end]
            nlinked += 1

            # A branch is found three ways -- anchored on the comparison
            # before it (B, C) and by its own shape (D) -- and the three
            # overlap, so they all go into one set of offsets and each site
            # is counted and validated once, at the end.  Counting as we went
            # reported 28 branch sites when there are 13: the anchored walk
            # and the shape walk were both adding to the same histogram.
            branch_offs = set()

            # B: every CMP AX,CX -- the only shape EmCmpAxCx emits, and the
            # only thing that can precede either lowering.  ParseCmp puts a
            # comparison VALUE there; the FOR test puts a BRANCH there.
            fixture_val_nibbles = []
            for off in find_all(code, CMP_AX_CX):
                ncmp += 1
                nxt = code[off + 2:off + 8]
                if is_value_shape(nxt):
                    val_nibbles[nxt[3] & 0x0F] += 1
                    fixture_val_nibbles.append(nxt[3] & 0x0F)
                    nval += 1
                elif is_branch_shape(nxt):
                    branch_offs.add(off + 2)
                    nbr_anchored += 1
                else:
                    problems.append(
                        "%s+%04X: CMP AX,CX is followed by %s -- neither "
                        "TP3 shape (MOV AX,1; Jcc +1; DEC AX, or Jcc +3; EJMP)"
                        % (name, start + off,
                           " ".join("%02X" % b for b in nxt) or "nothing"))

            # C: every CMP AX,0000 -- what IF, WHILE and REPEAT emit to test
            # a Boolean.  The three-byte anchor matters: a bare 3D also matches
            # displacement and immediate bytes, and taking it as an opcode is
            # what produced two false alarms here (a 3D inside a CALL
            # displacement in t11_for, and one inside a string in t21_mixed).
            for off in find_all(code, CMP_AX_ZERO):
                nxt = code[off + 3:off + 6]
                if is_branch_shape(nxt):
                    branch_offs.add(off + 3)
                    nbr_anchored += 1
                else:
                    problems.append(
                        "%s+%04X: CMP AX,0000 is followed by %s -- the three "
                        "EmCmpAxi (0) sites are IF/WHILE/REPEAT tests, so "
                        "each must be Jcc +3; EJMP"
                        % (name, start + off,
                           " ".join("%02X" % b for b in nxt) or "nothing"))

            # D: the same branches again, found by their own SHAPE rather than
            # by the instruction before it.  This is what covers the CASE arm,
            # whose EmCmpAxi carries a label rather than 0 and which no
            # comparison anchor can therefore find.  Discovery only -- the
            # counting and the checking happen once, over branch_offs.
            for off in find_all(code, b"\xe9"):
                if off >= 2 and is_branch_shape(code[off - 2:off + 1]):
                    branch_offs.add(off - 2)

            # E: each branch, counted under the nibble the COMPILER DECLARES
            # (the emitted one put back through the negation) and required to
            # be a condition Compiler.mod claims to use.
            for off in sorted(branch_offs):
                emitted = code[off] & 0x0F
                declared = negated(emitted)
                br_nibbles[declared] += 1
                if declared not in JCC_NIBBLES:
                    problems.append(
                        "%s+%04X: branch emits %Xh, which declares the "
                        "condition %Xh -- not one of the conditions "
                        "Compiler.mod declares for a branch (%s)"
                        % (name, start + off, code[off], declared,
                           ", ".join("%Xh" % k
                                     for k in sorted(JCC_NIBBLES))))

            # F: where the region sweeps clean -- no inline strings, so the
            # whole thing is code -- assert no 0F opcode over it as well.  This
            # is extra coverage, not the backbone, and how much of the suite
            # it reached is printed rather than implied.
            instrs, stopped = sweep(code, comimage.LOAD_BIAS + start)
            if stopped is None:
                swept_fixtures += 1
                swept_bytes += len(code)
                for o, b, _ in instrs:
                    if b == 0x0F:
                        problems.append(
                            "%s+%04X: 0F-prefixed opcode in swept code"
                            % (name, start + o))

            if verbose:
                print("%-16s code %d..%d%s"
                      % (name, start, end,
                         "" if stopped is None
                         else "  (sweep stops at +%04X: string data)"
                              % stopped))

            # H: WHICH branch condition each site means, per fixture.  The
            # table is read off the .pas sources, not off the image -- that is
            # the whole point, since a table measured from the image would
            # agree with any behaviour including a wrong one.
            #
            # This closes a hole the mutations above MEASURED rather than
            # assumed.  Clause E only rejects an emitted nibble that declares
            # a condition Compiler.mod does not claim for a branch, and the
            # inversion in EmJcc turns IF's declared 4 into an emitted 5 --
            # which is CASE's declared nibble, and IS claimed.  So dropping
            # the inversion for the IF and CASE sites alone left this check
            # green (mutation M5) while every conditional in every program
            # took the wrong path.  The FOR sites happen not to be blind that
            # way, because FOR declares C and F, whose negations D and E are
            # not declared for anything here -- so a whole-suite inversion is
            # caught by luck, and a partial one is not.
            #
            # It catches M5 because `declared' is computed from the EMITTED
            # byte by going back through the inversion: an IF that emitted
            # JccShort instead of JccShortInv reads back as declaring 5.
            got_br = sorted(negated(code[o] & 0x0F) for o in branch_offs)
            want_br = sorted(BRANCH_SITES.get(name, got_br))
            if got_br != want_br:
                problems.append(
                    "%s: its %d branch sites declare %s, but reading the "
                    "source says they are %s (%s)"
                    % (name, len(got_br),
                       " ".join("%Xh" % n for n in got_br),
                       " ".join("%Xh" % n for n in want_br),
                       BRANCH_WHY.get(name, "not a fixture with branches")))
            elif name in BRANCH_SITES:
                pinned.append(name)

            # G: for the one fixture whose operators are known from its
            # SOURCE, the emitted nibbles must match them IN ORDER.  This is
            # what catches a swap, which the shape clauses above cannot: a
            # SETG where a SETGE belongs is still a perfectly good 8086 shape.
            if name == ORDER_FIXTURE:
                ops = source_operators(src)
                want = [OP_NIBBLE[o] for o in ops]
                if fixture_val_nibbles != want:
                    problems.append(
                        "%s: the %d comparisons emitted as %s, but the source "
                        "asks in order for %s"
                        % (name, len(fixture_val_nibbles),
                           " ".join("%Xh" % n for n in fixture_val_nibbles),
                           " ".join("%s=%Xh" % (o, n)
                                    for o, n in zip(ops, want))))
                else:
                    ordered += 1
                    ordered_cmps += len(want)
    finally:
        subprocess.run(["rm", "-rf", work])

    # D: the declared conditions must all be exercised, or the check above is
    # only as good as whatever the suite happened to use.
    for nib, op in sorted(SETCC_NIBBLES.items()):
        if val_nibbles[nib] == 0:
            missing.append("`%s' (SETcc %02Xh) is declared by ParseCmp but no "
                           "fixture uses it as a comparison" % (op, nib | 0x90))
    for nib, where in sorted(JCC_NIBBLES.items()):
        if br_nibbles[nib] == 0:
            missing.append("the %s branch (Jcc nibble %Xh) is declared but no "
                           "fixture emits it" % (where, nib))
    problems += missing

    print("8086 check: %d comparison sites, %d lowered to a Boolean value, "
          "%d lowered to a branch" % (ncmp, nval, nbr_anchored))
    print("            value conditions  : %s"
          % "  ".join("%s x%d" % (SETCC_NIBBLES.get(n, "?%X?" % n), c)
                      for n, c in sorted(val_nibbles.items())))
    print("            branch conditions : %s"
          % "  ".join("%s x%d" % (JCC_NIBBLES.get(n, "?%X?" % n), c)
                      for n, c in sorted(br_nibbles.items())))
    print("            runtime: %d bytes, %d swept, %d 0F-prefixed"
          % (rt_info["size"], rt_info["ninstr"], rt_info["n0f"]))
    print("            program code: %d of %d fixtures swept end to end, "
          "%d bytes" % (swept_fixtures, nlinked, swept_bytes))
    print("            %s: %d comparisons matched against their source "
          "operators, in order" % (ORDER_FIXTURE, ordered_cmps))
    # H must have been reached for EVERY fixture it names.  A table row for a
    # fixture that no longer links, or whose region cannot be located, would
    # otherwise sit there looking like coverage while testing nothing.
    for name in sorted(set(BRANCH_SITES) - set(pinned)):
        problems.append("%s: clause H expects %d branch sites, but the "
                        "fixture contributed none -- the row is not being "
                        "tested" % (name, len(BRANCH_SITES[name])))
    print("            clause H: %d of %d fixtures matched the branch "
          "conditions read off their source"
          % (len(pinned), len(BRANCH_SITES)))

    if ordered == 0:
        problems.append("%s: no comparison was matched against its source "
                        "operator, so a swapped condition would go unnoticed"
                        % ORDER_FIXTURE)
    if ncmp == 0:
        problems.append("no comparison sites were found at all, so nothing "
                        "above was checked")
    if problems:
        print("FAIL: %d problem(s)" % len(problems))
        for p in problems:
            print("  - %s" % p)
        return 1
    print("PASS: no 0F-prefixed opcode in the runtime or in swept program "
          "code; every comparison is")
    print("      lowered to TP3's shape; all %d declared comparison "
          "conditions and all %d declared branch conditions are exercised"
          % (len(SETCC_NIBBLES), len(JCC_NIBBLES)))
    return 0


if __name__ == "__main__":
    sys.exit(main(sys.argv))