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)

5 files changed, 259 insertions, 17 deletions

diff --git a/src/test/scala/chiselTests/InstanceNameSpec.scala b/src/test/scala/chiselTests/InstanceNameSpec.scala
index 30dc46ba..7bb91b94 100644
--- a/src/test/scala/chiselTests/InstanceNameSpec.scala
+++ b/src/test/scala/chiselTests/InstanceNameSpec.scala
@@ -3,6 +3,7 @@
 package chiselTests
 
 import chisel3._
+import chisel3.util.Queue
 import chisel3.experimental.{DataMirror, FixedPoint}
 import chisel3.testers.BasicTester
 
@@ -17,7 +18,7 @@ class InstanceNameModule extends Module {
     val foo = UInt(8.W)
   }
 
-  val q = Module(new util.Queue(UInt(32.W), 4))
+  val q = Module(new Queue(UInt(32.W), 4))
 
   io.bar := io.foo + x
 }
diff --git a/src/test/scala/chiselTests/LFSR16.scala b/src/test/scala/chiselTests/LFSR16.scala
index 54a3591f..992bb4bf 100644
--- a/src/test/scala/chiselTests/LFSR16.scala
+++ b/src/test/scala/chiselTests/LFSR16.scala
@@ -5,6 +5,7 @@ package chiselTests
 import chisel3._
 import chisel3.testers.BasicTester
 import chisel3.util._
+import chisel3.util.random.{PRNG, LFSR}
 
 /**
   * This test creates two 4 sided dice.
@@ -12,14 +13,16 @@ import chisel3.util._
   * The asserts check that the bins show the correct distribution.
   */
 //scalastyle:off magic.number
-class LFSRTester extends BasicTester {
+class LFSRDistribution(gen: => UInt, cycles: Int = 10000) extends BasicTester {
+
+  val rv = gen
   val bins = Reg(Vec(8, UInt(32.W)))
 
   // Use tap points on each LFSR so values are more independent
-  val die0 = Cat(Seq.tabulate(2) { i => LFSR16()(i) })
-  val die1 = Cat(Seq.tabulate(2) { i => LFSR16()(i + 2) })
+  val die0 = Cat(Seq.tabulate(2) { i => rv(i) })
+  val die1 = Cat(Seq.tabulate(2) { i => rv(i + 2) })
 
-  val (trial, done) = Counter(true.B, 10000)
+  val (trial, done) = Counter(true.B, cycles)
 
   val rollValue = die0 +& die1  // Note +& is critical because sum will need an extra bit.
 
@@ -41,24 +44,53 @@ class LFSRTester extends BasicTester {
   }
 }
 
-class LFSR16MaxPeriod extends BasicTester {
+class LFSRMaxPeriod(gen: => UInt) extends BasicTester {
 
-  val lfsr16 = LFSR16()
+  val rv = gen
   val started = RegNext(true.B, false.B)
+  val seed = withReset(!started) { RegInit(rv) }
 
-  val (_, wrap) = Counter(started, math.pow(2.0, 16).toInt - 1)
-  when (lfsr16 === 1.U && started) {
+  val (_, wrap) = Counter(started, math.pow(2.0, rv.getWidth).toInt - 1)
+  when (rv === seed && started) {
     chisel3.assert(wrap)
     stop()
   }
 }
 
+/** Check that the output of the new LFSR is the same asthe old LFSR */
+class MeetTheNewLFSR16SameAsTheOldLFSR16 extends BasicTester {
+
+  /** This is the exact implementation of the old LFSR16 algorithm */
+  val oldLfsr = {
+    val width = 16
+    val lfsr = RegInit(1.U(width.W))
+    lfsr := Cat(lfsr(0)^lfsr(2)^lfsr(3)^lfsr(5), lfsr(width-1,1))
+    lfsr
+  }
+
+  /** The new LFSR16 uses equivalent taps and a reverse so that it can use LFSR(16) under the hood. */
+  val newLfsr = LFSR16()
+
+  val (_, done) = Counter(true.B, 16)
+
+  assert(oldLfsr === newLfsr)
+
+  when (done) {
+    stop()
+  }
+
+}
+
 class LFSRSpec extends ChiselPropSpec {
   property("LFSR16 can be used to produce pseudo-random numbers, this tests the distribution") {
-    assertTesterPasses{ new LFSRTester }
+    assertTesterPasses{ new LFSRDistribution(LFSR16()) }
   }
 
   property("LFSR16 period tester, Period should 2^16 - 1") {
-    assertTesterPasses { new LFSR16MaxPeriod }
+    assertTesterPasses{ new LFSRMaxPeriod(LFSR16()) }
+  }
+
+  property("New LFSR16 is the same as the old LFSR16") {
+    assertTesterPasses{ new MeetTheNewLFSR16SameAsTheOldLFSR16 }
   }
 }
diff --git a/src/test/scala/chiselTests/QueueSpec.scala b/src/test/scala/chiselTests/QueueSpec.scala
index 3f723ecf..994f3e6d 100644
--- a/src/test/scala/chiselTests/QueueSpec.scala
+++ b/src/test/scala/chiselTests/QueueSpec.scala
@@ -9,6 +9,7 @@ import org.scalacheck._
 import chisel3._
 import chisel3.testers.BasicTester
 import chisel3.util._
+import chisel3.util.random.LFSR
 
 class ThingsPassThroughTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: Int) extends BasicTester {
   val q = Module(new Queue(UInt(bitWidth.W), queueDepth))
@@ -19,7 +20,7 @@ class ThingsPassThroughTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int
   val outCnt = Counter(elements.length + 1)
 
   q.io.enq.valid := (inCnt.value < elements.length.U)
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
 
   q.io.enq.bits := elems(inCnt.value)
   when(q.io.enq.fire()) {
@@ -47,7 +48,7 @@ class QueueReasonableReadyValid(elements: Seq[Int], queueDepth: Int, bitWidth: I
   //Queue should be full or ready
   assert(q.io.enq.ready || q.io.count === queueDepth.U)
 
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
   //Queue should be empty or valid
   assert(q.io.deq.valid || q.io.count === 0.U)
 
@@ -72,7 +73,7 @@ class CountIsCorrectTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, t
   val outCnt = Counter(elements.length + 1)
 
   q.io.enq.valid := (inCnt.value < elements.length.U)
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
 
   q.io.enq.bits := elems(inCnt.value)
   when(q.io.enq.fire()) {
@@ -99,7 +100,7 @@ class QueueSinglePipeTester(elements: Seq[Int], bitWidth: Int, tap: Int) extends
   val outCnt = Counter(elements.length + 1)
 
   q.io.enq.valid := (inCnt.value < elements.length.U)
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
 
   assert(q.io.enq.ready || (q.io.count === 1.U && !q.io.deq.ready))
 
@@ -125,7 +126,7 @@ class QueuePipeTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: I
   val outCnt = Counter(elements.length + 1)
 
   q.io.enq.valid := (inCnt.value < elements.length.U)
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
 
   assert(q.io.enq.ready || (q.io.count === queueDepth.U && !q.io.deq.ready))
 
@@ -154,7 +155,7 @@ class QueueFlowTester(elements: Seq[Int], queueDepth: Int, bitWidth: Int, tap: I
   //Queue should be full or ready
   assert(q.io.enq.ready || q.io.count === queueDepth.U)
 
-  q.io.deq.ready := LFSR16()(tap)
+  q.io.deq.ready := LFSR(16)(tap)
   //Queue should be empty or valid
   assert(q.io.deq.valid || (q.io.count === 0.U && !q.io.enq.fire()))
 
diff --git a/src/test/scala/chiselTests/util/random/LFSRSpec.scala b/src/test/scala/chiselTests/util/random/LFSRSpec.scala
new file mode 100644
index 00000000..5aedca75
--- /dev/null
+++ b/src/test/scala/chiselTests/util/random/LFSRSpec.scala
@@ -0,0 +1,118 @@
+// See LICENSE for license details.
+
+package chiselTests.util.random
+
+import chisel3._
+import chisel3.util.{Counter, Enum}
+import chisel3.util.random._
+import chisel3.testers.BasicTester
+
+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
+}
+
+/** This tests that after reset an LFSR is not locked up. This manually sets the seed of the LFSR at run-time to the
+  * value that would cause it to lock up. It then asserts reset. The next cycle it checks that the value is NOT the
+  * locked up value.
+  * @param gen an LFSR to test
+  * @param lockUpValue the value that would lock up the LFSR
+  */
+class LFSRResetTester(gen: => LFSR, lockUpValue: BigInt) extends BasicTester {
+
+  val lfsr = Module(gen)
+  lfsr.io.seed.valid := false.B
+  lfsr.io.seed.bits := DontCare
+  lfsr.io.increment := true.B
+
+  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.increment := true.B
+
+  when (count === 2.U) {
+    assert(lfsr.io.out === 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!")
+  }
+
+  when (done) {
+    stop()
+  }
+
+}
+
+class LFSRSpec extends ChiselFlatSpec {
+
+  def periodCheck(gen: (Int, Set[Int], LFSRReduce) => PRNG, reduction: LFSRReduce, range: Range): Unit = {
+    it should s"have a maximal period over a range of widths (${range.head} to ${range.last}) using ${reduction.getClass}" in {
+      range
+        .foreach{ width =>
+          LFSR.tapsMaxPeriod(width).foreach{ taps =>
+            info(s"""width $width okay using taps: ${taps.mkString(", ")}""")
+            assertTesterPasses(new LFSRMaxPeriod(PRNG(gen(width, taps, reduction))))
+          }
+        }
+    }
+  }
+
+  behavior of "LFSR"
+
+  it should "throw an exception if initialized to a seed of zero for XOR configuration" in {
+    { the [IllegalArgumentException] thrownBy elaborate(new FooLFSR(XOR, Some(0))) }
+      .getMessage should include ("Seed cannot be zero")
+  }
+
+  it should "throw an exception if initialized to a seed of all ones for XNOR configuration" in {
+    { the [IllegalArgumentException] thrownBy elaborate(new FooLFSR(XNOR, Some(15))) }
+      .getMessage should include ("Seed cannot be all ones")
+  }
+
+  it should "reset correctly without a seed for XOR configuration" in {
+    assertTesterPasses(new LFSRResetTester(new FooLFSR(XOR, None), 0))
+  }
+
+  it should "reset correctly without a seed for XNOR configuration" in {
+    assertTesterPasses(new LFSRResetTester(new FooLFSR(XNOR, None), 15))
+  }
+
+  behavior of "MaximalPeriodGaloisLFSR"
+
+  it should "throw an exception if no LFSR taps are known" in {
+    { the [IllegalArgumentException] thrownBy elaborate(new MaxPeriodGaloisLFSR(787)) }
+      .getMessage should include ("No max period LFSR taps stored for requested width")
+  }
+
+  periodCheck((w: Int, t: Set[Int], r: LFSRReduce) => new GaloisLFSR(w, t, reduction=r), XOR, 2 to 16)
+  periodCheck((w: Int, t: Set[Int], r: LFSRReduce) => new GaloisLFSR(w, t, reduction=r), XNOR, 2 to 16)
+
+  ignore should "have a sane distribution for larger widths" in {
+    ((17 to 32) ++ Seq(64, 128, 256, 512, 1024, 2048, 4096))
+      .foreach{ width =>
+        info(s"width $width okay!")
+        assertTesterPasses(new LFSRDistribution(LFSR(width), math.pow(2, 22).toInt))
+      }
+  }
+
+  behavior of "MaximalPeriodFibonacciLFSR"
+
+  periodCheck((w: Int, t: Set[Int], r: LFSRReduce) => new FibonacciLFSR(w, t, reduction=r), XOR, 2 to 16)
+  periodCheck((w: Int, t: Set[Int], r: LFSRReduce) => new FibonacciLFSR(w, t, reduction=r), XNOR, 2 to 16)
+
+  behavior of "LFSR maximal period taps"
+
+  it should "contain all the expected widths" in {
+    ((2 to 786) ++ Seq(1024, 2048, 4096)).foreach(LFSR.tapsMaxPeriod.keys should contain (_))
+  }
+
+}
diff --git a/src/test/scala/chiselTests/util/random/PRNGSpec.scala b/src/test/scala/chiselTests/util/random/PRNGSpec.scala
new file mode 100644
index 00000000..138a6ceb
--- /dev/null
+++ b/src/test/scala/chiselTests/util/random/PRNGSpec.scala
@@ -0,0 +1,90 @@
+// See LICENSE for license details.
+
+package chiselTests.util.random
+
+import chisel3._
+import chisel3.testers.BasicTester
+import chisel3.util.Counter
+import chisel3.util.random.PRNG
+
+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)
+
+}
+
+class PRNGStepTest extends BasicTester {
+
+  val count2: UInt = Counter(true.B, 2)._1
+  val count4: UInt = Counter(true.B, 4)._1
+
+  val a: UInt = PRNG(new CyclePRNG(16, Some(1), 1, false), true.B)
+  val b: UInt = PRNG(new CyclePRNG(16, Some(1), 2, false), count2 === 1.U)
+  val c: UInt = PRNG(new CyclePRNG(16, Some(1), 4, false), count4 === 3.U)
+
+  val (_, done) = Counter(true.B, 16)
+
+  when (count2 === 0.U) {
+    assert(a === b, "1-step and 2-step PRNGs did not agree! (0b%b != 0b%b)", a, b)
+  }
+
+  when (count4 === 0.U) {
+    assert(a === c, "1-step and 4-step PRNGs did not agree!")
+  }
+
+  when (done) {
+    stop()
+  }
+
+}
+
+class PRNGUpdateSeedTest(updateSeed: Boolean, seed: BigInt, expected: BigInt) extends BasicTester {
+
+  val a: CyclePRNG = Module(new CyclePRNG(16, Some(1), 1, updateSeed))
+
+  val (count, done) = Counter(true.B, 4)
+
+  a.io.increment := true.B
+  a.io.seed.valid := count === 2.U
+  a.io.seed.bits := seed.U
+
+  when (count === 3.U) {
+    assert(a.io.out === expected.U, "Output didn't match!")
+  }
+
+  when (done) {
+    stop()
+  }
+
+}
+
+class PRNGSpec extends ChiselFlatSpec {
+
+  behavior of "PRNG"
+
+  it should "throw an exception if the step size is < 1" in {
+    { the [IllegalArgumentException] thrownBy elaborate(new CyclePRNG(0, Some(1), 1, true)) }
+      .getMessage should include ("Width must be greater than zero!")
+  }
+
+  it should "throw an exception if the step size is <= 0" in {
+    { the [IllegalArgumentException] thrownBy elaborate(new CyclePRNG(1, Some(1), 0, true)) }
+      .getMessage should include ("Step size must be greater than one!")
+  }
+
+  it should "handle non-unary steps" in {
+    assertTesterPasses(new PRNGStepTest)
+  }
+
+  it should "handle state update without and with updateSeed enabled" in {
+    info("without updateSeed okay!")
+    assertTesterPasses(new PRNGUpdateSeedTest(false, 3, 3))
+
+    info("with updateSeed okay!")
+    assertTesterPasses(new PRNGUpdateSeedTest(true, 3, 6))
+  }
+
+}