Compiler Explorer

Source code

import itertools
import copy

m = set()

all_ops = []
li_vars = ["A", "B", "C", "_not(A)", "_not(B)", "_not(C)"]
li_ops = ["_xor", "_or", "_and", "_notxor", "_notor", "_notand"]

def mcmp(x):
    base = x.count("~")
    nvars = 0
    nops = 0
    nops = x.count("_xor(") + x.count("_or(") + x.count("_and(")
    nops += (x.count("_notxor(") + x.count("_notor(") + x.count("_notand("))
    nops += x.count("_not(")

if "a" in x:
        nvars += 1
    if "b" in x:
        nvars += 1
    if "c" in x:
        nvars += 1
    return base + nvars * 100 + nops * 1000

def _not(x):
    return (~x)

def _xor(x, y):
    return (x ^ y)

def _or(x, y):
    return (x | y)

def _and(x, y):
    return (x & y)

def _notxor(x, y):
    return _not(_xor(x, y))

def _notor(x, y):
    return _not(_or(x, y))

def _notand(x, y):
    return _not(_and(x, y))

def _const(v):
    return v

def llvm(v):
    v = v.replace("_or(", "Or(")
    v = v.replace("_xor(", "Xor(")
    v = v.replace("_and(", "And(")
    v = v.replace("_not(", "Not(")
    v = v.replace("_notor(", "Nor(")
    v = v.replace("_notxor(", "Xnor(")
    v = v.replace("_notand(", "Nand(")
    v = v.replace("_const(0)", "Constant::getNullValue(Ty)")
    v = v.replace("_const(1)", "Constant::getAllOnesValue(Ty)")

foo = False
    if False:
        if "CreateNor" in v:
            foo = True
            v = v.replace("CreateNor(", "CreateNot(Or(") + ")"
        if "CreateXnor" in v:
            assert not foo
            foo = True
            v = v.replace("CreateXnor(", "CreateNot(Xor(") + ")"
        if "CreateNand" in v:
            assert not foo
            foo = True
            v = v.replace("CreateNand(", "CreateNot(And(") + ")"

return "return " + v + ";"

all_ops.append("_const(1)")
all_ops.append("_const(0)")

for vars in itertools.product(li_vars, repeat=1):
    break
    v0 = None
    v0 = "{}".format(vars[0])
    all_ops.append(v0)

new_ops = []
for vars in itertools.product(li_vars, repeat=2):
    break
    for ops in itertools.product(li_ops, repeat=1):
        v0 = None
        v0 = "{}({}, {})".format(ops[0], vars[0], vars[1])
        all_ops.append(v0)
        new_ops.append(v0)
for vars in itertools.product(li_vars, repeat=3):
    break
    for ops in itertools.product(li_ops, repeat=2):
        for j in range(0, 2):
            v0 = None
            if j == 0:
                v0 = "{}({}({}, {}), {})".format(ops[0], ops[1], vars[0],
                                                 vars[1], vars[2])
            elif j == 1:
                v0 = "{}({}, {}({}, {}))".format(ops[0], vars[0], ops[1],
                                                 vars[1], vars[2])
            all_ops.append(v0)

for vars in itertools.product(li_vars, repeat=4):
    break
    for ops in itertools.product(li_ops, repeat=3):
        for j in range(0, 4):
            v0 = None
            if j == 0:
                v0 = "{}({}({}, {}), {}({}, {}))".format(
                    ops[0], ops[1], vars[0], vars[1], ops[2], vars[2], vars[3])

elif j == 1:
                v0 = "{}({}({}({}, {}), {}), {})".format(
                    ops[0], ops[1], ops[2], vars[0], vars[1], vars[2], vars[3])
            elif j == 2:
                v0 = "{}({}, {}({}, {}({}, {})))".format(
                    ops[0], vars[0], ops[1], vars[1], ops[2], vars[2], vars[3])
            elif j == 3:
                v0 = "{}({}, {}({}({}, {}), {}))".format(
                    ops[0], vars[0], ops[1], ops[2], vars[1], vars[2], vars[3])

all_ops.append(v0)

for vars in itertools.product(li_vars, repeat=5):
    break
    for ops in itertools.product(li_ops, repeat=4):
        for j in range(0, 2):
            v0 = None
            if j == 0:
                v0 = "{}({}({}({}, {}), {}({}, {})),  {})".format(
                    ops[0], ops[1], ops[2], vars[0], vars[1], ops[3], vars[2],
                    vars[3], vars[4])

elif j == 1:
                v0 = "{}({}({}, {}), {}({}({}, {}), {}))".format(
                    ops[0], ops[1], vars[0], vars[1], ops[2], ops[3], vars[2],
                    vars[3], vars[4])
            all_ops.append(v0)

## This is what actually works nad the script takes a while
all_ops = [
    "_const(0)", "_notor(_or(A, B), C)", "_and(_notor(A, B), C)",
    "_notor(A, B)", "_and(_notor(A, C), B)", "_notor(A, C)",
    "_notor(A, _notxor(B, C))", "_notor(A, _and(B, C))",
    "_notor(A, _notand(B, C))", "_notor(A, _xor(B, C))", "_notor(A, _not(C))",
    "_notor(A, _notor(C, _not(B)))", "_notor(A, _not(B))",
    "_notor(A, _notor(B, _not(C)))", "_notor(A, _notor(B, C))", "_not(A)",
    "_and(A, _notor(B, C))", "_notor(B, C)", "_notor(_notxor(A, C), B)",
    "_notor(_and(A, C), B)", "_notor(_notxor(A, B), C)",
    "_notor(_and(A, B), C)", "_xor(_xor(A, B), _and(_notand(A, B), C))",
    "_xor(_or(A, B), _or(_notxor(A, B), C))",
    "_notor(_notxor(A, B), _notxor(A, C))",
    "_and(_notand(A, B), _notxor(B, C))", "_xor(A, _or(_and(A, B), C))",
    "_xor(A, _or(_notxor(A, B), C))", "_xor(A, _or(_and(A, C), B))",
    "_xor(A, _or(_notxor(A, C), B))", "_xor(A, _or(B, C))",
    "_notand(A, _or(B, C))", "_notor(_notand(A, C), B)",
    "_notor(_xor(A, C), B)", "_notor(B, _not(C))",
    "_notor(B, _notor(C, _not(A)))", "_notor(_notxor(A, B), _xor(A, C))",
    "_xor(A, _notand(_notand(A, B), C))", "_and(_notand(A, B), _xor(B, C))",
    "_xor(_or(_notxor(A, B), C), B)", "_and(_xor(A, B), C)",
    "_xor(_xor(A, B), _notor(_and(A, B), C))", "_and(_notand(A, B), C)",
    "_xor(_or(_notxor(A, B), _xor(A, C)),  A)",
    "_notor(_notxor(A, B), _notor(B, C))", "_xor(A, _or(B, _not(C)))",
    "_xor(A, _or(_xor(A, C), B))", "_notand(A, _or(B, _not(C)))",
    "_notor(B, _not(A))", "_notor(_notor(A, _not(C)), B)",
    "_notor(_notor(A, C), B)", "_not(B)", "_and(_xor(A, B), _notand(B, C))",
    "_xor(B, _or(A, _notxor(B, C)))", "_xor(_or(A, C), B)",
    "_notand(_or(A, C), B)", "_notor(_notxor(A, B), _notor(A, C))",
    "_xor(_or(A, _not(C)), B)", "_xor(B, _or(A, _xor(B, C)))",
    "_notand(_or(A, _not(C)), B)", "_xor(A, B)",
    "_xor(A, _or(_notor(A, C), B))", "_xor(A, _or(_notor(A, _not(C)), B))",
    "_notand(A, B)", "_notor(_notand(A, B), C)", "_notor(_xor(A, B), C)",
    "_notor(_xor(A, B), _notxor(A, C))", "_xor(A, _notand(_notand(A, C), B))",
    "_notor(C, _not(B))", "_notor(_notor(B, _not(A)), C)",
    "_xor(_or(_and(A, C), B), C)", "_xor(_or(_notxor(A, C), B), C)",
    "_and(_xor(A, C), B)", "_xor(_or(_notxor(A, B), _and(A, C)),  C)",
    "_notor(_notxor(A, C), _notor(B, C))", "_xor(A, _or(C, _not(B)))",
    "_and(_notand(A, C), B)", "_xor(_or(_xor(A, B), _notxor(A, C)),  A)",
    "_xor(A, _or(_xor(A, B), C))", "_notand(A, _notand(B, _not(C)))",
    "_notor(C, _not(A))", "_notor(_notor(A, _not(B)), C)",
    "_and(_xor(A, C), _notand(B, C))", "_xor(_or(_notxor(B, C), A), C)",
    "_notor(_notor(A, B), C)", "_not(C)", "_xor(_or(A, B), C)",
    "_notand(_or(A, B), C)", "_notor(_notor(A, B), _notxor(A, C))",
    "_xor(_or(A, _not(B)), C)", "_xor(A, C)", "_xor(A, _or(_notor(A, B), C))",
    "_xor(_or(_xor(B, C), A), C)", "_notand(_or(A, _not(B)), C)",
    "_xor(A, _or(_notor(A, _not(B)), C))", "_notand(A, C)",
    "_and(A, _xor(B, C))", "_xor(_or(_notxor(A, B), _and(B, C)),  C)",
    "_notor(_notor(A, C), _notxor(B, C))", "_xor(B, _or(C, _not(A)))",
    "_notor(_notor(A, B), _notxor(B, C))", "_xor(_or(B, _not(A)), C)",
    "_xor(B, C)", "_or(_notor(A, B), _xor(B, C))",
    "_xor(_xor(A, B), _notor(_notor(A, B), C))", "_xor(_notxor(A, B), C)",
    "_xor(_and(A, B), C)", "_or(_notor(A, B), _xor(_notxor(A, B), C))",
    "_xor(_and(A, C), B)", "_xor(_or(_notxor(A, B), _notor(A, C)),  C)",
    "_or(_notor(A, _not(B)), _xor(B, C))", "_notand(A, _notxor(B, C))",
    "_and(A, _notand(B, C))", "_xor(_notor(_xor(A, B), _xor(A, C)),  A)",
    "_xor(_or(_xor(A, B), C), B)", "_notand(_notand(A, _not(C)), B)",
    "_xor(_or(_xor(A, C), B), C)", "_notand(_notand(A, _not(B)), C)",
    "_xor(B, _or(_notor(B, _not(A)), C))", "_notand(B, C)",
    "_xor(A, _and(B, C))", "_xor(_or(_notxor(A, B), _notor(B, C)),  C)",
    "_or(_xor(A, C), _notor(B, _not(A)))", "_notand(_notxor(A, C), B)",
    "_or(_xor(A, B), _notor(C, _not(A)))", "_notand(_notxor(A, B), C)",
    "_or(_xor(A, B), _xor(A, C))", "_notand(_and(A, B), C)",
    "_and(_and(A, B), C)", "_notor(_xor(A, B), _xor(A, C))",
    "_and(_notxor(A, B), C)", "_notor(_xor(A, B), _notor(C, _not(A)))",
    "_and(_notxor(A, C), B)", "_notor(_xor(A, C), _notor(B, _not(A)))",
    "_xor(_notor(_notxor(A, B), _notor(B, C)),  C)", "_xor(A, _notand(B, C))",
    "_and(B, C)", "_xor(B, _notor(_notor(B, _not(A)), C))",
    "_and(_notand(A, _not(B)), C)", "_xor(_notor(_xor(A, C), B), C)",
    "_and(_notand(A, _not(C)), B)", "_xor(_notor(_xor(A, B), C), B)",
    "_xor(_or(_xor(A, B), _xor(A, C)),  A)", "_notand(A, _notand(B, C))",
    "_and(A, _notxor(B, C))", "_notor(_notor(A, _not(B)), _xor(B, C))",
    "_xor(_notor(_notxor(A, B), _notor(A, C)),  C)", "_xor(_notand(A, C), B)",
    "_notor(_notor(A, B), _xor(_notxor(A, B), C))", "_xor(_notand(A, B), C)",
    "_xor(_xor(A, B), C)", "_xor(_xor(A, B), _or(_notor(A, B), C))",
    "_notor(_notor(A, B), _xor(B, C))", "_notxor(B, C)",
    "_xor(_notor(B, _not(A)), C)", "_or(_notor(A, B), _notxor(B, C))",
    "_xor(B, _notor(C, _not(A)))", "_or(_notor(A, C), _notxor(B, C))",
    "_xor(_and(_xor(A, B), _notand(B, C)),  C)", "_notand(A, _xor(B, C))",
    "_and(A, C)", "_xor(A, _notor(_notor(A, _not(B)), C))",
    "_and(_or(A, _not(B)), C)", "_xor(_notor(_xor(B, C), A), C)",
    "_xor(A, _notor(_notor(A, B), C))", "_notxor(A, C)",
    "_xor(_notor(A, _not(B)), C)", "_or(_notor(A, B), _notxor(A, C))",
    "_and(_or(A, B), C)", "_xor(_notor(A, B), C)", "C", "_or(_notor(A, B), C)",
    "_xor(_notor(_notxor(B, C), A), C)", "_or(_notxor(A, C), _and(B, C))",
    "_or(_notor(A, _not(B)), C)", "_or(C, _not(A))",
    "_and(A, _notand(B, _not(C)))", "_xor(A, _notor(_xor(A, B), C))",
    "_xor(_notor(_xor(A, B), _notxor(A, C)),  A)", "_notand(_notand(A, C), B)",
    "_xor(A, _notor(C, _not(B)))", "_or(_notxor(A, C), _notor(B, C))",
    "_xor(_and(_xor(A, B), _notand(A, C)),  C)", "_notand(_xor(A, C), B)",
    "_xor(_notor(_notxor(A, C), B), C)", "_xor(_notor(_and(A, C), B), C)",
    "_or(_notor(B, _not(A)), C)", "_or(C, _not(B))",
    "_xor(A, _and(_notand(A, C), B))", "_or(_xor(A, B), _notxor(A, C))",
    "_or(_xor(A, B), C)", "_or(_notand(A, B), C)", "_and(A, B)",
    "_xor(A, _notor(_notor(A, _not(C)), B))",
    "_xor(A, _notor(_notor(A, C), B))", "_notxor(A, B)",
    "_and(_or(A, _not(C)), B)", "_xor(B, _notor(A, _xor(B, C)))",
    "_xor(_notor(A, _not(C)), B)", "_or(_notxor(A, B), _notor(A, C))",
    "_and(_or(A, C), B)", "_xor(_notor(A, C), B)",
    "_xor(B, _notor(A, _notxor(B, C)))", "_or(_notxor(A, B), _and(B, C))", "B",
    "_or(_notor(A, C), B)", "_or(_notor(A, _not(C)), B)", "_or(B, _not(A))",
    "_and(A, _or(B, _not(C)))", "_xor(A, _notor(_xor(A, C), B))",
    "_xor(A, _notor(B, _not(C)))", "_or(_notxor(A, B), _notor(B, C))",
    "_xor(_notor(_notxor(A, B), _xor(A, C)),  A)", "_notand(_notand(A, B), C)",
    "_xor(_xor(A, B), _or(_and(A, B), C))", "_notand(_xor(A, B), C)",
    "_xor(_notor(_notxor(A, B), C), B)", "_or(_and(A, B), _notxor(B, C))",
    "_xor(A, _and(_notand(A, B), C))", "_or(_notxor(A, B), _xor(A, C))",
    "_or(B, _notor(C, _not(A)))", "_or(B, _not(C))", "_or(_xor(A, C), B)",
    "_or(_notand(A, C), B)", "_and(A, _or(B, C))", "_xor(A, _notor(B, C))",
    "_xor(A, _notor(_notxor(A, C), B))", "_xor(A, _notor(_and(A, C), B))",
    "_xor(A, _notor(_notxor(A, B), C))", "_xor(A, _notor(_and(A, B), C))",
    "_or(_and(A, B), _xor(B, C))", "_or(_notxor(A, B), _notxor(A, C))",
    "_xor(_or(A, B), _notor(_notxor(A, B), C))",
    "_xor(_xor(A, B), _notand(_notand(A, B), C))", "_or(_and(A, B), C)",
    "_or(_notxor(A, B), C)", "_or(_and(A, C), B)", "_or(_notxor(A, C), B)",
    "_or(B, C)", "_notand(A, _notor(B, C))", "A", "_or(A, _notor(B, C))",
    "_or(A, _notor(B, _not(C)))", "_or(A, _not(B))",
    "_or(A, _notor(C, _not(B)))", "_or(A, _not(C))", "_or(A, _xor(B, C))",
    "_or(A, _notand(B, C))", "_or(A, _and(B, C))", "_or(A, _notxor(B, C))",
    "_or(A, C)", "_notand(_notor(A, C), B)", "_or(A, B)",
    "_notand(_notor(A, B), C)", "_or(_or(A, B), C)", "_const(1)"
]
rmap_i = {}

prog = int(len(all_ops) / 100)
cprog = 0
for i in range(0, len(all_ops)):
    use = all_ops[i]
    if i > cprog:
        print("{}/{}".format(i, len(all_ops)))
        cprog += prog
    v = []
    for a in [0, 1]:
        for b in [0, 1]:
            for c in [0, 1]:
                v.append(
                    eval(
                        use.replace("A", str(a)).replace("B", str(b)).replace(
                            "C", str(c))) & 1)
    v = "".join(map(str, v))
    assert len(v) == 8, v
    rmap_i.setdefault(v, []).append(use)

rmap = {}
for k in rmap_i:
    print(k)
    rmap[k] = sorted(rmap_i[k], key=mcmp)[0]

out = []
for i in range(0x0, 256):
    results = []
    for a in [0, 1]:
        for b in [0, 1]:
            for c in [0, 1]:
                res = i & (1 << ((a << 2) + (b << 1) + (c << 0)))
                if res != 0:
                    res = 1
                results.append(res)
                print("{}: {} | {} | {} -> {}".format(hex(i), a, b, c, res))

k = "".join(map(str, results))
    assert (len(k) == 8)
    print(k)
    if k in rmap:
        print("{} -> {}".format(hex(i), rmap[k]))
        print(llvm(rmap[k]))
        code = llvm(rmap[k])
        if i not in {
                0x0, 0xf, 0x33, 0x3c, 0x3f, 0x55, 0x5a, 0x5f, 0x66, 0x77, 0x88,
                0xa0, 0xaa, 0xc0, 0xcc, 0xee, 0xf0, 0xfa, 0xfc, 0xff
        }:
            checks = []
            if "A" in rmap[k] and "B" in rmap[k] and "C" in rmap[k]:
                checks.append("ABCIsConst")
            else:
                if "A" in rmap[k] and "B" in rmap[k]:
                    checks.append("ABIsConst")
                if "A" in rmap[k] and "C" in rmap[k]:
                    checks.append("ACIsConst")
                if "B" in rmap[k] and "C" in rmap[k]:
                    checks.append("BCIsConst")
            assert len(checks) == 1
            code = "if ({})\n{}\nbreak;".format(checks[0], code)

out.append("case {}: {}".format(hex(i), code))
    else:
        assert (0)
        out.append("case {}: // No 3-op solution.\nbreak;".format(hex(i)))
#    else:

m.add("".join(map(str, results)))
    print("")
print(len(m))

assert len(m) == 256
print("\n".join(out))