additionneur_4_bits.py
Attention ! Cet interpréteur n’est pas totalement compatible avec Python3.
Theme:
"""Algorithms for binary operations.
Running the file with 'python additionneur.py' runs the tests.
There is no way to interact with the program, but the tests print
the gates used in the adders.
"""
def words(n):
"""List of all possible words of n bits.
First bits are the least significant.
"""
assert isinstance(n, int), "words(n) only accepts an integer."
assert n >= 0, "words(n) only accepts non negative numbers."
if n == 0:
return [[]]
else:
ws = words(n - 1)
return [w + [False] for w in ws] + [w + [True] for w in ws]
def decode(bin_type, word):
"""Turn a word into a decimal integer."""
n = len(word)
if bin_type == 'unsigned':
return sum([pow(2,k) for k in range(n) if word[k]])
elif bin_type == 'signed':
sg = word[-1]
val = decode('unsigned', word[:-1])
return sg and -val or val
elif bin_type == 'bias':
return decode('unsigned', word) - pow(2, n-1)
elif bin_type == '2s_cplt':
sg = word[-1]
val = decode('unsigned', word[:-1])
return sg and val - pow(2, n-1) or val
def code(word_length, bin_type, n):
assert isinstance(word_length, int), "code only accepts integer word lengths."
assert word_length >= 0, "code only accepts non negative word lengths."
if bin_type == 'unsigned':
if word_length == 0:
return []
else:
return [n%2 == 1] + code(word_length - 1, bin_type, (n - n%2) / 2)
elif bin_type == 'signed':
if n >= 0:
return code(word_length - 1, 'unsigned', n) + [False]
else:
return code(word_length - 1, 'unsigned', -n) + [True]
elif bin_type == 'bias':
return code(word_length, 'unsigned', n + pow(2, word_length - 1))
elif bin_type == '2s_cplt':
if n >= 0:
return code(word_length - 1, 'unsigned', n) + [False]
else:
wl = word_length
# We don't have a binary adder yet, so we don't use
# (not n) + 1 but we code n + 2^(wl-1) instead.
return code(wl - 1, 'unsigned', n + pow(2, wl - 1)) + [True]
# Tests for decode('unsigned', ...):
for word, n in zip(words(4), range(pow(2,4))):
assert decode('unsigned', word) == n
# Tests for decode('signed', ...):
for word, n in zip(words(4), range(pow(2,3)) + range(0, -pow(2,3), -1)):
assert decode('signed', word) == n
# Tests for decode('bias', ...):
for word, n in zip(words(4), range(-pow(2,3), pow(2,3))):
assert decode('bias', word) == n
# Tests for decode('2s_cplt', ...):
for word, n in zip(words(4), range(pow(2,3)) + range(-pow(2,3), 0)):
assert decode('2s_cplt', word) == n
# Tests for code(4, ..., ...):
for bin_type in ['unsigned', 'signed', 'bias', '2s_cplt']:
for word in words(4):
n = decode(bin_type, word)
b = code(4, bin_type, n)
if bin_type == 'signed' and not any(word[:-1]) and word[-1]:
# [F, F, ... T] is zero too, but is coded [F, F, ... F],
# so we need to skip this pseudo-failure.
continue
assert b == word, "%s failed for %d, gave %s instead of %s." \
% (bin_type, n, b, word)
def gate_factory(gate_type):
"""Core mechanism for GF."""
global gate_count
gate_count[gate_type] += 1
if gate_type == 'NOT':
return lambda x: not x
elif gate_type == 'AND':
return lambda x, y: x and y
elif gate_type == 'OR':
return lambda x, y: x or y
elif gate_type == 'NAND':
return lambda x, y: not (x and y)
elif gate_type == 'NOR':
return lambda x, y: not (x or y)
elif gate_type == 'XOR':
return lambda x, y: (x and not y) or (not x and y)
else:
assert False, "Bad gate type."
class GF(object):
"""Logic Gate Factory, trickery to allow gf.GATE_TYPE."""
def __getattribute__(self, name):
return gate_factory(name)
def gf_reset():
"""Reset counts for the gate factory (OK, this is not classic OOP!)."""
global gate_count
gate_count = dict(empty_count)
empty_count = {'NOT': 0, 'AND': 0, 'OR': 0, 'NAND': 0, 'NOR': 0, 'XOR': 0}
gf = GF()
gf_reset()
# Tests for the gate factory:
assert gf.AND(True, gf.NOT(False)) == True, "Bad gate test."
expected_count_dict = {'NOT': 1, 'AND': 1, 'OR': 0, 'NAND': 0, 'NOR': 0, 'XOR': 0}
for gate_type, count in gate_count.items():
expected_count = expected_count_dict[gate_type]
assert count == expected_count, \
"Bad %s count: %d instead of %d." % (gate_type, count, expected_count)
gf_reset()
def create_add_2x1b():
"""Add two words of one bit, as unsigned numbers."""
x = gf.XOR
a = gf.AND
def f(word):
A, B = word
return [x(A, B), a(A, B)]
return f
# Tests for add_2x1b:
add_2x1b = create_add_2x1b()
assert [add_2x1b(word) for word in words(2)] == [
[False, False],
[True, False],
[True, False],
[False, True]], "Bad result for add_2x1b."
def create_add_3x1b():
"""Add three words of one bit, as unsigned numbers."""
a21_1, a21_2 = create_add_2x1b(), create_add_2x1b()
o = gf.OR
def f(word):
A, B, C = word
r1 = a21_1([A, B])
r2 = a21_2([r1[0], C])
return [r2[0], o(r1[1], r2[1])]
return f
# Tests for add_3x1b:
add_3x1b = create_add_3x1b()
results = [add_3x1b(word) for word in words(3)]
expected_results = [
[False, False],
[True, False],
[True, False],
[False, True],
[True, False],
[False, True],
[False, True],
[True, True],
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for add_3x1b: %s instead of %s." % (result, expected_result)
def create_add_unsigned_2xnb(n):
"""Add two words of several bits, as unsigned numbers."""
assert isinstance(n, int), "create_add_2xnb(n) only accepts an integer."
assert n > 0, "create_add_2xnb(n) only accepts positive numbers."
if n == 1:
return create_add_2x1b()
else:
add_2xn_minus_one_b = create_add_unsigned_2xnb(n - 1)
add_3x1b = create_add_3x1b()
def f(word):
A, B = word[:n], word[n:]
r = add_2xn_minus_one_b(A[:-1] + B[:-1]) # this + is a list concatenation
return r[:n-1] + add_3x1b([r[n-1], A[n-1], B[n-1]])
return f
# Tests for add_2x2b:
add_2x2b = create_add_unsigned_2xnb(2)
results = [add_2x2b(word) for word in words(4)]
expected_results = [
[False, False, False],
[True, False, False],
[False, True, False],
[True, True, False],
[True, False, False],
[False, True, False],
[True, True, False],
[False, False, True],
[False, True, False],
[True, True, False],
[False, False, True],
[True, False, True],
[True, True, False],
[False, False, True],
[True, False, True],
[False, True, True],
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for add_2x2b: %s instead of %s." % (result, expected_result)
# Tests for add_2x1b, add_2x2b, and add_2x3b:
for n in range(1, 4):
maxi = pow(2, n)
ints = range(maxi)
adder = create_add_unsigned_2xnb(n)
for A, B in [(a,b) for a in ints for b in ints]:
assert A + B == decode('unsigned', adder(
code(n, 'unsigned', A) + code(n, 'unsigned', B))), \
"Bad result for add_2x%db." % (n,)
def create_sub_2x1b():
"""Substract two words of one bit, as unsigned numbers."""
x = gf.XOR
n = gf.NOT
a = gf.AND
def f(word):
A, B = word
return [x(A, B), a(n(A), B)]
return f
# Tests for sub_2x1b:
sub_2x1b = create_sub_2x1b()
assert [sub_2x1b(word) for word in words(2)] == [
[False, False],
[True, False],
[True, True],
[False, False]], "Bad result for sub_2x1b."
def create_sub_3x1b():
"""Compute A-B-C with three words of one bit, as unsigned numbers."""
s21_1, s21_2 = create_sub_2x1b(), create_sub_2x1b()
o = gf.OR
def f(word):
A, B, C = word
r1 = s21_1([A, B])
r2 = s21_2([r1[0], C])
return [r2[0], o(r1[1], r2[1])]
return f
# Tests for sub_3x1b:
sub_3x1b = create_sub_3x1b()
results = [sub_3x1b(word) for word in words(3)]
expected_results = [
[False, False],
[True, False],
[True, True],
[False, False],
[True, True],
[False, False],
[False, True],
[True, True],
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for sub_3x1b: %s instead of %s." % (result, expected_result)
def create_sub_2xnb(n):
"""Substract two words of several bits, as unsigned numbers."""
assert isinstance(n, int), "create_sub_2xnb(n) only accepts an integer."
assert n > 0, "create_sub_2xnb(n) only accepts positive numbers."
if n == 1:
return create_sub_2x1b()
else:
sub_2xn_minus_one_b = create_sub_2xnb(n - 1)
sub_3x1b = create_sub_3x1b()
def f(word):
A, B = word[:n], word[n:]
r = sub_2xn_minus_one_b(A[:-1] + B[:-1]) # this + is a list concatenation
return r[:n-1] + sub_3x1b([A[n-1], B[n-1], r[n-1]])
return f
# Tests for sub_2x2b:
sub_2x2b = create_sub_2xnb(2)
results = [sub_2x2b(word) for word in words(4)]
expected_results = [
[False, False, False],
[True, False, False],
[False, True, False],
[True, True, False],
[True, True, True],
[False, False, False],
[True, False, False],
[False, True, False],
[False, True, True],
[True, True, True],
[False, False, False],
[True, False, False],
[True, False, True],
[False, True, True],
[True, True, True],
[False, False, False],
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for sub_2x2b: %s instead of %s." % (result, expected_result)
# Tests for sub_2x1b, sub_2x2b, and sub_2x3b:
for n in range(1, 4):
maxi = pow(2, n)
ints = range(maxi)
substractor = create_sub_2xnb(n)
for A, B in [(a,b) for a in ints for b in ints]:
if A < B:
continue
assert A - B == decode('unsigned', substractor(
code(n, 'unsigned', A) + code(n, 'unsigned', B))), \
"Bad result for sub_2x%db." % (n,)
def create_xormux_1b():
"""Direct information of the least sig. bit according to the two msb."""
a1, a2, x1, x2, n1 = gf.AND, gf.AND, gf.XOR, gf.XOR, gf.NOT
def f(word):
I, A, B = word
out1 = a1(I, n1(x1(A, B)))
out2 = a2(I, x2(A, B))
return [out1, out2]
return f
# Tests for xormux_1b:
mux = create_xormux_1b()
results = [mux(word) for word in words(3)]
expected_results = [
[False, False], # F FF
[True, False], # T FF
[False, False], # F TF
[False, True], # T TF
[False, False], # F FT
[False, True], # T FT
[False, False], # F TT
[True, False], # T TT
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for xormux_1b: %s instead of %s." % (result, expected_result)
def create_xormux_nb(n):
"""Direct a word of n bits (least sig. ones) according to the two msb."""
assert isinstance(n, int), "create_xormux_nb(n) only accepts an integer."
assert n > 0, "create_xormux_nb(n) only accepts positive numbers."
if n == 1:
return create_xormux_1b()
else:
# We know how to xormux words of n-1 bits or words of 1 bit:
mux_n_minus_one = create_xormux_nb(n - 1)
mux_1b = create_xormux_1b()
def f(word):
I, i, A, B = word[:n-1], word[n-1], word[-2], word[-1]
I_muxed = mux_n_minus_one(I + [A, B])
i_muxed = mux_1b([i, A, B])
return I_muxed[:n-1] + i_muxed[:1] + I_muxed[n-1:] + i_muxed[1:]
return f
# Tests for xormux_1b, xormux_2b, and xormux_3b:
for n in range(1, 4):
mux = create_xormux_nb(n)
for I, A, B in [(i, a, b) \
for i in words(n) \
for a in [False, True] \
for b in [False, True]]:
result = mux(I + [A, B]) # this + is a list concatenation
r1 = result[0:n]
r2 = result[n:2*n]
# Some results we expect to have:
bigfalse = [False] * n
# Now the tests:
if A == B:
assert r1 == I
assert r2 == bigfalse
else:
assert r1 == bigfalse
assert r2 == I
def create_strict_comp_1b():
"""Tell if two bits are equal on lsb, and if not if lsb > msb on msb."""
x, n, a = gf.XOR, gf.NOT, gf.AND
def f(word):
A, B = word
result_x = x(A, B)
return [n(result_x), a(result_x, A)]
return f
# Tests for strict_comp_1b:
comp = create_strict_comp_1b()
results = [comp(word) for word in words(2)]
expected_results = [
[True, False],
[False, True],
[False, False],
[True, False],
]
for result, expected_result in zip(results, expected_results):
assert result == expected_result, \
"Bad result for strict_comp_1b: %s instead of %s." % \
(result, expected_result)
def create_comp_nb(n):
"""Tell if the first word (lsw) of n bits is greater than the second."""
assert isinstance(n, int), "create_comp_nb(n) only accepts an integer."
assert n > 0, "create_comp_nb(n) only accepts positive numbers."
if n == 1:
n, o = gf.NOT, gf.OR
def f(word):
A, B = word
return [o(A, n(B))]
return f
else:
comp_n_minus_one_b = create_comp_nb(n - 1)
str_comp, a, o = create_strict_comp_1b(), gf.AND, gf.OR
def f(word):
msbA, msbB = word[n - 1], word[2*n - 1]
lsbsA, lsbsB = word[0:n - 1], word[n:2*n - 1]
result_c = str_comp([msbA, msbB])
return [o(a(comp_n_minus_one_b(lsbsA + lsbsB)[0], result_c[0]),
result_c[1])]
return f
# Tests for comp_1b, comp_2b, and comp_3b:
for n in range(1, 4):
maxi = pow(2, n)
ints = range(maxi)
comp = create_comp_nb(n)
for A, B in [(a,b) for a in ints for b in ints]:
result = comp(code(n, 'unsigned', A) + code(n, 'unsigned', B))
expected_result = A >= B
assert expected_result == result[0], "Bad result for comp_%db: %d >= %d is said %s." % \
(n, A, B, result[0])
def create_merge_mxnb(m, n):
"""Merge m words of n bits in one word of n bits with or gates.
Not optimized to have O(log(m)) gates.
"""
assert isinstance(m, int) and isinstance(n, int), \
"create_merge_mxnb(m, n) only accepts integers."
assert m > 0, \
"create_merge_mxnb(m, n) only creates mergers for at least one word."
assert n > 0, \
"create_merge_mxnb(m, n) only accepts positive number of bits."
if n == 1:
# This is basically a big OR gate with m input bits and one output.
if m == 1:
# One bit on input, one bit on output.
return lambda x: x
else:
merge_m_minus_one_x1b = create_merge_mxnb(m - 1, 1)
o = gf.OR
def f(word):
return [o(merge_m_minus_one_x1b(word[:-1])[0], word[-1])]
return f
else:
# We know how to merge m words of n-1 bits or m words of 1 bit:
merger_n_minus_one = create_merge_mxnb(m, n - 1)
merger_m_minus_one = create_merge_mxnb(m, 1)
def f(word):
# Our m words of n-1 bits (flattened with sum):
lsbs = sum([word[i*n : i*n + n-1] for i in range(m)], [])
# Our m words of 1 bit:
msbs = [word[i*n + n-1] for i in range(m)]
return merger_n_minus_one(lsbs) + merger_m_minus_one(msbs)
return f
# Tests for merge_mxnb, where m <- [1;4] and n <- [1;8]
# Please note that we only test the output of muxers.
for m in range(1, 5):
for n in range(1, 9):
merger = create_merge_mxnb(m, n)
# Build all possible output of muxers for test input:
for word in words(n):
for i in range(m):
I = [False] * m * n
for j in range(n):
I[i*n + j] = word[j]
merged = merger(I)
assert merged == word, \
"Bad merge for %s, %s instead of %s (m=%d, n=%d)." % \
(I, merged, word, m, n)
def create_switch_nb(n):
"""If msb is True, switch two words of n bits (2*n lsb)."""
assert isinstance(n, int), "create_switch_nb(n) only accepts an integer."
assert n > 0, "create_switch_nb(n) only accepts positive numbers."
if n == 1:
a1, a2, a3, a4 = gf.AND, gf.AND, gf.AND, gf.AND
o1, o2, n1, n2 = gf.OR, gf.OR, gf.NOT, gf.NOT
def f(word):
A, B, SW = word
return [o1(a1(A, n1(SW)), a2(B, SW)), o2(a3(A, SW), a4(B, n2(SW)))]
return f
else:
# We know how to switch words of n-1 bits:
switcher_n_minus_one = create_switch_nb(n - 1)
# We know how to switch words of 1 bit:
switcher_1b = create_switch_nb(1)
def f(word):
# Our 2 words of n-1 bits (flattened with sum):
lsbs = sum([word[i*n : i*n + n-1] for i in range(2)], [])
# Our 2 words of 1 bit:
msbs = [word[i*n + n-1] for i in range(2)]
SW = word[-1]
lsbs_to_return = switcher_n_minus_one(lsbs + [SW])
msbs_to_return = switcher_1b(msbs + [SW])
return lsbs_to_return[:n-1] + [msbs_to_return[0]] + \
lsbs_to_return[n-1:] + [msbs_to_return[1]]
return f
# Tests for switch_nb for n <- [1;3]:
for n in range(1, 4):
switcher = create_switch_nb(n)
for A, B in [(a,b) for a in words(n) for b in words(n)]:
AB, BA = A + B, B + A
for SW in [False, True]:
switched = switcher(AB + [SW])
expected = SW and BA or AB
assert switched == expected, \
"Bad switch for %s, %s: %s instead of %s." % \
(AB, SW, switched, expected)
def create_sign_handler_for_addition():
"""Given the sign of A and B, and |A| >= |B|, return the sign of A+B.
Remember True means negative.
"""
a1, a2, a3, a4, a5 = gf.AND, gf.AND, gf.AND, gf.AND, gf.AND
n1, n2, n3, m = gf.NOT, gf.NOT, gf.NOT, create_merge_mxnb(3, 1)
def f(word):
sgA, sgB, AgtB = word
return m([
a1(sgA, sgB),
a2(a4(sgA, n1(sgB)), AgtB),
a3(a5(n2(sgA), sgB), n3(AgtB))
])
return f
# Tests for sign_handler_for_addition.
values = range(-2, 3)
sign_add = create_sign_handler_for_addition()
for A, B in [(a,b) for a in values for b in values]:
if A + B == 0:
# Skip this case because 1) tricky,
# 2) in 'signed' coding, 0 has two forms.
continue
result = sign_add([A<0, B<0, abs(A) >= abs(B)])[0]
expected = A+B < 0
assert result == expected, \
"Bas sign_handler_for_add: %s instead of %s (A=%d, B=%d)." % \
(result, expected, A, B)
def create_add_relatives_2xnb(bin_type, n):
"""Add two signed (according to 'bin_type') words."""
if bin_type == 'signed':
mux = create_xormux_nb(2 * (n - 1)) # We mux two absolute values.
merge = create_merge_mxnb(2, n - 1)
add, sub = create_add_unsigned_2xnb(n - 1), create_sub_2xnb(n - 1)
comp, n1, sw = create_comp_nb(n - 1), gf.NOT, create_switch_nb(n - 1)
sign_handler = create_sign_handler_for_addition()
def f(word):
absA, sgA, absB, sgB = word[:n-1], word[n-1], word[n:-1], word[-1]
# A bit of plumbing...
muxed = mux(absA + absB + [sgA] + [sgB])
block = 2*(n - 1)
merged_to_add = muxed[:block]
absA_gte_absB = comp(absA + absB)[0]
absB_gt_absA = n1(absA_gte_absB)
to_switch = muxed[block:]
switched = sw(to_switch + [absB_gt_absA])
merged_to_substract = switched
raw_added, raw_subbed = add(merged_to_add), sub(merged_to_substract)
abs_added, Cout_added = raw_added[:n-1], [raw_added[n-1]]
abs_subbed = raw_subbed[:n-1]
abs_R = merge(abs_added + abs_subbed)
sg_R = sign_handler([sgA, sgB, absA_gte_absB])
return abs_R + sg_R + Cout_added
return f
elif bin_type == 'bias':
add = create_add_unsigned_2xnb(n)
sub = create_sub_2xnb(n + 1) # +1 to work with the deduct of the adder
comp1 = create_comp_nb(n + 1) # (same size again)
comp2 = create_comp_nb(n + 1) # (same size again)
o1, n1 = gf.OR, gf.NOT
two_power_n_on_n_plus_one_bits = [False] * n + [True]
two_power_n_minus_one_on_n_plus_one_bits = [False] * (n - 1) + [True] + [False]
def f(word):
added = add(word)
subbed = sub(added + two_power_n_minus_one_on_n_plus_one_bits)
# Two ways to overflow:
# 1) result not big enough: raw result < 2^(n-1)
# 2) result is too big: raw result >= 2^(n-1)
big_enough = comp1(added + two_power_n_minus_one_on_n_plus_one_bits)[0]
too_big = comp2(subbed[:-1] + two_power_n_on_n_plus_one_bits)[0]
Cout = o1(n1(big_enough), too_big)
return subbed[:-2] + [Cout]
return f
elif bin_type == '2s_cplt':
add = create_add_unsigned_2xnb(n)
a1, a2, a3 = gf.AND, gf.AND, gf.AND
o1, n1, nor1 = gf.OR, gf.NOT, gf.NOR
def f(word):
absA, sgA, absB, sgB = word[:n-1], word[n-1], word[n:-1], word[-1]
raw_added = add(word)
added, sg_added = raw_added[:-1], raw_added[-2]
# Overflow iff A>=0 and B>=0 but R<0, or A<0 and B<0 but R>=0.
Cout = o1(a3(a1(sgA, sgB), n1(sg_added)), a2(nor1(sgA, sgB), sg_added))
Cout = (sgA and sgB and not added[-1]) or (not sgA and not sgB and added[-1])
return added + [Cout]
return f
# Tests for add_relatives_2xnb for n <- [2;4]:
# (We start at 2 since relative numbers need at least 2 bits.)
for n in range(2, 5):
SHOW_TESTS = False
maxi = pow(2, n)
ints = range(-maxi/2, maxi/2)
print
print "Testing the adder for values in %s." % ints
for bin_type in [
'signed',
'bias',
'2s_cplt'
]:
print
print "Binary type: %s." % bin_type
gf_reset()
adder = create_add_relatives_2xnb(bin_type, n)
print "Our adder is built with these gates:"
print gate_count
for A, B in [(a,b) for a in ints for b in ints]:
# signed bin_type doesn't handle the lowest number -2^(n-1).
if bin_type == 'signed' and (-maxi/2 in [A, B]):
continue
binA, binB = code(n, bin_type, A), code(n, bin_type, B)
binary_result = adder(binA + binB)
result = decode(bin_type, binary_result[:-1])
expected = A + B
binary_expected = code(n, bin_type, expected)
# Check Cout and skip accordingly.
if binary_result[-1]:
if SHOW_TESTS: print "Skipped %d + %d = %d instead of %d." % \
(A, B, result, expected)
if expected in ints:
# signed bin_type should be the only one to not handle -2^(n-1).
assert bin_type == 'signed' and expected == -maxi/2, \
("Skipped %d + %d = %d instead of %d, but " + \
"result was codable (A was %s, B was %s).") % \
(A, B, result, expected, binA, binB)
continue
else:
if SHOW_TESTS: print "%d + %d = %d" % (A, B, result)
assert result == expected, \
("Bad result for add_relatives_2x%db (bin_type=%s): \n" + \
"A=%d (%s), B=%d (%s), \n" + \
"%d (%s) instead of %s (%s).") % \
(n, bin_type, A, binA, B, binB, result, binary_result[:-1], expected, binary_expected)