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, 42 insertions, 10 deletions

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