190 lines
7.3 KiB
Python
Executable File
190 lines
7.3 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
from tabulate import tabulate
|
|
import matplotlib
|
|
import matplotlib.pyplot as plt
|
|
|
|
# finds the two's compliment of a given number
|
|
def twos_comp(num, length):
|
|
if num == 0:
|
|
return 0
|
|
return abs((num ^ ((1 << length) - 1)) + 1)
|
|
|
|
# arithmaticlly shifts right; divides by 2
|
|
def arithmatic_shiftr(num, length, times):
|
|
for t in range(times):
|
|
num = (num >> 1) | ((1 << length - 1) & num)
|
|
return num
|
|
|
|
# arithmaticlly shifts left; multiplies by 2
|
|
def arithmatic_shiftl(num, length):
|
|
if num & (1 << length - 1):
|
|
return (num << 1) | (1 << length - 1)
|
|
else:
|
|
return (num << 1) & ~(1 << length - 1)
|
|
|
|
# only used for debugging function to allow python to natively use two's compliment numbers
|
|
def twoscomp_to_int(num, length):
|
|
if num & (1 << length - 1):
|
|
return (-1 * twos_comp(num, length))
|
|
return num & (1 << length) - 1
|
|
|
|
def debug(results):
|
|
headers = ['multiplicand bin', 'multiplier bin', 'multiplicand dec', 'multiplier dec', 'expected bin', 'expected dec', 'booth', 'mod booth']
|
|
table = []
|
|
for [multiplicand_bin, multiplier_bin, result_booth, result_booth_mod, length] in results:
|
|
multiplicand = twoscomp_to_int(multiplicand_bin, length)
|
|
multiplier = twoscomp_to_int(multiplier_bin, length)
|
|
expected = multiplicand * multiplier
|
|
expected_bin = (twos_comp(expected, length * 2), expected) [expected > 0]
|
|
success_b = [bin(result_booth), "PASS"] [result_booth == expected_bin]
|
|
success_bm = [bin(result_booth_mod), "PASS"] [result_booth_mod == expected_bin]
|
|
|
|
table.append([bin(multiplicand_bin), bin(multiplier_bin), multiplicand, multiplier, bin(expected_bin), expected, success_b, success_bm])
|
|
with open("report/debug_table.tex", "w") as f:
|
|
f.write(tabulate(table, headers, tablefmt="latex_longtable"))
|
|
print("\nCHECKS: \n", tabulate(table, headers), "\n")
|
|
|
|
|
|
|
|
def booth(multiplier, multiplicand, length):
|
|
operations = 0
|
|
multiplicand_twos_comp = twos_comp(multiplicand, length)
|
|
result = multiplier << 1 # extended bit
|
|
for i in range(length): # iteration count is size of one operand
|
|
op = result & 0b11
|
|
if op == 0b01:
|
|
operations += 1 # add upper half by multiplicand
|
|
result += multiplicand << (length + 1)
|
|
if op == 0b10:
|
|
operations += 1 # subtract upper half by multiplicand
|
|
result += multiplicand_twos_comp << (length + 1)
|
|
result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows
|
|
result = arithmatic_shiftr(result, (length * 2) + 1, 1)
|
|
result = result >> 1
|
|
return (result, operations)
|
|
|
|
def booth_mod(multiplier, multiplicand, length):
|
|
operations = 0
|
|
# extend workspace by *two* bits, MSB to prevent overflow when mult/sub by 2
|
|
multiplicand |= ((1 << length - 1) & multiplicand) << 1
|
|
multiplicand_twos_comp = twos_comp(multiplicand, length + 1)
|
|
result = multiplier << 1
|
|
for i in range(int((length) / 2)): # number of iterations is half the
|
|
op = result & 0b111
|
|
match op: # take action dependent on last two bits
|
|
case 0b010 | 0b001: # add upper half by multiplicand
|
|
print("add")
|
|
result += multiplicand << (length + 1)
|
|
case 0b011: # add upper half by 2x multiplicand
|
|
print("add * 2")
|
|
result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1)
|
|
case 0b100: # subtract upper half by 2x multiplicand
|
|
print("sub * 2")
|
|
result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1)
|
|
case 0b101 | 0b110: # subtract upper half my multiplicand
|
|
print("sub ")
|
|
result += multiplicand_twos_comp << (length + 1)
|
|
if op != 0b111 and op != 0:
|
|
operations += 1
|
|
result &= (1 << ((length * 2) + 2)) - 1 # get rid of any overflows
|
|
result = arithmatic_shiftr(result, (length * 2) + 2, 2)
|
|
# shifts the workspace right by one, while duplicating extra sign bit to second MSB, and clearing the MSB.
|
|
# this ensures the result length is 2x the operands.
|
|
result = ((result | ((1 << ((length * 2) + 2)) >> 1)) & ((1 << ((length * 2) + 1)) - 1)) >> 1
|
|
return (result, operations)
|
|
|
|
if __name__ == "__main__":
|
|
# set up headers for tables
|
|
result_headers = ['multiplicand', 'multiplier', 'result (bin)', 'result (hex)']
|
|
result_table = []
|
|
|
|
opcount_headers = ['multiplicand', 'multiplier', 'length', 'booth', 'modified booth']
|
|
opcount_table = []
|
|
|
|
lengths = []
|
|
ops_booth = []
|
|
ops_mod_booth = []
|
|
|
|
debug_results = []
|
|
|
|
# Reads operands from file.
|
|
# Each line needs to contain two operands in binary two's compliment form seperated by a space.
|
|
# Leading zeros should be appended to convey the length of operands.
|
|
# Operands must have the same size.
|
|
with open('input.txt') as f:
|
|
input_string = f.read().split('\n')
|
|
|
|
for operation in input_string:
|
|
if operation == '' or operation[0] == '#':
|
|
continue
|
|
length = len(operation.split(" ")[0])
|
|
multiplicand = int(operation.split(" ")[0], 2)
|
|
multiplier = int(operation.split(" ")[1], 2)
|
|
|
|
# get result and operation count of both algorithims
|
|
result_booth = booth(multiplier, multiplicand, length)
|
|
result_mod_booth = booth_mod(multiplier, multiplicand, length)
|
|
|
|
# gather data for matplotlib
|
|
ops_booth.append(result_booth[1])
|
|
ops_mod_booth.append(result_mod_booth[1])
|
|
lengths.append(length)
|
|
|
|
# gather data for report results table
|
|
result_table.append([bin(multiplicand), bin(multiplier), bin(result_booth[0]), hex(result_booth[0])])
|
|
|
|
# gather data for test function to check if simulator is working
|
|
debug_results.append([multiplicand, multiplier, result_booth[0], result_mod_booth[0], length])
|
|
|
|
# gather data for operation count table
|
|
opcount_table.append([bin(multiplicand), bin(multiplier), length, result_booth[1], result_mod_booth[1]])
|
|
|
|
# tests validity of results
|
|
debug(debug_results)
|
|
|
|
# generate tables for report
|
|
print(tabulate(result_table, result_headers, tablefmt="latex"))
|
|
print(tabulate(opcount_table, opcount_headers))
|
|
|
|
# output
|
|
with open("report/result_table.tex", 'w') as f:
|
|
f.write(tabulate(result_table, result_headers, tablefmt="latex_booktabs"))
|
|
|
|
with open("report/speed_table.tex", "w") as f:
|
|
f.write(tabulate(opcount_table, opcount_headers, tablefmt="latex_booktabs"))
|
|
|
|
# set up plotting
|
|
matplotlib.use("pgf")
|
|
matplotlib.rcParams.update({
|
|
"pgf.texsystem": "pdflatex",
|
|
'font.family': 'serif',
|
|
'text.usetex': True,
|
|
'pgf.rcfonts': False,
|
|
})
|
|
|
|
# generate table for operations vs operand length
|
|
plt.gcf().set_size_inches(w=4.5, h=3.5)
|
|
plt.plot(lengths, ops_booth, '^--m', label='booths algorithim')
|
|
plt.plot(lengths, ops_mod_booth, 'v--c', label='modified booths algorithim')
|
|
plt.gca().set_xlabel("Length of Operands")
|
|
plt.gca().set_ylabel("Number of Additions and Subtractions")
|
|
plt.legend(loc='upper left')
|
|
plt.savefig('report/performance.pgf')
|
|
|
|
|
|
# generate table of iterations vs operand length
|
|
iters_booth = []
|
|
iters_mod_booth = []
|
|
for length in lengths:
|
|
iters_booth.append(length)
|
|
iters_mod_booth.append(int(length / 2))
|
|
|
|
plt.figure()
|
|
plt.gcf().set_size_inches(w=4.5, h=3.5)
|
|
plt.plot(lengths, lengths, '^--m', label='booths algorithim')
|
|
plt.plot(lengths, [int(l/2) for l in lengths], 'v--c', label='modified booths algorithim')
|
|
plt.gca().set_xlabel("Operand Length")
|
|
plt.gca().set_ylabel("Number of iterations")
|
|
plt.legend(loc='upper left')
|
|
plt.savefig('report/iterations.pgf')
|