Add Lfsr tests

Add LFSR tests using LFSR16 testing infrastructure. This also adds
tests that are the same as the examples shown for LFSR scaladoc.

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

2 files changed, 208 insertions, 0 deletions

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))
+  }
+
+}