add cldivrem_shifting as a more efficient algorithm

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

diff --git a/src/nmigen_gf/hdl/cldivrem.py b/src/nmigen_gf/hdl/cldivrem.py
index bff3676a2a069eeb6db3a6d8d6815bb71c659831..897ced521446fbc66ee00cc0c5f7541921e820b2 100644 (file)
--- 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