src/ieee754/part_mul_add/multiply.py

   1 # SPDX-License-Identifier: LGPL-2.1-or-later
   2 # See Notices.txt for copyright information
   3 """Integer Multiplication."""
   4
   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
  12 class PartitionPoints(dict):
  13     """Partition points and corresponding ``Value``s.
  14
  15     The points at where an ALU is partitioned along with ``Value``s that
  16     specify if the corresponding partition points are enabled.
  17
  18     For example: ``{1: True, 5: True, 10: True}`` with
  19     ``width == 16`` specifies that the ALU is split into 4 sections:
  20     * bits 0 <= ``i`` < 1
  21     * bits 1 <= ``i`` < 5
  22     * bits 5 <= ``i`` < 10
  23     * bits 10 <= ``i`` < 16
  24
  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:
  28         * bits 0 <= ``i`` < 1
  29         * bits 1 <= ``i`` < 5
  30         * bits 5 <= ``i`` < 10
  31         * bits 10 <= ``i`` < 16
  32     * Otherwise
  33         * bits 0 <= ``i`` < 1
  34         * bits 1 <= ``i`` < 10
  35         * bits 10 <= ``i`` < 16
  36     """
  37
  38     def __init__(self, partition_points=None):
  39         """Create a new ``PartitionPoints``.
  40
  41         :param partition_points: the input partition points to values mapping.
  42         """
  43         super().__init__()
  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")
  48                 if point < 0:
  49                     raise ValueError("point must be a non-negative integer")
  50                 self[point] = Value.wrap(enabled)
  51
  52     def like(self, name=None, src_loc_at=0):
  53         """Create a new ``PartitionPoints`` with ``Signal``s for all values.
  54
  55         :param name: the base name for the new ``Signal``s.
  56         """
  57         if name is None:
  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}")
  62         return retval
  63
  64     def eq(self, rhs):
  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])
  70
  71     def as_mask(self, width):
  72         """Create a bit-mask from `self`.
  73
  74         Each bit in the returned mask is clear only if the partition point at
  75         the same bit-index is enabled.
  76
  77         :param width: the bit width of the resulting mask
  78         """
  79         bits = []
  80         for i in range(width):
  81             if i in self:
  82                 bits.append(~self[i])
  83             else:
  84                 bits.append(True)
  85         return Cat(*bits)
  86
  87     def get_max_partition_count(self, width):
  88         """Get the maximum number of partitions.
  89
  90         Gets the number of partitions when all partition points are enabled.
  91         """
  92         retval = 1
  93         for point in self.keys():
  94             if point < width:
  95                 retval += 1
  96         return retval
  97
  98     def fits_in_width(self, width):
  99         """Check if all partition points are smaller than `width`."""
 100         for point in self.keys():
 101             if point >= width:
 102                 return False
 103         return True
 104
 105
 106 class FullAdder(Elaboratable):
 107     """Full Adder.
 108
 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
 114     """
 115
 116     def __init__(self, width):
 117         """Create a ``FullAdder``.
 118
 119         :param width: the bit width of the input and output
 120         """
 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)
 126
 127     def elaborate(self, platform):
 128         """Elaborate this module."""
 129         m = 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))
 134         return m
 135
 136
 137 class PartitionedAdder(Elaboratable):
 138     """Partitioned Adder.
 139
 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``.
 146     """
 147
 148     def __init__(self, width, partition_points):
 149         """Create a ``PartitionedAdder``.
 150
 151         :param width: the bit width of the input and output
 152         :param partition_points: the input partition points
 153         """
 154         self.width = width
 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")
 161         expanded_width = 0
 162         for i in range(self.width):
 163             if i in self.partition_points:
 164                 expanded_width += 1
 165             expanded_width += 1
 166         self._expanded_width = expanded_width
 167         self._expanded_a = Signal(expanded_width)
 168         self._expanded_b = Signal(expanded_width)
 169         self._expanded_output = Signal(expanded_width)
 170
 171     def elaborate(self, platform):
 172         """Elaborate this module."""
 173         m = Module()
 174         expanded_index = 0
 175         # store bits in a list, use Cat later.  graphviz is much cleaner
 176         al = []
 177         bl = []
 178         ol = []
 179         ea = []
 180         eb = []
 181         eo = []
 182         # partition points are "breaks" (extra zeros) in what would otherwise
 183         # be a massive long add.
 184         for i in range(self.width):
 185             if i in self.partition_points:
 186                 # add extra bit set to 0 + 0 for enabled partition points
 187                 # and 1 + 0 for disabled partition points
 188                 ea.append(self._expanded_a[expanded_index])
 189                 al.append(~self.partition_points[i])
 190                 eb.append(self._expanded_b[expanded_index])
 191                 bl.append(C(0))
 192                 expanded_index += 1
 193             ea.append(self._expanded_a[expanded_index])
 194             al.append(self.a[i])
 195             eb.append(self._expanded_b[expanded_index])
 196             bl.append(self.b[i])
 197             eo.append(self._expanded_output[expanded_index])
 198             ol.append(self.output[i])
 199             expanded_index += 1
 200         # combine above using Cat
 201         m.d.comb += Cat(*ea).eq(Cat(*al))
 202         m.d.comb += Cat(*eb).eq(Cat(*bl))
 203         m.d.comb += Cat(*ol).eq(Cat(*eo))
 204         # use only one addition to take advantage of look-ahead carry and
 205         # special hardware on FPGAs
 206         m.d.comb += self._expanded_output.eq(
 207             self._expanded_a + self._expanded_b)
 208         return m
 209
 210
 211 FULL_ADDER_INPUT_COUNT = 3
 212
 213
 214 class AddReduce(Elaboratable):
 215     """Add list of numbers together.
 216
 217     :attribute inputs: input ``Signal``s to be summed. Modification not
 218         supported, except for by ``Signal.eq``.
 219     :attribute register_levels: List of nesting levels that should have
 220         pipeline registers.
 221     :attribute output: output sum.
 222     :attribute partition_points: the input partition points. Modification not
 223         supported, except for by ``Signal.eq``.
 224     """
 225
 226     def __init__(self, inputs, output_width, register_levels, partition_points):
 227         """Create an ``AddReduce``.
 228
 229         :param inputs: input ``Signal``s to be summed.
 230         :param output_width: bit-width of ``output``.
 231         :param register_levels: List of nesting levels that should have
 232             pipeline registers.
 233         :param partition_points: the input partition points.
 234         """
 235         self.inputs = list(inputs)
 236         self._resized_inputs = [
 237             Signal(output_width, name=f"resized_inputs[{i}]")
 238             for i in range(len(self.inputs))]
 239         self.register_levels = list(register_levels)
 240         self.output = Signal(output_width)
 241         self.partition_points = PartitionPoints(partition_points)
 242         if not self.partition_points.fits_in_width(output_width):
 243             raise ValueError("partition_points doesn't fit in output_width")
 244         self._reg_partition_points = self.partition_points.like()
 245         max_level = AddReduce.get_max_level(len(self.inputs))
 246         for level in self.register_levels:
 247             if level > max_level:
 248                 raise ValueError(
 249                     "not enough adder levels for specified register levels")
 250
 251     @staticmethod
 252     def get_max_level(input_count):
 253         """Get the maximum level.
 254
 255         All ``register_levels`` must be less than or equal to the maximum
 256         level.
 257         """
 258         retval = 0
 259         while True:
 260             groups = AddReduce.full_adder_groups(input_count)
 261             if len(groups) == 0:
 262                 return retval
 263             input_count %= FULL_ADDER_INPUT_COUNT
 264             input_count += 2 * len(groups)
 265             retval += 1
 266
 267     def next_register_levels(self):
 268         """``Iterable`` of ``register_levels`` for next recursive level."""
 269         for level in self.register_levels:
 270             if level > 0:
 271                 yield level - 1
 272
 273     @staticmethod
 274     def full_adder_groups(input_count):
 275         """Get ``inputs`` indices for which a full adder should be built."""
 276         return range(0,
 277                      input_count - FULL_ADDER_INPUT_COUNT + 1,
 278                      FULL_ADDER_INPUT_COUNT)
 279
 280     def elaborate(self, platform):
 281         """Elaborate this module."""
 282         m = Module()
 283
 284         # resize inputs to correct bit-width and optionally add in
 285         # pipeline registers
 286         resized_input_assignments = [self._resized_inputs[i].eq(self.inputs[i])
 287                                      for i in range(len(self.inputs))]
 288         if 0 in self.register_levels:
 289             m.d.sync += resized_input_assignments
 290             m.d.sync += self._reg_partition_points.eq(self.partition_points)
 291         else:
 292             m.d.comb += resized_input_assignments
 293             m.d.comb += self._reg_partition_points.eq(self.partition_points)
 294
 295         groups = AddReduce.full_adder_groups(len(self.inputs))
 296         # if there are no full adders to create, then we handle the base cases
 297         # and return, otherwise we go on to the recursive case
 298         if len(groups) == 0:
 299             if len(self.inputs) == 0:
 300                 # use 0 as the default output value
 301                 m.d.comb += self.output.eq(0)
 302             elif len(self.inputs) == 1:
 303                 # handle single input
 304                 m.d.comb += self.output.eq(self._resized_inputs[0])
 305             else:
 306                 # base case for adding 2 or more inputs, which get recursively
 307                 # reduced to 2 inputs
 308                 assert len(self.inputs) == 2
 309                 adder = PartitionedAdder(len(self.output),
 310                                          self._reg_partition_points)
 311                 m.submodules.final_adder = adder
 312                 m.d.comb += adder.a.eq(self._resized_inputs[0])
 313                 m.d.comb += adder.b.eq(self._resized_inputs[1])
 314                 m.d.comb += self.output.eq(adder.output)
 315             return m
 316         # go on to handle recursive case
 317         intermediate_terms = []
 318
 319         def add_intermediate_term(value):
 320             intermediate_term = Signal(
 321                 len(self.output),
 322                 name=f"intermediate_terms[{len(intermediate_terms)}]")
 323             intermediate_terms.append(intermediate_term)
 324             m.d.comb += intermediate_term.eq(value)
 325
 326         # store mask in intermediary (simplifies graph)
 327         part_mask = Signal(len(self.output), reset_less=True)
 328         mask = self._reg_partition_points.as_mask(len(self.output))
 329         m.d.comb += part_mask.eq(mask)
 330
 331         # create full adders for this recursive level.
 332         # this shrinks N terms to 2 * (N // 3) plus the remainder
 333         for i in groups:
 334             adder_i = FullAdder(len(self.output))
 335             setattr(m.submodules, f"adder_{i}", adder_i)
 336             m.d.comb += adder_i.in0.eq(self._resized_inputs[i])
 337             m.d.comb += adder_i.in1.eq(self._resized_inputs[i + 1])
 338             m.d.comb += adder_i.in2.eq(self._resized_inputs[i + 2])
 339             add_intermediate_term(adder_i.sum)
 340             shifted_carry = adder_i.carry << 1
 341             # mask out carry bits to prevent carries between partitions
 342             add_intermediate_term((adder_i.carry << 1) & part_mask)
 343         # handle the remaining inputs.
 344         if len(self.inputs) % FULL_ADDER_INPUT_COUNT == 1:
 345             add_intermediate_term(self._resized_inputs[-1])
 346         elif len(self.inputs) % FULL_ADDER_INPUT_COUNT == 2:
 347             # Just pass the terms to the next layer, since we wouldn't gain
 348             # anything by using a half adder since there would still be 2 terms
 349             # and just passing the terms to the next layer saves gates.
 350             add_intermediate_term(self._resized_inputs[-2])
 351             add_intermediate_term(self._resized_inputs[-1])
 352         else:
 353             assert len(self.inputs) % FULL_ADDER_INPUT_COUNT == 0
 354         # recursive invocation of ``AddReduce``
 355         next_level = AddReduce(intermediate_terms,
 356                                len(self.output),
 357                                self.next_register_levels(),
 358                                self._reg_partition_points)
 359         m.submodules.next_level = next_level
 360         m.d.comb += self.output.eq(next_level.output)
 361         return m
 362
 363
 364 OP_MUL_LOW = 0
 365 OP_MUL_SIGNED_HIGH = 1
 366 OP_MUL_SIGNED_UNSIGNED_HIGH = 2  # a is signed, b is unsigned
 367 OP_MUL_UNSIGNED_HIGH = 3
 368
 369
 370 def get_term(value, shift=0, enabled=None):
 371     if enabled is not None:
 372         value = Mux(enabled, value, 0)
 373     if shift > 0:
 374         value = Cat(Repl(C(0, 1), shift), value)
 375     else:
 376         assert shift == 0
 377     return value
 378
 379
 380 class Term(Elaboratable):
 381     def __init__(self, width, twidth, shift=0, enabled=None):
 382         self.width = width
 383         self.shift = shift
 384         self.enabled = enabled
 385         self.ti = Signal(width, reset_less=True)
 386         self.term = Signal(twidth, reset_less=True)
 387
 388     def elaborate(self, platform):
 389
 390         m = Module()
 391         m.d.comb += self.term.eq(get_term(self.ti, self.shift, self.enabled))
 392
 393         return m
 394
 395
 396 class ProductTerm(Elaboratable):
 397     def __init__(self, width, twidth, pbwid, a_index, b_index):
 398         self.a_index = a_index
 399         self.b_index = b_index
 400         shift = 8 * (self.a_index + self.b_index)
 401         self.width = width
 402         self.a = Signal(width, reset_less=True)
 403         self.b = Signal(width, reset_less=True)
 404         self.pb_en = Signal(pbwid, reset_less=True)
 405
 406         self.tl = tl = []
 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)
 412         if len(tl) > 0:
 413             term_enabled = Signal(name=name, reset_less=True)
 414         else:
 415             term_enabled = None
 416
 417         Term.__init__(self, width*2, twidth, shift, term_enabled)
 418
 419     def elaborate(self, platform):
 420
 421         m = Term.elaborate(self, platform)
 422         if self.enabled is not None:
 423             m.d.comb += self.enabled.eq(~(Cat(*self.tl).bool()))
 424         m.d.comb += self.ti.eq(self.a * self.b)
 425
 426         return m
 427
 428 class Part(Elaboratable):
 429     def __init__(self, width, n_parts, n_levels, pbwid):
 430
 431         # inputs
 432         self.a = Signal(64)
 433         self.b = Signal(64)
 434         self._a_signed = [Signal(name=f"_a_signed_{i}") for i in range(8)]
 435         self._b_signed = [Signal(name=f"_b_signed_{i}") for i in range(8)]
 436         self.pbs = Signal(pbwid, reset_less=True)
 437
 438         # outputs
 439         self.parts = [Signal(name=f"part_{i}") for i in range(n_parts)]
 440         self.delayed_parts = [
 441             [Signal(name=f"delayed_part_8_{delay}_{i}")
 442              for i in range(n_parts)]
 443                 for delay in range(n_levels)]
 444
 445         self.not_a_term = Signal(width)
 446         self.neg_lsb_a_term = Signal(width)
 447         self.not_b_term = Signal(width)
 448         self.neg_lsb_b_term = Signal(width)
 449
 450     def elaborate(self, platform):
 451         m = Module()
 452
 453         pbs, parts, delayed_parts = self.pbs, self.parts, self.delayed_parts
 454         byte_count = 8 // len(parts)
 455         for i in range(len(parts)):
 456             pbl = []
 457             pbl.append(~pbs[i * byte_count - 1])
 458             for j in range(i * byte_count, (i + 1) * byte_count - 1):
 459                 pbl.append(pbs[j])
 460             pbl.append(~pbs[(i + 1) * byte_count - 1])
 461             value = Signal(len(pbl), reset_less=True)
 462             m.d.comb += value.eq(Cat(*pbl))
 463             m.d.comb += parts[i].eq(~(value).bool())
 464             m.d.comb += delayed_parts[0][i].eq(parts[i])
 465             m.d.sync += [delayed_parts[j + 1][i].eq(delayed_parts[j][i])
 466                          for j in range(len(delayed_parts)-1)]
 467
 468         not_a_term, neg_lsb_a_term, not_b_term, neg_lsb_b_term = \
 469                 self.not_a_term, self.neg_lsb_a_term, \
 470                 self.not_b_term, self.neg_lsb_b_term
 471
 472         byte_width = 8 // len(parts)
 473         bit_width = 8 * byte_width
 474         nat, nbt, nla, nlb = [], [], [], []
 475         for i in range(len(parts)):
 476             be = parts[i] & self.a[(i + 1) * bit_width - 1] \
 477                 & self._a_signed[i * byte_width]
 478             ae = parts[i] & self.b[(i + 1) * bit_width - 1] \
 479                 & self._b_signed[i * byte_width]
 480             a_enabled = Signal(name="a_en_%d" % i, reset_less=True)
 481             b_enabled = Signal(name="b_en_%d" % i, reset_less=True)
 482             m.d.comb += a_enabled.eq(ae)
 483             m.d.comb += b_enabled.eq(be)
 484
 485             # for 8-bit values: form a * 0xFF00 by using -a * 0x100, the
 486             # negation operation is split into a bitwise not and a +1.
 487             # likewise for 16, 32, and 64-bit values.
 488             nat.append(Mux(a_enabled,
 489                     Cat(Repl(0, bit_width),
 490                         ~self.a.bit_select(bit_width * i, bit_width)),
 491                     0))
 492
 493             nla.append(Cat(Repl(0, bit_width), a_enabled,
 494                            Repl(0, bit_width-1)))
 495
 496             nbt.append(Mux(b_enabled,
 497                     Cat(Repl(0, bit_width),
 498                         ~self.b.bit_select(bit_width * i, bit_width)),
 499                     0))
 500
 501             nlb.append(Cat(Repl(0, bit_width), b_enabled,
 502                            Repl(0, bit_width-1)))
 503
 504         m.d.comb += [not_a_term.eq(Cat(*nat)),
 505                      not_b_term.eq(Cat(*nbt)),
 506                      neg_lsb_a_term.eq(Cat(*nla)),
 507                      neg_lsb_b_term.eq(Cat(*nlb)),
 508                     ]
 509
 510         return m
 511
 512
 513 class Mul8_16_32_64(Elaboratable):
 514     """Signed/Unsigned 8/16/32/64-bit partitioned integer multiplier.
 515
 516     Supports partitioning into any combination of 8, 16, 32, and 64-bit
 517     partitions on naturally-aligned boundaries. Supports the operation being
 518     set for each partition independently.
 519
 520     :attribute part_pts: the input partition points. Has a partition point at
 521         multiples of 8 in 0 < i < 64. Each partition point's associated
 522         ``Value`` is a ``Signal``. Modification not supported, except for by
 523         ``Signal.eq``.
 524     :attribute part_ops: the operation for each byte. The operation for a
 525         particular partition is selected by assigning the selected operation
 526         code to each byte in the partition. The allowed operation codes are:
 527
 528         :attribute OP_MUL_LOW: the LSB half of the product. Equivalent to
 529             RISC-V's `mul` instruction.
 530         :attribute OP_MUL_SIGNED_HIGH: the MSB half of the product where both
 531             ``a`` and ``b`` are signed. Equivalent to RISC-V's `mulh`
 532             instruction.
 533         :attribute OP_MUL_SIGNED_UNSIGNED_HIGH: the MSB half of the product
 534             where ``a`` is signed and ``b`` is unsigned. Equivalent to RISC-V's
 535             `mulhsu` instruction.
 536         :attribute OP_MUL_UNSIGNED_HIGH: the MSB half of the product where both
 537             ``a`` and ``b`` are unsigned. Equivalent to RISC-V's `mulhu`
 538             instruction.
 539     """
 540
 541     def __init__(self, register_levels= ()):
 542         self.part_pts = PartitionPoints()
 543         for i in range(8, 64, 8):
 544             self.part_pts[i] = Signal(name=f"part_pts_{i}")
 545         self.part_ops = [Signal(2, name=f"part_ops_{i}") for i in range(8)]
 546         self.a = Signal(64)
 547         self.b = Signal(64)
 548         self.output = Signal(64)
 549         self.register_levels = list(register_levels)
 550         self._intermediate_output = Signal(128)
 551         self._delayed_part_ops = [
 552             [Signal(2, name=f"_delayed_part_ops_{delay}_{i}")
 553              for i in range(8)]
 554             for delay in range(1 + len(self.register_levels))]
 555         self._output_64 = Signal(64)
 556         self._output_32 = Signal(64)
 557         self._output_16 = Signal(64)
 558         self._output_8 = Signal(64)
 559         self._a_signed = [Signal(name=f"_a_signed_{i}") for i in range(8)]
 560         self._b_signed = [Signal(name=f"_b_signed_{i}") for i in range(8)]
 561
 562     def _part_byte(self, index):
 563         if index == -1 or index == 7:
 564             return C(True, 1)
 565         assert index >= 0 and index < 8
 566         return self.part_pts[index * 8 + 8]
 567
 568     def elaborate(self, platform):
 569         m = Module()
 570
 571         # collect part-bytes
 572         pbs = Signal(8, reset_less=True)
 573         tl = []
 574         for i in range(8):
 575             pb = Signal(name="pb%d" % i, reset_less=True)
 576             m.d.comb += pb.eq(self._part_byte(i))
 577             tl.append(pb)
 578         m.d.comb += pbs.eq(Cat(*tl))
 579
 580         for i in range(len(self.part_ops)):
 581             m.d.comb += self._delayed_part_ops[0][i].eq(self.part_ops[i])
 582             m.d.sync += [self._delayed_part_ops[j + 1][i]
 583                          .eq(self._delayed_part_ops[j][i])
 584                          for j in range(len(self.register_levels))]
 585
 586         n_levels = len(self.register_levels)+1
 587         m.submodules.part_8 = part_8 = Part(128, 8, n_levels, 8)
 588         m.submodules.part_16 = part_16 = Part(128, 4, n_levels, 8)
 589         m.submodules.part_32 = part_32 = Part(128, 2, n_levels, 8)
 590         m.submodules.part_64 = part_64 = Part(128, 1, n_levels, 8)
 591         nat_l, nbt_l, nla_l, nlb_l = [], [], [], []
 592         for mod in [part_8, part_16, part_32, part_64]:
 593             m.d.comb += mod.a.eq(self.a)
 594             m.d.comb += mod.b.eq(self.b)
 595             for i in range(len(self._a_signed)):
 596                 m.d.comb += mod._a_signed[i].eq(self._a_signed[i])
 597             for i in range(len(self._b_signed)):
 598                 m.d.comb += mod._b_signed[i].eq(self._b_signed[i])
 599             m.d.comb += mod.pbs.eq(pbs)
 600             nat_l.append(mod.not_a_term)
 601             nbt_l.append(mod.not_b_term)
 602             nla_l.append(mod.neg_lsb_a_term)
 603             nlb_l.append(mod.neg_lsb_b_term)
 604
 605         terms = []
 606
 607         for a_index in range(8):
 608             for b_index in range(8):
 609                 t = ProductTerm(8, 128, 8, a_index, b_index)
 610                 setattr(m.submodules, "term_%d_%d" % (a_index, b_index), t)
 611
 612                 m.d.comb += t.a.eq(self.a.bit_select(a_index * 8, 8))
 613                 m.d.comb += t.b.eq(self.b.bit_select(b_index * 8, 8))
 614                 m.d.comb += t.pb_en.eq(pbs)
 615
 616                 terms.append(t.term)
 617
 618         for i in range(8):
 619             a_signed = self.part_ops[i] != OP_MUL_UNSIGNED_HIGH
 620             b_signed = (self.part_ops[i] == OP_MUL_LOW) \
 621                         | (self.part_ops[i] == OP_MUL_SIGNED_HIGH)
 622             m.d.comb += self._a_signed[i].eq(a_signed)
 623             m.d.comb += self._b_signed[i].eq(b_signed)
 624
 625         # it's fine to bitwise-or these together since they are never enabled
 626         # at the same time
 627         nat_l = reduce(or_, nat_l)
 628         nbt_l = reduce(or_, nbt_l)
 629         nla_l = reduce(or_, nla_l)
 630         nlb_l = reduce(or_, nlb_l)
 631         m.submodules.nat = nat = Term(128, 128)
 632         m.submodules.nla = nla = Term(128, 128)
 633         m.submodules.nbt = nbt = Term(128, 128)
 634         m.submodules.nlb = nlb = Term(128, 128)
 635         m.d.comb += nat.ti.eq(nat_l)
 636         m.d.comb += nbt.ti.eq(nbt_l)
 637         m.d.comb += nla.ti.eq(nla_l)
 638         m.d.comb += nlb.ti.eq(nlb_l)
 639         terms.append(nat.term)
 640         terms.append(nla.term)
 641         terms.append(nbt.term)
 642         terms.append(nlb.term)
 643
 644         expanded_part_pts = PartitionPoints()
 645         for i, v in self.part_pts.items():
 646             signal = Signal(name=f"expanded_part_pts_{i*2}", reset_less=True)
 647             expanded_part_pts[i * 2] = signal
 648             m.d.comb += signal.eq(v)
 649
 650         add_reduce = AddReduce(terms,
 651                                128,
 652                                self.register_levels,
 653                                expanded_part_pts)
 654         m.submodules.add_reduce = add_reduce
 655         m.d.comb += self._intermediate_output.eq(add_reduce.output)
 656         m.d.comb += self._output_64.eq(
 657             Mux(self._delayed_part_ops[-1][0] == OP_MUL_LOW,
 658                 self._intermediate_output.bit_select(0, 64),
 659                 self._intermediate_output.bit_select(64, 64)))
 660
 661         # create _output_32
 662         ol = []
 663         for i in range(2):
 664             op = Signal(32, reset_less=True, name="op32_%d" % i)
 665             m.d.comb += op.eq(
 666                 Mux(self._delayed_part_ops[-1][4 * i] == OP_MUL_LOW,
 667                     self._intermediate_output.bit_select(i * 64, 32),
 668                     self._intermediate_output.bit_select(i * 64 + 32, 32)))
 669             ol.append(op)
 670         m.d.comb += self._output_32.eq(Cat(*ol))
 671
 672         # create _output_16
 673         ol = []
 674         for i in range(4):
 675             op = Signal(16, reset_less=True, name="op16_%d" % i)
 676             m.d.comb += op.eq(
 677                 Mux(self._delayed_part_ops[-1][2 * i] == OP_MUL_LOW,
 678                     self._intermediate_output.bit_select(i * 32, 16),
 679                     self._intermediate_output.bit_select(i * 32 + 16, 16)))
 680             ol.append(op)
 681         m.d.comb += self._output_16.eq(Cat(*ol))
 682
 683         # create _output_8
 684         ol = []
 685         for i in range(8):
 686             op = Signal(8, reset_less=True, name="op8_%d" % i)
 687             m.d.comb += op.eq(
 688                 Mux(self._delayed_part_ops[-1][i] == OP_MUL_LOW,
 689                     self._intermediate_output.bit_select(i * 16, 8),
 690                     self._intermediate_output.bit_select(i * 16 + 8, 8)))
 691             ol.append(op)
 692         m.d.comb += self._output_8.eq(Cat(*ol))
 693
 694         # final output
 695         ol = []
 696         for i in range(8):
 697             op = Signal(8, reset_less=True, name="op%d" % i)
 698             m.d.comb += op.eq(
 699                 Mux(part_8.delayed_parts[-1][i]
 700                     | part_16.delayed_parts[-1][i // 2],
 701                     Mux(part_8.delayed_parts[-1][i],
 702                         self._output_8.bit_select(i * 8, 8),
 703                         self._output_16.bit_select(i * 8, 8)),
 704                     Mux(part_32.delayed_parts[-1][i // 4],
 705                         self._output_32.bit_select(i * 8, 8),
 706                         self._output_64.bit_select(i * 8, 8))))
 707             ol.append(op)
 708         m.d.comb += self.output.eq(Cat(*ol))
 709         return m
 710
 711
 712 if __name__ == "__main__":
 713     m = Mul8_16_32_64()
 714     main(m, ports=[m.a,
 715                    m.b,
 716                    m._intermediate_output,
 717                    m.output,
 718                    *m.part_ops,
 719                    *m.part_pts.values()])