remove unused imports
[nmigen-gf.git] / 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