From 3ceacf7889d8f926af3696de3d1bf3c79e66a7bd Mon Sep 17 00:00:00 2001 From: Jacob Lifshay 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