Skip to content

Instantly share code, notes, and snippets.

@michaeljclark

michaeljclark/pattern-synth.py

Last active September 9, 2024 11:32
Show Gist options
  • Save michaeljclark/ea2cd16b11ccfa36874c4a4fd38f78b5 to your computer and use it in GitHub Desktop.
Save michaeljclark/ea2cd16b11ccfa36874c4a4fd38f78b5 to your computer and use it in GitHub Desktop.
Download ZIP
combinatorial bit pattern synthesizer in python
Raw
pattern-synth.py
#!/usr/bin/env python3
# MIT license
#
# combinatorial bit pattern synthesizer in python
#
# Copyright (c) 2024 Michael Clark <michaeljclark@mac.com>
#
# Permission to use, copy, modify, and distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
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):
return map(lambda i : ''.join(map(lambda j:
( "▄", "▟", "▙", "█" )[(n >> ((i << 3) + (j << 1))) & 3],
reversed(range(0,4)))), reversed(range(0,16)))
def ListHexBytes(n):
return map(lambda i : "0x%s" % '{:02X}'.format((n>>(i<<3))&255),
reversed(range(0,16)))
def DumpHexBinary(n):
print(" ".join(ListBinaryBytes(n)))
print(" ".join(ListHexBytes(n)))
# 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
def GenPat():
def f(width,divs):
yield [CounterGen(-2,1)] + [AllZero(), AllOne()] * int(len(divs)/2)
yield [SparseRandGen(width,1,96)] + [AllZero(), AllOne()] * int(len(divs)/2)
yield [DiffuseRandGen(width,1)] + [AllZero(), AllOne()] * int(len(divs)/2)
yield [SparseRandGen(width,1,16)] + [AllZero(), AllOne()] * int(len(divs)/2)
return f
for v in SeqVal(128, GenDivs(PowBreak(0,-1), SpreadDiv(1)), GenPat(), OnePerm()):
DumpHexBinary(v)
for v in SeqVal(128, GenDivs(DivBreak(3,4), ScatterDiv(2)), GenPat(), AllPerms()):
DumpHexBinary(v)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment