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_
12 class PartitionPoints(dict):
13 """Partition points and corresponding ``Value``s.
15 The points at where an ALU is partitioned along with ``Value``s that
16 specify if the corresponding partition points are enabled.
18 For example: ``{1: True, 5: True, 10: True}`` with
19 ``width == 16`` specifies that the ALU is split into 4 sections:
22 * bits 5 <= ``i`` < 10
23 * bits 10 <= ``i`` < 16
25 If the partition_points were instead ``{1: True, 5: a, 10: True}``
26 where ``a`` is a 1-bit ``Signal``:
27 * If ``a`` is asserted:
30 * bits 5 <= ``i`` < 10
31 * bits 10 <= ``i`` < 16
34 * bits 1 <= ``i`` < 10
35 * bits 10 <= ``i`` < 16
38 def __init__(self
, partition_points
=None):
39 """Create a new ``PartitionPoints``.
41 :param partition_points: the input partition points to values mapping.
44 if partition_points
is not None:
45 for point
, enabled
in partition_points
.items():
46 if not isinstance(point
, int):
47 raise TypeError("point must be a non-negative integer")
49 raise ValueError("point must be a non-negative integer")
50 self
[point
] = Value
.wrap(enabled
)
52 def like(self
, name
=None, src_loc_at
=0):
53 """Create a new ``PartitionPoints`` with ``Signal``s for all values.
55 :param name: the base name for the new ``Signal``s.
58 name
= Signal(src_loc_at
=1+src_loc_at
).name
# get variable name
59 retval
= PartitionPoints()
60 for point
, enabled
in self
.items():
61 retval
[point
] = Signal(enabled
.shape(), name
=f
"{name}_{point}")
65 """Assign ``PartitionPoints`` using ``Signal.eq``."""
66 if set(self
.keys()) != set(rhs
.keys()):
67 raise ValueError("incompatible point set")
68 for point
, enabled
in self
.items():
69 yield enabled
.eq(rhs
[point
])
71 def as_mask(self
, width
):
72 """Create a bit-mask from `self`.
74 Each bit in the returned mask is clear only if the partition point at
75 the same bit-index is enabled.
77 :param width: the bit width of the resulting mask
80 for i
in range(width
):
87 def get_max_partition_count(self
, width
):
88 """Get the maximum number of partitions.
90 Gets the number of partitions when all partition points are enabled.
93 for point
in self
.keys():
98 def fits_in_width(self
, width
):
99 """Check if all partition points are smaller than `width`."""
100 for point
in self
.keys():
106 class FullAdder(Elaboratable
):
109 :attribute in0: the first input
110 :attribute in1: the second input
111 :attribute in2: the third input
112 :attribute sum: the sum output
113 :attribute carry: the carry output
116 def __init__(self
, width
):
117 """Create a ``FullAdder``.
119 :param width: the bit width of the input and output
121 self
.in0
= Signal(width
)
122 self
.in1
= Signal(width
)
123 self
.in2
= Signal(width
)
124 self
.sum = Signal(width
)
125 self
.carry
= Signal(width
)
127 def elaborate(self
, platform
):
128 """Elaborate this module."""
130 m
.d
.comb
+= self
.sum.eq(self
.in0 ^ self
.in1 ^ self
.in2
)
131 m
.d
.comb
+= self
.carry
.eq((self
.in0
& self
.in1
)
132 |
(self
.in1
& self
.in2
)
133 |
(self
.in2
& self
.in0
))
137 class PartitionedAdder(Elaboratable
):
138 """Partitioned Adder.
140 :attribute width: the bit width of the input and output. Read-only.
141 :attribute a: the first input to the adder
142 :attribute b: the second input to the adder
143 :attribute output: the sum output
144 :attribute partition_points: the input partition points. Modification not
145 supported, except for by ``Signal.eq``.
148 def __init__(self
, width
, partition_points
):
149 """Create a ``PartitionedAdder``.
151 :param width: the bit width of the input and output
152 :param partition_points: the input partition points
155 self
.a
= Signal(width
)
156 self
.b
= Signal(width
)
157 self
.output
= Signal(width
)
158 self
.partition_points
= PartitionPoints(partition_points
)
159 if not self
.partition_points
.fits_in_width(width
):
160 raise ValueError("partition_points doesn't fit in width")
162 for i
in range(self
.width
):
163 if i
in self
.partition_points
:
166 self
._expanded
_width
= expanded_width
167 # XXX these have to remain here due to some horrible nmigen
168 # simulation bugs involving sync. it is *not* necessary to
169 # have them here, they should (under normal circumstances)
170 # be moved into elaborate, as they are entirely local
171 self
._expanded
_a
= Signal(expanded_width
)
172 self
._expanded
_b
= Signal(expanded_width
)
173 self
._expanded
_output
= Signal(expanded_width
)
175 def elaborate(self
, platform
):
176 """Elaborate this module."""
179 # store bits in a list, use Cat later. graphviz is much cleaner
186 # partition points are "breaks" (extra zeros) in what would otherwise
187 # be a massive long add.
188 for i
in range(self
.width
):
189 if i
in self
.partition_points
:
190 # add extra bit set to 0 + 0 for enabled partition points
191 # and 1 + 0 for disabled partition points
192 ea
.append(self
._expanded
_a
[expanded_index
])
193 al
.append(~self
.partition_points
[i
])
194 eb
.append(self
._expanded
_b
[expanded_index
])
197 ea
.append(self
._expanded
_a
[expanded_index
])
199 eb
.append(self
._expanded
_b
[expanded_index
])
201 eo
.append(self
._expanded
_output
[expanded_index
])
202 ol
.append(self
.output
[i
])
204 # combine above using Cat
205 m
.d
.comb
+= Cat(*ea
).eq(Cat(*al
))
206 m
.d
.comb
+= Cat(*eb
).eq(Cat(*bl
))
207 m
.d
.comb
+= Cat(*ol
).eq(Cat(*eo
))
208 # use only one addition to take advantage of look-ahead carry and
209 # special hardware on FPGAs
210 m
.d
.comb
+= self
._expanded
_output
.eq(
211 self
._expanded
_a
+ self
._expanded
_b
)
215 FULL_ADDER_INPUT_COUNT
= 3
218 class AddReduce(Elaboratable
):
219 """Add list of numbers together.
221 :attribute inputs: input ``Signal``s to be summed. Modification not
222 supported, except for by ``Signal.eq``.
223 :attribute register_levels: List of nesting levels that should have
225 :attribute output: output sum.
226 :attribute partition_points: the input partition points. Modification not
227 supported, except for by ``Signal.eq``.
230 def __init__(self
, inputs
, output_width
, register_levels
, partition_points
):
231 """Create an ``AddReduce``.
233 :param inputs: input ``Signal``s to be summed.
234 :param output_width: bit-width of ``output``.
235 :param register_levels: List of nesting levels that should have
237 :param partition_points: the input partition points.
239 self
.inputs
= list(inputs
)
240 self
._resized
_inputs
= [
241 Signal(output_width
, name
=f
"resized_inputs[{i}]")
242 for i
in range(len(self
.inputs
))]
243 self
.register_levels
= list(register_levels
)
244 self
.output
= Signal(output_width
)
245 self
.partition_points
= PartitionPoints(partition_points
)
246 if not self
.partition_points
.fits_in_width(output_width
):
247 raise ValueError("partition_points doesn't fit in output_width")
248 self
._reg
_partition
_points
= self
.partition_points
.like()
249 max_level
= AddReduce
.get_max_level(len(self
.inputs
))
250 for level
in self
.register_levels
:
251 if level
> max_level
:
253 "not enough adder levels for specified register levels")
256 def get_max_level(input_count
):
257 """Get the maximum level.
259 All ``register_levels`` must be less than or equal to the maximum
264 groups
= AddReduce
.full_adder_groups(input_count
)
267 input_count
%= FULL_ADDER_INPUT_COUNT
268 input_count
+= 2 * len(groups
)
271 def next_register_levels(self
):
272 """``Iterable`` of ``register_levels`` for next recursive level."""
273 for level
in self
.register_levels
:
278 def full_adder_groups(input_count
):
279 """Get ``inputs`` indices for which a full adder should be built."""
281 input_count
- FULL_ADDER_INPUT_COUNT
+ 1,
282 FULL_ADDER_INPUT_COUNT
)
284 def elaborate(self
, platform
):
285 """Elaborate this module."""
288 # resize inputs to correct bit-width and optionally add in
290 resized_input_assignments
= [self
._resized
_inputs
[i
].eq(self
.inputs
[i
])
291 for i
in range(len(self
.inputs
))]
292 if 0 in self
.register_levels
:
293 m
.d
.sync
+= resized_input_assignments
294 m
.d
.sync
+= self
._reg
_partition
_points
.eq(self
.partition_points
)
296 m
.d
.comb
+= resized_input_assignments
297 m
.d
.comb
+= self
._reg
_partition
_points
.eq(self
.partition_points
)
299 groups
= AddReduce
.full_adder_groups(len(self
.inputs
))
300 # if there are no full adders to create, then we handle the base cases
301 # and return, otherwise we go on to the recursive case
303 if len(self
.inputs
) == 0:
304 # use 0 as the default output value
305 m
.d
.comb
+= self
.output
.eq(0)
306 elif len(self
.inputs
) == 1:
307 # handle single input
308 m
.d
.comb
+= self
.output
.eq(self
._resized
_inputs
[0])
310 # base case for adding 2 or more inputs, which get recursively
311 # reduced to 2 inputs
312 assert len(self
.inputs
) == 2
313 adder
= PartitionedAdder(len(self
.output
),
314 self
._reg
_partition
_points
)
315 m
.submodules
.final_adder
= adder
316 m
.d
.comb
+= adder
.a
.eq(self
._resized
_inputs
[0])
317 m
.d
.comb
+= adder
.b
.eq(self
._resized
_inputs
[1])
318 m
.d
.comb
+= self
.output
.eq(adder
.output
)
320 # go on to handle recursive case
321 intermediate_terms
= []
323 def add_intermediate_term(value
):
324 intermediate_term
= Signal(
326 name
=f
"intermediate_terms[{len(intermediate_terms)}]")
327 intermediate_terms
.append(intermediate_term
)
328 m
.d
.comb
+= intermediate_term
.eq(value
)
330 # store mask in intermediary (simplifies graph)
331 part_mask
= Signal(len(self
.output
), reset_less
=True)
332 mask
= self
._reg
_partition
_points
.as_mask(len(self
.output
))
333 m
.d
.comb
+= part_mask
.eq(mask
)
335 # create full adders for this recursive level.
336 # this shrinks N terms to 2 * (N // 3) plus the remainder
338 adder_i
= FullAdder(len(self
.output
))
339 setattr(m
.submodules
, f
"adder_{i}", adder_i
)
340 m
.d
.comb
+= adder_i
.in0
.eq(self
._resized
_inputs
[i
])
341 m
.d
.comb
+= adder_i
.in1
.eq(self
._resized
_inputs
[i
+ 1])
342 m
.d
.comb
+= adder_i
.in2
.eq(self
._resized
_inputs
[i
+ 2])
343 add_intermediate_term(adder_i
.sum)
344 shifted_carry
= adder_i
.carry
<< 1
345 # mask out carry bits to prevent carries between partitions
346 add_intermediate_term((adder_i
.carry
<< 1) & part_mask
)
347 # handle the remaining inputs.
348 if len(self
.inputs
) % FULL_ADDER_INPUT_COUNT
== 1:
349 add_intermediate_term(self
._resized
_inputs
[-1])
350 elif len(self
.inputs
) % FULL_ADDER_INPUT_COUNT
== 2:
351 # Just pass the terms to the next layer, since we wouldn't gain
352 # anything by using a half adder since there would still be 2 terms
353 # and just passing the terms to the next layer saves gates.
354 add_intermediate_term(self
._resized
_inputs
[-2])
355 add_intermediate_term(self
._resized
_inputs
[-1])
357 assert len(self
.inputs
) % FULL_ADDER_INPUT_COUNT
== 0
358 # recursive invocation of ``AddReduce``
359 next_level
= AddReduce(intermediate_terms
,
361 self
.next_register_levels(),
362 self
._reg
_partition
_points
)
363 m
.submodules
.next_level
= next_level
364 m
.d
.comb
+= self
.output
.eq(next_level
.output
)
369 OP_MUL_SIGNED_HIGH
= 1
370 OP_MUL_SIGNED_UNSIGNED_HIGH
= 2 # a is signed, b is unsigned
371 OP_MUL_UNSIGNED_HIGH
= 3
374 def get_term(value
, shift
=0, enabled
=None):
375 if enabled
is not None:
376 value
= Mux(enabled
, value
, 0)
378 value
= Cat(Repl(C(0, 1), shift
), value
)
384 class ProductTerm(Elaboratable
):
385 """ this class creates a single product term (a[..]*b[..]).
386 it has a design flaw in that is the *output* that is selected,
387 where the multiplication(s) are combinatorially generated
391 def __init__(self
, width
, twidth
, pbwid
, a_index
, b_index
):
392 self
.a_index
= a_index
393 self
.b_index
= b_index
394 shift
= 8 * (self
.a_index
+ self
.b_index
)
400 self
.ti
= Signal(self
.width
, reset_less
=True)
401 self
.term
= Signal(twidth
, reset_less
=True)
402 self
.a
= Signal(twidth
//2, reset_less
=True)
403 self
.b
= Signal(twidth
//2, reset_less
=True)
404 self
.pb_en
= Signal(pbwid
, reset_less
=True)
407 min_index
= min(self
.a_index
, self
.b_index
)
408 max_index
= max(self
.a_index
, self
.b_index
)
409 for i
in range(min_index
, max_index
):
410 tl
.append(self
.pb_en
[i
])
411 name
= "te_%d_%d" % (self
.a_index
, self
.b_index
)
413 term_enabled
= Signal(name
=name
, reset_less
=True)
416 self
.enabled
= term_enabled
417 self
.term
.name
= "term_%d_%d" % (a_index
, b_index
) # rename
419 def elaborate(self
, platform
):
422 if self
.enabled
is not None:
423 m
.d
.comb
+= self
.enabled
.eq(~
(Cat(*self
.tl
).bool()))
425 bsa
= Signal(self
.width
, reset_less
=True)
426 bsb
= Signal(self
.width
, reset_less
=True)
427 a_index
, b_index
= self
.a_index
, self
.b_index
429 m
.d
.comb
+= bsa
.eq(self
.a
.bit_select(a_index
* pwidth
, pwidth
))
430 m
.d
.comb
+= bsb
.eq(self
.b
.bit_select(b_index
* pwidth
, pwidth
))
431 m
.d
.comb
+= self
.ti
.eq(bsa
* bsb
)
432 m
.d
.comb
+= self
.term
.eq(get_term(self
.ti
, self
.shift
, self
.enabled
))
434 #TODO: sort out width issues, get inputs a/b switched on/off.
435 #data going into Muxes is 1/2 the required width
439 bsa = Signal(self.twidth//2, reset_less=True)
440 bsb = Signal(self.twidth//2, reset_less=True)
441 asel = Signal(width, reset_less=True)
442 bsel = Signal(width, reset_less=True)
443 a_index, b_index = self.a_index, self.b_index
444 m.d.comb += asel.eq(self.a.bit_select(a_index * pwidth, pwidth))
445 m.d.comb += bsel.eq(self.b.bit_select(b_index * pwidth, pwidth))
446 m.d.comb += bsa.eq(get_term(asel, self.shift, self.enabled))
447 m.d.comb += bsb.eq(get_term(bsel, self.shift, self.enabled))
448 m.d.comb += self.ti.eq(bsa * bsb)
449 m.d.comb += self.term.eq(self.ti)
455 class ProductTerms(Elaboratable
):
456 """ creates a bank of product terms. also performs the actual bit-selection
457 this class is to be wrapped with a for-loop on the "a" operand.
458 it creates a second-level for-loop on the "b" operand.
460 def __init__(self
, width
, twidth
, pbwid
, a_index
, blen
):
461 self
.a_index
= a_index
466 self
.a
= Signal(twidth
//2, reset_less
=True)
467 self
.b
= Signal(twidth
//2, reset_less
=True)
468 self
.pb_en
= Signal(pbwid
, reset_less
=True)
469 self
.terms
= [Signal(twidth
, name
="term%d"%i, reset_less
=True) \
470 for i
in range(blen
)]
472 def elaborate(self
, platform
):
476 for b_index
in range(self
.blen
):
477 t
= ProductTerm(self
.pwidth
, self
.twidth
, self
.pbwid
,
478 self
.a_index
, b_index
)
479 setattr(m
.submodules
, "term_%d" % b_index
, t
)
481 m
.d
.comb
+= t
.a
.eq(self
.a
)
482 m
.d
.comb
+= t
.b
.eq(self
.b
)
483 m
.d
.comb
+= t
.pb_en
.eq(self
.pb_en
)
485 m
.d
.comb
+= self
.terms
[b_index
].eq(t
.term
)
490 class Part(Elaboratable
):
491 """ a key class which, depending on the partitioning, will determine
492 what action to take when parts of the output are signed or unsigned.
494 this requires 2 pieces of data *per operand, per partition*:
495 whether the MSB is HI/LO (per partition!), and whether a signed
496 or unsigned operation has been *requested*.
498 once that is determined, signed is basically carried out
499 by splitting 2's complement into 1's complement plus one.
500 1's complement is just a bit-inversion.
502 the extra terms - as separate terms - are then thrown at the
503 AddReduce alongside the multiplication part-results.
505 def __init__(self
, width
, n_parts
, n_levels
, pbwid
):
510 self
.a_signed
= [Signal(name
=f
"a_signed_{i}") for i
in range(8)]
511 self
.b_signed
= [Signal(name
=f
"_b_signed_{i}") for i
in range(8)]
512 self
.pbs
= Signal(pbwid
, reset_less
=True)
515 self
.parts
= [Signal(name
=f
"part_{i}") for i
in range(n_parts
)]
516 self
.delayed_parts
= [
517 [Signal(name
=f
"delayed_part_{delay}_{i}")
518 for i
in range(n_parts
)]
519 for delay
in range(n_levels
)]
520 # XXX REALLY WEIRD BUG - have to take a copy of the last delayed_parts
521 self
.dplast
= [Signal(name
=f
"dplast_{i}")
522 for i
in range(n_parts
)]
524 self
.not_a_term
= Signal(width
)
525 self
.neg_lsb_a_term
= Signal(width
)
526 self
.not_b_term
= Signal(width
)
527 self
.neg_lsb_b_term
= Signal(width
)
529 def elaborate(self
, platform
):
532 pbs
, parts
, delayed_parts
= self
.pbs
, self
.parts
, self
.delayed_parts
533 byte_count
= 8 // len(parts
)
534 for i
in range(len(parts
)):
536 pbl
.append(~pbs
[i
* byte_count
- 1])
537 for j
in range(i
* byte_count
, (i
+ 1) * byte_count
- 1):
539 pbl
.append(~pbs
[(i
+ 1) * byte_count
- 1])
540 value
= Signal(len(pbl
), reset_less
=True)
541 m
.d
.comb
+= value
.eq(Cat(*pbl
))
542 m
.d
.comb
+= parts
[i
].eq(~
(value
).bool())
543 m
.d
.comb
+= delayed_parts
[0][i
].eq(parts
[i
])
544 m
.d
.sync
+= [delayed_parts
[j
+ 1][i
].eq(delayed_parts
[j
][i
])
545 for j
in range(len(delayed_parts
)-1)]
546 m
.d
.comb
+= self
.dplast
[i
].eq(delayed_parts
[-1][i
])
548 not_a_term
, neg_lsb_a_term
, not_b_term
, neg_lsb_b_term
= \
549 self
.not_a_term
, self
.neg_lsb_a_term
, \
550 self
.not_b_term
, self
.neg_lsb_b_term
552 byte_width
= 8 // len(parts
) # byte width
553 bit_wid
= 8 * byte_width
# bit width
554 ext
= Repl(0, bit_wid
) # extend output to HI part
555 nat
, nbt
, nla
, nlb
= [], [], [], []
556 for i
in range(len(parts
)):
557 # determine sign of each incoming number *in this partition*
558 be
= parts
[i
] & self
.a
[(i
+ 1) * bit_wid
- 1] \
# MSB
559 & self
.a_signed
[i
* byte_width
] # a op is signed?
560 ae
= parts
[i
] & self
.b
[(i
+ 1) * bit_wid
- 1] \
# MSB
561 & self
.b_signed
[i
* byte_width
] # b op is signed?
562 a_enabled
= Signal(name
="a_en_%d" % i
, reset_less
=True)
563 b_enabled
= Signal(name
="b_en_%d" % i
, reset_less
=True)
564 m
.d
.comb
+= a_enabled
.eq(ae
)
565 m
.d
.comb
+= b_enabled
.eq(be
)
567 # for 8-bit values: form a * 0xFF00 by using -a * 0x100, the
568 # negation operation is split into a bitwise not and a +1.
569 # likewise for 16, 32, and 64-bit values.
571 # a: width-extended 1s complement if a is signed, otherwise zero
572 nat
.append(Mux(a_enabled
,
573 Cat(ext
, ~self
.a
.bit_select(bit_wid
* i
, bit_wid
)),
576 # a: add 1 if a signed, otherwise add zero
577 nla
.append(Cat(ext
, a_enabled
, Repl(0, bit_wid
-1)))
579 # b: width-extended 1s complement if a is signed, otherwise zero
580 nbt
.append(Mux(b_enabled
,
581 Cat(ext
, ~self
.b
.bit_select(bit_wid
* i
, bit_wid
)),
584 # b: add 1 if b signed, otherwise add zero
585 nlb
.append(Cat(ext
, b_enabled
, Repl(0, bit_wid
-1)))
587 # concatenate together and return all 4 results.
588 m
.d
.comb
+= [not_a_term
.eq(Cat(*nat
)),
589 not_b_term
.eq(Cat(*nbt
)),
590 neg_lsb_a_term
.eq(Cat(*nla
)),
591 neg_lsb_b_term
.eq(Cat(*nlb
)),
597 class IntermediateOut(Elaboratable
):
598 """ selects the HI/LO part of the multiplication, for a given bit-width
599 the output is also reconstructed in its SIMD (partition) lanes.
601 def __init__(self
, width
, out_wid
, n_parts
):
603 self
.n_parts
= n_parts
604 self
.delayed_part_ops
= [Signal(2, name
="dpop%d" % i
, reset_less
=True)
606 self
.intermed
= Signal(out_wid
, reset_less
=True)
607 self
.output
= Signal(out_wid
//2, reset_less
=True)
609 def elaborate(self
, platform
):
615 for i
in range(self
.n_parts
):
616 op
= Signal(w
, reset_less
=True, name
="op%d_%d" % (w
, i
))
618 Mux(self
.delayed_part_ops
[sel
* i
] == OP_MUL_LOW
,
619 self
.intermed
.bit_select(i
* w
*2, w
),
620 self
.intermed
.bit_select(i
* w
*2 + w
, w
)))
622 m
.d
.comb
+= self
.output
.eq(Cat(*ol
))
627 class FinalOut(Elaboratable
):
628 """ selects the final output based on the partitioning.
630 each byte is selectable independently, i.e. it is possible
631 that some partitions requested 8-bit computation whilst others
632 requested 16 or 32 bit.
634 def __init__(self
, out_wid
):
636 self
.d8
= [Signal(name
=f
"d8_{i}", reset_less
=True) for i
in range(8)]
637 self
.d16
= [Signal(name
=f
"d16_{i}", reset_less
=True) for i
in range(4)]
638 self
.d32
= [Signal(name
=f
"d32_{i}", reset_less
=True) for i
in range(2)]
640 self
.i8
= Signal(out_wid
, reset_less
=True)
641 self
.i16
= Signal(out_wid
, reset_less
=True)
642 self
.i32
= Signal(out_wid
, reset_less
=True)
643 self
.i64
= Signal(out_wid
, reset_less
=True)
646 self
.out
= Signal(out_wid
, reset_less
=True)
648 def elaborate(self
, platform
):
652 # select one of the outputs: d8 selects i8, d16 selects i16
653 # d32 selects i32, and the default is i64.
654 # d8 and d16 are ORed together in the first Mux
655 # then the 2nd selects either i8 or i16.
656 # if neither d8 nor d16 are set, d32 selects either i32 or i64.
657 op
= Signal(8, reset_less
=True, name
="op_%d" % i
)
659 Mux(self
.d8
[i
] | self
.d16
[i
// 2],
660 Mux(self
.d8
[i
], self
.i8
.bit_select(i
* 8, 8),
661 self
.i16
.bit_select(i
* 8, 8)),
662 Mux(self
.d32
[i
// 4], self
.i32
.bit_select(i
* 8, 8),
663 self
.i64
.bit_select(i
* 8, 8))))
665 m
.d
.comb
+= self
.out
.eq(Cat(*ol
))
669 class OrMod(Elaboratable
):
670 """ ORs four values together in a hierarchical tree
672 def __init__(self
, wid
):
674 self
.orin
= [Signal(wid
, name
="orin%d" % i
, reset_less
=True)
676 self
.orout
= Signal(wid
, reset_less
=True)
678 def elaborate(self
, platform
):
680 or1
= Signal(self
.wid
, reset_less
=True)
681 or2
= Signal(self
.wid
, reset_less
=True)
682 m
.d
.comb
+= or1
.eq(self
.orin
[0] | self
.orin
[1])
683 m
.d
.comb
+= or2
.eq(self
.orin
[2] | self
.orin
[3])
684 m
.d
.comb
+= self
.orout
.eq(or1 | or2
)
689 class Signs(Elaboratable
):
690 """ determines whether a or b are signed numbers
691 based on the required operation type (OP_MUL_*)
695 self
.part_ops
= Signal(2, reset_less
=True)
696 self
.a_signed
= Signal(reset_less
=True)
697 self
.b_signed
= Signal(reset_less
=True)
699 def elaborate(self
, platform
):
703 asig
= self
.part_ops
!= OP_MUL_UNSIGNED_HIGH
704 bsig
= (self
.part_ops
== OP_MUL_LOW
) \
705 |
(self
.part_ops
== OP_MUL_SIGNED_HIGH
)
706 m
.d
.comb
+= self
.a_signed
.eq(asig
)
707 m
.d
.comb
+= self
.b_signed
.eq(bsig
)
712 class Mul8_16_32_64(Elaboratable
):
713 """Signed/Unsigned 8/16/32/64-bit partitioned integer multiplier.
715 Supports partitioning into any combination of 8, 16, 32, and 64-bit
716 partitions on naturally-aligned boundaries. Supports the operation being
717 set for each partition independently.
719 :attribute part_pts: the input partition points. Has a partition point at
720 multiples of 8 in 0 < i < 64. Each partition point's associated
721 ``Value`` is a ``Signal``. Modification not supported, except for by
723 :attribute part_ops: the operation for each byte. The operation for a
724 particular partition is selected by assigning the selected operation
725 code to each byte in the partition. The allowed operation codes are:
727 :attribute OP_MUL_LOW: the LSB half of the product. Equivalent to
728 RISC-V's `mul` instruction.
729 :attribute OP_MUL_SIGNED_HIGH: the MSB half of the product where both
730 ``a`` and ``b`` are signed. Equivalent to RISC-V's `mulh`
732 :attribute OP_MUL_SIGNED_UNSIGNED_HIGH: the MSB half of the product
733 where ``a`` is signed and ``b`` is unsigned. Equivalent to RISC-V's
734 `mulhsu` instruction.
735 :attribute OP_MUL_UNSIGNED_HIGH: the MSB half of the product where both
736 ``a`` and ``b`` are unsigned. Equivalent to RISC-V's `mulhu`
740 def __init__(self
, register_levels
=()):
741 """ register_levels: specifies the points in the cascade at which
742 flip-flops are to be inserted.
746 self
.register_levels
= list(register_levels
)
749 self
.part_pts
= PartitionPoints()
750 for i
in range(8, 64, 8):
751 self
.part_pts
[i
] = Signal(name
=f
"part_pts_{i}")
752 self
.part_ops
= [Signal(2, name
=f
"part_ops_{i}") for i
in range(8)]
756 # intermediates (needed for unit tests)
757 self
._intermediate
_output
= Signal(128)
760 self
.output
= Signal(64)
762 def _part_byte(self
, index
):
763 if index
== -1 or index
== 7:
765 assert index
>= 0 and index
< 8
766 return self
.part_pts
[index
* 8 + 8]
768 def elaborate(self
, platform
):
772 pbs
= Signal(8, reset_less
=True)
775 pb
= Signal(name
="pb%d" % i
, reset_less
=True)
776 m
.d
.comb
+= pb
.eq(self
._part
_byte
(i
))
778 m
.d
.comb
+= pbs
.eq(Cat(*tl
))
785 setattr(m
.submodules
, "signs%d" % i
, s
)
786 m
.d
.comb
+= s
.part_ops
.eq(self
.part_ops
[i
])
789 [Signal(2, name
=f
"_delayed_part_ops_{delay}_{i}")
791 for delay
in range(1 + len(self
.register_levels
))]
792 for i
in range(len(self
.part_ops
)):
793 m
.d
.comb
+= delayed_part_ops
[0][i
].eq(self
.part_ops
[i
])
794 m
.d
.sync
+= [delayed_part_ops
[j
+ 1][i
].eq(delayed_part_ops
[j
][i
])
795 for j
in range(len(self
.register_levels
))]
797 n_levels
= len(self
.register_levels
)+1
798 m
.submodules
.part_8
= part_8
= Part(128, 8, n_levels
, 8)
799 m
.submodules
.part_16
= part_16
= Part(128, 4, n_levels
, 8)
800 m
.submodules
.part_32
= part_32
= Part(128, 2, n_levels
, 8)
801 m
.submodules
.part_64
= part_64
= Part(128, 1, n_levels
, 8)
802 nat_l
, nbt_l
, nla_l
, nlb_l
= [], [], [], []
803 for mod
in [part_8
, part_16
, part_32
, part_64
]:
804 m
.d
.comb
+= mod
.a
.eq(self
.a
)
805 m
.d
.comb
+= mod
.b
.eq(self
.b
)
806 for i
in range(len(signs
)):
807 m
.d
.comb
+= mod
.a_signed
[i
].eq(signs
[i
].a_signed
)
808 m
.d
.comb
+= mod
.b_signed
[i
].eq(signs
[i
].b_signed
)
809 m
.d
.comb
+= mod
.pbs
.eq(pbs
)
810 nat_l
.append(mod
.not_a_term
)
811 nbt_l
.append(mod
.not_b_term
)
812 nla_l
.append(mod
.neg_lsb_a_term
)
813 nlb_l
.append(mod
.neg_lsb_b_term
)
817 for a_index
in range(8):
818 t
= ProductTerms(8, 128, 8, a_index
, 8)
819 setattr(m
.submodules
, "terms_%d" % a_index
, t
)
821 m
.d
.comb
+= t
.a
.eq(self
.a
)
822 m
.d
.comb
+= t
.b
.eq(self
.b
)
823 m
.d
.comb
+= t
.pb_en
.eq(pbs
)
828 # it's fine to bitwise-or data together since they are never enabled
830 m
.submodules
.nat_or
= nat_or
= OrMod(128)
831 m
.submodules
.nbt_or
= nbt_or
= OrMod(128)
832 m
.submodules
.nla_or
= nla_or
= OrMod(128)
833 m
.submodules
.nlb_or
= nlb_or
= OrMod(128)
834 for l
, mod
in [(nat_l
, nat_or
),
838 for i
in range(len(l
)):
839 m
.d
.comb
+= mod
.orin
[i
].eq(l
[i
])
840 terms
.append(mod
.orout
)
842 expanded_part_pts
= PartitionPoints()
843 for i
, v
in self
.part_pts
.items():
844 signal
= Signal(name
=f
"expanded_part_pts_{i*2}", reset_less
=True)
845 expanded_part_pts
[i
* 2] = signal
846 m
.d
.comb
+= signal
.eq(v
)
848 add_reduce
= AddReduce(terms
,
850 self
.register_levels
,
852 m
.submodules
.add_reduce
= add_reduce
853 m
.d
.comb
+= self
._intermediate
_output
.eq(add_reduce
.output
)
855 m
.submodules
.io64
= io64
= IntermediateOut(64, 128, 1)
856 m
.d
.comb
+= io64
.intermed
.eq(self
._intermediate
_output
)
858 m
.d
.comb
+= io64
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
861 m
.submodules
.io32
= io32
= IntermediateOut(32, 128, 2)
862 m
.d
.comb
+= io32
.intermed
.eq(self
._intermediate
_output
)
864 m
.d
.comb
+= io32
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
867 m
.submodules
.io16
= io16
= IntermediateOut(16, 128, 4)
868 m
.d
.comb
+= io16
.intermed
.eq(self
._intermediate
_output
)
870 m
.d
.comb
+= io16
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
873 m
.submodules
.io8
= io8
= IntermediateOut(8, 128, 8)
874 m
.d
.comb
+= io8
.intermed
.eq(self
._intermediate
_output
)
876 m
.d
.comb
+= io8
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
879 m
.submodules
.finalout
= finalout
= FinalOut(64)
880 for i
in range(len(part_8
.delayed_parts
[-1])):
881 m
.d
.comb
+= finalout
.d8
[i
].eq(part_8
.dplast
[i
])
882 for i
in range(len(part_16
.delayed_parts
[-1])):
883 m
.d
.comb
+= finalout
.d16
[i
].eq(part_16
.dplast
[i
])
884 for i
in range(len(part_32
.delayed_parts
[-1])):
885 m
.d
.comb
+= finalout
.d32
[i
].eq(part_32
.dplast
[i
])
886 m
.d
.comb
+= finalout
.i8
.eq(io8
.output
)
887 m
.d
.comb
+= finalout
.i16
.eq(io16
.output
)
888 m
.d
.comb
+= finalout
.i32
.eq(io32
.output
)
889 m
.d
.comb
+= finalout
.i64
.eq(io64
.output
)
890 m
.d
.comb
+= self
.output
.eq(finalout
.out
)
895 if __name__
== "__main__":
899 m
._intermediate
_output
,
902 *m
.part_pts
.values()])