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, Cat
  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         if (a >> i) & 1:
  27             if (b >> i) & 1:
  28                 eq = True  # both have no leading zeros so far...
  29             else:
  30                 eq = False  # different number of leading zeros
  31         else:
  32             if (b >> i) & 1:
  33                 eq = False  # different number of leading zeros
  34             else:
  35                 pass  # propagate results from lower bits
  36     return eq
  37
  38
  39 class EqualLeadingZeroCount(Elaboratable):
  40     """checks if `clz(a) == clz(b)`.
  41
  42     Properties:
  43     width: int
  44         the width in bits of `a` and `b`.
  45     a: Signal of width `width`
  46         input
  47     b: Signal of width `width`
  48         input
  49     out: Signal of width `1`
  50         output, set if the number of leading zeros in `a` is the same as in
  51         `b`.
  52     """
  53
  54     def __init__(self, width):
  55         assert isinstance(width, int)
  56         self.width = width
  57         self.a = Signal(width)
  58         self.b = Signal(width)
  59         self.out = Signal()
  60
  61     def elaborate(self, platform):
  62         # the operation is converted into calculation of the carry-out of a
  63         # binary addition, allowing FPGAs to re-use their specialized
  64         # carry-propagation logic. This should be simplified by yosys to
  65         # remove the extraneous xor gates from addition when targeting
  66         # FPGAs/ASICs, so no efficiency is lost.
  67         #
  68         # see `equal_leading_zero_count_reference` for a Python version of
  69         # the algorithm, but without conversion to carry-propagation.
  70         m = Module()
  71         addend1 = Signal(self.width)
  72         addend2 = Signal(self.width)
  73         for i in range(self.width):
  74             with m.Switch(Cat(self.a[i], self.b[i])):
  75                 with m.Case('11'):
  76                     # both have no leading zeros so far, so set carry
  77                     m.d.comb += [
  78                         addend1[i].eq(1),
  79                         addend2[i].eq(1),
  80                     ]
  81                 with m.Case('01', '10'):
  82                     # different number of leading zeros, so clear carry
  83                     m.d.comb += [
  84                         addend1[i].eq(0),
  85                         addend2[i].eq(0),
  86                     ]
  87                 with m.Case('00'):
  88                     # propagate results from lower bits
  89                     m.d.comb += [
  90                         addend1[i].eq(1),
  91                         addend2[i].eq(0),
  92                     ]
  93         sum = Signal(self.width + 1)
  94         carry_in = 1  # both have no leading zeros so far, so set carry
  95         m.d.comb += sum.eq(addend1 + addend2 + carry_in)
  96         m.d.comb += self.out.eq(sum[self.width])  # out is carry-out
  97         return m
  98
  99 # TODO: add CLDivRem