#!/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 ; +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))