PRNG state UInt->Vec[Bool], make async reset safe

Changes the internal state of PRNG to use Vec[Bool] instead of UInt.
This fixes an @aswaterman identified future problem with asynchronous
reset.

A register with an asynchronous reset can only be reset to a literal.
Previously, an LFSR would store state as a UInt. If it was not
parameterized with a seed it should have its least significant bit
reset to something to avoid locking up. It's ideal to not reset the
full UInt (better test coverage, decreased reset fanout). However,
it's difficult to only reset one bit of a UInt. Conversely, it's
trivial to reset one bit of a Vec[Bool]. This also moves PRNG/LFSR
closer to a canonical representation of their internal state, i.e.,
it's natural to think of generalizing Vec[Bool] to arbitrary finite
fields (Vec[A <: Field]) whereas UInt is tightly coupled to GF2.

Minor updates:

- Updates/fixes to some scaladoc
- Add assertion to period test to make sure LFSR is changing

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>

7 files changed, 33 insertions, 34 deletions

diff --git a/src/main/scala/chisel3/util/random/FibonacciLFSR.scala b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala
index 53a42320..c61f0210 100644
--- a/src/main/scala/chisel3/util/random/FibonacciLFSR.scala
+++ b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala
@@ -47,7 +47,7 @@ class FibonacciLFSR(
   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)
+  def delta(s: Seq[Bool]): Seq[Bool] = taps.map{ case i => s(i - 1) }.reduce(reduction) +: s.dropRight(1)
 
 }
 
diff --git a/src/main/scala/chisel3/util/random/GaloisLFSR.scala b/src/main/scala/chisel3/util/random/GaloisLFSR.scala
index 3a61df95..85a6afde 100644
--- a/src/main/scala/chisel3/util/random/GaloisLFSR.scala
+++ b/src/main/scala/chisel3/util/random/GaloisLFSR.scala
@@ -45,18 +45,14 @@ class GaloisLFSR(
   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)
+  def delta(s: Seq[Bool]): Seq[Bool] = {
+    val first = s.head
+    (s.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
+      .map {
+        case (a, i) if taps(i + 1) && (i + 1 != s.size) => reduction(a, first)
+        case (a, _)                                     => a
       }
-    out.asUInt
   }
 
 }
diff --git a/src/main/scala/chisel3/util/random/LFSR.scala b/src/main/scala/chisel3/util/random/LFSR.scala
index 6663940c..a19f40d3 100644
--- a/src/main/scala/chisel3/util/random/LFSR.scala
+++ b/src/main/scala/chisel3/util/random/LFSR.scala
@@ -55,8 +55,8 @@ trait LFSR extends PRNG {
       }
     case None =>
       reduction match {
-        case XOR  => when (reset.toBool) { state := state(width-1, 1) ## 1.U }
-        case XNOR => when (reset.toBool) { state := state(width-1, 1) ## 0.U }
+        case XOR  => when (reset.toBool) { state(0) := 1.U }
+        case XNOR => when (reset.toBool) { state(0) := 0.U }
       }
   }
 
diff --git a/src/main/scala/chisel3/util/random/PRNG.scala b/src/main/scala/chisel3/util/random/PRNG.scala
index e665648c..c74759b0 100644
--- a/src/main/scala/chisel3/util/random/PRNG.scala
+++ b/src/main/scala/chisel3/util/random/PRNG.scala
@@ -10,14 +10,14 @@ import chisel3.util.Valid
   */
 class PRNGIO(val n: Int) extends Bundle {
 
-  /** A [[chisel3.util.Valid Valid]] interface that can be used to set the seed */
-  val seed = Input(Valid(UInt(n.W)))
+  /** A [[chisel3.util.Valid Valid]] interface that can be used to set the seed (internal PRNG state) */
+  val seed: Valid[Vec[Bool]] = Input(Valid(Vec(n, Bool())))
 
   /** When asserted, the PRNG will increment by one */
-  val increment = Input(Bool())
+  val increment: Bool = Input(Bool())
 
   /** The current state of the PRNG */
-  val out = Output(UInt(n.W))
+  val out: Vec[Bool] = Output(Vec(n, Bool()))
 }
 
 /** An abstract class representing a Pseudo Random Number Generator (PRNG)
@@ -35,25 +35,25 @@ abstract class PRNG(val width: Int, val seed: Option[BigInt], step: Int = 1, upd
 
   /** Internal state of the PRNG. If the user sets a seed, this is initialized to the seed. If the user does not set a
     * seed this is left uninitialized. In the latter case, a PRNG subclass *must do something to handle lockup*, e.g.,
-    * the PRNG state should be manually reset to a safe value. E.g., [[LFSR]] will, based on the chosen reduction
-    * operator, either set or reset the least significant bit of the state.
+    * the PRNG state should be manually reset to a safe value. [[LFSR]] handles this by, based on the chosen reduction
+    * operator, either sets or resets the least significant bit of the state.
     */
-  val state: UInt = seed match {
-    case Some(s) => RegInit(s.U(width.W))
-    case None    => Reg(UInt(width.W))
+  private [random] val state: Vec[Bool] = seed match {
+    case Some(s) => RegInit(VecInit(s.U(width.W).asBools))
+    case None    => Reg(Vec(width, Bool()))
   }
 
   /** State update function
     * @param s input state
     * @return the next state
     */
-  def delta(s: UInt): UInt
+  def delta(s: Seq[Bool]): Seq[Bool]
 
   /** The method that will be used to update the state of this PRNG
     * @param s input state
     * @return the next state after `step` applications of [[PRNG.delta]]
     */
-  final def nextState(s: UInt): UInt = (0 until step).foldLeft(s){ case (s, _) => delta(s) }
+  final def nextState(s: Seq[Bool]): Seq[Bool] = (0 until step).foldLeft(s){ case (s, _) => delta(s) }
 
   when (io.increment) {
     state := nextState(state)
@@ -80,7 +80,7 @@ object PRNG {
     prng.io.seed.valid := false.B
     prng.io.seed.bits := DontCare
     prng.io.increment := increment
-    prng.io.out
+    prng.io.out.asUInt
   }
 
 }
diff --git a/src/test/scala/chiselTests/LFSR16.scala b/src/test/scala/chiselTests/LFSR16.scala
index 992bb4bf..d0f06865 100644
--- a/src/test/scala/chiselTests/LFSR16.scala
+++ b/src/test/scala/chiselTests/LFSR16.scala
@@ -51,10 +51,15 @@ class LFSRMaxPeriod(gen: => UInt) extends BasicTester {
   val seed = withReset(!started) { RegInit(rv) }
 
   val (_, wrap) = Counter(started, math.pow(2.0, rv.getWidth).toInt - 1)
+
   when (rv === seed && started) {
     chisel3.assert(wrap)
     stop()
   }
+
+  val last = RegNext(rv)
+  chisel3.assert(rv =/= last, "LFSR last value (0b%b) was equal to current value (0b%b)", rv, last)
+
 }
 
 /** Check that the output of the new LFSR is the same asthe old LFSR */
diff --git a/src/test/scala/chiselTests/util/random/LFSRSpec.scala b/src/test/scala/chiselTests/util/random/LFSRSpec.scala
index 5aedca75..ce0abf69 100644
--- a/src/test/scala/chiselTests/util/random/LFSRSpec.scala
+++ b/src/test/scala/chiselTests/util/random/LFSRSpec.scala
@@ -12,7 +12,7 @@ import chiselTests.{ChiselFlatSpec, LFSRDistribution, LFSRMaxPeriod}
 import math.pow
 
 class FooLFSR(val reduction: LFSRReduce, seed: Option[BigInt]) extends PRNG(4, seed) with LFSR {
-  def delta(s: UInt): UInt = s
+  def delta(s: Seq[Bool]): Seq[Bool] = s
 }
 
 /** This tests that after reset an LFSR is not locked up. This manually sets the seed of the LFSR at run-time to the
@@ -30,20 +30,18 @@ class LFSRResetTester(gen: => LFSR, lockUpValue: BigInt) extends BasicTester {
 
   val (count, done) = Counter(true.B, 5)
 
-  printf("%d: 0b%b\n", count, lfsr.io.out)
-
   lfsr.io.seed.valid := count === 1.U
-  lfsr.io.seed.bits := lockUpValue.U
+  lfsr.io.seed.bits := lockUpValue.U(lfsr.width.W).asBools
   lfsr.io.increment := true.B
 
   when (count === 2.U) {
-    assert(lfsr.io.out === lockUpValue.U, "LFSR is NOT locked up, but should be!")
+    assert(lfsr.io.out.asUInt === lockUpValue.U, "LFSR is NOT locked up, but should be!")
   }
 
   lfsr.reset := count === 3.U
 
   when (count === 4.U) {
-    assert(lfsr.io.out =/= lockUpValue.U, "LFSR is locked up, but should not be after reset!")
+    assert(lfsr.io.out.asUInt =/= lockUpValue.U, "LFSR is locked up, but should not be after reset!")
   }
 
   when (done) {
diff --git a/src/test/scala/chiselTests/util/random/PRNGSpec.scala b/src/test/scala/chiselTests/util/random/PRNGSpec.scala
index 138a6ceb..341fb685 100644
--- a/src/test/scala/chiselTests/util/random/PRNGSpec.scala
+++ b/src/test/scala/chiselTests/util/random/PRNGSpec.scala
@@ -12,7 +12,7 @@ import chiselTests.ChiselFlatSpec
 class CyclePRNG(width: Int, seed: Option[BigInt], step: Int, updateSeed: Boolean)
     extends PRNG(width, seed, step, updateSeed) {
 
-  def delta(s: UInt): UInt = s ## s(width - 1)
+  def delta(s: Seq[Bool]): Seq[Bool] = s.last +: s.dropRight(1)
 
 }
 
@@ -49,10 +49,10 @@ class PRNGUpdateSeedTest(updateSeed: Boolean, seed: BigInt, expected: BigInt) ex
 
   a.io.increment := true.B
   a.io.seed.valid := count === 2.U
-  a.io.seed.bits := seed.U
+  a.io.seed.bits := seed.U(a.width.W).asBools
 
   when (count === 3.U) {
-    assert(a.io.out === expected.U, "Output didn't match!")
+    assert(a.io.out.asUInt === expected.U, "Output didn't match!")
   }
 
   when (done) {