1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

import sys

# Tree-covering toy for technology mapping.
# Subject: m1 = NOT (a AND b), m2 = NOT (c AND d), f = m1 AND m2.
# Each node takes one cell; NAND2 absorbs an inverter over an AND.

A = ("PI", "a")
B = ("PI", "b")
C = ("PI", "c")
D = ("PI", "d")

def and_node(x, y):
    return ("AND", x, y)

def inv_node(x):
    return ("INV", x)

M1 = inv_node(and_node(A, B))
M2 = inv_node(and_node(C, D))
F = and_node(M1, M2)

PH0 = ("PH", 0)
PH1 = ("PH", 1)

PATTERNS = [
    ("INV", 1, ("INV", PH0)),
    ("NAND2", 2, ("INV", ("AND", PH0, PH1))),
    ("AND2", 3, ("AND", PH0, PH1)),
    ("OR2", 3, ("OR", PH0, PH1)),
    ("NOR2", 2, ("INV", ("OR", PH0, PH1))),
]

def match(shape, node, env):
    if shape[0] == "PH":
        idx = shape[1]
        if idx in env:
            return env[idx] == node
        env[idx] = node
        return True
    if shape[0] != node[0]:
        return False
    if len(shape) != len(node):
        return False
    for i in range(1, len(shape)):
        if not match(shape[i], node[i], env):
            return False
    return True

def pin_cover(node):
    return (0, node[1], ("pin", node[1]))

def covers(node):
    if node[0] == "PI":
        return [pin_cover(node)]
    out = []
    for (cell, cost, shape) in PATTERNS:
        env = {}
        if not match(shape, node, env):
            continue
        subs = []
        for i in sorted(env.keys()):
            bound = env[i]
            if bound[0] == "PI":
                subs.append([pin_cover(bound)])
            else:
                subs.append(covers(bound))
        combos = [[]]
        for s in subs:
            grown = []
            for prefix in combos:
                for item in s:
                    grown.append(prefix + [item])
            combos = grown
        for combo in combos:
            total = cost
            parts = []
            kids = []
            for (sc, sd, st) in combo:
                total = total + sc
                parts.append(sd)
                kids.append(st)
            desc = cell + "(" + ",".join(parts) + ")"
            out.append((total, desc, (cell,) + tuple(kids)))
    return out

def run(cover, vals):
    kind = cover[0]
    if kind == "pin":
        return vals[cover[1]]
    if kind == "INV":
        return 1 - run(cover[1], vals)
    if kind == "NAND2":
        return 1 - (run(cover[1], vals) & run(cover[2], vals))
    if kind == "AND2":
        return run(cover[1], vals) & run(cover[2], vals)
    if kind == "OR2":
        return run(cover[1], vals) | run(cover[2], vals)
    if kind == "NOR2":
        return 1 - (run(cover[1], vals) | run(cover[2], vals))
    return None

def spec(vals):
    return (1 - (vals["a"] & vals["b"])) & (1 - (vals["c"] & vals["d"]))

found = covers(F)
areas = sorted([a for (a, d, t) in found])
best = min(found, key=lambda c: c[0])

if len(found) != 4:
    print("FAIL: wanted 4 covers, got " + str(len(found)))
    sys.exit(1)
if areas != [7, 9, 9, 11]:
    print("FAIL: wanted areas 7 9 9 11, got " + " ".join([str(a) for a in areas]))
    sys.exit(1)
if best[0] != 7 or best[1] != "AND2(NAND2(a,b),NAND2(c,d))":
    print("FAIL: wrong minimum cover " + best[1] + " " + str(best[0]))
    sys.exit(1)
for (a, d, t) in found:
    for n in range(16):
        vals = {"a": (n >> 0) & 1, "b": (n >> 1) & 1, "c": (n >> 2) & 1, "d": (n >> 3) & 1}
        if run(t, vals) != spec(vals):
            print("FAIL: cover " + d + " differs on input " + str(n))
            sys.exit(1)
print("PASS: 4 covers with areas 7 9 9 11, minimum area 7 by exhaustive search")