Merge pull request #1088 from freechipsproject/lfsr

- Add chisel3.util.random package with Galois and Fibonacci LFSRs
- Add maximal period LFSR generation and maximal period taps
- Deprecate chisel3.util.LFSR16 in favor of chisel3.util.random.LFSR(16)

1 files changed, 118 insertions, 0 deletions

diff --git a/src/main/scala/chisel3/util/random/GaloisLFSR.scala b/src/main/scala/chisel3/util/random/GaloisLFSR.scala
new file mode 100644
index 00000000..3a61df95
--- /dev/null
+++ b/src/main/scala/chisel3/util/random/GaloisLFSR.scala
@@ -0,0 +1,118 @@
+// See LICENSE for license details.
+
+package chisel3.util.random
+
+import chisel3._
+
+/** Galois Linear Feedback Shift Register (LFSR) generator.
+  *
+  * A Galois LFSR can be generated by defining a width and a set of tap points. Optionally, an initial seed and a
+  * reduction operation ([[XOR]], the default, or [[XNOR]]) can be used to augment the generated hardware. The resulting
+  * hardware has support for a run-time programmable seed (via [[PRNGIO.seed]]) and conditional increment (via
+  * [[PRNGIO.increment]]).
+  *
+  * $seedExplanation
+  *
+  * In the example below, a 4-bit LFSR Fibonacci LFSR is constructed. The tap points are defined as four and three
+  * (using LFSR convention of indexing from one). This results in the hardware configuration shown in the diagram.
+  *
+  * {{{
+  * val lfsr4 = Module(new GaloisLFSR(4, Set(4, 3))
+  * // +-----------------+---------------------------------------------------------+
+  * // |                 |                                                         |
+  * // |   +-------+     v     +-------+           +-------+           +-------+   |
+  * // |   |       |   +---+   |       |           |       |           |       |   |
+  * // +-->|  x^4  |-->|XOR|-->|  x^3  |---------->|  x^2  |---------->|  x^1  |---+
+  * //     |       |   +---+   |       |           |       |           |       |
+  * //     +-------+           +-------+           +-------+           +-------+
+  * }}}
+  *
+  * If you require a maximal period Galois LFSR of a specific width, you can use [[MaxPeriodGaloisLFSR]]. If you only
+  * require a pseudorandom [[UInt]] you can use the [[GaloisLFSR$ GaloisLFSR companion object]].
+  * @see [[https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Galois_LFSRs]]
+  * $paramWidth
+  * $paramTaps
+  * $paramSeed
+  * $paramReduction
+  * $paramStep
+  * $paramUpdateSeed
+  */
+class GaloisLFSR(
+  width: Int,
+  taps: Set[Int],
+  seed: Option[BigInt] = Some(1),
+  val reduction: LFSRReduce = XOR,
+  step: Int = 1,
+  updateSeed: Boolean = false) extends PRNG(width, seed, step, updateSeed) with LFSR {
+
+  def delta(s: UInt): UInt = {
+    val in = s.asBools
+    val first = in.head
+    val out = Wire(Vec(s.getWidth, Bool()))
+    out
+      .zip(in.tail :+ first)
+      .zipWithIndex
+      .foreach {
+        case ((l, r), i) if taps(i + 1) && (i + 1 != out.size) => l := reduction(r, first)
+        case ((l, r), _)                                       => l := r
+      }
+    out.asUInt
+  }
+
+}
+
+/** A maximal period Galois Linear Feedback Shift Register (LFSR) generator. The maximal period taps are sourced from
+  * [[LFSR.tapsMaxPeriod LFSR.tapsMaxPeriod]].
+  * {{{
+  * val lfsr8 = Module(new MaxPeriodGaloisLFSR(8))
+  * }}}
+  * $paramWidth
+  * $paramSeed
+  * $paramReduction
+  */
+class MaxPeriodGaloisLFSR(width: Int, seed: Option[BigInt] = Some(1), reduction: LFSRReduce = XOR)
+    extends GaloisLFSR(width, LFSR.tapsMaxPeriod.getOrElse(width, LFSR.badWidth(width)).head, seed, reduction)
+
+/** Utility for generating a pseudorandom [[UInt]] from a [[GaloisLFSR]].
+  *
+  * For example, to generate a pseudorandom 8-bit [[UInt]] that changes every cycle, you can use:
+  * {{{
+  * val pseudoRandomNumber = GaloisLFSR.maxPeriod(8)
+  * }}}
+  *
+  * @define paramWidth @param width of pseudorandom output
+  * @define paramTaps @param taps a set of tap points to use when constructing the LFSR
+  * @define paramIncrement @param increment when asserted, a new random value will be generated
+  * @define paramSeed @param seed an initial value for internal LFSR state
+  * @define paramReduction @param reduction the reduction operation (either [[XOR]] or
+  * [[XNOR]])
+  */
+object GaloisLFSR {
+
+  /** Return a pseudorandom [[UInt]] generated from a [[FibonacciLFSR]].
+    * $paramWidth
+    * $paramTaps
+    * $paramIncrement
+    * $paramSeed
+    * $paramReduction
+    */
+  def apply(
+    width: Int,
+    taps: Set[Int],
+    increment: Bool = true.B,
+    seed: Option[BigInt] = Some(1),
+    reduction: LFSRReduce = XOR): UInt = PRNG(new GaloisLFSR(width, taps, seed, reduction), increment)
+
+  /** Return a pseudorandom [[UInt]] generated using a maximal period [[GaloisLFSR]]
+    * $paramWidth
+    * $paramIncrement
+    * $paramSeed
+    * $paramReduction
+    */
+  def maxPeriod(
+    width: Int,
+    increment: Bool = true.B,
+    seed: Option[BigInt] = Some(1),
+    reduction: LFSRReduce = XOR): UInt = PRNG(new MaxPeriodGaloisLFSR(width, seed, reduction), increment)
+
+}