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         # * if both_ones is set, then both_ones[i] and different[i] are both
  82         #   ones in order to set the carry bit out.
  83         # * if different is set, then both_ones[i] and different[i] are both
  84         #   zeros in order to clear the carry bit out.
  85         # * otherwise exactly one of both_ones[i] and different[i] are set and
  86         #   the other is clear in order to propagate the carry bit from
  87         #   less significant bits.
  88         # * different is zero when both_ones is set, so we don't need to
  89         #   OR-in both_ones
  90
  91         # `both_ones` is set if both have no leading zeros so far
  92         m.d.comb += both_ones.eq(self.a & self.b)
  93         # `different` is set if there are a different number of leading
  94         # zeros so far
  95         m.d.comb += different.eq(~(self.a ^ self.b))
  96
  97         # now [ab]use add: the last bit [carry-out] is the result
  98         csum = Signal(self.width + 1)
  99         carry_in = 1  # both have no leading zeros so far, so set carry
 100         m.d.comb += csum.eq(both_ones + different + carry_in)
 101         m.d.comb += self.out.eq(csum[self.width])  # out is carry-out
 102
 103         return m
 104
 105 # TODO: add CLDivRem