Track alignment (and other known-bits properties) through arithmetic

aligner.py

#!/usr/bin/python2

NUM_BITS = 16
ALL_BITS = (1 << NUM_BITS) - 1

def cpl(x):
    return (~x)&ALL_BITS

class AlignedNumber(object):
    def __init__(self, mask=ALL_BITS, value=0):
        self.mask = mask & ALL_BITS
        self.value = value & ALL_BITS
        self.validate()
    @classmethod
    def const(cls, value):
        """All bits are known, so mask is zero."""
        return cls(0, value)
    def validate(self):
        # Check for bits both known and unknown
        assert not self.mask & self.value, str(self)
    def __str__(self):
        return '%04x:%04x'%(self.value, self.mask)
    def bin(self):
        out = []
        m = self.mask
        v = self.value
        while len(out) < NUM_BITS:
            if m & 1:
                out.insert(0, 'x')
            else:
                out.insert(0, '%d'%(v&1))
            m >>= 1
            v >>= 1
        return ''.join(out)
    def __lshift__(self, sh):
        """Shift mask and value left, low bits become 0"""
        assert isinstance(sh, int), sh
        return self.__class__(self.mask << sh, self.value << sh)
    def __rshift__(self, sh):
        """Shift mask and value right, high bits become 0."""
        assert isinstance(sh, int), sh
        return self.__class__(self.mask >> sh, self.value >> sh)
    def __add__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        sm = (self.mask + other.mask) & ALL_BITS
        sv = (self.value + other.value) & ALL_BITS
        sigma = (sm + sv) & ALL_BITS
        chi = sigma ^ sv # unknown carries
        mu = chi | self.mask | other.mask
        return self.__class__(mu, sv & cpl(mu))
    def __sub__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        dv = (self.value - other.value) & ALL_BITS
        alpha = (dv + self.mask) & ALL_BITS
        beta = (dv - other.mask) & ALL_BITS
        chi = alpha ^ beta
        mu = chi | self.mask | other.mask
        return self.__class__(mu, dv & cpl(mu))
    def __and__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        alpha = self.value | self.mask
        beta = other.value | other.mask
        v = self.value & other.value
        return self.__class__(alpha & beta & cpl(v), v)
    def __or__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        v = self.value | other.value
        mu = self.mask | other.mask
        return self.__class__(mu & cpl(v), v)
    def __xor__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        v = self.value ^ other.value
        mu = self.mask | other.mask
        return self.__class__(mu, v & cpl(mu))
    def __mul__(self, other):
        if isinstance(other, int):
            other = AlignedNumber.const(other)
        assert isinstance(other, AlignedNumber), other
        pi = self.value * other.value
        gamma = self.mask * other.value
        accum = AlignedNumber(0, pi) + AlignedNumber(gamma, 0)
        reg = self.mask | self.value
        bits = other.mask
        while bits:
            if (bits & 1):
                accum += AlignedNumber(reg, 0)
            bits >>= 1
            reg <<= 1
        return accum
    def is_aligned(self, bits):
        """We are 2^n-aligned iff the bottom n bits are known-0."""
        mask = (1 << bits) - 1
        return not ((self.mask | self.value) & mask)

if __name__ == '__main__':
    a = AlignedNumber.const(2)
    b = AlignedNumber() << 2
    c = AlignedNumber.const(14)
    print a, b, c
    print a + b, a + b + c
    assert (a + b + c).is_aligned(2)
    d = (AlignedNumber() << 4) >> 2
    print d
    assert d.is_aligned(2)
    e = d - 3
    print e, e - 1
    assert (e - 1).is_aligned(2)
    f = AlignedNumber(1, 0x8c)
    g = AlignedNumber(4, 1)
    print f, g, f * g
    h = (f * g) >> 1
    print h
    assert h.is_aligned(1)
    print '\n'.join(o.bin() for o in (a, b, c, a + b, a + b + c, d, e, e - 1, f, g, f * g, h))
    i = AlignedNumber(0x38, 7)
    j = AlignedNumber(0x92, 0x49)
    print i, j, i&j, i|j, i^j
    print '\n'.join(o.bin() for o in (i, j, i&j, i|j, i^j))