From 3d66690b7029037d91fcc524c51d77f68c7fa57e Mon Sep 17 00:00:00 2001
From: Brett Weiland <brett_weiland@gmail.com>
Date: Wed, 10 Apr 2024 22:20:55 -0500
Subject: fixed the stupid thing

---
 booth_multiplier.py | 34 ++++++++++++++++++----------------
 1 file 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
 
 
-- 
cgit v1.2.3