src/nmutil/ripple.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 """
   3     This work is funded through NLnet under Grant 2019-02-012
   4
   5     License: LGPLv3+
   6
   7 """
   8
   9 # need to ripple the starting LSB of each partition up through the
  10 # rest of the partition.  a Mux on the partition gate therefore selects
  11 # either the current "thing" being propagated, or, if the gate is set open,
  12 # will select the current bit from the input.
  13 #
  14 # this is actually a useful function, it's one of "set before first" or
  15 # "set after first" from vector predication processing.
  16
  17 from nmigen import Signal, Module, Elaboratable, Mux, Cat
  18 from nmigen.cli import main
  19
  20
  21 class Ripple(Elaboratable):
  22     """Ripple
  23
  24     starting from certain bits (marked by "gates") that bit is "rippled"
  25     up to the point where a gate bit is no longer set.  ripple direction can
  26     be set by start_lsb.
  27
  28     if start_lsb=True:
  29         gates      =>  1 1 0 0 0 1 1
  30         (ripples)     <<<< xxx <<<<<
  31         results_in => 0 0 1 0 1 0 0 1
  32         output     => 1 1 1 0 0 1 1 1
  33     """
  34
  35     def __init__(self, width, start_lsb=True):
  36         self.width = width
  37         self.start_lsb = start_lsb
  38         self.results_in = Signal(width, reset_less=True)
  39         self.gates = Signal(width-1, reset_less=True)
  40         self.output = Signal(width, reset_less=True)
  41
  42     def elaborate(self, platform):
  43         m = Module()
  44         comb = m.d.comb
  45         width = self.width
  46
  47         results_in = list(self.results_in)
  48         if not self.start_lsb:
  49             results_in = reversed(results_in)
  50         l = [results_in[0]]
  51
  52         for i in range(width-1):
  53             l.append(Mux(self.gates[i], results_in[i+1], self.output[i]))
  54
  55         if not self.start_lsb:
  56             l = reversed(l)
  57         comb += self.output.eq(Cat(*l))
  58
  59         return m
  60
  61
  62 class RippleLSB(Ripple):
  63     """RippleLSB
  64
  65     based on a partition mask, the LSB is "rippled" (duplicated)
  66     up to the beginning of the next partition.
  67     """
  68
  69     def __init__(self, width):
  70         Ripple.__init__(self, width, start_lsb=True)
  71
  72
  73 class RippleMSB(Ripple):
  74     """RippleMSB
  75
  76     based on a partition mask, the MSB is "rippled" (duplicated)
  77     down to the beginning of the next partition.
  78     """
  79
  80     def __init__(self, width):
  81         Ripple.__init__(self, width, start_lsb=False)
  82
  83
  84 class MoveMSBDown(Elaboratable):
  85     """MoveMSBDown
  86
  87     based on a partition mask, moves the MSB down to the LSB position.
  88     only the MSB is relevant, other bits are ignored.  works by first
  89     rippling the MSB across the entire partition (TODO: split that out
  90     into its own useful module), then ANDs the (new) LSB with the
  91     partition mask to isolate it.
  92     """
  93
  94     def __init__(self, width):
  95         self.width = width
  96         self.results_in = Signal(width, reset_less=True)
  97         self.gates = Signal(width-1, reset_less=True)
  98         self.output = Signal(width, reset_less=True)
  99
 100     def elaborate(self, platform):
 101         m = Module()
 102         comb = m.d.comb
 103         width = self.width
 104         intermed = Signal(width, reset_less=True)
 105
 106         # first propagate MSB down until the nearest partition gate
 107         comb += intermed[-1].eq(self.results_in[-1])  # start at MSB
 108         for i in range(width-2, -1, -1):
 109             cur = Mux(self.gates[i], self.results_in[i], intermed[i+1])
 110             comb += intermed[i].eq(cur)
 111
 112         # now only select those bits where the mask starts
 113         out = [intermed[0]]  # LSB of first part always set
 114         for i in range(width-1):  # length of partition gates
 115             out.append(self.gates[i] & intermed[i+1])
 116         comb += self.output.eq(Cat(*out))
 117
 118         return m
 119
 120
 121 if __name__ == "__main__":
 122     # python3 ieee754/part_cmp/ripple.py generate -t il > ripple.il
 123     # then check with yosys "read_ilang ripple.il; show top"
 124     alu = MoveMSBDown(width=4)
 125     main(alu, ports=[alu.results_in, alu.gates, alu.output])