From 9b2a6304989519a3edce217b1f55432095e9cac9 Mon Sep 17 00:00:00 2001
From: Luke Kenneth Casson Leighton <lkcl@lkcl.net>
Date: Tue, 17 Mar 2020 17:57:48 +0000
Subject: [PATCH] create MultiPriorityPicker which can mutually-exclusively
 select M outputs from Mx N-way inputs to be used for example to ensure that M
 "things" seeking access to M "other things" do not conflict: that only one
 "thing" at a time gets access to the other "things"

---
 src/nmutil/latch.py  | 19 +++++++++----
 src/nmutil/picker.py | 66 +++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 78 insertions(+), 7 deletions(-)

diff --git a/src/nmutil/latch.py b/src/nmutil/latch.py
index 2086fe5..6bf6fd9 100644
--- a/src/nmutil/latch.py
+++ b/src/nmutil/latch.py
@@ -29,16 +29,23 @@ def latchregister(m, incoming, outgoing, settrue, name=None):
     with m.Else():
         m.d.comb += outgoing.eq(reg) # return input (combinatorial)
 
+def mkname(prefix, suffix):
+    if suffix is None:
+        return prefix
+    return "%s_%s" % (prefix, suffix)
 
 class SRLatch(Elaboratable):
-    def __init__(self, sync=True, llen=1):
+    def __init__(self, sync=True, llen=1, name=None):
         self.sync = sync
         self.llen = llen
-        self.s = Signal(llen, reset=0)
-        self.r = Signal(llen, reset=(1<<llen)-1) # defaults to off
-        self.q = Signal(llen, reset_less=True)
-        self.qn = Signal(llen, reset_less=True)
-        self.qlq = Signal(llen, reset_less=True)
+        s_n, r_n = mkname("s", name), mkname("r", name)
+        q_n, qn_n = mkname("q", name), mkname("qn", name)
+        qlq_n = mkname("qlq", name)
+        self.s = Signal(llen, name=s_n, reset=0)
+        self.r = Signal(llen, name=r_n, reset=(1<<llen)-1) # defaults to off
+        self.q = Signal(llen, name=q_n, reset_less=True)
+        self.qn = Signal(llen, name=qn_n, reset_less=True)
+        self.qlq = Signal(llen, name=qlq_n, reset_less=True)
 
     def elaborate(self, platform):
         m = Module()
diff --git a/src/nmutil/picker.py b/src/nmutil/picker.py
index d47f785..844e7b0 100644
--- a/src/nmutil/picker.py
+++ b/src/nmutil/picker.py
@@ -1,10 +1,12 @@
 """ Priority Picker: optimised back-to-back PriorityEncoder and Decoder
+    and MultiPriorityPicker: cascading mutually-exclusive pickers
 
     The input is N bits, the output is N bits wide and only one is
     enabled.
 """
 
-from nmigen import Module, Signal, Cat, Elaboratable
+from nmigen import Module, Signal, Cat, Elaboratable, Array, Const
+from nmigen.cli import verilog, rtlil
 
 class PriorityPicker(Elaboratable):
     """ implements a priority-picker.  input: N bits, output: N bits
@@ -40,3 +42,65 @@ class PriorityPicker(Elaboratable):
 
     def ports(self):
         return list(self)
+
+
+class MultiPriorityPicker(Elaboratable):
+    """ implements a multi-input priority picker
+        Mx inputs of N bits, Mx outputs of N bits, only one is set
+
+        Each picker masks out the one below it, such that the first
+        gets top priority, the second cannot have the same bit that
+        the first has set, and so on.  To do this, a "mask" accumulates
+        the output from the chain, masking the input to the next chain.
+    """
+    def __init__(self, wid, levels):
+        self.levels = levels
+        self.wid = wid
+
+        self.i = [] # store the array of picker inputs
+        self.o = [] # store the array of picker outputs
+
+        for j in range(self.levels):
+            i = Signal(self.wid, name="i_%d" % j, reset_less=True)
+            o = Signal(self.wid, name="o_%d" % j, reset_less=True)
+            self.i.append(i)
+            self.o.append(o)
+        self.i = Array(self.i)
+        self.o = Array(self.o)
+
+    def elaborate(self, platform):
+        m = Module()
+        comb = m.d.comb
+
+        prev_pp = None
+        p_mask = None
+        for j in range(self.levels):
+            o, i = self.o[j], self.i[j]
+            pp = PriorityPicker(self.wid)
+            setattr(m.submodules, "pp%d" % j, pp)
+            comb += o.eq(pp.o)
+            if prev_pp is None:
+                comb += pp.i.eq(i)
+                p_mask = Const(0, self.wid)
+            else:
+                mask = Signal(self.wid, name="m_%d" % j, reset_less=True)
+                comb += mask.eq(prev_pp.o | p_mask) # accumulate output bits
+                comb += pp.i.eq(i & ~mask)          # mask out input
+                p_mask = mask
+            prev_pp = pp
+
+        return m
+
+    def __iter__(self):
+        yield from self.i
+        yield from self.o
+
+    def ports(self):
+        return list(self)
+
+
+if __name__ == '__main__':
+    dut = MultiPriorityPicker(5, 4)
+    vl = rtlil.convert(dut, ports=dut.ports())
+    with open("test_multi_picker.il", "w") as f:
+        f.write(vl)
-- 
2.30.2