Ternary logic multiplication (0, 1, unknown)

gistfile1.py

N_BITS = 8
MASK = (1 << N_BITS) - 1

class Ternary:
    def __init__(self, ones, unknowns):
        self.ones = ones & MASK
        self.unknowns = unknowns & MASK
        assert (self.ones & self.unknowns) == 0, (bin(self.ones), bin(self.unknowns))

    def __add__(self, other):
        x = self.ones + other.ones
        u = self.unknowns | other.unknowns | (x ^ (x + self.unknowns + other.unknowns))
        return Ternary(x & ~u, u)

    def __sub__(self, other):
        x = self.ones - other.ones
        u = self.unknowns | other.unknowns | ((x + self.unknowns) ^ (x - other.unknowns))
        return Ternary(x & ~u, u)

    def __or__(self, other):
        o = self.ones | other.ones
        return Ternary(o, (self.unknowns | other.unknowns) & ~o)

    def __lshift__(self, count):
        return Ternary(self.ones << count, self.unknowns << count)

    def __mul__(self, other):
        # imprecise
        result = Ternary(0, 0)
        for i in range(N_BITS):
            if self.ones & 1 << i:
                result += other << i
            elif self.unknowns & 1 << i:
                u = other << i
                result += Ternary(0, u.ones | u.unknowns)
        return result

    def __repr__(self):
        return ''.join('U' if self.unknowns & 1 << i else str(self.ones >> i & 1)
                for i in reversed(range(N_BITS)))

    def iter_values(self):
        ones = self.ones
        mask = self.unknowns
        value = 0
        while True:
            yield ones | value
            value = (value - mask) & mask
            if value == 0:
                return

def union(a, b):
    return Ternary(a.ones & b.ones, a.unknowns | b.unknowns | (a.ones ^ b.ones))

def slow_op(a, b, op):
    r = Ternary(op(a.ones, b.ones), 0)
    for A in a.iter_values():
        for B in b.iter_values():
            r = union(r, Ternary(op(A, B), 0))
    return r

def test_op(f, name, input_size=4):
    good = 0
    imprecise = 0
    wrong = 0
    for ao in range(1 << input_size):
        for au in range(1 << input_size):
            if (ao & au) != 0:
                continue
            for bo in range(1 << input_size):
                for bu in range(1 << input_size):
                    if (bo & bu) != 0:
                        continue
                    a = Ternary(ao, au)
                    b = Ternary(bo, bu)
                    r0 = slow_op(a, b, f)
                    r1 = f(a, b)
                    if repr(r0) != repr(r1):
                        if (r0.unknowns & ~r1.unknowns) != 0 or (r1.ones & ~(r0.unknowns | r1.unknowns)) != (r0.ones & ~(r0.unknowns | r1.unknowns)):
                            wrong += 1
                            print('wrong: %r %s %r -> slow=%r, fast=%r' % (a, name, b, r0, r1))
                        else:
                            imprecise += 1
                            print('imprecise: %r %s %r -> slow=%r, fast=%r' % (a, name, b, r0, r1))
                    else:
                        good += 1
    print('testing %r: %d good, %d imprecise, %d wrong' % (name, good, imprecise, wrong))

test_op(lambda a, b: (a * b), "*")
test_op(lambda a, b: (a + b), "+")
test_op(lambda a, b: (a - b), "-")