Construction of a few simple generators (WIP)
import sys
sys.path.insert(0, '../..')
The simple model counting '1' bits in a standard logic array is as follows:
def count_ones(v):
ones = 0
for i, item in enumerate(v):
if item == True:
ones += 1
return ones
Verify:
from myirl import *
v = intbv(0xaa)[8:]
assert count_ones(v) == 4
We could implement the above as is and let synthesis figure out the rest. However, we could also model it according to this interesting article using half and full adders with the most basic logic possible. So, we first define these as primitive functions:
Bool = Signal.Type(bool)
def half_adder(a : Bool, b : Bool, q : Bool.Output, c : Bool.Output):
return [
q.set(a ^ b), c.set(a & b)
]
def full_adder(a : Bool, b : Bool, cin : Bool, q : Bool.Output, c : Bool.Output):
x = a ^ b
return [
q.set(x ^ cin), c.set((a & b) | (cin & (x)))
]
We then compose the '1' bit counter from these primitives by an inductive approach. For a 2-bit intbv, we can use a half adder. Note the *half_adder
notation to unroll into a flat list for the return value:
def bit_count2(A, ones):
Sum = Bool(name = "S")
Carry = Bool(name = "C")
return [
*half_adder(A[0], A[1], Sum, Carry),
ones.set(concat(Carry, Sum))
]
Make sure this yields the same as the count_ones
function applied on the wire bit array for all values possible.
To evaluate this functional description manually:
from myirl import *
import math
@utils.timer
def verify(N, func):
A = Signal(intbv()[N:])
M = int(math.log2(N))
ones = Signal(intbv()[1 + M:])
for i in range((2 ** N)-1, -1, -1):
A.set(i).evaluate() # Set current signal value to `i`
for gen in func(A, ones):
gen.evaluate()
n = count_ones(A.wire) # Call count_ones for the wire bits of A
_n = int(ones.evaluate())
print(bin(A.wire), "-->", _n)
assert _n == n
Let's take this for the double amount.
def bit_count4(A, ones):
o = [ Signal(intbv()[2:]) for _ in range(2)]
C0, C1 = [Bool() for _ in range(2)]
S0, S1 = [Bool() for _ in range(2)]
logic = [
*bit_count2(A[2:0], o[0]),
*bit_count2(A[4:2], o[1]),
# We could replace this reduction by the adder primitives below:
ones.set(o[0] + o[1]),
# *half_adder(o[0][0], o[1][0], S0, C0),
# *full_adder(o[0][1], o[1][1], C0, S1, C1),
# ones.set(concat(C1, S1, S0))
]
return logic
verify(4, bit_count4)
0b1111 --> 4 0b1110 --> 3 0b1101 --> 3 0b1100 --> 2 0b1011 --> 3 0b1010 --> 2 0b1001 --> 2 0b1000 --> 1 0b111 --> 3 0b110 --> 2 0b101 --> 2 0b100 --> 1 0b11 --> 2 0b10 --> 1 0b1 --> 1 0b0 --> 0 Finished verify in 2.4207 secs
Note: This does not result in the optimum gate level count, because the two bit result of the half adder is maximum 2 (Input: "11"). For recursion with restriction to power of two data widths however, this is easiest to implement.
Finally, let's go 'recursive'. Since the variables and signals inside the function are flattened by default through the recursion, we need to provide unique names. This is simply done by prefixing.
Due to VHDL being stricter with recursive slicing than Python, we need to use variables. We don't prefix them, to generate less unnecessary instances. (Question: Why can't we do this with signals?)
def bit_count(A, ones, prefix = "R"):
N = len(A)
M = N // 2
if N > 2:
o = [ Signal(intbv()[len(ones)-1:], name=prefix + "%do_%d" % (i, M)) for i in range(2)]
upper = Variable("u_%d" % M, intbv()[M:])
lower = Variable("l_%d" % M, intbv()[M:])
logic = [
lower.assign(A[:M]),
upper.assign(A[M:]),
*bit_count(lower, o[0], prefix + "0"),
*bit_count(upper, o[1], prefix + "1"),
ones.set(o[0] + o[1]),
]
else:
Sum = Bool(name = prefix + "S")
Carry = Bool(name = prefix + "C")
logic = [
*half_adder(A[0], A[1], Sum, Carry),
ones.set(concat(Carry, Sum))
]
return logic
We don't verify that, as it would take too long. Instead, we generate HDL from it:
from myirl import *
@block
def ones_counter(data : Signal, count_ones : Signal.Output):
if len(data) != 2 ** (len(count_ones) -1):
raise ValueError("Check dimensions")
@genprocess()
def worker():
yield bit_count(data, count_ones)
return instances()
from myirl import simulation as sim
from myirl.test.common_test import *
@block
def testbench():
data = Signal(intbv()[32:])
count1s = Signal(intbv()[6:])
uut = ones_counter(data, count1s)
@sim.generator
def test():
for v in [0xaaf0, 0x1000, 0x2340]:
z = intbv(v)[32:]
c = count_ones(z)
yield [
data.set(z),
sim.wait("1 ns"),
sim.print_("COUNT:", count1s),
sim.assert_(count1s == c, "Failed"),
]
return instances()
def test():
tb = testbench()
f = tb.elab(targets.VHDL, elab_all = True)
run_ghdl(f, tb, debug = True)
test()
Creating sequential 'testbench/test' Writing 'ones_counter' to file /tmp/myirl_top_testbench_06qpa197/ones_counter.vhdl Finished _elab in 0.0115 secs Writing 'testbench' to file /tmp/myirl_top_testbench_06qpa197/testbench.vhdl DEBUG BOOLOP True count1s == C:8 DEBUG BOOLOP True count1s == C:1 DEBUG BOOLOP True count1s == C:4 Finished _elab in 0.0099 secs Creating library file /tmp/myirl_module_defs_tof8m9tn/module_defs.vhdl ==== COSIM stdout ==== ==== COSIM stderr ==== ==== COSIM stdout ==== analyze /home/testing/src/myhdl2/myhdl.v2we/examples/../../myirl/targets/../test/vhdl/txt_util.vhdl analyze /home/testing/src/myhdl2/myhdl.v2we/examples/../../myirl/targets/libmyirl.vhdl analyze /tmp/myirl_top_testbench_06qpa197/ones_counter.vhdl analyze /tmp/myirl_top_testbench_06qpa197/testbench.vhdl elaborate testbench ==== COSIM stderr ==== ==== COSIM stdout ==== COUNT: 0x08 COUNT: 0x01 COUNT: 0x04 ==== COSIM stderr ====
The procedurally generated result is rather unreadable:
# !cat -n {testbench.ctx.path_prefix}ones_counter.vhdl
For an 8 bit value, we could also use full adders in the first place and handle the resulting values, likewise:
def bit_count8(v, sum_ones):
s = [ Signal(bool()) for _ in range(8)]
c = [ Signal(bool()) for _ in range(8)]
logic = [
# (0) (1) (2)
# | | |
*full_adder(v[0], v[1], v[2], s[0], c[0]),
*full_adder(v[3], v[4], v[5], s[1], c[1]),
*half_adder(v[6], v[7], s[2], c[2]),
# | |
# (0) (1)
*full_adder(s[0], s[1], s[2], s[3], c[3]), # (0)
# | | |
*full_adder(c[0], c[1], c[2], s[4], c[4]), # (1)
# | | |
*half_adder(c[3], s[4], s[5], c[5]),
# | |
*half_adder(c[4], c[5], s[6], c[6]),
]
# | | | |
bits = [ s[3], s[5], s[6], c[6] ]
logic += [ sum_ones.set(concat(*reversed(bits))) ]
return logic
N = 8
# This will take a long time without acceleration:
# verify(N, bit_count8)