src/nmutil/ripple.py

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