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         m = Module()
  74         addend1 = Signal(self.width)
  75         addend2 = Signal(self.width)
  76         for i in range(self.width):
  77             # `both_ones` is set if both have no leading zeros so far
  78             both_ones = self.a[i] & self.b[i]
  79             # `different` is set if there are a different number of leading
  80             # zeros so far
  81             different = self.a[i] != self.b[i]
  82
  83             # build addend1 and addend2 such that:
  84             # * if both_ones is set, then addend1[i] and addend2[i] are both
  85             #   ones in order to set the carry bit out.
  86             # * if different is set, then addend1[i] and addend2[i] are both
  87             #   zeros in order to clear the carry bit out.
  88             # * otherwise exactly one of addend1[i] and addend2[i] are set and
  89             #   the other is clear in order to propagate the carry bit from
  90             #   less significant bits.
  91             m.d.comb += [
  92                 addend1[i].eq(both_ones),
  93                 # different is zero when both_ones is set, so we don't need to
  94                 # OR-in both_ones
  95                 addend2[i].eq(~different),
  96             ]
  97         sum = Signal(self.width + 1)
  98         carry_in = 1  # both have no leading zeros so far, so set carry
  99         m.d.comb += sum.eq(addend1 + addend2 + carry_in)
 100         m.d.comb += self.out.eq(sum[self.width])  # out is carry-out
 101         return m
 102
 103 # TODO: add CLDivRem