#!/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 if correct', 'booth mod if correct'] 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]) 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.title("Operations vs Operand Length") 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.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')