Espresso Decoder (#1964)

Co-authored-by: Haoran Yuan <sinofp@tuta.io>
Co-authored-by: Boyang Han <yqszxx@gmail.com>

5 files changed, 157 insertions, 1 deletions

diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
index 6d68ad1a..b2620d2f 100644
--- a/.github/workflows/test.yml
+++ b/.github/workflows/test.yml
@@ -19,6 +19,7 @@ jobs:
         scala: ["2.13.6", "2.12.13"]
         verilator: ["4.204"]
         z3: ["4.8.10"]
+        espresso: ["2.4"]
     runs-on: ${{ matrix.system }}
 
     steps:
@@ -74,6 +75,28 @@ jobs:
           sudo make install
           verilator --version
 
+      - name: Cache Espresso ${{ matrix.espresso }}
+        uses: actions/cache@v2
+        id: cache-espresso
+        with:
+          path: espresso-${{ matrix.espresso }}
+          key: ${{ matrix.system }}-espresso-${{ matrix.espresso }}
+      - name: Compile Espresso ${{ matrix.espresso }}
+        if: steps.cache-espresso.outputs.cache-hit != 'true'
+        run: |
+          wget https://github.com/chipsalliance/espresso/archive/refs/tags/v${{ matrix.espresso }}.tar.gz
+          tar xvf v${{ matrix.espresso }}.tar.gz
+          cd espresso-${{ matrix.espresso }}
+          mkdir -p build
+          cd build
+          cmake ..
+          make
+      - name: Install Espresso ${{ matrix.espresso }}
+        run: |
+          cd espresso-${{ matrix.espresso }}/build
+          sudo make install
+
+
       - name: Setup Scala
         uses: olafurpg/setup-scala@v10
         with:
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)
+    }
+  }
 }
diff --git a/src/test/scala/chiselTests/util/experimental/minimizer/EspressoSpec.scala b/src/test/scala/chiselTests/util/experimental/minimizer/EspressoSpec.scala
new file mode 100644
index 00000000..f3270cae
--- /dev/null
+++ b/src/test/scala/chiselTests/util/experimental/minimizer/EspressoSpec.scala
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chiselTests.util.experimental.minimizer
+import chisel3.util.experimental.decode.EspressoMinimizer
+import chisel3.util.experimental.decode.Minimizer
+
+class EspressoSpec extends MinimizerSpec {
+  override def minimizer: Minimizer = EspressoMinimizer
+}