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     def __init__(self, width, start_lsb=True):
  34         self.width = width
  35         self.start_lsb = start_lsb
  36         self.results_in = Signal(width, reset_less=True)
  37         self.gates = Signal(width-1, reset_less=True)
  38         self.output = Signal(width, reset_less=True)
  39
  40     def elaborate(self, platform):
  41         m = Module()
  42         comb = m.d.comb
  43         width = self.width
  44
  45         results_in = list(self.results_in)
  46         if not self.start_lsb: results_in = reversed(results_in)
  47         l = [results_in[0]]
  48
  49         for i in range(width-1):
  50             l.append(Mux(self.gates[i], results_in[i+1], self.output[i]))
  51
  52         if not self.start_lsb: l = reversed(l)
  53         comb += self.output.eq(Cat(*l))
  54
  55         return m
  56
  57
  58 class RippleLSB(Ripple):
  59     """RippleLSB
  60
  61     based on a partition mask, the LSB is "rippled" (duplicated)
  62     up to the beginning of the next partition.
  63     """
  64     def __init__(self, width):
  65         Ripple.__init__(self, width, start_lsb=True)
  66
  67
  68 class RippleMSB(Ripple):
  69     """RippleMSB
  70
  71     based on a partition mask, the MSB is "rippled" (duplicated)
  72     down to the beginning of the next partition.
  73     """
  74     def __init__(self, width):
  75         Ripple.__init__(self, width, start_lsb=True)
  76
  77
  78 class MoveMSBDown(Elaboratable):
  79     """MoveMSBDown
  80
  81     based on a partition mask, moves the MSB down to the LSB position.
  82     only the MSB is relevant, other bits are ignored.  works by first
  83     rippling the MSB across the entire partition (TODO: split that out
  84     into its own useful module), then ANDs the (new) LSB with the
  85     partition mask to isolate it.
  86     """
  87     def __init__(self, width):
  88         self.width = width
  89         self.results_in = Signal(width, reset_less=True)
  90         self.gates = Signal(width-1, reset_less=True)
  91         self.output = Signal(width, reset_less=True)
  92
  93     def elaborate(self, platform):
  94         m = Module()
  95         comb = m.d.comb
  96         width = self.width
  97         intermed = Signal(width, reset_less=True)
  98
  99         # first propagate MSB down until the nearest partition gate
 100         comb += intermed[-1].eq(self.results_in[-1]) # start at MSB
 101         for i in range(width-2, -1, -1):
 102             cur = Mux(self.gates[i], self.results_in[i], intermed[i+1])
 103             comb += intermed[i].eq(cur)
 104
 105         # now only select those bits where the mask starts
 106         out = [intermed[0]] # LSB of first part always set
 107         for i in range(width-1): # length of partition gates
 108             out.append(self.gates[i] & intermed[i+1])
 109         comb += self.output.eq(Cat(*out))
 110
 111         return m
 112
 113
 114 if __name__ == "__main__":
 115     # python3 ieee754/part_cmp/ripple.py generate -t il > ripple.il
 116     # then check with yosys "read_ilang ripple.il; show top"
 117     alu = MoveMSBDown(width=4)
 118     main(alu, ports=[alu.results_in, alu.gates, alu.output])
 119