1 # SPDX-License-Identifier: LGPL-2.1-or-later
2 # See Notices.txt for copyright information
3 """Integer Multiplication."""
5 from nmigen
import Signal
, Module
, Value
, Elaboratable
, Cat
, C
, Mux
, Repl
6 from nmigen
.hdl
.ast
import Assign
7 from abc
import ABCMeta
, abstractmethod
8 from nmigen
.cli
import main
9 from functools
import reduce
10 from operator
import or_
11 from ieee754
.pipeline
import PipelineSpec
12 from nmutil
.pipemodbase
import PipeModBase
14 from ieee754
.part_mul_add
.partpoints
import PartitionPoints
17 class FullAdder(Elaboratable
):
20 :attribute in0: the first input
21 :attribute in1: the second input
22 :attribute in2: the third input
23 :attribute sum: the sum output
24 :attribute carry: the carry output
26 Rather than do individual full adders (and have an array of them,
27 which would be very slow to simulate), this module can specify the
28 bit width of the inputs and outputs: in effect it performs multiple
29 Full 3-2 Add operations "in parallel".
32 def __init__(self
, width
):
33 """Create a ``FullAdder``.
35 :param width: the bit width of the input and output
37 self
.in0
= Signal(width
, reset_less
=True)
38 self
.in1
= Signal(width
, reset_less
=True)
39 self
.in2
= Signal(width
, reset_less
=True)
40 self
.sum = Signal(width
, reset_less
=True)
41 self
.carry
= Signal(width
, reset_less
=True)
43 def elaborate(self
, platform
):
44 """Elaborate this module."""
46 m
.d
.comb
+= self
.sum.eq(self
.in0 ^ self
.in1 ^ self
.in2
)
47 m
.d
.comb
+= self
.carry
.eq((self
.in0
& self
.in1
)
48 |
(self
.in1
& self
.in2
)
49 |
(self
.in2
& self
.in0
))
53 class MaskedFullAdder(Elaboratable
):
56 :attribute mask: the carry partition mask
57 :attribute in0: the first input
58 :attribute in1: the second input
59 :attribute in2: the third input
60 :attribute sum: the sum output
61 :attribute mcarry: the masked carry output
63 FullAdders are always used with a "mask" on the output. To keep
64 the graphviz "clean", this class performs the masking here rather
65 than inside a large for-loop.
67 See the following discussion as to why this is no longer derived
68 from FullAdder. Each carry is shifted here *before* being ANDed
69 with the mask, so that an AOI cell may be used (which is more
71 https://en.wikipedia.org/wiki/AND-OR-Invert
72 https://groups.google.com/d/msg/comp.arch/fcq-GLQqvas/vTxmcA0QAgAJ
75 def __init__(self
, width
):
76 """Create a ``MaskedFullAdder``.
78 :param width: the bit width of the input and output
81 self
.mask
= Signal(width
, reset_less
=True)
82 self
.mcarry
= Signal(width
, reset_less
=True)
83 self
.in0
= Signal(width
, reset_less
=True)
84 self
.in1
= Signal(width
, reset_less
=True)
85 self
.in2
= Signal(width
, reset_less
=True)
86 self
.sum = Signal(width
, reset_less
=True)
88 def elaborate(self
, platform
):
89 """Elaborate this module."""
91 s1
= Signal(self
.width
, reset_less
=True)
92 s2
= Signal(self
.width
, reset_less
=True)
93 s3
= Signal(self
.width
, reset_less
=True)
94 c1
= Signal(self
.width
, reset_less
=True)
95 c2
= Signal(self
.width
, reset_less
=True)
96 c3
= Signal(self
.width
, reset_less
=True)
97 m
.d
.comb
+= self
.sum.eq(self
.in0 ^ self
.in1 ^ self
.in2
)
98 m
.d
.comb
+= s1
.eq(Cat(0, self
.in0
))
99 m
.d
.comb
+= s2
.eq(Cat(0, self
.in1
))
100 m
.d
.comb
+= s3
.eq(Cat(0, self
.in2
))
101 m
.d
.comb
+= c1
.eq(s1
& s2
& self
.mask
)
102 m
.d
.comb
+= c2
.eq(s2
& s3
& self
.mask
)
103 m
.d
.comb
+= c3
.eq(s3
& s1
& self
.mask
)
104 m
.d
.comb
+= self
.mcarry
.eq(c1 | c2 | c3
)
108 class PartitionedAdder(Elaboratable
):
109 """Partitioned Adder.
111 Performs the final add. The partition points are included in the
112 actual add (in one of the operands only), which causes a carry over
113 to the next bit. Then the final output *removes* the extra bits from
116 partition: .... P... P... P... P... (32 bits)
117 a : .... .... .... .... .... (32 bits)
118 b : .... .... .... .... .... (32 bits)
119 exp-a : ....P....P....P....P.... (32+4 bits, P=1 if no partition)
120 exp-b : ....0....0....0....0.... (32 bits plus 4 zeros)
121 exp-o : ....xN...xN...xN...xN... (32+4 bits - x to be discarded)
122 o : .... N... N... N... N... (32 bits - x ignored, N is carry-over)
124 :attribute width: the bit width of the input and output. Read-only.
125 :attribute a: the first input to the adder
126 :attribute b: the second input to the adder
127 :attribute output: the sum output
128 :attribute partition_points: the input partition points. Modification not
129 supported, except for by ``Signal.eq``.
132 def __init__(self
, width
, partition_points
, partition_step
=1):
133 """Create a ``PartitionedAdder``.
135 :param width: the bit width of the input and output
136 :param partition_points: the input partition points
137 :param partition_step: a multiplier (typically double) step
138 which in-place "expands" the partition points
141 self
.pmul
= partition_step
142 self
.a
= Signal(width
, reset_less
=True)
143 self
.b
= Signal(width
, reset_less
=True)
144 self
.output
= Signal(width
, reset_less
=True)
145 self
.partition_points
= PartitionPoints(partition_points
)
146 if not self
.partition_points
.fits_in_width(width
):
147 raise ValueError("partition_points doesn't fit in width")
149 for i
in range(self
.width
):
150 if i
in self
.partition_points
:
153 self
._expanded
_width
= expanded_width
155 def elaborate(self
, platform
):
156 """Elaborate this module."""
158 expanded_a
= Signal(self
._expanded
_width
, reset_less
=True)
159 expanded_b
= Signal(self
._expanded
_width
, reset_less
=True)
160 expanded_o
= Signal(self
._expanded
_width
, reset_less
=True)
163 # store bits in a list, use Cat later. graphviz is much cleaner
164 al
, bl
, ol
, ea
, eb
, eo
= [],[],[],[],[],[]
166 # partition points are "breaks" (extra zeros or 1s) in what would
167 # otherwise be a massive long add. when the "break" points are 0,
168 # whatever is in it (in the output) is discarded. however when
169 # there is a "1", it causes a roll-over carry to the *next* bit.
170 # we still ignore the "break" bit in the [intermediate] output,
171 # however by that time we've got the effect that we wanted: the
172 # carry has been carried *over* the break point.
174 for i
in range(self
.width
):
175 pi
= i
/self
.pmul
# double the range of the partition point test
176 if pi
.is_integer() and pi
in self
.partition_points
:
177 # add extra bit set to 0 + 0 for enabled partition points
178 # and 1 + 0 for disabled partition points
179 ea
.append(expanded_a
[expanded_index
])
180 al
.append(~self
.partition_points
[pi
]) # add extra bit in a
181 eb
.append(expanded_b
[expanded_index
])
182 bl
.append(C(0)) # yes, add a zero
183 expanded_index
+= 1 # skip the extra point. NOT in the output
184 ea
.append(expanded_a
[expanded_index
])
185 eb
.append(expanded_b
[expanded_index
])
186 eo
.append(expanded_o
[expanded_index
])
189 ol
.append(self
.output
[i
])
192 # combine above using Cat
193 m
.d
.comb
+= Cat(*ea
).eq(Cat(*al
))
194 m
.d
.comb
+= Cat(*eb
).eq(Cat(*bl
))
195 m
.d
.comb
+= Cat(*ol
).eq(Cat(*eo
))
197 # use only one addition to take advantage of look-ahead carry and
198 # special hardware on FPGAs
199 m
.d
.comb
+= expanded_o
.eq(expanded_a
+ expanded_b
)