From af00fbb15b18fc9b55048922b7cf5d069f8e8f32 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Wed, 4 May 2022 23:23:21 -0700 Subject: [PATCH] shrink signal widths --- src/nmigen_gf/hdl/cldivrem.py | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) diff --git a/src/nmigen_gf/hdl/cldivrem.py b/src/nmigen_gf/hdl/cldivrem.py index 897ced5..02ce034 100644 --- a/src/nmigen_gf/hdl/cldivrem.py +++ b/src/nmigen_gf/hdl/cldivrem.py @@ -120,18 +120,27 @@ def cldivrem_shifting(n, d, width): 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) + + shift_wid = (width - 1).bit_length() + + # `clz(d, width)`, but maxes out at `width - 1` instead of `width` in + # order to both fit in `shift_wid` bits and not shift by more than needed. + shift = clz(d >> 1, width - 1) + assert shift < 1 << shift_wid, f"shift overflows a {shift_wid}-bit signal" d <<= shift + assert d < 1 << width, f"d overflows a {width}-bit signal" n <<= shift + assert n < 1 << (width * 2), f"n overflows a {width * 2}-bit signal" r = n q = 0 - d <<= width for _ in range(width): q <<= 1 r <<= 1 if r >> (width * 2 - 1) != 0: - r ^= d + r ^= d << width q |= 1 + assert q < 1 << width, f"q overflows a {width}-bit signal" + assert r < 1 << (width * 2), f"r overflows a {width * 2}-bit signal" r >>= width r >>= shift return q, r -- 2.30.2