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
):
386 def __init__(self
, width
, twidth
, pbwid
, a_index
, b_index
):
387 self
.a_index
= a_index
388 self
.b_index
= b_index
389 shift
= 8 * (self
.a_index
+ self
.b_index
)
395 self
.ti
= Signal(self
.width
, reset_less
=True)
396 self
.term
= Signal(twidth
, reset_less
=True)
397 self
.a
= Signal(twidth
//2, reset_less
=True)
398 self
.b
= Signal(twidth
//2, reset_less
=True)
399 self
.pb_en
= Signal(pbwid
, reset_less
=True)
402 min_index
= min(self
.a_index
, self
.b_index
)
403 max_index
= max(self
.a_index
, self
.b_index
)
404 for i
in range(min_index
, max_index
):
405 tl
.append(self
.pb_en
[i
])
406 name
= "te_%d_%d" % (self
.a_index
, self
.b_index
)
408 term_enabled
= Signal(name
=name
, reset_less
=True)
411 self
.enabled
= term_enabled
412 self
.term
.name
= "term_%d_%d" % (a_index
, b_index
) # rename
414 def elaborate(self
, platform
):
417 if self
.enabled
is not None:
418 m
.d
.comb
+= self
.enabled
.eq(~
(Cat(*self
.tl
).bool()))
420 bsa
= Signal(self
.width
, reset_less
=True)
421 bsb
= Signal(self
.width
, reset_less
=True)
422 a_index
, b_index
= self
.a_index
, self
.b_index
424 m
.d
.comb
+= bsa
.eq(self
.a
.bit_select(a_index
* pwidth
, pwidth
))
425 m
.d
.comb
+= bsb
.eq(self
.b
.bit_select(b_index
* pwidth
, pwidth
))
426 m
.d
.comb
+= self
.ti
.eq(bsa
* bsb
)
427 m
.d
.comb
+= self
.term
.eq(get_term(self
.ti
, self
.shift
, self
.enabled
))
429 #TODO: sort out width issues, get inputs a/b switched on/off.
430 #data going into Muxes is 1/2 the required width
434 bsa = Signal(self.twidth//2, reset_less=True)
435 bsb = Signal(self.twidth//2, reset_less=True)
436 asel = Signal(width, reset_less=True)
437 bsel = Signal(width, reset_less=True)
438 a_index, b_index = self.a_index, self.b_index
439 m.d.comb += asel.eq(self.a.bit_select(a_index * pwidth, pwidth))
440 m.d.comb += bsel.eq(self.b.bit_select(b_index * pwidth, pwidth))
441 m.d.comb += bsa.eq(get_term(asel, self.shift, self.enabled))
442 m.d.comb += bsb.eq(get_term(bsel, self.shift, self.enabled))
443 m.d.comb += self.ti.eq(bsa * bsb)
444 m.d.comb += self.term.eq(self.ti)
450 class ProductTerms(Elaboratable
):
452 def __init__(self
, width
, twidth
, pbwid
, a_index
, blen
):
453 self
.a_index
= a_index
458 self
.a
= Signal(twidth
//2, reset_less
=True)
459 self
.b
= Signal(twidth
//2, reset_less
=True)
460 self
.pb_en
= Signal(pbwid
, reset_less
=True)
461 self
.terms
= [Signal(twidth
, name
="term%d"%i, reset_less
=True) \
462 for i
in range(blen
)]
464 def elaborate(self
, platform
):
468 for b_index
in range(self
.blen
):
469 t
= ProductTerm(self
.pwidth
, self
.twidth
, self
.pbwid
,
470 self
.a_index
, b_index
)
471 setattr(m
.submodules
, "term_%d" % b_index
, t
)
473 m
.d
.comb
+= t
.a
.eq(self
.a
)
474 m
.d
.comb
+= t
.b
.eq(self
.b
)
475 m
.d
.comb
+= t
.pb_en
.eq(self
.pb_en
)
477 m
.d
.comb
+= self
.terms
[b_index
].eq(t
.term
)
482 class Part(Elaboratable
):
483 def __init__(self
, width
, n_parts
, n_levels
, pbwid
):
488 self
.a_signed
= [Signal(name
=f
"a_signed_{i}") for i
in range(8)]
489 self
.b_signed
= [Signal(name
=f
"_b_signed_{i}") for i
in range(8)]
490 self
.pbs
= Signal(pbwid
, reset_less
=True)
493 self
.parts
= [Signal(name
=f
"part_{i}") for i
in range(n_parts
)]
494 self
.delayed_parts
= [
495 [Signal(name
=f
"delayed_part_{delay}_{i}")
496 for i
in range(n_parts
)]
497 for delay
in range(n_levels
)]
498 # XXX REALLY WEIRD BUG - have to take a copy of the last delayed_parts
499 self
.dplast
= [Signal(name
=f
"dplast_{i}")
500 for i
in range(n_parts
)]
502 self
.not_a_term
= Signal(width
)
503 self
.neg_lsb_a_term
= Signal(width
)
504 self
.not_b_term
= Signal(width
)
505 self
.neg_lsb_b_term
= Signal(width
)
507 def elaborate(self
, platform
):
510 pbs
, parts
, delayed_parts
= self
.pbs
, self
.parts
, self
.delayed_parts
511 byte_count
= 8 // len(parts
)
512 for i
in range(len(parts
)):
514 pbl
.append(~pbs
[i
* byte_count
- 1])
515 for j
in range(i
* byte_count
, (i
+ 1) * byte_count
- 1):
517 pbl
.append(~pbs
[(i
+ 1) * byte_count
- 1])
518 value
= Signal(len(pbl
), reset_less
=True)
519 m
.d
.comb
+= value
.eq(Cat(*pbl
))
520 m
.d
.comb
+= parts
[i
].eq(~
(value
).bool())
521 m
.d
.comb
+= delayed_parts
[0][i
].eq(parts
[i
])
522 m
.d
.sync
+= [delayed_parts
[j
+ 1][i
].eq(delayed_parts
[j
][i
])
523 for j
in range(len(delayed_parts
)-1)]
524 m
.d
.comb
+= self
.dplast
[i
].eq(delayed_parts
[-1][i
])
526 not_a_term
, neg_lsb_a_term
, not_b_term
, neg_lsb_b_term
= \
527 self
.not_a_term
, self
.neg_lsb_a_term
, \
528 self
.not_b_term
, self
.neg_lsb_b_term
530 byte_width
= 8 // len(parts
)
531 bit_width
= 8 * byte_width
532 nat
, nbt
, nla
, nlb
= [], [], [], []
533 for i
in range(len(parts
)):
534 be
= parts
[i
] & self
.a
[(i
+ 1) * bit_width
- 1] \
535 & self
.a_signed
[i
* byte_width
]
536 ae
= parts
[i
] & self
.b
[(i
+ 1) * bit_width
- 1] \
537 & self
.b_signed
[i
* byte_width
]
538 a_enabled
= Signal(name
="a_en_%d" % i
, reset_less
=True)
539 b_enabled
= Signal(name
="b_en_%d" % i
, reset_less
=True)
540 m
.d
.comb
+= a_enabled
.eq(ae
)
541 m
.d
.comb
+= b_enabled
.eq(be
)
543 # for 8-bit values: form a * 0xFF00 by using -a * 0x100, the
544 # negation operation is split into a bitwise not and a +1.
545 # likewise for 16, 32, and 64-bit values.
546 nat
.append(Mux(a_enabled
,
547 Cat(Repl(0, bit_width
),
548 ~self
.a
.bit_select(bit_width
* i
, bit_width
)),
551 nla
.append(Cat(Repl(0, bit_width
), a_enabled
,
552 Repl(0, bit_width
-1)))
554 nbt
.append(Mux(b_enabled
,
555 Cat(Repl(0, bit_width
),
556 ~self
.b
.bit_select(bit_width
* i
, bit_width
)),
559 nlb
.append(Cat(Repl(0, bit_width
), b_enabled
,
560 Repl(0, bit_width
-1)))
562 m
.d
.comb
+= [not_a_term
.eq(Cat(*nat
)),
563 not_b_term
.eq(Cat(*nbt
)),
564 neg_lsb_a_term
.eq(Cat(*nla
)),
565 neg_lsb_b_term
.eq(Cat(*nlb
)),
571 class IntermediateOut(Elaboratable
):
572 def __init__(self
, width
, out_wid
, n_parts
):
574 self
.n_parts
= n_parts
575 self
.delayed_part_ops
= [Signal(2, name
="dpop%d" % i
, reset_less
=True)
577 self
.intermed
= Signal(out_wid
, reset_less
=True)
578 self
.output
= Signal(out_wid
//2, reset_less
=True)
580 def elaborate(self
, platform
):
586 for i
in range(self
.n_parts
):
587 op
= Signal(w
, reset_less
=True, name
="op%d_%d" % (w
, i
))
589 Mux(self
.delayed_part_ops
[sel
* i
] == OP_MUL_LOW
,
590 self
.intermed
.bit_select(i
* w
*2, w
),
591 self
.intermed
.bit_select(i
* w
*2 + w
, w
)))
593 m
.d
.comb
+= self
.output
.eq(Cat(*ol
))
598 class FinalOut(Elaboratable
):
599 def __init__(self
, out_wid
):
601 self
.d8
= [Signal(name
=f
"d8_{i}", reset_less
=True) for i
in range(8)]
602 self
.d16
= [Signal(name
=f
"d16_{i}", reset_less
=True) for i
in range(4)]
603 self
.d32
= [Signal(name
=f
"d32_{i}", reset_less
=True) for i
in range(2)]
604 self
.d64
= [Signal(name
=f
"d64_{i}", reset_less
=True) for i
in range(1)]
606 self
.i8
= Signal(out_wid
, reset_less
=True)
607 self
.i16
= Signal(out_wid
, reset_less
=True)
608 self
.i32
= Signal(out_wid
, reset_less
=True)
609 self
.i64
= Signal(out_wid
, reset_less
=True)
612 self
.out
= Signal(out_wid
, reset_less
=True)
614 def elaborate(self
, platform
):
618 op
= Signal(8, reset_less
=True, name
="op_%d" % i
)
619 choice
= Signal(4, reset_less
=True)
620 m
.d
.comb
+= choice
.eq(Cat(self
.d8
[i
], self
.d16
[i
//2],
621 self
.d32
[i
//4], self
.d64
[i
//8]))
622 # select one of the outputs.
623 with m
.Switch(choice
):
624 with m
.Case(0b0001): # d8
625 m
.d
.comb
+= op
.eq(self
.i8
.bit_select(i
* 8, 8))
626 with m
.Case(0b0010): # d16
627 m
.d
.comb
+= op
.eq(self
.i16
.bit_select(i
* 8, 8))
628 with m
.Case(0b0100): # d32
629 m
.d
.comb
+= op
.eq(self
.i32
.bit_select(i
* 8, 8))
630 with m
.Case(0b1000): # d64
631 m
.d
.comb
+= op
.eq(self
.i64
.bit_select(i
* 8, 8))
633 m
.d
.comb
+= self
.out
.eq(Cat(*ol
))
637 class OrMod(Elaboratable
):
638 def __init__(self
, wid
):
640 self
.orin
= [Signal(wid
, name
="orin%d" % i
, reset_less
=True)
642 self
.orout
= Signal(wid
, reset_less
=True)
644 def elaborate(self
, platform
):
646 or1
= Signal(self
.wid
, reset_less
=True)
647 or2
= Signal(self
.wid
, reset_less
=True)
648 m
.d
.comb
+= or1
.eq(self
.orin
[0] | self
.orin
[1])
649 m
.d
.comb
+= or2
.eq(self
.orin
[2] | self
.orin
[3])
650 m
.d
.comb
+= self
.orout
.eq(or1 | or2
)
655 class Signs(Elaboratable
):
658 self
.part_ops
= Signal(2, reset_less
=True)
659 self
.a_signed
= Signal(reset_less
=True)
660 self
.b_signed
= Signal(reset_less
=True)
662 def elaborate(self
, platform
):
666 asig
= self
.part_ops
!= OP_MUL_UNSIGNED_HIGH
667 bsig
= (self
.part_ops
== OP_MUL_LOW
) \
668 |
(self
.part_ops
== OP_MUL_SIGNED_HIGH
)
669 m
.d
.comb
+= self
.a_signed
.eq(asig
)
670 m
.d
.comb
+= self
.b_signed
.eq(bsig
)
675 class Mul8_16_32_64(Elaboratable
):
676 """Signed/Unsigned 8/16/32/64-bit partitioned integer multiplier.
678 Supports partitioning into any combination of 8, 16, 32, and 64-bit
679 partitions on naturally-aligned boundaries. Supports the operation being
680 set for each partition independently.
682 :attribute part_pts: the input partition points. Has a partition point at
683 multiples of 8 in 0 < i < 64. Each partition point's associated
684 ``Value`` is a ``Signal``. Modification not supported, except for by
686 :attribute part_ops: the operation for each byte. The operation for a
687 particular partition is selected by assigning the selected operation
688 code to each byte in the partition. The allowed operation codes are:
690 :attribute OP_MUL_LOW: the LSB half of the product. Equivalent to
691 RISC-V's `mul` instruction.
692 :attribute OP_MUL_SIGNED_HIGH: the MSB half of the product where both
693 ``a`` and ``b`` are signed. Equivalent to RISC-V's `mulh`
695 :attribute OP_MUL_SIGNED_UNSIGNED_HIGH: the MSB half of the product
696 where ``a`` is signed and ``b`` is unsigned. Equivalent to RISC-V's
697 `mulhsu` instruction.
698 :attribute OP_MUL_UNSIGNED_HIGH: the MSB half of the product where both
699 ``a`` and ``b`` are unsigned. Equivalent to RISC-V's `mulhu`
703 def __init__(self
, register_levels
= ()):
706 self
.register_levels
= list(register_levels
)
709 self
.part_pts
= PartitionPoints()
710 for i
in range(8, 64, 8):
711 self
.part_pts
[i
] = Signal(name
=f
"part_pts_{i}")
712 self
.part_ops
= [Signal(2, name
=f
"part_ops_{i}") for i
in range(8)]
716 # intermediates (needed for unit tests)
717 self
._intermediate
_output
= Signal(128)
720 self
.output
= Signal(64)
722 def _part_byte(self
, index
):
723 if index
== -1 or index
== 7:
725 assert index
>= 0 and index
< 8
726 return self
.part_pts
[index
* 8 + 8]
728 def elaborate(self
, platform
):
732 pbs
= Signal(8, reset_less
=True)
735 pb
= Signal(name
="pb%d" % i
, reset_less
=True)
736 m
.d
.comb
+= pb
.eq(self
._part
_byte
(i
))
738 m
.d
.comb
+= pbs
.eq(Cat(*tl
))
745 setattr(m
.submodules
, "signs%d" % i
, s
)
746 m
.d
.comb
+= s
.part_ops
.eq(self
.part_ops
[i
])
749 [Signal(2, name
=f
"_delayed_part_ops_{delay}_{i}")
751 for delay
in range(1 + len(self
.register_levels
))]
752 for i
in range(len(self
.part_ops
)):
753 m
.d
.comb
+= delayed_part_ops
[0][i
].eq(self
.part_ops
[i
])
754 m
.d
.sync
+= [delayed_part_ops
[j
+ 1][i
].eq(delayed_part_ops
[j
][i
])
755 for j
in range(len(self
.register_levels
))]
757 n_levels
= len(self
.register_levels
)+1
758 m
.submodules
.part_8
= part_8
= Part(128, 8, n_levels
, 8)
759 m
.submodules
.part_16
= part_16
= Part(128, 4, n_levels
, 8)
760 m
.submodules
.part_32
= part_32
= Part(128, 2, n_levels
, 8)
761 m
.submodules
.part_64
= part_64
= Part(128, 1, n_levels
, 8)
762 nat_l
, nbt_l
, nla_l
, nlb_l
= [], [], [], []
763 for mod
in [part_8
, part_16
, part_32
, part_64
]:
764 m
.d
.comb
+= mod
.a
.eq(self
.a
)
765 m
.d
.comb
+= mod
.b
.eq(self
.b
)
766 for i
in range(len(signs
)):
767 m
.d
.comb
+= mod
.a_signed
[i
].eq(signs
[i
].a_signed
)
768 m
.d
.comb
+= mod
.b_signed
[i
].eq(signs
[i
].b_signed
)
769 m
.d
.comb
+= mod
.pbs
.eq(pbs
)
770 nat_l
.append(mod
.not_a_term
)
771 nbt_l
.append(mod
.not_b_term
)
772 nla_l
.append(mod
.neg_lsb_a_term
)
773 nlb_l
.append(mod
.neg_lsb_b_term
)
777 for a_index
in range(8):
778 t
= ProductTerms(8, 128, 8, a_index
, 8)
779 setattr(m
.submodules
, "terms_%d" % a_index
, t
)
781 m
.d
.comb
+= t
.a
.eq(self
.a
)
782 m
.d
.comb
+= t
.b
.eq(self
.b
)
783 m
.d
.comb
+= t
.pb_en
.eq(pbs
)
788 # it's fine to bitwise-or data together since they are never enabled
790 m
.submodules
.nat_or
= nat_or
= OrMod(128)
791 m
.submodules
.nbt_or
= nbt_or
= OrMod(128)
792 m
.submodules
.nla_or
= nla_or
= OrMod(128)
793 m
.submodules
.nlb_or
= nlb_or
= OrMod(128)
794 for l
, mod
in [(nat_l
, nat_or
),
798 for i
in range(len(l
)):
799 m
.d
.comb
+= mod
.orin
[i
].eq(l
[i
])
800 terms
.append(mod
.orout
)
802 expanded_part_pts
= PartitionPoints()
803 for i
, v
in self
.part_pts
.items():
804 signal
= Signal(name
=f
"expanded_part_pts_{i*2}", reset_less
=True)
805 expanded_part_pts
[i
* 2] = signal
806 m
.d
.comb
+= signal
.eq(v
)
808 add_reduce
= AddReduce(terms
,
810 self
.register_levels
,
812 m
.submodules
.add_reduce
= add_reduce
813 m
.d
.comb
+= self
._intermediate
_output
.eq(add_reduce
.output
)
815 m
.submodules
.io64
= io64
= IntermediateOut(64, 128, 1)
816 m
.d
.comb
+= io64
.intermed
.eq(self
._intermediate
_output
)
818 m
.d
.comb
+= io64
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
821 m
.submodules
.io32
= io32
= IntermediateOut(32, 128, 2)
822 m
.d
.comb
+= io32
.intermed
.eq(self
._intermediate
_output
)
824 m
.d
.comb
+= io32
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
827 m
.submodules
.io16
= io16
= IntermediateOut(16, 128, 4)
828 m
.d
.comb
+= io16
.intermed
.eq(self
._intermediate
_output
)
830 m
.d
.comb
+= io16
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
833 m
.submodules
.io8
= io8
= IntermediateOut(8, 128, 8)
834 m
.d
.comb
+= io8
.intermed
.eq(self
._intermediate
_output
)
836 m
.d
.comb
+= io8
.delayed_part_ops
[i
].eq(delayed_part_ops
[-1][i
])
839 m
.submodules
.fo
= fo
= FinalOut(64)
840 for i
in range(len(part_8
.delayed_parts
[-1])):
841 m
.d
.comb
+= fo
.d8
[i
].eq(part_8
.dplast
[i
])
842 for i
in range(len(part_16
.delayed_parts
[-1])):
843 m
.d
.comb
+= fo
.d16
[i
].eq(part_16
.dplast
[i
])
844 for i
in range(len(part_32
.delayed_parts
[-1])):
845 m
.d
.comb
+= fo
.d32
[i
].eq(part_32
.dplast
[i
])
846 for i
in range(len(part_64
.delayed_parts
[-1])):
847 m
.d
.comb
+= fo
.d64
[i
].eq(part_64
.dplast
[i
])
848 m
.d
.comb
+= fo
.i8
.eq(io8
.output
)
849 m
.d
.comb
+= fo
.i16
.eq(io16
.output
)
850 m
.d
.comb
+= fo
.i32
.eq(io32
.output
)
851 m
.d
.comb
+= fo
.i64
.eq(io64
.output
)
852 m
.d
.comb
+= self
.output
.eq(fo
.out
)
857 if __name__
== "__main__":
861 m
._intermediate
_output
,
864 *m
.part_pts
.values()])