From 7ce0f10f6c4723b99e6fdf20b37b706c8ae51c2e Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Mon, 6 May 2019 23:44:20 -0400
Subject: Add chisel3.util.random lib w/ LFSR generator

Builds out PRNG and LFSR type hierarchy. PRNG is the base class of
LFSR of which Galois and Fibonacci are concrete implementations.

PRNGs contain state (a UInt) and an update (delta) function. They have
a compile-time optional seed to set the PRNG state. The seed/state can
also be set at run-time. PRNGs can be run-time parameterized based on
how many updates they should do per cycle and whether or not to send
the seed through step-count state updates before loading it. (h/t
@jwright6323)

LFSRs are parameterized in a reduction operation (XOR or XNOR). An
LFSR that does NOT have a seed will be automatically initialized to a
minimally safe state (set/reset one bit) based on their reduction
operation. (h/t @aswaterman)

Adds Galois and Fibonacci LFSRs that define appropriate update
functions. Companion objects provide helpers to automatically generate
maximal period variants. Taps are provide for a very large set of
widths. The LFSR companion object provides an apply method to generate
a Fibonacci LFSR random variable (like the old LFSR16).
---
 .../scala/chisel3/util/random/FibonacciLFSR.scala  | 108 +++++++++++++++++++++
 1 file changed, 108 insertions(+)
 create mode 100644 src/main/scala/chisel3/util/random/FibonacciLFSR.scala

(limited to 'src/main/scala/chisel3/util/random/FibonacciLFSR.scala')

diff --git a/src/main/scala/chisel3/util/random/FibonacciLFSR.scala b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala
new file mode 100644
index 00000000..53a42320
--- /dev/null
+++ b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala
@@ -0,0 +1,108 @@
+// See LICENSE for license details.
+
+package chisel3.util.random
+
+import chisel3._
+
+/** Fibonacci Linear Feedback Shift Register (LFSR) generator.
+  *
+  * A Fibonacci LFSR can be generated by defining a width and a set of tap points (corresponding to a polynomial). An
+  * optional 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 Fibonacci LFSR is constructed. 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 FibonacciLFSR(4, Set(4, 3))
+  * //                 +---+
+  * // +-------------->|XOR|-------------------------------------------------------+
+  * // |               +---+                                                       |
+  * // |   +-------+     ^     +-------+           +-------+           +-------+   |
+  * // |   |       |     |     |       |           |       |           |       |   |
+  * // +---+  x^4  |<----+-----|  x^3  |<----------|  x^2  |<----------|  x^1  |<--+
+  * //     |       |           |       |           |       |           |       |
+  * //     +-------+           +-------+           +-------+           +-------+
+  * }}}
+  *
+  * If you require a maximal period Fibonacci LFSR of a specific width, you can use [[MaxPeriodFibonacciLFSR]]. If you
+  * only require a pseudorandom [[UInt]] you can use the [[FibonacciLFSR$ FibonacciLFSR companion
+  * object]].
+  * @see [[https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Fibonacci_LFSRs]]
+  * $paramWidth
+  * $paramTaps
+  * $paramSeed
+  * $paramReduction
+  * $paramStep
+  * $paramUpdateSeed
+  */
+class FibonacciLFSR(
+  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 = s(width-2,0) ## taps.map{ case i => s(i - 1) }.reduce(reduction)
+
+}
+
+/** A maximal period Fibonacci Linear Feedback Shift Register (LFSR) generator. The maximal period taps are sourced from
+  * [[LFSR.tapsMaxPeriod LFSR.tapsMaxPeriod]].
+  * {{{
+  * val lfsr8 = Module(new MaxPeriodFibonacciLFSR(8))
+  * }}}
+  * $paramWidth
+  * $paramSeed
+  * $paramReduction
+  */
+class MaxPeriodFibonacciLFSR(width: Int, seed: Option[BigInt] = Some(1), reduction: LFSRReduce = XOR)
+    extends FibonacciLFSR(width, LFSR.tapsMaxPeriod.getOrElse(width, LFSR.badWidth(width)).head, seed, reduction)
+
+/** Utility for generating a pseudorandom [[UInt]] from a [[FibonacciLFSR]].
+  *
+  * For example, to generate a pseudorandom 8-bit [[UInt]] that changes every cycle, you can use:
+  * {{{
+  * val pseudoRandomNumber = FibonacciLFSR.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 FibonacciLFSR {
+
+  /** 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 FibonacciLFSR(width, taps, seed, reduction), increment)
+
+  /** Return a pseudorandom [[UInt]] generated using a maximal period [[FibonacciLFSR]]
+    * $paramWidth
+    * $paramIncrement
+    * $paramSeed
+    * $paramReduction
+    */
+  def maxPeriod(
+    width: Int,
+    increment: Bool = true.B,
+    seed: Option[BigInt] = Some(1),
+    reduction: LFSRReduce = XOR): UInt = PRNG(new MaxPeriodFibonacciLFSR(width, seed, reduction), increment)
+
+}
-- 
cgit v1.2.3