diff options
| -rwxr-xr-x | booth_multiplier.py | 34 |
1 files changed, 18 insertions, 16 deletions
diff --git a/booth_multiplier.py b/booth_multiplier.py index 517c613..58abe8b 100755 --- a/booth_multiplier.py +++ b/booth_multiplier.py @@ -9,15 +9,18 @@ def twos_comp(num, length): return 0 return abs((num ^ ((1 << length) - 1)) + 1) -def logical_shiftr(num, length, times): - #print("SHIFT START___") - #print(bin(num)) +def arithmatic_shiftr(num, length, times): for t in range(times): - num = (num >> 1) | ((1 << length) & num) - #print(bin(num)) - #print("SHIFT END___") + num = (num >> 1) | ((1 << length - 1) & num) return num +def arithmatic_shiftl(num, length): + if num & (1 << length - 1): + return (num << 1) | (1 << length - 1) + else: + return (num << 1) & ~(1 << length - 1) + + def convert_if_twoscomp(num, length): if num & (1 << length - 1): return (-1 * twos_comp(num, length)) @@ -49,29 +52,28 @@ def booth(multiplier, multiplicand, length): if op == 0b10: result += multiplicand_twos_comp << (length + 1) result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows - result = logical_shiftr(result, length * 2, 1) + result = arithmatic_shiftr(result, (length * 2) + 1, 1) result = result >> 1 return result def booth_mod(multiplier, multiplicand, length): - multiplicand_twos_comp = twos_comp(multiplicand, length) + multiplicand |= ((1 << length - 1) & multiplicand) << 1 # extend multiplicand sign to prevent overflow when mult/sub by 2 + multiplicand_twos_comp = twos_comp(multiplicand, length + 1) result = multiplier << 1 # extended bit operations = 0 - for i in range(int(length / 2)): + for i in range(int((length) / 2)): match result & 0b111: case 0b010 | 0b001: # add result += multiplicand << (length + 1) case 0b011: # add * 2 - result += multiplicand << (length + 2) # extra shift is multiplying multiplicand by 2 + result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1) # extra shift is multiplying multiplicand by 2 case 0b100: # sub * 2 - result += multiplicand_twos_comp << (length + 2) + result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1) # extra shift is multiplying multiplicand by 2 case 0b101 | 0b110: # sub result += multiplicand_twos_comp << (length + 1) - if result & (1 << length): - print("{}: overflow".format(bin(multiplicand))) - result &= (1 << ((length * 2) + 1)) - 1 # get rid of any overflows - result = logical_shiftr(result, length * 2, 2) - result = result >> 1 + result &= (1 << ((length * 2) + 2)) - 1 # get rid of any overflows + result = arithmatic_shiftr(result, (length * 2) + 2, 2) + result = ((result | ((1 << ((length * 2) + 2)) >> 1)) & ((1 << ((length * 2) + 1)) - 1)) >> 1 return result |