From a8245c3704bf5d4e53630ca25efd6362de164c08 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Mon, 14 Mar 2022 22:11:13 -0700 Subject: [PATCH] rename bitmanip_inlines -> bitmanip --- cldivrem.py | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 cldivrem.py diff --git a/cldivrem.py b/cldivrem.py new file mode 100644 index 0000000..5bf49b1 --- /dev/null +++ b/cldivrem.py @@ -0,0 +1,34 @@ +def cldivrem(n, d, width): + """ Carry-less Division and Remainder. + `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 d != 0, "TODO: decide what happens on division by zero" + assert 0 <= n < 1 << width, f"bad n (doesn't fit in {width}-bit uint)" + assert 0 <= d < 1 << width, f"bad d (doesn't fit in {width}-bit uint)" + r = n + q = 0 + r_shift = 0 + d_shift = 0 + msb = 1 << (width - 1) + for _ in range(width): + if r & msb: + if d & msb: + r ^= d + q |= 1 + else: + d <<= 1 + d_shift += 1 + else: + if d & msb: + r <<= 1 + q <<= 1 + r_shift += 1 + else: + r <<= 1 + r_shift += 1 + d <<= 1 + d_shift += 1 + r >>= r_shift + return q, r -- 2.30.2