add validate layer

3 files changed, 346 insertions, 16 deletions

diff --git a/README.md b/README.md
index 55e5375..cd47df9 100644
--- a/README.md
+++ b/README.md
@@ -33,15 +33,17 @@ back to front:
 
 - `elf.py`: takes hex bytes and segment headers, outputs an ELF file
 - `pack.py`: packs bitfields (`3/3 1/1 f/4`) into hex bytes (`fb`)
+- `format.py`: bit-packs ops into ISA format
 - `survey.py`: replaces label references by their addresses
-- `format.py`: checks op-arguments and chops and orders arguments into ISA formats
+- `validate.py`: checks op-arguments and puts them into canonical order
 
 and now front to back with a little example:
 
-    $ ./format.py <ex.subv   >ex.format
-    $ ./survey.py <ex.format >ex.survey
-    $ ./pack.py   <ex.survey >ex.pack
-    $ ./elf.py    <ex.pack   >ex.elf
+    $ ./validate.py <ex.subv  >ex.valid
+    $ ./survey.py  <ex.valid  >ex.survey
+    $ ./format.py  <ex.survey >ex.format
+    $ ./pack.py    <ex.format >ex.pack
+    $ ./elf.py     <ex.pack   >ex.elf
     $ ./qemu.sh ex.elf
 
 `ex.subv`: hand-writable.
@@ -63,47 +65,80 @@ and now front to back with a little example:
       # jump back up to the top
       6f/jal 0/rd/x0 main/off21
 
-`ex.format`: arguments sliced and diced and put into the ISA order.
+`ex.format`: mnemonics validated and discarded
 
     == code 0x80000000
     # repeatedly print "Hi\n"
     main:
     # load 0x10010000 (UART0) into t0
-    37/7 05/5 10010/20
+    37/u 05/rd 10010/imm20
     # store 0x48 (H) in UART0+0
-    13/7 06/5 00/3 00/5 48/12
-    23/7 00/5 02/3 05/5 06/5 00/7
+    13/i 0/subop 6/rd 0/rs 48/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
     # store 0x69 (i) in UART0+0
-    13/7 06/5 00/3 00/5 69/12
-    23/7 00/5 02/3 05/5 06/5 00/7
+    13/i 0/subop 6/rd 0/rs 69/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
     # store 0x0a (\n) in UART0+0
-    13/7 06/5 00/3 00/5 0a/12
-    23/7 00/5 02/3 05/5 06/5 00/7
+    13/i 0/subop 6/rd 0/rs 0a/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
+    # jump back up to the top
+    6f/j 0/4d main/off21
+
+`ex.survey`: references resolved and labels removed
+
+    == code 0x80000000
+    # repeatedly print "Hi\n"
+    # main:
+    # load 0x10010000 (UART0) into t0
+    37/u 05/rd 10010/imm20
+    # store 0x48 (H) in UART0+0
+    13/i 0/subop 6/rd 0/rs 48/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
+    # store 0x69 (i) in UART0+0
+    13/i 0/subop 6/rd 0/rs 69/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
+    # store 0x0a (\n) in UART0+0
+    13/i 0/subop 6/rd 0/rs 0a/imm12
+    23/s 2/subop 5/rs2 6/rs1 0/off12
     # jump back up to the top
-    6f/7 00/5 main/8/off21>>12 main/1/off21>>11 main/10/off21>>1 main/1/off21>>20
+    6f/j 0/4d fffe4/off21
 
-`ex.survey`: labels resolved, ready to be packed into hex format
+`ex.format`: arguments sliced and diced and put into the ISA order.
 
     == code 0x80000000
+    # repeatedly print "Hi\n"
+    # main:
+    # load 0x10010000 (UART0) into t0
     37/7 05/5 10010/20
+    # store 0x48 (H) in UART0+0
     13/7 06/5 00/3 00/5 48/12
     23/7 00/5 02/3 05/5 06/5 00/7
+    # store 0x69 (i) in UART0+0
     13/7 06/5 00/3 00/5 69/12
     23/7 00/5 02/3 05/5 06/5 00/7
+    # store 0x0a (\n) in UART0+0
     13/7 06/5 00/3 00/5 0a/12
     23/7 00/5 02/3 05/5 06/5 00/7
+    # jump back up to the top
     6f/7 00/5 ff/8 01/1 3f2/10 01/1
 
 `ex.pack`: fully packed, ready to run bare-metal
 
     == code 0x80000000
+    # repeatedly print "Hi\n"
+    # main:
+    # load 0x10010000 (UART0) into t0
     b7 02 01 10
+    # store 0x48 (H) in UART0+0
     13 03 80 04
     23 a0 62 00
+    # store 0x69 (i) in UART0+0
     13 03 90 06
     23 a0 62 00
+    # store 0x0a (\n) in UART0+0
     13 03 a0 00
     23 a0 62 00
+    # jump back up to the top
     6f f0 5f fe
 
 `ex.elf`: binary file for use with `qemu` (see next section).
diff --git a/subv.py b/subv.py
index e0285cb..3e768a1 100644
--- a/subv.py
+++ b/subv.py
@@ -312,7 +312,7 @@ def format_part(part):
     if isinstance(part, bits.WordBase):
         return str(part)
     elif not is_reference(part):
-        first = "{:02x}".format(part[0])
+        first = "{:x}".format(part[0])
         part = (first, *part[1:])
     return "/".join([str(p) for p in part])
 
diff --git a/validate.py b/validate.py
new file mode 100755
index 0000000..452b4fa
--- /dev/null
+++ b/validate.py
@@ -0,0 +1,295 @@
+#!/usr/bin/env python3
+""" validate.py
+Validates mnemonic labels match the numeric values given for opcodes,
+register codes, etc; normalizes argument order and verifies  that there are
+no missing arguments.
+
+>>> from io import StringIO
+>>> # doctest: +REPORT_NDIFF
+... print(subv.join_all(validate(StringIO('''
+... == code 0x80000000
+... main:
+... # load 0x10010000 (UART0) into t0
+... 37/lui 5/rd/t0 0x10010/imm20
+... # store 0x48 (H) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 48/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # store 0x65 (e) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 65/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # store 0x6c (l) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 6c/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # store 0x6c (l) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 6c/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # store 0x6f (o) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 6f/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # store 0x0a (\\\\n) in UART0+0
+... 13/opi 0/subop/add 6/rd/t1 0/rs/x0 0a/imm12
+... 23/store 2/width/word 5/rs/t0 6/rs/t1 0/off12
+... # jump back up to the top
+... 6f/jal 0/rd/x0 main/off21
+... '''[1:-1]))))
+== code 0x80000000
+main:
+# load 0x10010000 (UART0) into t0
+37/u 5/rd 10010/imm20
+# store 0x48 (H) in UART0+0
+13/i 6/rd 0/funct3 0/rs 48/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# store 0x65 (e) in UART0+0
+13/i 6/rd 0/funct3 0/rs 65/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# store 0x6c (l) in UART0+0
+13/i 6/rd 0/funct3 0/rs 6c/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# store 0x6c (l) in UART0+0
+13/i 6/rd 0/funct3 0/rs 6c/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# store 0x6f (o) in UART0+0
+13/i 6/rd 0/funct3 0/rs 6f/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# store 0x0a (\\n) in UART0+0
+13/i 6/rd 0/funct3 0/rs a/imm12
+23/s 5/rs1 0/off12 2/funct3 6/rs2
+# jump back up to the top
+6f/j 0/rd main/off21
+"""
+
+import subv
+import bits
+
+
+def pop_piece(line, labels):
+    for part in line:
+        if part[1] in labels:
+            line.remove(part)
+            return (part[0], labels[0])
+
+    raise ValueError("Expected a part with labels {}".format(labels))
+
+
+REG_NAMES = {}
+REG_NAMES.update(
+    {
+        name: i
+        for i, name in enumerate(
+            [
+                "zero",
+                "ra",
+                "sp",
+                "gp",
+                "tp",
+                "t0",
+                "t1",
+                "t2",
+                "s0",
+                "s1",
+                "a0",
+                "a1",
+                "a2",
+                "a3",
+                "a4",
+                "a5",
+                "a6",
+                "a7",
+                "s2",
+                "s3",
+                "s4",
+                "s5",
+                "s6",
+                "s7",
+                "s8",
+                "s9",
+                "s10",
+                "s11",
+                "t3",
+                "t4",
+                "t5",
+                "t6",
+            ]
+        )
+    }
+)
+REG_NAMES.update({"x{}".format(i): i for i in range(32)})
+
+
+def pop_register(line, labels):
+    for part in line:
+        if part[1] in labels:
+            line.remove(part)
+
+            value = part[0]
+            if value < 0 or value > 31:
+                raise ValueError(
+                    "Invalid register value {} (expected 0...31)".format(value)
+                )
+
+            if len(part) > 2:
+                name = part[2]
+                try:
+                    assert value == REG_NAMES[name], ValueError(
+                        "Invalid register value {} for '{}', expected {}".format(
+                            value, name, REG_NAMES[name]
+                        )
+                    )
+                except KeyError:
+                    raise ValueError("Unknown register name '{}'".format(name))
+
+            return (part[0], labels[0])
+
+    raise ValueError("Expected a register with labels {}".format(labels))
+
+
+def validate_u(inputs):
+    op = inputs.pop(0)
+    rd = pop_register(inputs, ["rd", "dest"])
+    imm = inputs.pop()
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "u"),
+        rd,
+        imm,
+    ]
+
+
+def validate_s(inputs):
+    op = inputs.pop(0)
+    width = pop_piece(inputs, ["funct3", "funct", "width"])
+    base = pop_register(inputs, ["rs1", "rs", "base"])
+    src = pop_register(inputs, ["rs2", "rs", "src"])
+    offset = inputs.pop()
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "s"),
+        base,
+        offset,
+        width,
+        src,
+    ]
+
+
+def validate_i(inputs):
+    op = inputs.pop(0)
+
+    rs_name = "src"
+    if op[1] in ["load", "jalr"]:
+        rs_name = "base"
+
+    dest = pop_register(inputs, ["rd", "dest"])
+    funct = pop_piece(inputs, ["funct3", "funct", "subop"])
+    rs = pop_register(inputs, ["rs", rs_name])
+    imm = inputs.pop()
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "i"),
+        dest,
+        funct,
+        rs,
+        imm,
+    ]
+
+
+def validate_r(inputs):
+    op = inputs.pop(0)
+
+    dest = pop_register(inputs, ["rd", "dest"])
+    funct = pop_piece(inputs, ["funct7", "funct", "subop"])
+    rs1 = pop_register(inputs, ["rs1", "rs", "src1", "src"])
+    rs2 = pop_register(inputs, ["rs2", "rs", "src2", "src"])
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "r"),
+        dest,
+        funct,
+        rs1,
+        rs2,
+    ]
+
+
+def validate_j(inputs):
+    op = inputs.pop(0)
+
+    dest = pop_register(inputs, ["rd", "dest"])
+    offset = inputs.pop()
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "j"),
+        dest,
+        offset,
+    ]
+
+
+def validate_b(inputs):
+    op = inputs.pop(0)
+
+    funct = pop_piece(inputs, ["funct3", "funct", "subop"])
+    rs1 = pop_register(inputs, ["rs1", "rs", "src1", "src"])
+    rs2 = pop_register(inputs, ["rs2", "rs", "src2", "src"])
+    offset = inputs.pop()
+
+    assert len(inputs) == 0, ValueError("Extra arguments: {}".format(inputs))
+
+    return [
+        (op[0], "b"),
+        funct,
+        src1,
+        src2,
+        offset,
+    ]
+
+
+instr_map = {
+    "opi": (validate_i, 0x13),
+    "opr": (validate_r, 0x33),
+    "load": (validate_i, 0x03),
+    "store": (validate_s, 0x23),
+    "jal": (validate_j, 0x6F),
+    "jalr": (validate_i, 0x67),
+    "branch": (validate_b, 0x63),
+    "lui": (validate_u, 0x37),
+    "auipc": (validate_u, 0x17),
+}
+
+
+@subv.with_parsed_lines
+def validate(iter):
+    for segment, line in iter:
+        if line["type"] == "instr" and segment == "code":
+            op = line["instr"][0]
+            assert len(op) == 2, "instruction without op label: {}".format(op)
+
+            (op, label) = op
+            if label not in instr_map:
+                raise ValueError("unknown op label: {}".format(label))
+            (validator, expected) = instr_map[label]
+            if op != expected:
+                raise ValueError(
+                    "opcode {} doesn't match label {} (expected {})".format(
+                        op, label, expected
+                    )
+                )
+
+            line["instr"] = validator(line["instr"][:])
+            line = yield subv.format(line)
+        else:
+            line = yield line["raw"]
+
+
+if __name__ == "__main__":
+    import sys
+
+    for line in validate(sys.stdin):
+        print(line)