add cldivrem_shifting as a more efficient algorithm

[nmigen-gf.git] / src / nmigen_gf / hdl / test / test_cldivrem.py

diff --git a/src/nmigen_gf/hdl/test/test_cldivrem.py b/src/nmigen_gf/hdl/test/test_cldivrem.py
index fa93812df04b301cc21e9d7dd0fdb5e988f41555..de7cf34025e5e7c13e173d3c30a3440abb63c2f1 100644 (file)
--- 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)