From 723cfb0cbe5e20db02637c194f129e57d4071ee2 Mon Sep 17 00:00:00 2001 From: Schuyler Eldridge Date: Mon, 6 May 2019 23:43:27 -0400 Subject: Genericize LFSR testing infrastructure Make LFSR testing generic to enable it to test other LFSRs. Signed-off-by: Schuyler Eldridge --- src/test/scala/chiselTests/LFSR16.scala | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) (limited to 'src/test/scala') diff --git a/src/test/scala/chiselTests/LFSR16.scala b/src/test/scala/chiselTests/LFSR16.scala index 54a3591f..c3c9dfad 100644 --- a/src/test/scala/chiselTests/LFSR16.scala +++ b/src/test/scala/chiselTests/LFSR16.scala @@ -12,14 +12,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,13 +43,14 @@ 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() } @@ -55,10 +58,10 @@ class LFSR16MaxPeriod extends BasicTester { 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()) } } } -- cgit v1.2.3 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). --- src/test/scala/chiselTests/InstanceNameSpec.scala | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/test/scala') 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 } -- cgit v1.2.3 From f35f2a2784d8df7c079ee46eb33eeffd805edb44 Mon Sep 17 00:00:00 2001 From: Schuyler Eldridge Date: Wed, 8 May 2019 15:11:52 -0400 Subject: 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 --- .../scala/chiselTests/util/random/LFSRSpec.scala | 118 +++++++++++++++++++++ .../scala/chiselTests/util/random/PRNGSpec.scala | 90 ++++++++++++++++ 2 files changed, 208 insertions(+) create mode 100644 src/test/scala/chiselTests/util/random/LFSRSpec.scala create mode 100644 src/test/scala/chiselTests/util/random/PRNGSpec.scala (limited to 'src/test/scala') 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)) + } + +} -- cgit v1.2.3 From aaee64deb9c4990d0e38043a2b6a4ce747bb6935 Mon Sep 17 00:00:00 2001 From: Schuyler Eldridge Date: Tue, 7 May 2019 02:21:50 -0400 Subject: Deprecate LFSR16, use FibonacciLFSR internally Signed-off-by: Schuyler Eldridge --- src/test/scala/chiselTests/LFSR16.scala | 31 +++++++++++++++++++++++++++++- src/test/scala/chiselTests/QueueSpec.scala | 13 +++++++------ 2 files changed, 37 insertions(+), 7 deletions(-) (limited to 'src/test/scala') diff --git a/src/test/scala/chiselTests/LFSR16.scala b/src/test/scala/chiselTests/LFSR16.scala index c3c9dfad..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. @@ -56,12 +57,40 @@ class LFSRMaxPeriod(gen: => UInt) extends BasicTester { } } +/** 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 LFSRDistribution(LFSR16()) } } property("LFSR16 period tester, Period should 2^16 - 1") { - assertTesterPasses { new LFSRMaxPeriod(LFSR16()) } + 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())) -- cgit v1.2.3