src/nmigen_gf/hdl/cldivrem.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 # Copyright 2022 Jacob Lifshay programmerjake@gmail.com
   3
   4 # Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part
   5 # of Horizon 2020 EU Programme 957073.
   6
   7 """ Carry-less Division and Remainder.
   8
   9 https://bugs.libre-soc.org/show_bug.cgi?id=784
  10 """
  11
  12 from nmigen.hdl.ir import Elaboratable
  13 from nmigen.hdl.ast import Signal
  14 from nmigen.hdl.dsl import Module
  15
  16
  17 def equal_leading_zero_count_reference(a, b, width):
  18     """checks if `clz(a) == clz(b)`.
  19     Reference code for algorithm used in `EqualLeadingZeroCount`.
  20     """
  21     assert isinstance(width, int) and 0 <= width
  22     assert isinstance(a, int) and 0 <= a < (1 << width)
  23     assert isinstance(b, int) and 0 <= b < (1 << width)
  24     eq = True  # both have no leading zeros so far...
  25     for i in range(width):
  26         a_bit = (a >> i) & 1
  27         b_bit = (b >> i) & 1
  28         # `both_ones` is set if both have no leading zeros so far
  29         both_ones = a_bit & b_bit
  30         # `different` is set if there are a different number of leading
  31         # zeros so far
  32         different = a_bit != b_bit
  33         if both_ones:
  34             eq = True
  35         elif different:
  36             eq = False
  37         else:
  38             pass  # propagate from lower bits
  39     return eq
  40
  41
  42 class EqualLeadingZeroCount(Elaboratable):
  43     """checks if `clz(a) == clz(b)`.
  44
  45     Properties:
  46     width: int
  47         the width in bits of `a` and `b`.
  48     a: Signal of width `width`
  49         input
  50     b: Signal of width `width`
  51         input
  52     out: Signal of width `1`
  53         output, set if the number of leading zeros in `a` is the same as in
  54         `b`.
  55     """
  56
  57     def __init__(self, width):
  58         assert isinstance(width, int)
  59         self.width = width
  60         self.a = Signal(width)
  61         self.b = Signal(width)
  62         self.out = Signal()
  63
  64     def elaborate(self, platform):
  65         # the operation is converted into calculation of the carry-out of a
  66         # binary addition, allowing FPGAs to re-use their specialized
  67         # carry-propagation logic. This should be simplified by yosys to
  68         # remove the extraneous xor gates from addition when targeting
  69         # FPGAs/ASICs, so no efficiency is lost.
  70         #
  71         # see `equal_leading_zero_count_reference` for a Python version of
  72         # the algorithm, but without conversion to carry-propagation.
  73         # note that it's possible to do all the bits at once: a for-loop
  74         # (unlike in the reference-code) is not necessary
  75
  76         m = Module()
  77         both_ones = Signal(self.width)
  78         different = Signal(self.width)
  79
  80         # build `both_ones` and `different` such that:
  81         # for every bit index `i`:
  82         # * if `both_ones[i]` is set, then both addends bits at index `i` are
  83         #   set in order to set the carry bit out, since `cin + 1 + 1` always
  84         #   has a carry out.
  85         # * if `different[i]` is set, then both addends bits at index `i` are
  86         #   zeros in order to clear the carry bit out, since `cin + 0 + 0`
  87         #   never has a carry out.
  88         # * otherwise exactly one of the addends bits at index `i` is set and
  89         #   the other is clear in order to propagate the carry bit from
  90         #   less significant bits, since `cin + 1 + 0` has a carry out that is
  91         #   equal to `cin`.
  92
  93         # `both_ones` is set if both have no leading zeros so far
  94         m.d.comb += both_ones.eq(self.a & self.b)
  95         # `different` is set if there are a different number of leading
  96         # zeros so far
  97         m.d.comb += different.eq(self.a ^ self.b)
  98
  99         # now [ab]use add: the last bit [carry-out] is the result
 100         csum = Signal(self.width + 1)
 101         carry_in = 1  # both have no leading zeros so far, so set carry in
 102         m.d.comb += csum.eq(both_ones + (~different) + carry_in)
 103         m.d.comb += self.out.eq(csum[self.width])  # out is carry-out
 104
 105         return m
 106
 107 # TODO: add CLDivRem