From 3ceacf7889d8f926af3696de3d1bf3c79e66a7bd Mon Sep 17 00:00:00 2001
From: Jacob Lifshay <programmerjake@gmail.com>
Date: Wed, 4 May 2022 23:02:11 -0700
Subject: [PATCH] add cldivrem_shifting as a more efficient algorithm

---
 src/nmigen_gf/hdl/cldivrem.py           | 30 +++++++++++++++++++
 src/nmigen_gf/hdl/test/test_cldivrem.py | 39 ++++++++++++++++++++++++-
 2 files changed, 68 insertions(+), 1 deletion(-)

diff --git a/src/nmigen_gf/hdl/cldivrem.py b/src/nmigen_gf/hdl/cldivrem.py
index bff3676..897ced5 100644
--- a/src/nmigen_gf/hdl/cldivrem.py
+++ b/src/nmigen_gf/hdl/cldivrem.py
@@ -14,6 +14,7 @@ from nmigen.hdl.ir import Elaboratable
 from nmigen.hdl.ast import Signal, Value
 from nmigen.hdl.dsl import Module
 from nmutil.singlepipe import ControlBase
+from nmutil.clz import CLZ, clz
 
 
 def equal_leading_zero_count_reference(a, b, width):
@@ -107,6 +108,35 @@ class EqualLeadingZeroCount(Elaboratable):
         return m
 
 
+def cldivrem_shifting(n, d, width):
+    """ Carry-less Division and Remainder based on shifting at start and end
+        allowing us to get away with checking a single bit each iteration
+        rather than checking for equal degrees every iteration.
+        `n` and `d` are integers, `width` is the number of bits needed to hold
+        each input/output.
+        Returns a tuple `q, r` of the quotient and remainder.
+    """
+    assert isinstance(width, int) and width >= 1
+    assert isinstance(n, int) and 0 <= n < 1 << width
+    assert isinstance(d, int) and 0 <= d < 1 << width
+    assert d != 0, "TODO: decide what happens on division by zero"
+    shift = clz(d, width)
+    d <<= shift
+    n <<= shift
+    r = n
+    q = 0
+    d <<= width
+    for _ in range(width):
+        q <<= 1
+        r <<= 1
+        if r >> (width * 2 - 1) != 0:
+            r ^= d
+            q |= 1
+    r >>= width
+    r >>= shift
+    return q, r
+
+
 @dataclass(frozen=True, unsafe_hash=True)
 class CLDivRemShape:
     width: int
diff --git a/src/nmigen_gf/hdl/test/test_cldivrem.py b/src/nmigen_gf/hdl/test/test_cldivrem.py
index fa93812..de7cf34 100644
--- a/src/nmigen_gf/hdl/test/test_cldivrem.py
+++ b/src/nmigen_gf/hdl/test/test_cldivrem.py
@@ -9,7 +9,8 @@ from nmigen.hdl.ast import AnyConst, Assert, Signal, Const, unsigned
 from nmigen.hdl.dsl import Module
 from nmutil.formaltest import FHDLTestCase
 from nmigen_gf.hdl.cldivrem import (CLDivRemFSMStage, CLDivRemInputData,
-                                    CLDivRemOutputData, CLDivRemShape, CLDivRemState,
+                                    CLDivRemOutputData, CLDivRemShape,
+                                    cldivrem_shifting, CLDivRemState,
                                     equal_leading_zero_count_reference,
                                     EqualLeadingZeroCount)
 from nmigen.sim import Delay, Tick
@@ -104,6 +105,42 @@ class TestEqualLeadingZeroCount(FHDLTestCase):
         self.tst_formal(3)
 
 
+class TestCLDivRemShifting(FHDLTestCase):
+    def tst(self, width, full):
+        def case(n, d):
+            assert isinstance(n, int)
+            assert isinstance(d, int)
+            if d != 0:
+                expected_q, expected_r = cldivrem(n, d, width=width)
+                q, r = cldivrem_shifting(n, d, width=width)
+            else:
+                expected_q = expected_r = 0
+                q = r = 0
+            with self.subTest(n=hex(n), d=hex(d),
+                              expected_q=hex(expected_q),
+                              expected_r=hex(expected_r),
+                              q=hex(q), r=hex(r)):
+                self.assertEqual(expected_q, q)
+                self.assertEqual(expected_r, r)
+        if full:
+            for n in range(1 << width):
+                for d in range(1 << width):
+                    case(n, d)
+        else:
+            for i in range(100):
+                n = hash_256(f"cldivrem comb n {i}")
+                n = Const.normalize(n, unsigned(width))
+                d = hash_256(f"cldivrem comb d {i}")
+                d = Const.normalize(d, unsigned(width))
+                case(n, d)
+
+    def test_6(self):
+        self.tst(6, full=True)
+
+    def test_64(self):
+        self.tst(64, full=False)
+
+
 class TestCLDivRemComb(FHDLTestCase):
     def tst(self, shape, full):
         assert isinstance(shape, CLDivRemShape)
-- 
2.30.2