1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
// SPDX-License-Identifier: Apache-2.0
package chisel3.util.experimental.decode
import chisel3.util.BitPat
import scala.collection.mutable
sealed class TruthTable private (val table: Seq[(BitPat, BitPat)], val default: BitPat, val sort: Boolean) {
def inputWidth = table.head._1.getWidth
def outputWidth = table.head._2.getWidth
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}")).mkString("\n")
}
def copy(table: Seq[(BitPat, BitPat)] = this.table, default: BitPat = this.default, sort: Boolean = this.sort) =
TruthTable(table, default, sort)
override def equals(y: Any): Boolean = {
y match {
case y: TruthTable => toString == y.toString
case _ => false
}
}
}
object TruthTable {
/** Pad the input signals to equalize all input widths. Pads input signals
* to the maximum width found in the table.
*
* @param table the truth table whose rows will be padded
* @return the same truth table but with inputs padded
*/
private def padInputs(table: Iterable[(BitPat, BitPat)]): Iterable[(BitPat, BitPat)] = {
val inputWidth = table.map(_._1.getWidth).max
table.map {
case (in, out) if inputWidth > in.width =>
(BitPat.N(inputWidth - in.width) ## in, out)
case (in, out) => (in, out)
}
}
/** For each duplicated input, collect the outputs into a single Seq.
*
* @param table the truth table
* @return a Seq of tuple of length 2, where the first element is the
* input and the second element is a Seq of OR-ed outputs
* for the input
*/
private def mergeTableOnInputs(table: Iterable[(BitPat, BitPat)]): Seq[(BitPat, Seq[BitPat])] = {
groupByIntoSeq(table)(_._1).map {
case (input, mappings) =>
input -> mappings.map(_._2)
}
}
/** Merge two BitPats by OR-ing the values and masks, and setting the
* width to the max width among the two
*/
private def merge(a: BitPat, b: BitPat): BitPat = {
new BitPat(a.value | b.value, a.mask | b.mask, a.width.max(b.width))
}
/** Public method for calling with the Espresso decoder format fd
*
* For Espresso, for each output, a 1 means this product term belongs to the ON-set,
* a 0 means this product term has no meaning for the value of this function.
* This is the same as the fd (or f) type in espresso.
*
* @param table the truth table
* @param default the default BitPat is made up of a single bit type, either "?", "0" or "1".
* A default of "?" sets Espresso to fr-format, while a "0" or "1" sets it to the
* fd-format.
* @param sort whether to sort the final truth table using BitPat.bitPatOrder
* @return a fully built TruthTable
*/
def fromEspressoOutput(table: Iterable[(BitPat, BitPat)], default: BitPat, sort: Boolean = true): TruthTable = {
apply_impl(table, default, sort, false)
}
/** Public apply method to TruthTable. Calls apply_impl with the default value true of checkCollisions */
def apply(table: Iterable[(BitPat, BitPat)], default: BitPat, sort: Boolean = true): TruthTable = {
apply_impl(table, default, sort, true)
}
/** Convert a table and default output into a [[TruthTable]]. */
private def apply_impl(
table: Iterable[(BitPat, BitPat)],
default: BitPat,
sort: Boolean,
checkCollisions: Boolean
): TruthTable = {
val paddedTable = padInputs(table)
require(table.map(_._2.getWidth).toSet.size == 1, "output width not equal.")
val mergedTable = mergeTableOnInputs(paddedTable)
val finalTable: Seq[(BitPat, BitPat)] = mergedTable.map {
case (input, outputs) =>
val (result, noCollisions) = outputs.tail.foldLeft((outputs.head, checkCollisions)) {
case ((acc, ok), o) => (merge(acc, o), ok && acc.overlap(o))
}
// Throw an error if checkCollisions is true but there are bits with a non-zero overlap.
require(!checkCollisions || noCollisions, s"TruthTable conflict on merged row:\n $input -> $outputs")
(input, result)
}
import BitPat.bitPatOrder
new TruthTable(if (sort) finalTable.sorted else finalTable, default, sort)
}
/** Parse TruthTable from its string representation. */
def fromString(tableString: String): TruthTable = {
TruthTable(
tableString
.split("\n")
.filter(_.contains("->"))
.map(_.split("->").map(str => BitPat(s"b$str")))
.map(bps => bps(0) -> bps(1))
.toSeq,
BitPat(s"b${tableString.split("\n").filterNot(_.contains("->")).head.replace(" ", "")}")
)
}
/** consume 1 table, split it into up to 3 tables with the same default bits.
*
* @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)
.collectFirst { case (k, v) if k == bitPat.toString => v }
.getOrElse(BitPat.dontCare(indexes.size))
.rawString
.zip(indexes)
def bitPat(indexedChar: Seq[(Char, Int)]) = BitPat(s"b${indexedChar
.sortBy(_._2)
.map(_._1)
.mkString}")
TruthTable(
tables
.flatMap(_._1.table.map(_._1))
.map { key =>
key -> bitPat(tables.flatMap { case (table, indexes) => reIndex(key, table, indexes) })
},
bitPat(tables.flatMap { case (table, indexes) => table.default.rawString.zip(indexes) })
)
}
/** Similar to Seq.groupBy except that it preserves ordering of elements within each group */
private def groupByIntoSeq[A, K](xs: Iterable[A])(f: A => K): Seq[(K, Seq[A])] = {
val map = mutable.LinkedHashMap.empty[K, mutable.ListBuffer[A]]
for (x <- xs) {
val key = f(x)
val l = map.getOrElseUpdate(key, mutable.ListBuffer.empty[A])
l += x
}
map.view.map({ case (k, vs) => k -> vs.toList }).toList
}
}
|
