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/TruthTable.scala') 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 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/TruthTable.scala') 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/TruthTable.scala') 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 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 --- 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/TruthTable.scala') 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 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 Co-authored-by: Boyang Han --- src/main/scala/chisel3/util/experimental/decode/TruthTable.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/main/scala/chisel3/util/experimental/decode/TruthTable.scala') 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) -- 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.--- .../chisel3/util/experimental/decode/TruthTable.scala | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) (limited to 'src/main/scala/chisel3/util/experimental/decode/TruthTable.scala') 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