Implement PLA (#1912)

* implement pla

* implement test for pla

* implement inverter matrix of PLA generator

* fix for review.

Co-authored-by: Boyang Han <yqszxx@gmail.com>

2 files changed, 199 insertions, 0 deletions

diff --git a/src/main/scala/chisel3/util/pla.scala b/src/main/scala/chisel3/util/pla.scala
new file mode 100644
index 00000000..bb2b7996
--- /dev/null
+++ b/src/main/scala/chisel3/util/pla.scala
@@ -0,0 +1,119 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util
+
+import chisel3._
+
+object pla {
+
+  /** Construct a [[https://en.wikipedia.org/wiki/Programmable_logic_array]] from specified table.
+    *
+    * Each position in the input matrix corresponds to an input variable where
+    * `0` implies the corresponding input literal appears complemented in the product term.
+    * `1` implies the input literal appears uncomplemented in the product term
+    * `?` implies the input literal does not appear in the product term.
+    *
+    * For each output
+    * a `1` means this product term makes the function value to `1`
+    * and a `0` or `?` means this product term make the function value to `0`
+    *
+    * @param table A [[Seq]] of inputs -> outputs mapping
+    * @param invert A [[BitPat]] specify which bit of the output should be inverted. `1` means the correspond position
+    *               of the output should be inverted in the PLA, a `0` or a `?` means direct output from the OR matrix.
+    * @return the (input, output) [[Wire]] of [[UInt]] of the constructed pla.
+    * {{{
+    *   // A 1-of-8 decoder (like the 74xx138) can be constructed as follow
+    *   val (inputs, outputs) = pla(Seq(
+    *     (BitPat("b000"), BitPat("b00000001")),
+    *     (BitPat("b001"), BitPat("b00000010")),
+    *     (BitPat("b010"), BitPat("b00000100")),
+    *     (BitPat("b011"), BitPat("b00001000")),
+    *     (BitPat("b100"), BitPat("b00010000")),
+    *     (BitPat("b101"), BitPat("b00100000")),
+    *     (BitPat("b110"), BitPat("b01000000")),
+    *     (BitPat("b111"), BitPat("b10000000")),
+    *   ))
+    * }}}
+    */
+  def apply(table: Seq[(BitPat, BitPat)], invert: BitPat = BitPat("b0")): (UInt, UInt) = {
+    require(table.nonEmpty, "pla table must not be empty")
+
+    val (inputTerms, outputTerms) = table.unzip
+    require(
+      inputTerms.map(_.getWidth).distinct.size == 1,
+      "all `BitPat`s in the input part of specified PLA table must have the same width"
+    )
+    require(
+      outputTerms.map(_.getWidth).distinct.size == 1,
+      "all `BitPat`s in the output part of specified PLA table must have the same width"
+    )
+
+    // now all inputs / outputs have the same width
+    val numberOfInputs = inputTerms.head.getWidth
+    val numberOfOutputs = outputTerms.head.getWidth
+
+    val inverterMask = invert.value & invert.mask
+    if (inverterMask.bitCount != 0)
+      require(invert.getWidth == numberOfOutputs,
+        "non-zero inverter mask must have the same width as the output part of specified PLA table"
+      )
+
+    // input wires of the generated PLA
+    val inputs = Wire(UInt(numberOfInputs.W))
+    val invInputs = ~inputs
+
+    // output wires of the generated PLA
+    val outputs = Wire(UInt(numberOfOutputs.W))
+
+    // the AND matrix
+    // use `term -> AND line` map to reuse AND matrix output lines
+    val andMatrixOutputs: Map[String, Bool] = inputTerms.map { t =>
+      t.toString -> Cat(
+        Seq
+          .tabulate(numberOfInputs) { i =>
+            if (t.mask.testBit(i)) {
+              Some(
+                if (t.value.testBit(i)) inputs(i)
+                else invInputs(i)
+              )
+            } else {
+              None
+            }
+          }
+          .flatten
+      ).andR()
+    }.toMap
+
+    // the OR matrix
+    val orMatrixOutputs: UInt = Cat(
+        Seq
+          .tabulate(numberOfOutputs) { i =>
+            val andMatrixLines = table
+              // OR matrix composed by input terms which makes this output bit a `1`
+              .filter {
+                case (_, or) => or.mask.testBit(i) && or.value.testBit(i)
+              }.map {
+                case (inputTerm, _) =>
+                  andMatrixOutputs(inputTerm.toString)
+              }
+            if (andMatrixLines.isEmpty) false.B
+            else Cat(andMatrixLines).orR()
+          }
+          .reverse
+      )
+
+    // the INV matrix, useful for decoders
+    val invMatrixOutputs: UInt = Cat(
+      Seq
+        .tabulate(numberOfOutputs) { i =>
+          if (inverterMask.testBit(i)) ~orMatrixOutputs(i)
+          else                          orMatrixOutputs(i)
+        }
+        .reverse
+    )
+
+    outputs := invMatrixOutputs
+
+    (inputs, outputs)
+  }
+}
diff --git a/src/test/scala/chiselTests/util/experimental/PlaSpec.scala b/src/test/scala/chiselTests/util/experimental/PlaSpec.scala
new file mode 100644
index 00000000..45ac012e
--- /dev/null
+++ b/src/test/scala/chiselTests/util/experimental/PlaSpec.scala
@@ -0,0 +1,80 @@
+package chiselTests.util.experimental
+
+import chisel3._
+import chisel3.stage.PrintFullStackTraceAnnotation
+import chisel3.testers.BasicTester
+import chisel3.util.{BitPat, pla}
+import chiselTests.ChiselFlatSpec
+
+class PlaSpec extends ChiselFlatSpec {
+  "A 1-of-8 decoder (eg. 74xx138 without enables)" should "be generated correctly" in {
+    assertTesterPasses(new BasicTester {
+      val table = Seq(
+        (BitPat("b000"), BitPat("b00000001")),
+        (BitPat("b001"), BitPat("b00000010")),
+        (BitPat("b010"), BitPat("b00000100")),
+        (BitPat("b011"), BitPat("b00001000")),
+        (BitPat("b100"), BitPat("b00010000")),
+        (BitPat("b101"), BitPat("b00100000")),
+        (BitPat("b110"), BitPat("b01000000")),
+        (BitPat("b111"), BitPat("b10000000")),
+      )
+      table.foreach { case (i, o) =>
+        val (plaIn, plaOut) = pla(table)
+        plaIn := WireDefault(i.value.U(3.W))
+        chisel3.assert(plaOut === o.value.U(8.W), "Input " + i.toString + " produced incorrect output BitPat(%b)", plaOut)
+      }
+      stop()
+    })
+  }
+
+  "An active-low 1-of-8 decoder (eg. inverted 74xx138 without enables)" should "be generated correctly" in {
+    assertTesterPasses(new BasicTester {
+      val table = Seq(
+        (BitPat("b000"), BitPat("b00000001")),
+        (BitPat("b001"), BitPat("b00000010")),
+        (BitPat("b010"), BitPat("b00000100")),
+        (BitPat("b011"), BitPat("b00001000")),
+        (BitPat("b100"), BitPat("b00010000")),
+        (BitPat("b101"), BitPat("b00100000")),
+        (BitPat("b110"), BitPat("b01000000")),
+        (BitPat("b111"), BitPat("b10000000")),
+      )
+      table.foreach { case (i, o) =>
+        val (plaIn, plaOut) = pla(table, BitPat("b11111111"))
+        plaIn := WireDefault(i.value.U(3.W))
+        chisel3.assert(plaOut === ~o.value.U(8.W), "Input " + i.toString + " produced incorrect output BitPat(%b)", plaOut)
+      }
+      stop()
+    })
+  }
+
+  "A simple PLA" should "be generated correctly" in {
+    assertTesterPasses(new BasicTester {
+      val table = Seq(
+        (BitPat("b0000"), BitPat("b1")),
+        (BitPat("b0001"), BitPat("b1")),
+        (BitPat("b0010"), BitPat("b0")),
+        (BitPat("b0011"), BitPat("b1")),
+        (BitPat("b0100"), BitPat("b1")),
+        (BitPat("b0101"), BitPat("b0")),
+        (BitPat("b0110"), BitPat("b0")),
+        (BitPat("b0111"), BitPat("b0")),
+        (BitPat("b1000"), BitPat("b0")),
+        (BitPat("b1001"), BitPat("b0")),
+        (BitPat("b1010"), BitPat("b1")),
+        (BitPat("b1011"), BitPat("b0")),
+        (BitPat("b1100"), BitPat("b0")),
+        (BitPat("b1101"), BitPat("b1")),
+        (BitPat("b1110"), BitPat("b1")),
+        (BitPat("b1111"), BitPat("b1")),
+      )
+      table.foreach { case (i, o) =>
+        val (plaIn, plaOut) = pla(table)
+        plaIn := WireDefault(i.value.U(4.W))
+        chisel3.assert(plaOut === o.value.U(1.W), "Input " + i.toString + " produced incorrect output BitPat(%b)", plaOut)
+      }
+      stop()
+    })
+  }
+}