combinatorial bit pattern synthesizer in python

pattern-synth.py

#!/usr/bin/env python3

from math import log
from random import randint
from functools import reduce
from itertools import product
from itertools import permutations

# Random bit utilities

def popcnt(v):
    count = 0
    for i in range(v.bit_length()):
        if (v & (1 << i)) != 0:
            count += 1
    return count

def sparserandint(w,d):
    v = 0
    while (popcnt(v) < d):
        v = v | 1 << randint(0,w)
    return v

# Bit pattern generators

class Div:
    def __init__(self,idx,width,msb,lsb):
        self.idx = idx
        self.width = width
        self.msb = msb
        self.lsb = lsb

class BitPattern:
    def mask(self,d):
        return ((1 << d.msb) - 1) - ((1 << d.lsb) - 1)

class FixedPattern(BitPattern):
    def __init__(self,val):
        self.val = val
    def fval(self):
        return self.val
    def values(self):
        return [self.val]
    def patterns(self):
        return [self]

class AllZero(FixedPattern):
    def __init__(self):
        FixedPattern.__init__(self,0)

class AllOne(FixedPattern):
    def __init__(self):
        FixedPattern.__init__(self,-1)

class PatternGen(BitPattern):
    def __init__(self,gen):
        self.val = list(gen)
    def values(self):
        return self.val
    def patterns(self):
        return map(lambda i: FixedPattern(i), self.values())

class CounterGen(PatternGen):
    def __init__(self,s,e):
        super().__init__(range(s,e+1))

class DiffuseRandGen(PatternGen):
    def __init__(self,w,n):
        super().__init__(map(lambda i : randint(0,2**w), range(0,n)))

class SparseRandGen(PatternGen):
    def __init__(self,w,n,d):
        super().__init__(map(lambda i : sparserandint(w,d), range(0,n)))

# Two's complement integer utilities

def IntToUInt(w,n):
    if n < 0:
        n = ((-n ^ (2 ** w - 1)) + 1) % (2 ** w)
    return n

def UIntToInt(w,n):
    if n & ((2 ** (w-1))-1):
        n = -(((n ^ (2 ** w - 1)) + 1) % (2 ** w))
    return n

def ListBinaryBytes(n,w):
    return map(lambda i : ''.join(map(lambda j:
        ( "▄", "▟", "▙", "█" )[(n >> ((i << 3) + (j << 1))) & 3],
        reversed(range(0,4)))), reversed(range(0,w>>3)))

def ListHexBytes(n,w):
    return map(lambda i : "0x%s" % '{:02X}'.format((n>>(i<<3))&255),
        reversed(range(0,w>>3)))

def DumpHexBinary(n,w):
    print(" ".join(ListBinaryBytes(n,w)))
    print(" ".join(ListHexBytes(n,w)))

# Combinatorial expansion of pattern subdivision generators

def SubDiv(p1,p2):
    return map(lambda i : 2 ** i, range(p1,p2))

def PowBreak(n,m):
    return lambda width: SubDiv(n,m if m != -1 else int(log(width,2))+1)

def DivBreak(n,m):
    return lambda width: map(lambda x: int(width/x), range(n,m+1))

def CumulativeSum(l): 
    return [sum(l[0:x:1]) for x in range(0, len(l)+1)][1:]

def SpreadDiv(count):
    def f(width,incr):
        for iter in range(0,count):
            m = int(width/incr)
            l = CumulativeSum([incr]*m)
            i = 0
            while l[-1] < width:
                l[i % m] += 1
                i += 1
            yield [Div(i,width,t[0],t[1])
                for i, t in enumerate(zip(l, [0]+list(l)))] 
    return f

def ScatterDiv(count):
    def f(width,incr):
        for iter in range(0,count):
            m = int(width/incr)
            l = [randint(0,width) for i in range(0,m-1)]
            l.sort()
            l.append(width)
            yield [Div(i,width,t[0],t[1])
                for i, t in enumerate(zip(l, [0]+list(l)))] 
    return f

def GenDivs(genbreak,gendiv):
    def f(width):
        for incr in genbreak(width):
            yield gendiv(width,incr)
    return f

def OnePerm():
    def f(pat):
        return [pat]
    return f

def AllPerms():
    def f(pat):
        return permutations(pat)
    return f

def CombineDiv(pats,divs):
    return map(lambda pat : reduce(lambda x,y : x|y,
        [IntToUInt(d.width, p.fval() << d.lsb) & p.mask(d)
            for p,d in zip(pat,divs)]), pats)

def ReifyPat(width,divs,pat):
    pats = map(lambda pc : pc.patterns(), pat[:len(divs)])
    return CombineDiv(product(*pats), divs)

# Test combinatorial expansion of bit pattern subdivision generators

def SeqVal(width,GenDivs,GenPat,GenPerm):
    for divsgen in GenDivs(width):
        for divs in divsgen:
            for pat in GenPat(width,divs):
                pat = pat[:len(divs)]
                for perm in GenPerm(pat):
                    for val in ReifyPat(width,divs,perm):
                        yield val

# pattern synthesis generator functions
#
# - PowBreak does creates power of 2 subdivisions.
# - DivBreak uses divides over the range of bits e.g. 128/5.
# - SpreadDiv spreads the division out evenly.
# - ScatterDiv spreads them out with a jitter parameter.
# - GenPat is a user function to yield pattern templates.
# - SeqVal ties together the cascade of permutations and combinations. 

def GenPat():
    def f(w,d):
        q = w - (w>>2)
        yield [CounterGen(-2,1)] + [AllZero(), AllOne()] * int(len(d)/2)
        yield [SparseRandGen(w,1,q)] + [AllZero(), AllOne()] * int(len(d)/2)
        yield [DiffuseRandGen(w,1)] + [AllZero(), AllOne()] * int(len(d)/2)
        yield [SparseRandGen(w,1,q)] + [AllZero(), AllOne()] * int(len(d)/2)
    return f

w = 128

for v in SeqVal(w, GenDivs(PowBreak(0,-1), SpreadDiv(1)), GenPat(), OnePerm()):
    DumpHexBinary(v,w)

for v in SeqVal(w, GenDivs(DivBreak(3,4), ScatterDiv(2)), GenPat(), AllPerms()):
    DumpHexBinary(v,w)