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         # 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)
 174
 175     def elaborate(self, platform):
 176         """Elaborate this module."""
 177         m = Module()
 178         expanded_index = 0
 179         # store bits in a list, use Cat later.  graphviz is much cleaner
 180         al = []
 181         bl = []
 182         ol = []
 183         ea = []
 184         eb = []
 185         eo = []
 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])
 195                 bl.append(C(0))
 196                 expanded_index += 1
 197             ea.append(self._expanded_a[expanded_index])
 198             al.append(self.a[i])
 199             eb.append(self._expanded_b[expanded_index])
 200             bl.append(self.b[i])
 201             eo.append(self._expanded_output[expanded_index])
 202             ol.append(self.output[i])
 203             expanded_index += 1
 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)
 212         return m
 213
 214
 215 FULL_ADDER_INPUT_COUNT = 3
 216
 217
 218 class AddReduce(Elaboratable):
 219     """Add list of numbers together.
 220
 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
 224         pipeline registers.
 225     :attribute output: output sum.
 226     :attribute partition_points: the input partition points. Modification not
 227         supported, except for by ``Signal.eq``.
 228     """
 229
 230     def __init__(self, inputs, output_width, register_levels, partition_points):
 231         """Create an ``AddReduce``.
 232
 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
 236             pipeline registers.
 237         :param partition_points: the input partition points.
 238         """
 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:
 252                 raise ValueError(
 253                     "not enough adder levels for specified register levels")
 254
 255     @staticmethod
 256     def get_max_level(input_count):
 257         """Get the maximum level.
 258
 259         All ``register_levels`` must be less than or equal to the maximum
 260         level.
 261         """
 262         retval = 0
 263         while True:
 264             groups = AddReduce.full_adder_groups(input_count)
 265             if len(groups) == 0:
 266                 return retval
 267             input_count %= FULL_ADDER_INPUT_COUNT
 268             input_count += 2 * len(groups)
 269             retval += 1
 270
 271     def next_register_levels(self):
 272         """``Iterable`` of ``register_levels`` for next recursive level."""
 273         for level in self.register_levels:
 274             if level > 0:
 275                 yield level - 1
 276
 277     @staticmethod
 278     def full_adder_groups(input_count):
 279         """Get ``inputs`` indices for which a full adder should be built."""
 280         return range(0,
 281                      input_count - FULL_ADDER_INPUT_COUNT + 1,
 282                      FULL_ADDER_INPUT_COUNT)
 283
 284     def elaborate(self, platform):
 285         """Elaborate this module."""
 286         m = Module()
 287
 288         # resize inputs to correct bit-width and optionally add in
 289         # pipeline registers
 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)
 295         else:
 296             m.d.comb += resized_input_assignments
 297             m.d.comb += self._reg_partition_points.eq(self.partition_points)
 298
 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
 302         if len(groups) == 0:
 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])
 309             else:
 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)
 319             return m
 320         # go on to handle recursive case
 321         intermediate_terms = []
 322
 323         def add_intermediate_term(value):
 324             intermediate_term = Signal(
 325                 len(self.output),
 326                 name=f"intermediate_terms[{len(intermediate_terms)}]")
 327             intermediate_terms.append(intermediate_term)
 328             m.d.comb += intermediate_term.eq(value)
 329
 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)
 334
 335         # create full adders for this recursive level.
 336         # this shrinks N terms to 2 * (N // 3) plus the remainder
 337         for i in groups:
 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])
 356         else:
 357             assert len(self.inputs) % FULL_ADDER_INPUT_COUNT == 0
 358         # recursive invocation of ``AddReduce``
 359         next_level = AddReduce(intermediate_terms,
 360                                len(self.output),
 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)
 365         return m
 366
 367
 368 OP_MUL_LOW = 0
 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
 372
 373
 374 def get_term(value, shift=0, enabled=None):
 375     if enabled is not None:
 376         value = Mux(enabled, value, 0)
 377     if shift > 0:
 378         value = Cat(Repl(C(0, 1), shift), value)
 379     else:
 380         assert shift == 0
 381     return value
 382
 383
 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
 388         all the time.
 389     """
 390
 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)
 395         self.pwidth = width
 396         self.twidth = twidth
 397         self.width = width*2
 398         self.shift = shift
 399
 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)
 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         self.enabled = term_enabled
 417         self.term.name = "term_%d_%d" % (a_index, b_index) # rename
 418
 419     def elaborate(self, platform):
 420
 421         m = Module()
 422         if self.enabled is not None:
 423             m.d.comb += self.enabled.eq(~(Cat(*self.tl).bool()))
 424
 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
 428         pwidth = self.pwidth
 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))
 433         """
 434         #TODO: sort out width issues, get inputs a/b switched on/off.
 435         #data going into Muxes is 1/2 the required width
 436
 437         pwidth = self.pwidth
 438         width = self.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)
 450         """
 451
 452         return m
 453
 454
 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.
 459     """
 460     def __init__(self, width, twidth, pbwid, a_index, blen):
 461         self.a_index = a_index
 462         self.blen = blen
 463         self.pwidth = width
 464         self.twidth = twidth
 465         self.pbwid = pbwid
 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)]
 471
 472     def elaborate(self, platform):
 473
 474         m = Module()
 475
 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)
 480
 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)
 484
 485             m.d.comb += self.terms[b_index].eq(t.term)
 486
 487         return m
 488
 489
 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.
 493
 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*.
 497
 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.
 501
 502         the extra terms - as separate terms - are then thrown at the
 503         AddReduce alongside the multiplication part-results.
 504     """
 505     def __init__(self, width, n_parts, n_levels, pbwid):
 506
 507         # inputs
 508         self.a = Signal(64)
 509         self.b = Signal(64)
 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)
 513
 514         # outputs
 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)]
 523
 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)
 528
 529     def elaborate(self, platform):
 530         m = Module()
 531
 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)):
 535             pbl = []
 536             pbl.append(~pbs[i * byte_count - 1])
 537             for j in range(i * byte_count, (i + 1) * byte_count - 1):
 538                 pbl.append(pbs[j])
 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])
 547
 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
 551
 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)
 566
 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.
 570
 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)),
 574                            0))
 575
 576             # a: add 1 if a signed, otherwise add zero
 577             nla.append(Cat(ext, a_enabled, Repl(0, bit_wid-1)))
 578
 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)),
 582                            0))
 583
 584             # b: add 1 if b signed, otherwise add zero
 585             nlb.append(Cat(ext, b_enabled, Repl(0, bit_wid-1)))
 586
 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)),
 592                     ]
 593
 594         return m
 595
 596
 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.
 600     """
 601     def __init__(self, width, out_wid, n_parts):
 602         self.width = width
 603         self.n_parts = n_parts
 604         self.delayed_part_ops = [Signal(2, name="dpop%d" % i, reset_less=True)
 605                                      for i in range(8)]
 606         self.intermed = Signal(out_wid, reset_less=True)
 607         self.output = Signal(out_wid//2, reset_less=True)
 608
 609     def elaborate(self, platform):
 610         m = Module()
 611
 612         ol = []
 613         w = self.width
 614         sel = w // 8
 615         for i in range(self.n_parts):
 616             op = Signal(w, reset_less=True, name="op%d_%d" % (w, i))
 617             m.d.comb += op.eq(
 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)))
 621             ol.append(op)
 622         m.d.comb += self.output.eq(Cat(*ol))
 623
 624         return m
 625
 626
 627 class FinalOut(Elaboratable):
 628     """ selects the final output based on the partitioning.
 629
 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.
 633     """
 634     def __init__(self, out_wid):
 635         # inputs
 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)]
 639
 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)
 644
 645         # output
 646         self.out = Signal(out_wid, reset_less=True)
 647
 648     def elaborate(self, platform):
 649         m = Module()
 650         ol = []
 651         for i in range(8):
 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)
 658             m.d.comb += op.eq(
 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))))
 664             ol.append(op)
 665         m.d.comb += self.out.eq(Cat(*ol))
 666         return m
 667
 668
 669 class OrMod(Elaboratable):
 670     """ ORs four values together in a hierarchical tree
 671     """
 672     def __init__(self, wid):
 673         self.wid = wid
 674         self.orin = [Signal(wid, name="orin%d" % i, reset_less=True)
 675                      for i in range(4)]
 676         self.orout = Signal(wid, reset_less=True)
 677
 678     def elaborate(self, platform):
 679         m = Module()
 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)
 685
 686         return m
 687
 688
 689 class Signs(Elaboratable):
 690     """ determines whether a or b are signed numbers
 691         based on the required operation type (OP_MUL_*)
 692     """
 693
 694     def __init__(self):
 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)
 698
 699     def elaborate(self, platform):
 700
 701         m = Module()
 702
 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)
 708
 709         return m
 710
 711
 712 class Mul8_16_32_64(Elaboratable):
 713     """Signed/Unsigned 8/16/32/64-bit partitioned integer multiplier.
 714
 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.
 718
 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
 722         ``Signal.eq``.
 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:
 726
 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`
 731             instruction.
 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`
 737             instruction.
 738     """
 739
 740     def __init__(self, register_levels=()):
 741         """ register_levels: specifies the points in the cascade at which
 742             flip-flops are to be inserted.
 743         """
 744
 745         # parameter(s)
 746         self.register_levels = list(register_levels)
 747
 748         # inputs
 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)]
 753         self.a = Signal(64)
 754         self.b = Signal(64)
 755
 756         # intermediates (needed for unit tests)
 757         self._intermediate_output = Signal(128)
 758
 759         # output
 760         self.output = Signal(64)
 761
 762     def _part_byte(self, index):
 763         if index == -1 or index == 7:
 764             return C(True, 1)
 765         assert index >= 0 and index < 8
 766         return self.part_pts[index * 8 + 8]
 767
 768     def elaborate(self, platform):
 769         m = Module()
 770
 771         # collect part-bytes
 772         pbs = Signal(8, reset_less=True)
 773         tl = []
 774         for i in range(8):
 775             pb = Signal(name="pb%d" % i, reset_less=True)
 776             m.d.comb += pb.eq(self._part_byte(i))
 777             tl.append(pb)
 778         m.d.comb += pbs.eq(Cat(*tl))
 779
 780         # local variables
 781         signs = []
 782         for i in range(8):
 783             s = Signs()
 784             signs.append(s)
 785             setattr(m.submodules, "signs%d" % i, s)
 786             m.d.comb += s.part_ops.eq(self.part_ops[i])
 787
 788         delayed_part_ops = [
 789             [Signal(2, name=f"_delayed_part_ops_{delay}_{i}")
 790              for i in range(8)]
 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))]
 796
 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)
 814
 815         terms = []
 816
 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)
 820
 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)
 824
 825             for term in t.terms:
 826                 terms.append(term)
 827
 828         # it's fine to bitwise-or data together since they are never enabled
 829         # at the same time
 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),
 835                              (nbt_l, nbt_or),
 836                              (nla_l, nla_or),
 837                              (nlb_l, nlb_or)]:
 838             for i in range(len(l)):
 839                 m.d.comb += mod.orin[i].eq(l[i])
 840             terms.append(mod.orout)
 841
 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)
 847
 848         add_reduce = AddReduce(terms,
 849                                128,
 850                                self.register_levels,
 851                                expanded_part_pts)
 852         m.submodules.add_reduce = add_reduce
 853         m.d.comb += self._intermediate_output.eq(add_reduce.output)
 854         # create _output_64
 855         m.submodules.io64 = io64 = IntermediateOut(64, 128, 1)
 856         m.d.comb += io64.intermed.eq(self._intermediate_output)
 857         for i in range(8):
 858             m.d.comb += io64.delayed_part_ops[i].eq(delayed_part_ops[-1][i])
 859
 860         # create _output_32
 861         m.submodules.io32 = io32 = IntermediateOut(32, 128, 2)
 862         m.d.comb += io32.intermed.eq(self._intermediate_output)
 863         for i in range(8):
 864             m.d.comb += io32.delayed_part_ops[i].eq(delayed_part_ops[-1][i])
 865
 866         # create _output_16
 867         m.submodules.io16 = io16 = IntermediateOut(16, 128, 4)
 868         m.d.comb += io16.intermed.eq(self._intermediate_output)
 869         for i in range(8):
 870             m.d.comb += io16.delayed_part_ops[i].eq(delayed_part_ops[-1][i])
 871
 872         # create _output_8
 873         m.submodules.io8 = io8 = IntermediateOut(8, 128, 8)
 874         m.d.comb += io8.intermed.eq(self._intermediate_output)
 875         for i in range(8):
 876             m.d.comb += io8.delayed_part_ops[i].eq(delayed_part_ops[-1][i])
 877
 878         # final output
 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)
 891
 892         return m
 893
 894
 895 if __name__ == "__main__":
 896     m = Mul8_16_32_64()
 897     main(m, ports=[m.a,
 898                    m.b,
 899                    m._intermediate_output,
 900                    m.output,
 901                    *m.part_ops,
 902                    *m.part_pts.values()])