From 71575609ae7242585ed1008b8473acae1a42165e Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Thu, 6 May 2021 16:18:58 +0000
Subject: implement TruthTable to represent a decode table.

---
 .../util/experimental/decode/TruthTable.scala      | 102 +++++++++++++++++++++
 1 file changed, 102 insertions(+)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/TruthTable.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
new file mode 100644
index 00000000..084403ac
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -0,0 +1,102 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import chisel3.util.BitPat
+
+class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
+  require(table.map(_._1.getWidth).toSet.size == 1, "input width not equal.")
+  require(table.map(_._2.getWidth).toSet.size == 1, "output width not equal.")
+
+  def inputWidth = table.head._1.getWidth
+
+  def outputWidth = table.head._2.getWidth
+
+  override def toString: String = {
+    def writeRow(map: (BitPat, BitPat)): String =
+      s"${TruthTable.bpStr(map._1)}->${TruthTable.bpStr(map._2)}"
+
+    (table.map(writeRow) ++ Seq(s"${" "*(inputWidth + 2)}${TruthTable.bpStr(default)}")).toSeq.sorted.mkString("\n")
+  }
+
+  def copy(table: Map[BitPat, BitPat] = this.table, default: BitPat = this.default) = new TruthTable(table, default)
+
+  override def equals(y: Any): Boolean = {
+    y match {
+      case y: TruthTable => toString == y.toString
+      case _ => false
+    }
+  }
+}
+
+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))
+        .toMap,
+      BitPat(s"b${tableString.split("\n").filterNot(_.contains("->")).head.replace(" ", "")}")
+    )
+  }
+
+  def apply(table: Map[BitPat, BitPat], default: BitPat) = new TruthTable(table, default)
+
+
+  /** consume 1 table, split it into up to 3 tables with the same default bits.
+    *
+    * @return table and its indexes from original bits.
+    * @note
+    * Since most of minimizer(like espresso) cannot handle a multiple default table.
+    * It is useful to split a table into 3 tables based on the default type.
+    */
+  private[decode] def split(
+    table: TruthTable
+  ): Seq[(TruthTable, Seq[Int])] = {
+    def bpFilter(bitPat: BitPat, indexes: Seq[Int]): BitPat =
+      BitPat(s"b${bpStr(bitPat).zipWithIndex.filter(b => indexes.contains(b._2)).map(_._1).mkString}")
+
+    def tableFilter(indexes: Seq[Int]): Option[(TruthTable, Seq[Int])] = {
+      if(indexes.nonEmpty) Some((TruthTable(
+        table.table.map { case (in, out) => in -> bpFilter(out, indexes) },
+        bpFilter(table.default, indexes)
+      ), indexes)) else None
+    }
+
+    def index(bitPat: BitPat, bpType: Char): Seq[Int] =
+      bpStr(bitPat).zipWithIndex.filter(_._1 == bpType).map(_._2)
+
+    Seq('1', '0', '?').flatMap(t => tableFilter(index(table.default, t)))
+  }
+
+  /** consume tables, merge it into single table with different default bits.
+    *
+    * @note
+    * Since most of minimizer(like espresso) cannot handle a multiple default table.
+    * It is useful to split a table into 3 tables based on the default type.
+    */
+  private[decode] def merge(
+    tables: Seq[(TruthTable, Seq[Int])]
+  ): TruthTable = {
+    def reIndex(bitPat: BitPat, table: TruthTable, indexes: Seq[Int]): Seq[(Char, Int)] =
+      bpStr(table.table.getOrElse(bitPat, BitPat.dontCare(indexes.size))).zip(indexes)
+    def bitPat(indexedChar: Seq[(Char, Int)]) = BitPat(s"b${indexedChar
+      .sortBy(_._2)
+      .map(_._1)
+      .mkString}")
+    TruthTable(
+      tables
+        .flatMap(_._1.table.keys)
+        .map { key =>
+          key -> bitPat(tables.flatMap { case (table, indexes) => reIndex(key, table, indexes) })
+        }
+        .toMap,
+      bitPat(tables.flatMap { case (table, indexes) => bpStr(table.default).zip(indexes) })
+    )
+  }
+
+  private def bpStr(bitPat: BitPat) = bitPat.toString.drop(7).dropRight(1)
+}
-- 
cgit v1.2.3


From 1c9163bb05ff7e50885d1560a9df088ff1f2b49d Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Thu, 6 May 2021 16:15:14 +0000
Subject: implement DecodeTableAnnotation for decode table caching.

---
 .../util/experimental/decode/DecodeTableAnnotation.scala    | 13 +++++++++++++
 1 file changed, 13 insertions(+)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
new file mode 100644
index 00000000..3a6957e2
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
@@ -0,0 +1,13 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import firrtl.annotations.{Annotation, ReferenceTarget, SingleTargetAnnotation}
+
+case class DecodeTableAnnotation(
+  target:         ReferenceTarget,
+  truthTable:     TruthTable,
+  minimizedTable: TruthTable)
+    extends SingleTargetAnnotation[ReferenceTarget] {
+  override def duplicate(n: ReferenceTarget): Annotation = this.copy(target = n)
+}
-- 
cgit v1.2.3


From 28eef17430d8bbca2765b5a2b0ab0337f7484840 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Sun, 23 May 2021 07:55:48 +0000
Subject: TruthTable can merge same inputs now.

---
 .../util/experimental/decode/TruthTable.scala      | 27 ++++++++++++++++++----
 1 file changed, 22 insertions(+), 5 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index 084403ac..37bfec77 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -4,9 +4,7 @@ package chisel3.util.experimental.decode
 
 import chisel3.util.BitPat
 
-class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
-  require(table.map(_._1.getWidth).toSet.size == 1, "input width not equal.")
-  require(table.map(_._2.getWidth).toSet.size == 1, "output width not equal.")
+sealed class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
 
   def inputWidth = table.head._1.getWidth
 
@@ -38,12 +36,31 @@ object TruthTable {
         .filter(_.contains("->"))
         .map(_.split("->").map(str => BitPat(s"b$str")))
         .map(bps => bps(0) -> bps(1))
-        .toMap,
+        .toSeq,
       BitPat(s"b${tableString.split("\n").filterNot(_.contains("->")).head.replace(" ", "")}")
     )
   }
 
-  def apply(table: Map[BitPat, BitPat], default: BitPat) = new TruthTable(table, default)
+  /** Convert a table and default output into a [[TruthTable]]. */
+  def apply(table: Iterable[(BitPat, BitPat)], default: BitPat) = {
+    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).map { case (key, values) =>
+      // merge same input inputs.
+      key -> BitPat(s"b${
+        Seq.tabulate(outputWidth) { i =>
+          val outputSet = values.map(_._2)
+            .map(bpStr)
+            .map(_ (i))
+            .toSet
+            .filterNot(_ == '?')
+          require(outputSet.size != 2, s"TruthTable conflict in :\n${values.map { case (i, o) => s"${bpStr(i)}->${bpStr(o)}" }.mkString("\n")}")
+          outputSet.headOption.getOrElse('?')
+        }.mkString
+      }")
+    }, default)
+  }
 
 
   /** consume 1 table, split it into up to 3 tables with the same default bits.
-- 
cgit v1.2.3


From f3318e52e4338dc558de8a900f93bc5757223642 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Sun, 23 May 2021 13:35:54 +0000
Subject: fix for 2.13

---
 src/main/scala/chisel3/util/experimental/decode/TruthTable.scala | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index 37bfec77..cde9cf14 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -46,9 +46,9 @@ object 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).map { case (key, values) =>
+    new TruthTable(table.toSeq.groupBy(_._1.toString).map { case (key, values) =>
       // merge same input inputs.
-      key -> BitPat(s"b${
+      values.head._1 -> BitPat(s"b${
         Seq.tabulate(outputWidth) { i =>
           val outputSet = values.map(_._2)
             .map(bpStr)
-- 
cgit v1.2.3


From 819e806664da117172b6d46aa1adf83d39042d48 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Thu, 6 May 2021 16:16:52 +0000
Subject: implement abstract Minimizer as a general API.

---
 .../util/experimental/decode/Minimizer.scala       | 29 ++++++++++++++++++++++
 1 file changed, 29 insertions(+)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/Minimizer.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/Minimizer.scala b/src/main/scala/chisel3/util/experimental/decode/Minimizer.scala
new file mode 100644
index 00000000..86847710
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/Minimizer.scala
@@ -0,0 +1,29 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+abstract class Minimizer {
+  /** Minimize a multi-input multi-output logic function given by the truth table `table`, with function output values
+    * on unspecified inputs treated as `default`, and return a minimized PLA-like representation of the function.
+    *
+    * Each bit of `table[]._1` encodes one 1-bit input variable of the logic function, and each bit of `default` and
+    * `table[]._2` represents one 1-bit output value of the function.
+    *
+    * @param table    Truth table, can have don't cares in both inputs and outputs, specified as [(inputs, outputs), ...]
+    * @return         Minimized truth table, [(inputs, outputs), ...]
+    *
+    * @example {{{
+    *          minimize(BitPat("b?"), Seq(
+    *              (BitPat("b000"), BitPat("b0")),
+    *              // (BitPat("b001"), BitPat("b?")),  // same as default, can be omitted
+    *              // (BitPat("b010"), BitPat("b?")),  // same as default, can be omitted
+    *              (BitPat("b011"), BitPat("b0")),
+    *              (BitPat("b100"), BitPat("b1")),
+    *              (BitPat("b101"), BitPat("b1")),
+    *              (BitPat("b110"), BitPat("b0")),
+    *              (BitPat("b111"), BitPat("b1")),
+    *          ))
+    * }}}
+    */
+  def minimize(table: TruthTable): TruthTable
+}
\ No newline at end of file
-- 
cgit v1.2.3


From 3691fe61cc43beb0e7d0f813723d4150daa79372 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Thu, 6 May 2021 16:20:50 +0000
Subject: add a simple decoder API.

---
 .../decode/DecodeTableAnnotation.scala             |  4 +-
 .../chisel3/util/experimental/decode/decoder.scala | 53 ++++++++++++++++++++++
 2 files changed, 55 insertions(+), 2 deletions(-)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/decoder.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
index 3a6957e2..cd289a5d 100644
--- a/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
@@ -6,8 +6,8 @@ import firrtl.annotations.{Annotation, ReferenceTarget, SingleTargetAnnotation}
 
 case class DecodeTableAnnotation(
   target:         ReferenceTarget,
-  truthTable:     TruthTable,
-  minimizedTable: TruthTable)
+  truthTable:     String,
+  minimizedTable: String)
     extends SingleTargetAnnotation[ReferenceTarget] {
   override def duplicate(n: ReferenceTarget): Annotation = this.copy(target = n)
 }
diff --git a/src/main/scala/chisel3/util/experimental/decode/decoder.scala b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
new file mode 100644
index 00000000..2ef474e1
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -0,0 +1,53 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import chisel3._
+import chisel3.experimental.{ChiselAnnotation, annotate}
+import chisel3.util.{BitPat, pla}
+import chisel3.util.experimental.getAnnotations
+import firrtl.annotations.Annotation
+import logger.LazyLogging
+
+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)
+    }.toMap.getOrElse(
+      {
+        logger.trace(s"""Decoder Cache Hit!
+                        |${truthTable.table}
+                        |""".stripMargin)
+        truthTable
+      }, {
+        val startTime = System.nanoTime()
+        val minimizedTable = minimizer.minimize(truthTable)
+        val totalTime = System.nanoTime() - startTime
+        val totalTimeInSeconds = totalTime / 1e9
+        val info = f"Logic Minimize with $minimizer finished in ${totalTimeInSeconds} second"
+        if (totalTimeInSeconds > 5)
+          logger.error(
+            s"$info spends too long, consider using chisel3.util.experimental.DecodeTableAnnotation to cache decode result or switch to EspressoMinimizer."
+          )
+        else logger.trace(info)
+        minimizedTable
+      }
+    )
+    if (minimizedTable.table.isEmpty) {
+      val outputs = Wire(UInt(minimizedTable.default.getWidth.W))
+      outputs := minimizedTable.default.value.U(minimizedTable.default.getWidth.W)
+      outputs
+    } else {
+      val (plaInput, plaOutput) =
+        pla(minimizedTable.table.toSeq, BitPat(minimizedTable.default.value.U(minimizedTable.default.getWidth.W)))
+
+      annotate(new ChiselAnnotation {
+        override def toFirrtl: Annotation =
+          DecodeTableAnnotation(plaOutput.toTarget, truthTable.toString, minimizedTable.toString)
+      })
+
+      plaInput := input
+      plaOutput
+    }
+  }
+}
-- 
cgit v1.2.3


From d2c71fbf64a4728914414bbf27803d7cf03f94ad Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Tue, 25 May 2021 04:54:14 +0000
Subject: async decoder with 5 seconds timeout.

---
 .../chisel3/util/experimental/decode/decoder.scala | 25 ++++++++++++++--------
 1 file changed, 16 insertions(+), 9 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/decoder.scala b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
index 2ef474e1..87e839d3 100644
--- a/src/main/scala/chisel3/util/experimental/decode/decoder.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -9,27 +9,34 @@ import chisel3.util.experimental.getAnnotations
 import firrtl.annotations.Annotation
 import logger.LazyLogging
 
+import scala.concurrent.ExecutionContext.Implicits.global
+import scala.concurrent.duration.Duration
+import scala.concurrent.{Await, Future}
+
 object decoder extends LazyLogging {
-  def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable): UInt = {
+  def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable, timeout: Int = 5): UInt = {
     val minimizedTable = getAnnotations().collect {
       case DecodeTableAnnotation(_, in, out) => TruthTable(in) -> TruthTable(out)
     }.toMap.getOrElse(
       {
-        logger.trace(s"""Decoder Cache Hit!
+        logger.warn(s"""Decoder Cache Hit!
                         |${truthTable.table}
                         |""".stripMargin)
         truthTable
       }, {
         val startTime = System.nanoTime()
-        val minimizedTable = minimizer.minimize(truthTable)
+        val future = Future(minimizer.minimize(truthTable))
+        var now = System.nanoTime()
+        while (!future.isCompleted) {
+          val elapsed = (System.nanoTime() - now) / 1e9
+          now = System.nanoTime()
+          if(elapsed > timeout) logger.error(s"Minimizer has been executed for ${(System.nanoTime() - startTime) / 1e9} seconds.")
+        }
+        val minimizedTable = Await.result(future, Duration.Inf)
         val totalTime = System.nanoTime() - startTime
         val totalTimeInSeconds = totalTime / 1e9
-        val info = f"Logic Minimize with $minimizer finished in ${totalTimeInSeconds} second"
-        if (totalTimeInSeconds > 5)
-          logger.error(
-            s"$info spends too long, consider using chisel3.util.experimental.DecodeTableAnnotation to cache decode result or switch to EspressoMinimizer."
-          )
-        else logger.trace(info)
+        val info = f"Logic Minimize with $minimizer finished in $totalTimeInSeconds second"
+        logger.warn(info)
         minimizedTable
       }
     )
-- 
cgit v1.2.3


From 88b7c48c18267e55c755f4fe6615c2faf2910906 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Tue, 25 May 2021 07:22:32 +0000
Subject: remove all timeouts by review.

---
 .../chisel3/util/experimental/decode/decoder.scala | 30 ++--------------------
 1 file changed, 2 insertions(+), 28 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/decoder.scala b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
index 87e839d3..8168824f 100644
--- a/src/main/scala/chisel3/util/experimental/decode/decoder.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -9,37 +9,11 @@ import chisel3.util.experimental.getAnnotations
 import firrtl.annotations.Annotation
 import logger.LazyLogging
 
-import scala.concurrent.ExecutionContext.Implicits.global
-import scala.concurrent.duration.Duration
-import scala.concurrent.{Await, Future}
-
 object decoder extends LazyLogging {
-  def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable, timeout: Int = 5): UInt = {
+  def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable): UInt = {
     val minimizedTable = getAnnotations().collect {
       case DecodeTableAnnotation(_, in, out) => TruthTable(in) -> TruthTable(out)
-    }.toMap.getOrElse(
-      {
-        logger.warn(s"""Decoder Cache Hit!
-                        |${truthTable.table}
-                        |""".stripMargin)
-        truthTable
-      }, {
-        val startTime = System.nanoTime()
-        val future = Future(minimizer.minimize(truthTable))
-        var now = System.nanoTime()
-        while (!future.isCompleted) {
-          val elapsed = (System.nanoTime() - now) / 1e9
-          now = System.nanoTime()
-          if(elapsed > timeout) logger.error(s"Minimizer has been executed for ${(System.nanoTime() - startTime) / 1e9} seconds.")
-        }
-        val minimizedTable = Await.result(future, Duration.Inf)
-        val totalTime = System.nanoTime() - startTime
-        val totalTimeInSeconds = totalTime / 1e9
-        val info = f"Logic Minimize with $minimizer finished in $totalTimeInSeconds second"
-        logger.warn(info)
-        minimizedTable
-      }
-    )
+    }.toMap.getOrElse(truthTable, minimizer.minimize(truthTable))
     if (minimizedTable.table.isEmpty) {
       val outputs = Wire(UInt(minimizedTable.default.getWidth.W))
       outputs := minimizedTable.default.value.U(minimizedTable.default.getWidth.W)
-- 
cgit v1.2.3


From c11fdf33981365927ea085b7aee095933a4a5ddf Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Mon, 14 Jun 2021 14:58:01 +0000
Subject: add documentation for DecodeTableAnnotation.

---
 .../chisel3/util/experimental/decode/DecodeTableAnnotation.scala | 9 +++++++++
 1 file changed, 9 insertions(+)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
index cd289a5d..2b50ef90 100644
--- a/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
@@ -4,6 +4,15 @@ package chisel3.util.experimental.decode
 
 import firrtl.annotations.{Annotation, ReferenceTarget, SingleTargetAnnotation}
 
+/** DecodeTableAnnotation used to store a decode result for a specific [[TruthTable]].
+  * This is useful for saving large [[TruthTable]] during a elaboration time.
+  *
+  * @note user should manage the correctness of [[minimizedTable]].
+  *
+  * @param target output wire of a decoder.
+  * @param truthTable input [[TruthTable]] encoded in a serialized [[TruthTable]].
+  * @param minimizedTable minimized [[truthTable]] encoded in a serialized [[TruthTable]].
+  */
 case class DecodeTableAnnotation(
   target:         ReferenceTarget,
   truthTable:     String,
-- 
cgit v1.2.3


From 48548463c6c5c6bc9076c80924cb4683fc737f11 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Mon, 14 Jun 2021 22:39:42 +0800
Subject: Apply Jack's Review

1. `TruthTable` is final now.
2. add return type for `TruthTable`

Co-authored-by: Jack Koenig <koenig@sifive.com>---
 src/main/scala/chisel3/util/experimental/decode/TruthTable.scala | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index cde9cf14..ca0ff8b4 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -4,7 +4,7 @@ package chisel3.util.experimental.decode
 
 import chisel3.util.BitPat
 
-sealed class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
+final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
 
   def inputWidth = table.head._1.getWidth
 
@@ -42,7 +42,7 @@ object TruthTable {
   }
 
   /** Convert a table and default output into a [[TruthTable]]. */
-  def apply(table: Iterable[(BitPat, BitPat)], default: BitPat) = {
+  def apply(table: Iterable[(BitPat, BitPat)], default: BitPat): 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
-- 
cgit v1.2.3


From f48b4abd9b2e10a5243cadf3803f7f42d4ce25fc Mon Sep 17 00:00:00 2001
From: Boyang Han
Date: Thu, 6 May 2021 16:27:11 +0000
Subject: implement QMC.

---
 .../util/experimental/decode/QMCMinimizer.scala    | 282 +++++++++++++++++++++
 1 file changed, 282 insertions(+)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
new file mode 100644
index 00000000..bc5ea351
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -0,0 +1,282 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import chisel3.util.BitPat
+
+import scala.annotation.tailrec
+import scala.math.Ordered.orderingToOrdered
+import scala.language.implicitConversions
+
+object QMCMinimizer extends Minimizer {
+  private implicit def toImplicant(x: BitPat): Implicant = new Implicant(x)
+
+  private class Implicant(val bp: BitPat) {
+    var isPrime: Boolean = true
+
+    def width = bp.getWidth
+
+    override def equals(that: Any): Boolean = that match {
+      case x: Implicant => bp.value == x.bp.value && bp.mask == x.bp.mask
+      case _ => false
+    }
+
+    override def hashCode = bp.value.toInt
+
+    /** Check whether two implicants have the same value on all of the cared bits (intersection).
+      *
+      * {{{
+      * value ^^ x.value                                       // bits that are different
+      * (bits that are different) & x.mask                     // bits that are different and `this` care
+      * (bits that are different and `this` care) & y.mask     // bits that are different and `both` care
+      * (bits that are different and both care) == 0           // no (bits that are different and we both care) exists
+      * no (bits that are different and we both care) exists   // all cared bits are the same, two terms intersect
+      * }}}
+      *
+      * @param y Implicant to be checked with
+      * @return Whether two implicants intersect
+      */
+    def intersects(y: Implicant): Boolean = ((bp.value ^ y.bp.value) & bp.mask & y.bp.mask) == 0
+
+    /** Check whether two implicants are similar.
+      * Two implicants are "similar" when they satisfy all the following rules:
+      *   1. have the same mask ('?'s are at the same positions)
+      *   1. values only differ by one bit
+      *   1. the bit at the differed position of this term is '1' (that of the other term is '0')
+      *
+      * @example this = 11?0, x = 10?0 -> similar
+      * @example this = 11??, x = 10?0 -> not similar, violated rule 1
+      * @example this = 11?1, x = 10?0 -> not similar, violated rule 2
+      * @example this = 10?0, x = 11?0 -> not similar, violated rule 3
+      * @param y Implicant to be checked with
+      * @return Whether this term is similar to the other
+      */
+    def similar(y: Implicant): Boolean = {
+      val diff = bp.value - y.bp.value
+      bp.mask == y.bp.mask && bp.value > y.bp.value && (diff & diff - 1) == 0
+    }
+
+    /** Merge two similar implicants
+      * Rule of merging: '0' and '1' merge to '?'
+      *
+      * @param y Term to be merged with
+      * @return A new term representing the merge result
+      */
+    def merge(y: Implicant): Implicant = {
+      require(similar(y), s"merge is only reasonable when $this is similar to $y")
+
+      // if two term can be merged, then they both are not prime implicants.
+      isPrime = false
+      y.isPrime = false
+      val bit = bp.value - y.bp.value
+      new BitPat(bp.value &~ bit, bp.mask &~ bit, width)
+    }
+
+    /** Check all bits in `x` cover the correspond position in `y`.
+      *
+      * Rule to define coverage relationship among `0`, `1` and `?`:
+      *   1. '?' covers '0' and '1', '0' covers '0', '1' covers '1'
+      *   1. '1' doesn't cover '?', '1' doesn't cover '0'
+      *   1. '0' doesn't cover '?', '0' doesn't cover '1'
+      *
+      * For all bits that `x` don't care, `y` can be `0`, `1`, `?`
+      * For all bits that `x` care, `y` must be the same value and not masked.
+      * {{{
+      *    (~x.mask & -1) | ((x.mask) & ((x.value xnor y.value) & y.mask)) = -1
+      * -> ~x.mask | ((x.mask) & ((x.value xnor y.value) & y.mask)) = -1
+      * -> ~x.mask | ((x.value xnor y.value) & y.mask) = -1
+      * -> x.mask & ~((x.value xnor y.value) & y.mask) = 0
+      * -> x.mask & (~(x.value xnor y.value) | ~y.mask) = 0
+      * -> x.mask & ((x.value ^ y.value) | ~y.mask) = 0
+      * -> ((x.value ^ y.value) & x.mask | ~y.mask & x.mask) = 0
+      * }}}
+      *
+      * @param y to check is covered by `x` or not.
+      * @return Whether `x` covers `y`
+      */
+    def covers(y: Implicant): Boolean = ((bp.value ^ y.bp.value) & bp.mask | ~y.bp.mask & bp.mask) == 0
+
+    override def toString = (if (!isPrime) "Non" else "") + "Prime" + bp.toString.replace("BitPat", "Implicant")
+  }
+
+  /**
+    * If two terms have different value, then their order is determined by the value, or by the mask.
+    */
+  private implicit def ordering: Ordering[Implicant] = new Ordering[Implicant] {
+    override def compare(x: Implicant, y: Implicant): Int =
+      if (x.bp.value < y.bp.value || x.bp.value == y.bp.value && x.bp.mask > y.bp.mask) -1 else 1
+  }
+
+  /** Calculate essential prime implicants based on previously calculated prime implicants and all implicants.
+    *
+    * @param primes    Prime implicants
+    * @param minterms All implicants
+    * @return (a, b, c)
+    *         a: essential prime implicants
+    *         b: nonessential prime implicants
+    *         c: implicants that are not cover by any of the essential prime implicants
+    */
+  private def getEssentialPrimeImplicants(primes: Seq[Implicant], minterms: Seq[Implicant]): (Seq[Implicant], Seq[Implicant], Seq[Implicant]) = {
+    // primeCovers(i): implicants that `prime(i)` covers
+    val primeCovers = primes.map(p => minterms.filter(p.covers))
+    // eliminate prime implicants that can be covered by other prime implicants
+    for (((icover, pi), i) <- (primeCovers zip primes).zipWithIndex) {
+      for (((jcover, pj), _) <- (primeCovers zip primes).zipWithIndex.drop(i + 1)) {
+        // we prefer prime implicants with wider implicants coverage
+        if (icover.size > jcover.size && jcover.forall(pi.covers)) {
+          // calculate essential prime implicants with `pj` eliminated from prime implicants table
+          return getEssentialPrimeImplicants(primes.filter(_ != pj), minterms)
+        }
+      }
+    }
+
+    // implicants that only one prime implicant covers
+    val essentiallyCovered = minterms.filter(t => primes.count(_.covers(t)) == 1)
+    // essential prime implicants, prime implicants that covers only one implicant
+    val essential = primes.filter(p => essentiallyCovered.exists(p.covers))
+    // {nonessential} = {prime implicants} - {essential prime implicants}
+    val nonessential = primes.filterNot(essential contains _)
+    // implicants that no essential prime implicants covers
+    val uncovered = minterms.filterNot(t => essential.exists(_.covers(t)))
+    if (essential.isEmpty || uncovered.isEmpty)
+      (essential, nonessential, uncovered)
+    else {
+      // now there are implicants (`uncovered`) that are covered by multiple nonessential prime implicants (`nonessential`)
+      // need to reduce prime implicants
+      val (a, b, c) = getEssentialPrimeImplicants(nonessential, uncovered)
+      (essential ++ a, b, c)
+    }
+  }
+
+  /** Use [[https://en.wikipedia.org/wiki/Petrick%27s_method]] to select a [[Seq]] of nonessential prime implicants
+    * that covers all implicants that are not covered by essential prime implicants.
+    *
+    * @param implicants Nonessential prime implicants
+    * @param minterms   Implicants that are not covered by essential prime implicants
+    * @return Selected nonessential prime implicants
+    */
+  private def getCover(implicants: Seq[Implicant], minterms: Seq[Implicant]): Seq[Implicant] = {
+    /** Calculate the implementation cost (using comparators) of a list of implicants, more don't cares is cheaper
+      *
+      * @param cover Implicant list
+      * @return How many comparators need to implement this list of implicants
+      */
+    def getCost(cover: Seq[Implicant]): Int = cover.map(_.bp.mask.bitCount).sum
+
+    /** Determine if one combination of prime implicants is cheaper when implementing as comparators.
+      * Shorter term list is cheaper, term list with more don't cares is cheaper (less comparators)
+      *
+      * @param a    Operand a
+      * @param b    Operand b
+      * @return `a` < `b`
+      */
+    def cheaper(a: Seq[Implicant], b: Seq[Implicant]): Boolean = {
+      val ca = getCost(a)
+      val cb = getCost(b)
+
+      /** If `a` < `b`
+        *
+        * Like comparing the dictionary order of two strings.
+        * Define `a` < `b` if both `a` and `b` are empty.
+        *
+        * @param a Operand a
+        * @param b Operand b
+        * @return `a` < `b`
+        */
+      @tailrec
+      def listLess(a: Seq[Implicant], b: Seq[Implicant]): Boolean = b.nonEmpty && (a.isEmpty || a.head < b.head || a.head == b.head && listLess(a.tail, b.tail))
+
+      ca < cb || ca == cb && listLess(a.sortWith(_ < _), b.sortWith(_ < _))
+    }
+
+    // if there are no implicant that is not covered by essential prime implicants, which means all implicants are
+    // covered by essential prime implicants, there is no need to apply Petrick's method
+    if (minterms.nonEmpty) {
+      // cover(i): nonessential prime implicants that covers `minterms(i)`
+      val cover = minterms.map(m => implicants.filter(_.covers(m)))
+      val all = cover.tail.foldLeft(cover.head.map(Set(_)))((c0, c1) => c0.flatMap(a => c1.map(a + _)))
+      all.map(_.toList).reduceLeft((a, b) => if (cheaper(a, b)) a else b)
+    } else
+      Seq[Implicant]()
+  }
+
+  def minimize(table: TruthTable): TruthTable = {
+    require(table.table.nonEmpty, "Truth table must not be empty")
+
+    // extract decode table to inputs and outputs
+    val (inputs, outputs) = table.table.unzip
+
+    require(outputs.map(_.getWidth == table.default.getWidth).reduce(_ && _), "All output BitPats and default BitPat must have the same length")
+    require(if (inputs.toSeq.length > 1) inputs.tail.map(_.width == inputs.head.width).reduce(_ && _) else true, "All input BitPats must have the same length")
+
+    // make sure no two inputs specified in the truth table intersect
+    for (t <- inputs.tails; if t.nonEmpty)
+      for (u <- t.tail)
+        require(!t.head.intersects(u), "truth table entries " + t.head + " and " + u + " overlap")
+
+    // number of inputs
+    val n = inputs.head.width
+    // number of outputs
+    val m = outputs.head.getWidth
+
+    // for all outputs
+    table.copy(table = (0 until m).flatMap(i => {
+      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) }.map(_._1).map(toImplicant).toSeq
+      // 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) }.map(_._1).map(toImplicant).toSeq
+      // 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) }.map(_._1).map(toImplicant).toSeq
+
+      val (implicants, defaultToDc) = table.default match {
+        case x if x.mask.testBit(i) && !x.value.testBit(i) => // default to 0
+          (mint ++ dc, false)
+        case x if x.mask.testBit(i) && x.value.testBit(i) => // default to 1
+          (maxt ++ dc, false)
+        case x if !x.mask.testBit(i) => // default to ?
+          (mint, true)
+      }
+
+      implicants.foreach(_.isPrime = true)
+      val cols = (0 to n).reverse.map(b => implicants.filter(b == _.bp.mask.bitCount))
+      val mergeTable = cols.map(
+        c => (0 to n).map(
+          b => collection.mutable.Set(c.filter(b == _.bp.value.bitCount):_*)
+        )
+      )
+
+      for (i <- 0 to n) {
+        for (j <- 0 until n - i) {
+          mergeTable(i)(j).foreach(a => mergeTable(i + 1)(j) ++= mergeTable(i)(j + 1).filter(_ similar a).map(_ merge a))
+        }
+        if (defaultToDc) {
+          for (j <- 0 until n - i) {
+            for (a <- mergeTable(i)(j).filter(_.isPrime)) {
+              if (a.bp.mask.testBit(i) && !a.bp.value.testBit(i)) {
+                // this bit is `0`
+                val t = new BitPat(a.bp.value.setBit(i), a.bp.mask, a.width)
+                if (!maxt.exists(_.intersects(t))) mergeTable(i + 1)(j) += t merge a
+              }
+            }
+            for (a <- mergeTable(i)(j + 1).filter(_.isPrime)) {
+              if (a.bp.mask.testBit(i) && a.bp.value.testBit(i)) {
+                // this bit is `1`
+                val t = new BitPat(a.bp.value.clearBit(i), a.bp.mask, a.width)
+                if (!maxt.exists(_.intersects(t))) mergeTable(i + 1)(j) += a merge t
+              }
+            }
+          }
+        }
+      }
+
+      val primeImplicants = mergeTable.flatten.flatten.filter(_.isPrime).sortWith(_ < _)
+
+      val (essentialPrimeImplicants, nonessentialPrimeImplicants, uncoveredImplicants) =
+        getEssentialPrimeImplicants(primeImplicants, implicants)
+
+      (essentialPrimeImplicants ++ getCover(nonessentialPrimeImplicants, uncoveredImplicants)).map(a => (a.bp, outputBp))
+    }).toMap)
+  }
+}
\ No newline at end of file
-- 
cgit v1.2.3


From 93e9e2ba8058ef89afacc00c16e138b0243587ba Mon Sep 17 00:00:00 2001
From: Boyang Han
Date: Sun, 23 May 2021 04:04:42 -0700
Subject: Merge minimized table before return as a TruthTable

---
 .../chisel3/util/experimental/decode/QMCMinimizer.scala | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
index bc5ea351..3fa5a70c 100644
--- a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -220,7 +220,7 @@ object QMCMinimizer extends Minimizer {
     val m = outputs.head.getWidth
 
     // for all outputs
-    table.copy(table = (0 until m).flatMap(i => {
+    val minimized = (0 until m).flatMap(i => {
       val outputBp = BitPat("b" + "?" * (m - i - 1) + "1" + "?" * i)
 
       // Minterms, implicants that makes the output to be 1
@@ -277,6 +277,19 @@ object QMCMinimizer extends Minimizer {
         getEssentialPrimeImplicants(primeImplicants, implicants)
 
       (essentialPrimeImplicants ++ getCover(nonessentialPrimeImplicants, uncoveredImplicants)).map(a => (a.bp, outputBp))
-    }).toMap)
+    })
+
+    minimized.tail.foldLeft(table.copy(table = Map(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) {
+            def ones(bitPat: BitPat) = bitPat.toString.drop(7).dropRight(1).zipWithIndex.collect{case ('1', x) => x}
+            (k, BitPat("b" + (0 until v.getWidth).map(i => if ((ones(v) ++ ones(t._2)).contains(i)) "1" else "?").mkString))
+          } else (k, v)
+        })
+      } else {
+        tb.copy(table = tb.table + t)
+      }
+    }
   }
 }
\ No newline at end of file
-- 
cgit v1.2.3


From 6bcedfdc01e51079c258c5cc576356ad561e2555 Mon Sep 17 00:00:00 2001
From: Boyang Han
Date: Tue, 11 May 2021 06:01:25 -0700
Subject: Refactor to a more `scala` form

---
 src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
index 3fa5a70c..b6b97daf 100644
--- a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -224,11 +224,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) }.map(_._1).map(toImplicant).toSeq
+      val mint: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && t.value.testBit(i) }.keys.map(toImplicant).toSeq
       // 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) }.map(_._1).map(toImplicant).toSeq
+      val maxt: Seq[Implicant] = table.table.filter { case (_, t) => t.mask.testBit(i) && !t.value.testBit(i) }.keys.map(toImplicant).toSeq
       // 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) }.map(_._1).map(toImplicant).toSeq
+      val dc: Seq[Implicant] = table.table.filter { case (_, t) => !t.mask.testBit(i) }.keys.map(toImplicant).toSeq
 
       val (implicants, defaultToDc) = table.default match {
         case x if x.mask.testBit(i) && !x.value.testBit(i) => // default to 0
-- 
cgit v1.2.3


From 31821aabdb8222dfeae76bac24858dd2ec271aa9 Mon Sep 17 00:00:00 2001
From: Boyang Han
Date: Tue, 11 May 2021 06:23:30 -0700
Subject: Add computational complexity analysis

---
 src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
index b6b97daf..54faa734 100644
--- a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -194,6 +194,7 @@ object QMCMinimizer extends Minimizer {
     if (minterms.nonEmpty) {
       // cover(i): nonessential prime implicants that covers `minterms(i)`
       val cover = minterms.map(m => implicants.filter(_.covers(m)))
+      // all subsets of `cover`, NP algorithm, O(2 ^ len(cover))
       val all = cover.tail.foldLeft(cover.head.map(Set(_)))((c0, c1) => c0.flatMap(a => c1.map(a + _)))
       all.map(_.toList).reduceLeft((a, b) => if (cheaper(a, b)) a else b)
     } else
@@ -247,6 +248,7 @@ object QMCMinimizer extends Minimizer {
         )
       )
 
+      // O(n ^ 3)
       for (i <- 0 to n) {
         for (j <- 0 until n - i) {
           mergeTable(i)(j).foreach(a => mergeTable(i + 1)(j) ++= mergeTable(i)(j + 1).filter(_ similar a).map(_ merge a))
@@ -273,6 +275,7 @@ object QMCMinimizer extends Minimizer {
 
       val primeImplicants = mergeTable.flatten.flatten.filter(_.isPrime).sortWith(_ < _)
 
+      // O(len(primeImplicants) ^ 4)
       val (essentialPrimeImplicants, nonessentialPrimeImplicants, uncoveredImplicants) =
         getEssentialPrimeImplicants(primeImplicants, implicants)
 
-- 
cgit v1.2.3


From 695864f5716626a15a7798dae048d8301940a2db Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Thu, 15 Jul 2021 02:32:06 +0800
Subject: Espresso Decoder (#1964)

Co-authored-by: Haoran Yuan <sinofp@tuta.io>
Co-authored-by: Boyang Han <yqszxx@gmail.com>---
 .../experimental/decode/EspressoMinimizer.scala    | 75 ++++++++++++++++++++++
 .../util/experimental/decode/TruthTable.scala      |  2 +-
 .../chisel3/util/experimental/decode/decoder.scala | 49 ++++++++++++++
 3 files changed, 125 insertions(+), 1 deletion(-)
 create mode 100644 src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
new file mode 100644
index 00000000..0351a46a
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
@@ -0,0 +1,75 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import chisel3.util.BitPat
+import logger.LazyLogging
+
+case object EspressoNotFoundException extends Exception
+
+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 = {
+    def writeTable(table: TruthTable): String = {
+      def invert(string: String) = string
+        .replace('0', 't')
+        .replace('1', '0')
+        .replace('t', '1')
+      val defaultType: Char = {
+        val t = table.default.toString.drop(7).dropRight(1).toCharArray.distinct
+        require(t.length == 1, "Internal Error: espresso only accept unified default type.")
+        t.head
+      }
+      val tableType: String = defaultType match {
+        case '?' => "fr"
+        case _ => "fd"
+      }
+      val rawTable = table
+        .toString
+        .split("\n")
+        .filter(_.contains("->"))
+        .mkString("\n")
+        .replace("->", " ")
+        .replace('?', '-')
+      // invert all output, since espresso cannot handle default is on.
+      val invertRawTable = rawTable
+        .split("\n")
+        .map(_.split(" "))
+        .map(row => s"${row(0)} ${invert(row(1))}")
+        .mkString("\n")
+      s""".i ${table.inputWidth}
+         |.o ${table.outputWidth}
+         |.type ${tableType}
+         |""".stripMargin ++ (if (defaultType == '1') invertRawTable else rawTable)
+    }
+
+    def readTable(espressoTable: String): Map[BitPat, BitPat] = {
+      def bitPat(espresso: String): BitPat = BitPat("b" + espresso.replace('-', '?'))
+
+      espressoTable
+        .split("\n")
+        .filterNot(_.startsWith("."))
+        .map(_.split(' '))
+        .map(row => bitPat(row(0)) -> bitPat(row(1)))
+        .toMap
+    }
+
+    // Since Espresso don't implements pipe, we use a temp file to do so.
+    val input = writeTable(table)
+    logger.trace(s"""espresso input table:
+                    |$input
+                    |""".stripMargin)
+    val f = os.temp(input)
+    val o = try {
+      os.proc("espresso", f).call().out.chunks.mkString
+    } catch {
+      case e: java.io.IOException if e.getMessage.contains("error=2, No such file or directory") => throw EspressoNotFoundException
+    }
+    logger.trace(s"""espresso output table:
+                    |$o
+                    |""".stripMargin)
+    TruthTable(readTable(o), table.default)
+  }
+}
diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index ca0ff8b4..f4f200ce 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -99,7 +99,7 @@ object TruthTable {
     tables: Seq[(TruthTable, Seq[Int])]
   ): TruthTable = {
     def reIndex(bitPat: BitPat, table: TruthTable, indexes: Seq[Int]): Seq[(Char, Int)] =
-      bpStr(table.table.getOrElse(bitPat, BitPat.dontCare(indexes.size))).zip(indexes)
+      bpStr(table.table.map(a => a._1.toString -> a._2).getOrElse(bitPat.toString, BitPat.dontCare(indexes.size))).zip(indexes)
     def bitPat(indexedChar: Seq[(Char, Int)]) = BitPat(s"b${indexedChar
       .sortBy(_._2)
       .map(_._1)
diff --git a/src/main/scala/chisel3/util/experimental/decode/decoder.scala b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
index 8168824f..42e374d1 100644
--- a/src/main/scala/chisel3/util/experimental/decode/decoder.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -10,6 +10,13 @@ import firrtl.annotations.Annotation
 import logger.LazyLogging
 
 object decoder extends LazyLogging {
+  /** Use a specific [[Minimizer]] to generated decoded signals.
+    *
+    * @param minimizer  specific [[Minimizer]], can be [[QMCMinimizer]] or [[EspressoMinimizer]].
+    * @param input      input signal that contains decode table input
+    * @param truthTable [[TruthTable]] to decode user input.
+    * @return decode table output.
+    */
   def apply(minimizer: Minimizer, input: UInt, truthTable: TruthTable): UInt = {
     val minimizedTable = getAnnotations().collect {
       case DecodeTableAnnotation(_, in, out) => TruthTable(in) -> TruthTable(out)
@@ -31,4 +38,46 @@ object decoder extends LazyLogging {
       plaOutput
     }
   }
+
+  /** Use [[EspressoMinimizer]] to generated decoded signals.
+    *
+    * @param input      input signal that contains decode table input
+    * @param truthTable [[TruthTable]] to decode user input.
+    * @return decode table output.
+    */
+  def espresso(input: UInt, truthTable: TruthTable): UInt = apply(EspressoMinimizer, input, truthTable)
+
+  /** Use [[QMCMinimizer]] to generated decoded signals.
+    *
+    * @param input      input signal that contains decode table input
+    * @param truthTable [[TruthTable]] to decode user input.
+    * @return decode table output.
+    */
+  def qmc(input: UInt, truthTable: TruthTable): UInt = apply(QMCMinimizer, input, truthTable)
+
+  /** try to use [[EspressoMinimizer]] to decode `input` by `truthTable`
+    * if `espresso` not exist in your PATH environment it will fall back to [[QMCMinimizer]], and print a warning.
+    *
+    * @param input      input signal that contains decode table input
+    * @param truthTable [[TruthTable]] to decode user input.
+    * @return decode table output.
+    */
+  def apply(input: UInt, truthTable: TruthTable): UInt = {
+    def qmcFallBack(input: UInt, truthTable: TruthTable) = {
+      """fall back to QMC.
+        |Quine-McCluskey is a NP complete algorithm, may run forever or run out of memory in large decode tables.
+        |To get rid of this warning, please use `decoder.qmc` directly, or add espresso to your PATH.
+        |""".stripMargin
+      qmc(input, truthTable)
+    }
+
+    try espresso(input, truthTable) catch {
+      case EspressoNotFoundException =>
+        logger.error(s"espresso is not found in your PATH:\n${sys.env("PATH").split(":").mkString("\n")}".stripMargin)
+        qmcFallBack(input, truthTable)
+      case e: java.io.IOException =>
+        logger.error(s"espresso failed to run with ${e.getMessage}")
+        qmcFallBack(input, truthTable)
+    }
+  }
 }
-- 
cgit v1.2.3


From aae627919336f0efff98dc47b2ea5694728d5350 Mon Sep 17 00:00:00 2001
From: Boyang Han
Date: Thu, 12 Aug 2021 01:36:03 -0700
Subject: Pass truth table to espresso using stdin instead of temp file

---
 .../chisel3/util/experimental/decode/EspressoMinimizer.scala   | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
index 0351a46a..3ecec048 100644
--- a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
@@ -56,20 +56,18 @@ object EspressoMinimizer extends Minimizer with LazyLogging {
         .toMap
     }
 
-    // Since Espresso don't implements pipe, we use a temp file to do so.
     val input = writeTable(table)
     logger.trace(s"""espresso input table:
                     |$input
                     |""".stripMargin)
-    val f = os.temp(input)
-    val o = try {
-      os.proc("espresso", f).call().out.chunks.mkString
+    val output = try {
+      os.proc("espresso").call(stdin = input).out.chunks.mkString
     } catch {
       case e: java.io.IOException if e.getMessage.contains("error=2, No such file or directory") => throw EspressoNotFoundException
     }
     logger.trace(s"""espresso output table:
-                    |$o
+                    |$output
                     |""".stripMargin)
-    TruthTable(readTable(o), table.default)
+    TruthTable(readTable(output), table.default)
   }
 }
-- 
cgit v1.2.3


From e74b978d5188d9cd28e3520912d858d228136e75 Mon Sep 17 00:00:00 2001
From: Jiuyang Liu
Date: Fri, 27 Aug 2021 04:37:34 +0800
Subject: add new APIs to BitPat (#2076)

* add Y and N to BitPat.

* add ## for BitPat.

* add rawString API.

* use rawString in decoder

* add select and slice to BitPat.---
 .../util/experimental/decode/EspressoMinimizer.scala   |  2 +-
 .../util/experimental/decode/QMCMinimizer.scala        |  2 +-
 .../chisel3/util/experimental/decode/TruthTable.scala  | 18 ++++++++----------
 3 files changed, 10 insertions(+), 12 deletions(-)

(limited to 'src/main/scala/chisel3/util/experimental/decode')

diff --git a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
index 3ecec048..1d725875 100644
--- a/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
@@ -18,7 +18,7 @@ object EspressoMinimizer extends Minimizer with LazyLogging {
         .replace('1', '0')
         .replace('t', '1')
       val defaultType: Char = {
-        val t = table.default.toString.drop(7).dropRight(1).toCharArray.distinct
+        val t = table.default.rawString.toCharArray.distinct
         require(t.length == 1, "Internal Error: espresso only accept unified default type.")
         t.head
       }
diff --git a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
index 54faa734..c1533f44 100644
--- a/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -286,7 +286,7 @@ object QMCMinimizer extends Minimizer {
       if (tb.table.exists(x => x._1 == t._1)) {
         tb.copy(table = tb.table.map { case (k, v) =>
           if (k == t._1) {
-            def ones(bitPat: BitPat) = bitPat.toString.drop(7).dropRight(1).zipWithIndex.collect{case ('1', x) => x}
+            def ones(bitPat: BitPat) = bitPat.rawString.zipWithIndex.collect{case ('1', x) => x}
             (k, BitPat("b" + (0 until v.getWidth).map(i => if ((ones(v) ++ ones(t._2)).contains(i)) "1" else "?").mkString))
           } else (k, v)
         })
diff --git a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
index f4f200ce..683de16b 100644
--- a/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -12,9 +12,9 @@ final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
 
   override def toString: String = {
     def writeRow(map: (BitPat, BitPat)): String =
-      s"${TruthTable.bpStr(map._1)}->${TruthTable.bpStr(map._2)}"
+      s"${map._1.rawString}->${map._2.rawString}"
 
-    (table.map(writeRow) ++ Seq(s"${" "*(inputWidth + 2)}${TruthTable.bpStr(default)}")).toSeq.sorted.mkString("\n")
+    (table.map(writeRow) ++ Seq(s"${" "*(inputWidth + 2)}${default.rawString}")).toSeq.sorted.mkString("\n")
   }
 
   def copy(table: Map[BitPat, BitPat] = this.table, default: BitPat = this.default) = new TruthTable(table, default)
@@ -51,11 +51,11 @@ object TruthTable {
       values.head._1 -> BitPat(s"b${
         Seq.tabulate(outputWidth) { i =>
           val outputSet = values.map(_._2)
-            .map(bpStr)
+            .map(_.rawString)
             .map(_ (i))
             .toSet
             .filterNot(_ == '?')
-          require(outputSet.size != 2, s"TruthTable conflict in :\n${values.map { case (i, o) => s"${bpStr(i)}->${bpStr(o)}" }.mkString("\n")}")
+          require(outputSet.size != 2, s"TruthTable conflict in :\n${values.map { case (i, o) => s"${i.rawString}->${o.rawString}" }.mkString("\n")}")
           outputSet.headOption.getOrElse('?')
         }.mkString
       }")
@@ -74,7 +74,7 @@ object TruthTable {
     table: TruthTable
   ): Seq[(TruthTable, Seq[Int])] = {
     def bpFilter(bitPat: BitPat, indexes: Seq[Int]): BitPat =
-      BitPat(s"b${bpStr(bitPat).zipWithIndex.filter(b => indexes.contains(b._2)).map(_._1).mkString}")
+      BitPat(s"b${bitPat.rawString.zipWithIndex.filter(b => indexes.contains(b._2)).map(_._1).mkString}")
 
     def tableFilter(indexes: Seq[Int]): Option[(TruthTable, Seq[Int])] = {
       if(indexes.nonEmpty) Some((TruthTable(
@@ -84,7 +84,7 @@ object TruthTable {
     }
 
     def index(bitPat: BitPat, bpType: Char): Seq[Int] =
-      bpStr(bitPat).zipWithIndex.filter(_._1 == bpType).map(_._2)
+      bitPat.rawString.zipWithIndex.filter(_._1 == bpType).map(_._2)
 
     Seq('1', '0', '?').flatMap(t => tableFilter(index(table.default, t)))
   }
@@ -99,7 +99,7 @@ object TruthTable {
     tables: Seq[(TruthTable, Seq[Int])]
   ): TruthTable = {
     def reIndex(bitPat: BitPat, table: TruthTable, indexes: Seq[Int]): Seq[(Char, Int)] =
-      bpStr(table.table.map(a => a._1.toString -> a._2).getOrElse(bitPat.toString, BitPat.dontCare(indexes.size))).zip(indexes)
+      (table.table.map(a => a._1.toString -> a._2).getOrElse(bitPat.toString, BitPat.dontCare(indexes.size))).rawString.zip(indexes)
     def bitPat(indexedChar: Seq[(Char, Int)]) = BitPat(s"b${indexedChar
       .sortBy(_._2)
       .map(_._1)
@@ -111,9 +111,7 @@ object TruthTable {
           key -> bitPat(tables.flatMap { case (table, indexes) => reIndex(key, table, indexes) })
         }
         .toMap,
-      bitPat(tables.flatMap { case (table, indexes) => bpStr(table.default).zip(indexes) })
+      bitPat(tables.flatMap { case (table, indexes) => table.default.rawString.zip(indexes) })
     )
   }
-
-  private def bpStr(bitPat: BitPat) = bitPat.toString.drop(7).dropRight(1)
 }
-- 
cgit v1.2.3