Merge branch 'master' into 3.5-release

6 files changed, 622 insertions, 0 deletions

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..2b50ef90
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/DecodeTableAnnotation.scala
@@ -0,0 +1,22 @@
+// SPDX-License-Identifier: Apache-2.0
+
+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,
+  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/EspressoMinimizer.scala b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
new file mode 100644
index 00000000..1d725875
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/EspressoMinimizer.scala
@@ -0,0 +1,73 @@
+// 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.rawString.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
+    }
+
+    val input = writeTable(table)
+    logger.trace(s"""espresso input table:
+                    |$input
+                    |""".stripMargin)
+    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:
+                    |$output
+                    |""".stripMargin)
+    TruthTable(readTable(output), table.default)
+  }
+}
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
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..c1533f44
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/QMCMinimizer.scala
@@ -0,0 +1,298 @@
+// 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)))
+      // 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
+      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
+    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
+      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) }.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) }.keys.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):_*)
+        )
+      )
+
+      // 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))
+        }
+        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(_ < _)
+
+      // O(len(primeImplicants) ^ 4)
+      val (essentialPrimeImplicants, nonessentialPrimeImplicants, uncoveredImplicants) =
+        getEssentialPrimeImplicants(primeImplicants, implicants)
+
+      (essentialPrimeImplicants ++ getCover(nonessentialPrimeImplicants, uncoveredImplicants)).map(a => (a.bp, outputBp))
+    })
+
+    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.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)
+        })
+      } else {
+        tb.copy(table = tb.table + t)
+      }
+    }
+  }
+}
\ No newline at end of file
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..683de16b
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/TruthTable.scala
@@ -0,0 +1,117 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util.experimental.decode
+
+import chisel3.util.BitPat
+
+final class TruthTable(val table: Map[BitPat, BitPat], val default: BitPat) {
+
+  def inputWidth = table.head._1.getWidth
+
+  def outputWidth = table.head._2.getWidth
+
+  override def toString: String = {
+    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")
+  }
+
+  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))
+        .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 = {
+    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) =>
+      // merge same input inputs.
+      values.head._1 -> BitPat(s"b${
+        Seq.tabulate(outputWidth) { i =>
+          val outputSet = values.map(_._2)
+            .map(_.rawString)
+            .map(_ (i))
+            .toSet
+            .filterNot(_ == '?')
+          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
+      }")
+    }, 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${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(
+        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] =
+      bitPat.rawString.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)] =
+      (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)
+      .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) => 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
new file mode 100644
index 00000000..42e374d1
--- /dev/null
+++ b/src/main/scala/chisel3/util/experimental/decode/decoder.scala
@@ -0,0 +1,83 @@
+// 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 {
+  /** 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)
+    }.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)
+      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
+    }
+  }
+
+  /** 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)
+    }
+  }
+}