Merge branch 'master' into 3.5-release

4 files changed, 82 insertions, 34 deletions

diff --git a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
index 1d725875..4dcea99e 100644
--- a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
@@ -7,11 +7,21 @@ import logger.LazyLogging
 
 case object EspressoNotFoundException extends Exception
 
+/** A [[Minimizer]] implementation to use espresso to minimize the [[TruthTable]].
+  *
+  * espresso uses heuristic algorithm providing a sub-optimized) result.
+  * For implementation details, please refer to:
+  * [[https://www.springerprofessional.de/en/logic-minimization-algorithms-for-vlsi-synthesis/13780088]]
+  *
+  * a espresso executable should be downloaded from [[https://github.com/chipsalliance/espresso]]
+  *
+  * If user want to user the this [[Minimizer]], a espresso executable should be added to system PATH environment.
+  */
 object EspressoMinimizer extends Minimizer with LazyLogging {
   def minimize(table: TruthTable): TruthTable =
     TruthTable.merge(TruthTable.split(table).map{case (table, indexes) => (espresso(table), indexes)})
 
-  def espresso(table: TruthTable): TruthTable = {
+  private def espresso(table: TruthTable): TruthTable = {
     def writeTable(table: TruthTable): String = {
       def invert(string: String) = string
         .replace('0', 't')
@@ -45,7 +55,7 @@ object EspressoMinimizer extends Minimizer with LazyLogging {
          |""".stripMargin ++ (if (defaultType == '1') invertRawTable else rawTable)
     }
 
-    def readTable(espressoTable: String): Map[BitPat, BitPat] = {
+    def readTable(espressoTable: String) = {
       def bitPat(espresso: String): BitPat = BitPat("b" + espresso.replace('-', '?'))
 
       espressoTable
@@ -53,7 +63,6 @@ object EspressoMinimizer extends Minimizer with LazyLogging {
         .filterNot(_.startsWith("."))
         .map(_.split(' '))
         .map(row => bitPat(row(0)) -> bitPat(row(1)))
-        .toMap
     }
 
     val input = writeTable(table)
diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
index c1533f44..59120221 100644
--- a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -8,6 +8,15 @@ import scala.annotation.tailrec
 import scala.math.Ordered.orderingToOrdered
 import scala.language.implicitConversions
 
+/** A [[Minimizer]] implementation to use Quine-Mccluskey algorithm to minimize the [[TruthTable]].
+  *
+  * This algorithm can always find the best solution, but is a NP-Complete algorithm,
+  * which means, for large-scale [[TruthTable]] minimization task, it will be really slow,
+  * and might run out of memory of JVM stack.
+  *
+  * In this situation, users should consider switch to [[EspressoMinimizer]],
+  * which uses heuristic algorithm providing a sub-optimized result.
+  */
 object QMCMinimizer extends Minimizer {
   private implicit def toImplicant(x: BitPat): Implicant = new Implicant(x)
 
@@ -225,11 +234,11 @@ object QMCMinimizer extends Minimizer {
       val outputBp = BitPat("b" + "?" * (m - i - 1) + "1" + "?" * i)
 
       // Minterms, implicants that makes the output to be 1
-      val mint: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && t.value.testBit(i) }.keys.map(toImplicant).toSeq
+      val mint: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && t.value.testBit(i) }.map(_._1).map(toImplicant)
       // Maxterms, implicants that makes the output to be 0
-      val maxt: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && !t.value.testBit(i) }.keys.map(toImplicant).toSeq
+      val maxt: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && !t.value.testBit(i) }.map(_._1).map(toImplicant)
       // Don't cares, implicants that can produce either 0 or 1 as output
-      val dc: Seq[Implicant] = table.table.filter { case (_, t) => !t.mask.testBit(i) }.keys.map(toImplicant).toSeq
+      val dc: Seq[Implicant] = table.table.filter { case (_, t) => !t.mask.testBit(i) }.map(_._1).map(toImplicant)
 
       val (implicants, defaultToDc) = table.default match {
         case x if x.mask.testBit(i) && !x.value.testBit(i) => // default to 0
@@ -282,7 +291,7 @@ object QMCMinimizer extends Minimizer {
       (essentialPrimeImplicants ++ getCover(nonessentialPrimeImplicants, uncoveredImplicants)).map(a => (a.bp, outputBp))
     })
 
-    minimized.tail.foldLeft(table.copy(table = Map(minimized.head))) { case (tb, t) =>
+    minimized.tail.foldLeft(table.copy(table = Seq(minimized.head))) { case (tb, t) =>
       if (tb.table.exists(x => x._1 == t._1)) {
         tb.copy(table = tb.table.map { case (k, v) =>
           if (k == t._1) {
@@ -291,7 +300,7 @@ object QMCMinimizer extends Minimizer {
           } else (k, v)
         })
       } else {
-        tb.copy(table = tb.table + t)
+        tb.copy(table = tb.table :+ t)
       }
     }
   }
diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index 683de16b..322466f9 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -4,8 +4,7 @@ package chisel3.util.experimental.decode
 
 import chisel3.util.BitPat
 
-final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
-
+sealed class TruthTable private (val table: Seq[(BitPat, BitPat)], val default: BitPat, val sort: Boolean) {
   def inputWidth = table.head._1.getWidth
 
   def outputWidth = table.head._2.getWidth
@@ -14,10 +13,10 @@ final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
     def writeRow(map: (BitPat, BitPat)): String =
       s"${map._1.rawString}->${map._2.rawString}"
 
-    (table.map(writeRow) ++ Seq(s"${" "*(inputWidth + 2)}${default.rawString}")).toSeq.sorted.mkString("\n")
+    (table.map(writeRow) ++ Seq(s"${" "*(inputWidth + 2)}${default.rawString}")).mkString("\n")
   }
 
-  def copy(table: Map[BitPat, BitPat] = this.table, default: BitPat = this.default) = new TruthTable(table, default)
+  def copy(table: Seq[(BitPat, BitPat)] = this.table, default: BitPat = this.default, sort: Boolean = this.sort) = TruthTable(table, default, sort)
 
   override def equals(y: Any): Boolean = {
     y match {
@@ -28,25 +27,12 @@ final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
 }
 
 object TruthTable {
-  /** Parse TruthTable from its string representation. */
-  def apply(tableString: String): TruthTable = {
-    TruthTable(
-      tableString
-        .split("\n")
-        .filter(_.contains("->"))
-        .map(_.split("->").map(str => BitPat(s"b$str")))
-        .map(bps => bps(0) -> bps(1))
-        .toSeq,
-      BitPat(s"b${tableString.split("\n").filterNot(_.contains("->")).head.replace(" ", "")}")
-    )
-  }
-
   /** Convert a table and default output into a [[TruthTable]]. */
-  def apply(table: Iterable[(BitPat, BitPat)], default: BitPat): TruthTable = {
+  def apply(table: Iterable[(BitPat, BitPat)], default: BitPat, sort: Boolean = true): TruthTable = {
     require(table.map(_._1.getWidth).toSet.size == 1, "input width not equal.")
     require(table.map(_._2.getWidth).toSet.size == 1, "output width not equal.")
     val outputWidth = table.map(_._2.getWidth).head
-    new TruthTable(table.toSeq.groupBy(_._1.toString).map { case (key, values) =>
+    val mergedTable = table.groupBy(_._1.toString).map { case (key, values) =>
       // merge same input inputs.
       values.head._1 -> BitPat(s"b${
         Seq.tabulate(outputWidth) { i =>
@@ -59,9 +45,23 @@ object TruthTable {
           outputSet.headOption.getOrElse('?')
         }.mkString
       }")
-    }, default)
+    }.toSeq
+    import BitPat.bitPatOrder
+    new TruthTable(if(sort) mergedTable.sorted else mergedTable, default, sort)
   }
 
+  /** Parse TruthTable from its string representation. */
+  def fromString(tableString: String): TruthTable = {
+    TruthTable(
+      tableString
+        .split("\n")
+        .filter(_.contains("->"))
+        .map(_.split("->").map(str => BitPat(s"b$str")))
+        .map(bps => bps(0) -> bps(1))
+        .toSeq,
+      BitPat(s"b${tableString.split("\n").filterNot(_.contains("->")).head.replace(" ", "")}")
+    )
+  }
 
   /** consume 1 table, split it into up to 3 tables with the same default bits.
     *
@@ -99,18 +99,17 @@ object TruthTable {
     tables: Seq[(TruthTable, Seq[Int])]
   ): TruthTable = {
     def reIndex(bitPat: BitPat, table: TruthTable, indexes: Seq[Int]): Seq[(Char, Int)] =
-      (table.table.map(a => a._1.toString -> a._2).getOrElse(bitPat.toString, BitPat.dontCare(indexes.size))).rawString.zip(indexes)
+      table.table.map(a => a._1.toString -> a._2).collectFirst{ case (k, v) if k == bitPat.toString => v}.getOrElse(BitPat.dontCare(indexes.size)).rawString.zip(indexes)
     def bitPat(indexedChar: Seq[(Char, Int)]) = BitPat(s"b${indexedChar
       .sortBy(_._2)
       .map(_._1)
       .mkString}")
     TruthTable(
       tables
-        .flatMap(_._1.table.keys)
+        .flatMap(_._1.table.map(_._1))
         .map { key =>
           key -> bitPat(tables.flatMap { case (table, indexes) => reIndex(key, table, indexes) })
-        }
-        .toMap,
+        },
       bitPat(tables.flatMap { case (table, indexes) => table.default.rawString.zip(indexes) })
     )
   }
diff --git a/src/main/scala/chisel3/util/experimental/decode/decoder.scala b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
index 42e374d1..e0bf83b2 100644
--- a/src/main/scala/chisel3/util/experimental/decode/decoder.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -5,7 +5,7 @@ package chisel3.util.experimental.decode
 import chisel3._
 import chisel3.experimental.{ChiselAnnotation, annotate}
 import chisel3.util.{BitPat, pla}
-import chisel3.util.experimental.getAnnotations
+import chisel3.util.experimental.{BitSet, getAnnotations}
 import firrtl.annotations.Annotation
 import logger.LazyLogging
 
@@ -19,7 +19,7 @@ object decoder extends LazyLogging {
     */
   def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable): UInt = {
     val minimizedTable = getAnnotations().collect {
-      case DecodeTableAnnotation(_, in, out) => TruthTable(in) -> TruthTable(out)
+      case DecodeTableAnnotation(_, in, out) => TruthTable.fromString(in) -> TruthTable.fromString(out)
     }.toMap.getOrElse(truthTable, minimizer.minimize(truthTable))
     if (minimizedTable.table.isEmpty) {
       val outputs = Wire(UInt(minimizedTable.default.getWidth.W))
@@ -80,4 +80,35 @@ object decoder extends LazyLogging {
         qmcFallBack(input, truthTable)
     }
   }
+
+
+  /** Generate a decoder circuit that matches the input to each bitSet.
+    *
+    * The resulting circuit functions like the following but is optimized with a logic minifier.
+    * {{{
+    *   when(input === bitSets(0)) { output := b000001 }
+    *   .elsewhen (input === bitSets(1)) { output := b000010 }
+    *   ....
+    *   .otherwise { if (errorBit) output := b100000 else output := DontCare }
+    * }}}
+    *
+    * @param input input to the decoder circuit, width should be equal to bitSets.width
+    * @param bitSets set of ports to be matched, all width should be the equal
+    * @param errorBit whether generate an additional decode error bit at MSB of output.
+    * @return decoded wire
+    */
+  def bitset(input: chisel3.UInt, bitSets: Seq[BitSet], errorBit: Boolean = false): chisel3.UInt =
+    chisel3.util.experimental.decode.decoder(
+      input,
+      chisel3.util.experimental.decode.TruthTable.fromString(
+        {
+          bitSets.zipWithIndex.flatMap {
+            case (bs, i) =>
+              bs.terms.map(bp =>
+                s"${bp.rawString}->${if (errorBit) "0"}${"0" * (bitSets.size - i - 1)}1${"0" * i}"
+              )
+          } ++ Seq(s"${if (errorBit) "1"}${"?" * bitSets.size}")
+        }.mkString("\n")
+      )
+    )
 }