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') 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). --- .../scala/chisel3/util/random/FibonacciLFSR.scala | 108 +++ .../scala/chisel3/util/random/GaloisLFSR.scala | 118 +++ src/main/scala/chisel3/util/random/LFSR.scala | 894 +++++++++++++++++++++ src/main/scala/chisel3/util/random/PRNG.scala | 86 ++ src/test/scala/chiselTests/InstanceNameSpec.scala | 3 +- 5 files changed, 1208 insertions(+), 1 deletion(-) create mode 100644 src/main/scala/chisel3/util/random/FibonacciLFSR.scala create mode 100644 src/main/scala/chisel3/util/random/GaloisLFSR.scala create mode 100644 src/main/scala/chisel3/util/random/LFSR.scala create mode 100644 src/main/scala/chisel3/util/random/PRNG.scala (limited to 'src') diff --git a/src/main/scala/chisel3/util/random/FibonacciLFSR.scala b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala new file mode 100644 index 00000000..53a42320 --- /dev/null +++ b/src/main/scala/chisel3/util/random/FibonacciLFSR.scala @@ -0,0 +1,108 @@ +// See LICENSE for license details. + +package chisel3.util.random + +import chisel3._ + +/** Fibonacci Linear Feedback Shift Register (LFSR) generator. + * + * A Fibonacci LFSR can be generated by defining a width and a set of tap points (corresponding to a polynomial). An + * optional initial seed and a reduction operation ([[XOR]], the default, or [[XNOR]]) can be used to augment the + * generated hardware. The resulting hardware has support for a run-time programmable seed (via [[PRNGIO.seed]]) and + * conditional increment (via [[PRNGIO.increment]]). + * + * $seedExplanation + * + * In the example below, a 4-bit Fibonacci LFSR is constructed. Tap points are defined as four and three (using LFSR + * convention of indexing from one). This results in the hardware configuration shown in the diagram. + * + * {{{ + * val lfsr4 = Module(new FibonacciLFSR(4, Set(4, 3)) + * // +---+ + * // +-------------->|XOR|-------------------------------------------------------+ + * // | +---+ | + * // | +-------+ ^ +-------+ +-------+ +-------+ | + * // | | | | | | | | | | | + * // +---+ x^4 |<----+-----| x^3 |<----------| x^2 |<----------| x^1 |<--+ + * // | | | | | | | | + * // +-------+ +-------+ +-------+ +-------+ + * }}} + * + * If you require a maximal period Fibonacci LFSR of a specific width, you can use [[MaxPeriodFibonacciLFSR]]. If you + * only require a pseudorandom [[UInt]] you can use the [[FibonacciLFSR$ FibonacciLFSR companion + * object]]. + * @see [[https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Fibonacci_LFSRs]] + * $paramWidth + * $paramTaps + * $paramSeed + * $paramReduction + * $paramStep + * $paramUpdateSeed + */ +class FibonacciLFSR( + width: Int, + taps: Set[Int], + seed: Option[BigInt] = Some(1), + val reduction: LFSRReduce = XOR, + 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) + +} + +/** A maximal period Fibonacci Linear Feedback Shift Register (LFSR) generator. The maximal period taps are sourced from + * [[LFSR.tapsMaxPeriod LFSR.tapsMaxPeriod]]. + * {{{ + * val lfsr8 = Module(new MaxPeriodFibonacciLFSR(8)) + * }}} + * $paramWidth + * $paramSeed + * $paramReduction + */ +class MaxPeriodFibonacciLFSR(width: Int, seed: Option[BigInt] = Some(1), reduction: LFSRReduce = XOR) + extends FibonacciLFSR(width, LFSR.tapsMaxPeriod.getOrElse(width, LFSR.badWidth(width)).head, seed, reduction) + +/** Utility for generating a pseudorandom [[UInt]] from a [[FibonacciLFSR]]. + * + * For example, to generate a pseudorandom 8-bit [[UInt]] that changes every cycle, you can use: + * {{{ + * val pseudoRandomNumber = FibonacciLFSR.maxPeriod(8) + * }}} + * + * @define paramWidth @param width of pseudorandom output + * @define paramTaps @param taps a set of tap points to use when constructing the LFSR + * @define paramIncrement @param increment when asserted, a new random value will be generated + * @define paramSeed @param seed an initial value for internal LFSR state + * @define paramReduction @param reduction the reduction operation (either [[XOR]] or + * [[XNOR]]) + */ +object FibonacciLFSR { + + /** Return a pseudorandom [[UInt]] generated from a [[FibonacciLFSR]]. + * $paramWidth + * $paramTaps + * $paramIncrement + * $paramSeed + * $paramReduction + */ + def apply( + width: Int, + taps: Set[Int], + increment: Bool = true.B, + seed: Option[BigInt] = Some(1), + reduction: LFSRReduce = XOR): UInt = PRNG(new FibonacciLFSR(width, taps, seed, reduction), increment) + + /** Return a pseudorandom [[UInt]] generated using a maximal period [[FibonacciLFSR]] + * $paramWidth + * $paramIncrement + * $paramSeed + * $paramReduction + */ + def maxPeriod( + width: Int, + increment: Bool = true.B, + seed: Option[BigInt] = Some(1), + reduction: LFSRReduce = XOR): UInt = PRNG(new MaxPeriodFibonacciLFSR(width, seed, reduction), increment) + +} diff --git a/src/main/scala/chisel3/util/random/GaloisLFSR.scala b/src/main/scala/chisel3/util/random/GaloisLFSR.scala new file mode 100644 index 00000000..3a61df95 --- /dev/null +++ b/src/main/scala/chisel3/util/random/GaloisLFSR.scala @@ -0,0 +1,118 @@ +// See LICENSE for license details. + +package chisel3.util.random + +import chisel3._ + +/** Galois Linear Feedback Shift Register (LFSR) generator. + * + * A Galois LFSR can be generated by defining a width and a set of tap points. Optionally, an initial seed and a + * reduction operation ([[XOR]], the default, or [[XNOR]]) can be used to augment the generated hardware. The resulting + * hardware has support for a run-time programmable seed (via [[PRNGIO.seed]]) and conditional increment (via + * [[PRNGIO.increment]]). + * + * $seedExplanation + * + * In the example below, a 4-bit LFSR Fibonacci LFSR is constructed. The tap points are defined as four and three + * (using LFSR convention of indexing from one). This results in the hardware configuration shown in the diagram. + * + * {{{ + * val lfsr4 = Module(new GaloisLFSR(4, Set(4, 3)) + * // +-----------------+---------------------------------------------------------+ + * // | | | + * // | +-------+ v +-------+ +-------+ +-------+ | + * // | | | +---+ | | | | | | | + * // +-->| x^4 |-->|XOR|-->| x^3 |---------->| x^2 |---------->| x^1 |---+ + * // | | +---+ | | | | | | + * // +-------+ +-------+ +-------+ +-------+ + * }}} + * + * If you require a maximal period Galois LFSR of a specific width, you can use [[MaxPeriodGaloisLFSR]]. If you only + * require a pseudorandom [[UInt]] you can use the [[GaloisLFSR$ GaloisLFSR companion object]]. + * @see [[https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Galois_LFSRs]] + * $paramWidth + * $paramTaps + * $paramSeed + * $paramReduction + * $paramStep + * $paramUpdateSeed + */ +class GaloisLFSR( + width: Int, + taps: Set[Int], + seed: Option[BigInt] = Some(1), + val reduction: LFSRReduce = XOR, + 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) + .zipWithIndex + .foreach { + case ((l, r), i) if taps(i + 1) && (i + 1 != out.size) => l := reduction(r, first) + case ((l, r), _) => l := r + } + out.asUInt + } + +} + +/** A maximal period Galois Linear Feedback Shift Register (LFSR) generator. The maximal period taps are sourced from + * [[LFSR.tapsMaxPeriod LFSR.tapsMaxPeriod]]. + * {{{ + * val lfsr8 = Module(new MaxPeriodGaloisLFSR(8)) + * }}} + * $paramWidth + * $paramSeed + * $paramReduction + */ +class MaxPeriodGaloisLFSR(width: Int, seed: Option[BigInt] = Some(1), reduction: LFSRReduce = XOR) + extends GaloisLFSR(width, LFSR.tapsMaxPeriod.getOrElse(width, LFSR.badWidth(width)).head, seed, reduction) + +/** Utility for generating a pseudorandom [[UInt]] from a [[GaloisLFSR]]. + * + * For example, to generate a pseudorandom 8-bit [[UInt]] that changes every cycle, you can use: + * {{{ + * val pseudoRandomNumber = GaloisLFSR.maxPeriod(8) + * }}} + * + * @define paramWidth @param width of pseudorandom output + * @define paramTaps @param taps a set of tap points to use when constructing the LFSR + * @define paramIncrement @param increment when asserted, a new random value will be generated + * @define paramSeed @param seed an initial value for internal LFSR state + * @define paramReduction @param reduction the reduction operation (either [[XOR]] or + * [[XNOR]]) + */ +object GaloisLFSR { + + /** Return a pseudorandom [[UInt]] generated from a [[FibonacciLFSR]]. + * $paramWidth + * $paramTaps + * $paramIncrement + * $paramSeed + * $paramReduction + */ + def apply( + width: Int, + taps: Set[Int], + increment: Bool = true.B, + seed: Option[BigInt] = Some(1), + reduction: LFSRReduce = XOR): UInt = PRNG(new GaloisLFSR(width, taps, seed, reduction), increment) + + /** Return a pseudorandom [[UInt]] generated using a maximal period [[GaloisLFSR]] + * $paramWidth + * $paramIncrement + * $paramSeed + * $paramReduction + */ + def maxPeriod( + width: Int, + increment: Bool = true.B, + seed: Option[BigInt] = Some(1), + reduction: LFSRReduce = XOR): UInt = PRNG(new MaxPeriodGaloisLFSR(width, seed, reduction), increment) + +} diff --git a/src/main/scala/chisel3/util/random/LFSR.scala b/src/main/scala/chisel3/util/random/LFSR.scala new file mode 100644 index 00000000..6663940c --- /dev/null +++ b/src/main/scala/chisel3/util/random/LFSR.scala @@ -0,0 +1,894 @@ +// See LICENSE for license details. + +package chisel3.util.random + +import chisel3._ + +/** A reduction operation for an LFSR. + * @see [[XOR]] + * @see [[XNOR]] + */ +sealed trait LFSRReduce extends ((Bool, Bool) => Bool) + +/** XOR (exclusive or) reduction operation */ +object XOR extends LFSRReduce { + def apply(a: Bool, b: Bool): Bool = a ^ b +} + +/** Not XOR (exclusive or) reduction operation */ +object XNOR extends LFSRReduce { + def apply(a: Bool, b: Bool): Bool = !(a ^ b) +} + +/** Trait that defines a Linear Feedback Shift Register (LFSR). + * + * $seedExplanation + * @see [[FibonacciLFSR]] + * @see [[GaloisLFSR]] + * @see [[https://en.wikipedia.org/wiki/Linear-feedback_shift_register]] + * + * @define paramWidth @param width the width of the LFSR + * @define paramTaps @param taps a set of tap points to use when constructing the LFSR + * @define paramSeed @param seed an initial value for internal LFSR state. If [[scala.None None]], then the LFSR + * state LSB will be set to a known safe value on reset (to prevent lock up). + * @define paramReduction @param reduction the reduction operation (either [[chisel3.util.random.XOR XOR]] or + * [[chisel3.util.random.XNOR XNOR]]) + * @define paramStep @param step the number of state updates per cycle + * @define paramUpdateSeed @param updateSeed if true, when loading the seed the state will be updated as if the seed + * were the current state, if false, the state will be set to the seed + * @define seedExplanation If the user specifies a seed, then a compile-time check is added that they are not + * initializing the LFSR to a state which will cause it to lock up. If the user does not set a seed, then the least + * significant bit of the state will be set or reset based on the choice of reduction operator. + */ +trait LFSR extends PRNG { + + /** The binary reduction operation used by this LFSR, either [[chisel3.util.random.XOR XOR]] or + * [[chisel3.util.random.XNOR XNOR]]. This has the effect of mandating what seed is invalid. + */ + def reduction: LFSRReduce + + seed match { + case Some(s) => + reduction match { + case XOR => require(s != 0, "Seed cannot be zero") + case XNOR => require(s != BigInt(2).pow(width) - 1, "Seed cannot be all ones (max value)") + } + 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 } + } + } + +} + +/** Utilities related to psuedorandom number generation using Linear Feedback Shift Registers (LFSRs). + * + * For example, to generate a pseudorandom 16-bit [[UInt]] that changes every cycle, you can use: + * {{{ + * val pseudoRandomNumber = LFSR(16) + * }}} + */ +object LFSR { + + /** Return a pseudorandom [[UInt]] generated using a [[FibonacciLFSR]]. If you require a Galois LFSR, use + * [[GaloisLFSR$.maxPeriod GaloisLFSR.maxPeriod]]. + * @param width the width of the LFSR + * @param increment when asserted, the LFSR will increment + * @param seed an initial seed (this cannot be zero) + * @return a [[UInt]] that is the output of a maximal period LFSR of the requested width + */ + def apply(width: Int, increment: Bool = true.B, seed: Option[BigInt] = Some(1)): UInt = + FibonacciLFSR.maxPeriod(width, increment, seed, XOR) + + /** Utility used to report an unknown tap width */ + private [random] def badWidth(width: Int): Nothing = throw new IllegalArgumentException( + s"No max period LFSR taps stored for requested width '$width'") + + /** A mapping of widths to a sequence of known LFSR taps that produce a maximal period LFSR. These work for either a + * [[chisel3.util.random.FibonacciLFSR Fibonacci LFSR]] or a [[chisel3.util.random.GaloisLFSR Galois LFSR]]. Taps are + * available for bit widths of 2--786, 1024, 2048, and 4096. + * + * Users can automatically generate [[LFSR]]s using these taps with [[LFSR.apply]] for a maximum period Fibonacci XOR + * LFSR or with [[MaxPeriodGaloisLFSR]]/[[GaloisLFSR.maxPeriod]] or + * [[MaxPeriodFibonacciLFSR]]/[[FibonacciLFSR.maxPeriod]] for more configuration options. + * @see [[http://courses.cse.tamu.edu/walker/csce680/lfsr_table.pdf]] + * @see [[https://www.xilinx.com/support/documentation/application_notes/xapp052.pdf]] + */ + lazy val tapsMaxPeriod: Map[Int, Seq[Set[Int]]] = tapsFirst ++ tapsSecond + + /** First portion of known taps (a combined map hits the 64KB JVM method limit) */ + private def tapsFirst = Map( // scalastyle:off magic.number + 2 -> Seq(Set(2, 1)), + 3 -> Seq(Set(3, 2)), + 4 -> Seq(Set(4, 3)), + 5 -> Seq(Set(5, 3), Set(5, 4, 3, 2)), + 6 -> Seq(Set(6, 5), Set(6, 5, 3, 2)), + 7 -> Seq(Set(7, 6), Set(7, 6, 5, 4)), + 8 -> Seq(Set(8, 6, 5, 4)), + 9 -> Seq(Set(9, 5), Set(9, 8, 6, 5)), + 10 -> Seq(Set(10, 7), Set(10, 9, 7, 6)), + 11 -> Seq(Set(11, 9), Set(11, 10, 9, 7)), + 12 -> Seq(Set(12, 11, 8, 6)), + 13 -> Seq(Set(13, 12, 10, 9)), + 14 -> Seq(Set(14, 13, 11, 9)), + 15 -> Seq(Set(15, 14), Set(15, 14, 13, 11)), + 16 -> Seq(Set(16, 14, 13, 11)), + 17 -> Seq(Set(17, 14), Set(17, 16, 15, 14)), + 18 -> Seq(Set(18, 11), Set(18, 17, 16, 13)), + 19 -> Seq(Set(19, 18, 17, 14)), + 20 -> Seq(Set(20, 17), Set(20, 19, 16, 14)), + 21 -> Seq(Set(21, 19), Set(21, 20, 19, 16)), + 22 -> Seq(Set(22, 21), Set(22, 19, 18, 17)), + 23 -> Seq(Set(23, 18), Set(23, 22, 20, 18)), + 24 -> Seq(Set(24, 23, 21, 20)), + 25 -> Seq(Set(25, 22), Set(25, 24, 23, 22)), + 26 -> Seq(Set(26, 25, 24, 20)), + 27 -> Seq(Set(27, 26, 25, 22)), + 28 -> Seq(Set(28, 25), Set(28, 27, 24, 22)), + 29 -> Seq(Set(29, 27), Set(29, 28, 27, 25)), + 30 -> Seq(Set(30, 29, 26, 24)), + 31 -> Seq(Set(31, 28), Set(31, 30, 29, 28)), + 32 -> Seq(Set(32, 30, 26, 25)), + 33 -> Seq(Set(33, 20), Set(33, 32, 29, 27)), + 34 -> Seq(Set(34, 31, 30, 26)), + 35 -> Seq(Set(35, 33), Set(35, 34, 28, 27)), + 36 -> Seq(Set(36, 25), Set(36, 35, 29, 28)), + 37 -> Seq(Set(37, 36, 33, 31)), + 38 -> Seq(Set(38, 37, 33, 32)), + 39 -> Seq(Set(39, 35), Set(39, 38, 35, 32)), + 40 -> Seq(Set(40, 37, 36, 35)), + 41 -> Seq(Set(41, 38), Set(41, 40, 39, 38)), + 42 -> Seq(Set(42, 40, 37, 35)), + 43 -> Seq(Set(43, 42, 38, 37)), + 44 -> Seq(Set(44, 42, 39, 38)), + 45 -> Seq(Set(45, 44, 42, 41)), + 46 -> Seq(Set(46, 40, 39, 38)), + 47 -> Seq(Set(47, 42), Set(47, 46, 43, 42)), + 48 -> Seq(Set(48, 44, 41, 39)), + 49 -> Seq(Set(49, 40), Set(49, 45, 44, 43)), + 50 -> Seq(Set(50, 48, 47, 46)), + 51 -> Seq(Set(51, 50, 48, 45)), + 52 -> Seq(Set(52, 49), Set(52, 51, 49, 46)), + 53 -> Seq(Set(53, 52, 51, 47)), + 54 -> Seq(Set(54, 51, 48, 46)), + 55 -> Seq(Set(55, 31), Set(55, 54, 53, 49)), + 56 -> Seq(Set(56, 54, 52, 49)), + 57 -> Seq(Set(57, 50), Set(57, 55, 54, 52)), + 58 -> Seq(Set(58, 39), Set(58, 57, 53, 52)), + 59 -> Seq(Set(59, 57, 55, 52)), + 60 -> Seq(Set(60, 59), Set(60, 58, 56, 55)), + 61 -> Seq(Set(61, 60, 59, 56)), + 62 -> Seq(Set(62, 59, 57, 56)), + 63 -> Seq(Set(63, 62), Set(63, 62, 59, 58)), + 64 -> Seq(Set(64, 63, 61, 60)), + 65 -> Seq(Set(65, 47), Set(65, 64, 62, 61)), + 66 -> Seq(Set(66, 60, 58, 57)), + 67 -> Seq(Set(67, 66, 65, 62)), + 68 -> Seq(Set(68, 59), Set(68, 67, 63, 61)), + 69 -> Seq(Set(69, 67, 64, 63)), + 70 -> Seq(Set(70, 69, 67, 65)), + 71 -> Seq(Set(71, 65), Set(71, 70, 68, 66)), + 72 -> Seq(Set(72, 69, 63, 62)), + 73 -> Seq(Set(73, 48), Set(73, 71, 70, 69)), + 74 -> Seq(Set(74, 71, 70, 67)), + 75 -> Seq(Set(75, 74, 72, 69)), + 76 -> Seq(Set(76, 74, 72, 71)), + 77 -> Seq(Set(77, 75, 72, 71)), + 78 -> Seq(Set(78, 77, 76, 71)), + 79 -> Seq(Set(79, 70), Set(79, 77, 76, 75)), + 80 -> Seq(Set(80, 78, 76, 71)), + 81 -> Seq(Set(81, 77), Set(81, 79, 78, 75)), + 82 -> Seq(Set(82, 78, 76, 73)), + 83 -> Seq(Set(83, 81, 79, 76)), + 84 -> Seq(Set(84, 71), Set(84, 83, 77, 75)), + 85 -> Seq(Set(85, 84, 83, 77)), + 86 -> Seq(Set(86, 84, 81, 80)), + 87 -> Seq(Set(87, 74), Set(87, 86, 82, 80)), + 88 -> Seq(Set(88, 80, 79, 77)), + 89 -> Seq(Set(89, 51), Set(89, 86, 84, 83)), + 90 -> Seq(Set(90, 88, 87, 85)), + 91 -> Seq(Set(91, 90, 86, 83)), + 92 -> Seq(Set(92, 90, 87, 86)), + 93 -> Seq(Set(93, 91), Set(93, 91, 90, 87)), + 94 -> Seq(Set(94, 73), Set(94, 93, 89, 88)), + 95 -> Seq(Set(95, 84), Set(95, 94, 90, 88)), + 96 -> Seq(Set(96, 90, 87, 86)), + 97 -> Seq(Set(97, 91), Set(97, 95, 93, 91)), + 98 -> Seq(Set(98, 87), Set(98, 97, 91, 90)), + 99 -> Seq(Set(99, 95, 94, 92)), + 100 -> Seq(Set(100, 63), Set(100, 98, 93, 92)), + 101 -> Seq(Set(101, 100, 95, 94)), + 102 -> Seq(Set(102, 99, 97, 96)), + 103 -> Seq(Set(103, 94), Set(103, 102, 99, 94)), + 104 -> Seq(Set(104, 103, 94, 93)), + 105 -> Seq(Set(105, 89), Set(105, 104, 99, 98)), + 106 -> Seq(Set(106, 91), Set(106, 105, 101, 100)), + 107 -> Seq(Set(107, 105, 99, 98)), + 108 -> Seq(Set(108, 77), Set(108, 103, 97, 96)), + 109 -> Seq(Set(109, 107, 105, 104)), + 110 -> Seq(Set(110, 109, 106, 104)), + 111 -> Seq(Set(111, 101), Set(111, 109, 107, 104)), + 112 -> Seq(Set(112, 108, 106, 101)), + 113 -> Seq(Set(113, 104), Set(113, 111, 110, 108)), + 114 -> Seq(Set(114, 113, 112, 103)), + 115 -> Seq(Set(115, 110, 108, 107)), + 116 -> Seq(Set(116, 114, 111, 110)), + 117 -> Seq(Set(117, 116, 115, 112)), + 118 -> Seq(Set(118, 85), Set(118, 116, 113, 112)), + 119 -> Seq(Set(119, 111), Set(119, 116, 111, 110)), + 120 -> Seq(Set(120, 118, 114, 111)), + 121 -> Seq(Set(121, 103), Set(121, 120, 116, 113)), + 122 -> Seq(Set(122, 121, 120, 116)), + 123 -> Seq(Set(123, 121), Set(123, 122, 119, 115)), + 124 -> Seq(Set(124, 87), Set(124, 119, 118, 117)), + 125 -> Seq(Set(125, 120, 119, 118)), + 126 -> Seq(Set(126, 124, 122, 119)), + 127 -> Seq(Set(127, 126), Set(127, 126, 124, 120)), + 128 -> Seq(Set(128, 127, 126, 121)), + 129 -> Seq(Set(129, 124), Set(129, 128, 125, 124)), + 130 -> Seq(Set(130, 127), Set(130, 129, 128, 125)), + 131 -> Seq(Set(131, 129, 128, 123)), + 132 -> Seq(Set(132, 103), Set(132, 130, 127, 123)), + 133 -> Seq(Set(133, 131, 125, 124)), + 134 -> Seq(Set(134, 77), Set(134, 133, 129, 127)), + 135 -> Seq(Set(135, 124), Set(135, 132, 131, 129)), + 136 -> Seq(Set(136, 134, 133, 128)), + 137 -> Seq(Set(137, 116), Set(137, 136, 133, 126)), + 138 -> Seq(Set(138, 137, 131, 130)), + 139 -> Seq(Set(139, 136, 134, 131)), + 140 -> Seq(Set(140, 111), Set(140, 139, 136, 132)), + 141 -> Seq(Set(141, 140, 135, 128)), + 142 -> Seq(Set(142, 121), Set(142, 141, 139, 132)), + 143 -> Seq(Set(143, 141, 140, 138)), + 144 -> Seq(Set(144, 142, 140, 137)), + 145 -> Seq(Set(145, 93), Set(145, 144, 140, 139)), + 146 -> Seq(Set(146, 144, 143, 141)), + 147 -> Seq(Set(147, 145, 143, 136)), + 148 -> Seq(Set(148, 121), Set(148, 145, 143, 141)), + 149 -> Seq(Set(149, 142, 140, 139)), + 150 -> Seq(Set(150, 97), Set(150, 148, 147, 142)), + 151 -> Seq(Set(151, 148), Set(151, 150, 149, 148)), + 152 -> Seq(Set(152, 150, 149, 146)), + 153 -> Seq(Set(153, 152), Set(153, 149, 148, 145)), + 154 -> Seq(Set(154, 153, 149, 145)), + 155 -> Seq(Set(155, 151, 150, 148)), + 156 -> Seq(Set(156, 153, 151, 147)), + 157 -> Seq(Set(157, 155, 152, 151)), + 158 -> Seq(Set(158, 153, 152, 150)), + 159 -> Seq(Set(159, 128), Set(159, 156, 153, 148)), + 160 -> Seq(Set(160, 158, 157, 155)), + 161 -> Seq(Set(161, 143), Set(161, 159, 158, 155)), + 162 -> Seq(Set(162, 158, 155, 154)), + 163 -> Seq(Set(163, 160, 157, 156)), + 164 -> Seq(Set(164, 159, 158, 152)), + 165 -> Seq(Set(165, 162, 157, 156)), + 166 -> Seq(Set(166, 164, 163, 156)), + 167 -> Seq(Set(167, 161), Set(167, 165, 163, 161)), + 168 -> Seq(Set(168, 162, 159, 152)), + 169 -> Seq(Set(169, 135), Set(169, 164, 163, 161)), + 170 -> Seq(Set(170, 147), Set(170, 169, 166, 161)), + 171 -> Seq(Set(171, 169, 166, 165)), + 172 -> Seq(Set(172, 165), Set(172, 169, 165, 161)), + 173 -> Seq(Set(173, 171, 168, 165)), + 174 -> Seq(Set(174, 161), Set(174, 169, 166, 165)), + 175 -> Seq(Set(175, 169), Set(175, 173, 171, 169)), + 176 -> Seq(Set(176, 167, 165, 164)), + 177 -> Seq(Set(177, 169), Set(177, 175, 174, 172)), + 178 -> Seq(Set(178, 91), Set(178, 176, 171, 170)), + 179 -> Seq(Set(179, 178, 177, 175)), + 180 -> Seq(Set(180, 173, 170, 168)), + 181 -> Seq(Set(181, 180, 175, 174)), + 182 -> Seq(Set(182, 181, 176, 174)), + 183 -> Seq(Set(183, 127), Set(183, 179, 176, 175)), + 184 -> Seq(Set(184, 177, 176, 175)), + 185 -> Seq(Set(185, 161), Set(185, 184, 182, 177)), + 186 -> Seq(Set(186, 180, 178, 177)), + 187 -> Seq(Set(187, 182, 181, 180)), + 188 -> Seq(Set(188, 186, 183, 182)), + 189 -> Seq(Set(189, 187, 184, 183)), + 190 -> Seq(Set(190, 188, 184, 177)), + 191 -> Seq(Set(191, 182), Set(191, 187, 185, 184)), + 192 -> Seq(Set(192, 190, 178, 177)), + 193 -> Seq(Set(193, 178), Set(193, 189, 186, 184)), + 194 -> Seq(Set(194, 107), Set(194, 192, 191, 190)), + 195 -> Seq(Set(195, 193, 192, 187)), + 196 -> Seq(Set(196, 194, 187, 185)), + 197 -> Seq(Set(197, 195, 193, 188)), + 198 -> Seq(Set(198, 133), Set(198, 193, 190, 183)), + 199 -> Seq(Set(199, 165), Set(199, 198, 195, 190)), + 200 -> Seq(Set(200, 198, 197, 195)), + 201 -> Seq(Set(201, 187), Set(201, 199, 198, 195)), + 202 -> Seq(Set(202, 147), Set(202, 198, 196, 195)), + 203 -> Seq(Set(203, 202, 196, 195)), + 204 -> Seq(Set(204, 201, 200, 194)), + 205 -> Seq(Set(205, 203, 200, 196)), + 206 -> Seq(Set(206, 201, 197, 196)), + 207 -> Seq(Set(207, 164), Set(207, 206, 201, 198)), + 208 -> Seq(Set(208, 207, 205, 199)), + 209 -> Seq(Set(209, 203), Set(209, 207, 206, 204)), + 210 -> Seq(Set(210, 207, 206, 198)), + 211 -> Seq(Set(211, 203, 201, 200)), + 212 -> Seq(Set(212, 107), Set(212, 209, 208, 205)), + 213 -> Seq(Set(213, 211, 208, 207)), + 214 -> Seq(Set(214, 213, 211, 209)), + 215 -> Seq(Set(215, 192), Set(215, 212, 210, 209)), + 216 -> Seq(Set(216, 215, 213, 209)), + 217 -> Seq(Set(217, 172), Set(217, 213, 212, 211)), + 218 -> Seq(Set(218, 207), Set(218, 217, 211, 210)), + 219 -> Seq(Set(219, 218, 215, 211)), + 220 -> Seq(Set(220, 211, 210, 208)), + 221 -> Seq(Set(221, 219, 215, 213)), + 222 -> Seq(Set(222, 220, 217, 214)), + 223 -> Seq(Set(223, 190), Set(223, 221, 219, 218)), + 224 -> Seq(Set(224, 222, 217, 212)), + 225 -> Seq(Set(225, 193), Set(225, 224, 220, 215)), + 226 -> Seq(Set(226, 223, 219, 216)), + 227 -> Seq(Set(227, 223, 218, 217)), + 228 -> Seq(Set(228, 226, 217, 216)), + 229 -> Seq(Set(229, 228, 225, 219)), + 230 -> Seq(Set(230, 224, 223, 222)), + 231 -> Seq(Set(231, 205), Set(231, 229, 227, 224)), + 232 -> Seq(Set(232, 228, 223, 221)), + 233 -> Seq(Set(233, 159), Set(233, 232, 229, 224)), + 234 -> Seq(Set(234, 203), Set(234, 232, 225, 223)), + 235 -> Seq(Set(235, 234, 229, 226)), + 236 -> Seq(Set(236, 231), Set(236, 229, 228, 226)), + 237 -> Seq(Set(237, 236, 233, 230)), + 238 -> Seq(Set(238, 237, 236, 233)), + 239 -> Seq(Set(239, 203), Set(239, 238, 232, 227)), + 240 -> Seq(Set(240, 237, 235, 232)), + 241 -> Seq(Set(241, 171), Set(241, 237, 233, 232)), + 242 -> Seq(Set(242, 241, 236, 231)), + 243 -> Seq(Set(243, 242, 238, 235)), + 244 -> Seq(Set(244, 243, 240, 235)), + 245 -> Seq(Set(245, 244, 241, 239)), + 246 -> Seq(Set(246, 245, 244, 235)), + 247 -> Seq(Set(247, 165), Set(247, 245, 243, 238)), + 248 -> Seq(Set(248, 238, 234, 233)), + 249 -> Seq(Set(249, 163), Set(249, 248, 245, 242)), + 250 -> Seq(Set(250, 147), Set(250, 247, 245, 240)), + 251 -> Seq(Set(251, 249, 247, 244)), + 252 -> Seq(Set(252, 185), Set(252, 251, 247, 241)), + 253 -> Seq(Set(253, 252, 247, 246)), + 254 -> Seq(Set(254, 253, 252, 247)), + 255 -> Seq(Set(255, 203), Set(255, 253, 252, 250)), + 256 -> Seq(Set(256, 254, 251, 246)), + 257 -> Seq(Set(257, 245), Set(257, 255, 251, 250)), + 258 -> Seq(Set(258, 175), Set(258, 254, 252, 249)), + 259 -> Seq(Set(259, 257, 253, 249)), + 260 -> Seq(Set(260, 253, 252, 250)), + 261 -> Seq(Set(261, 257, 255, 254)), + 262 -> Seq(Set(262, 258, 254, 253)), + 263 -> Seq(Set(263, 170), Set(263, 261, 258, 252)), + 264 -> Seq(Set(264, 263, 255, 254)), + 265 -> Seq(Set(265, 223), Set(265, 263, 262, 260)), + 266 -> Seq(Set(266, 219), Set(266, 265, 260, 259)), + 267 -> Seq(Set(267, 264, 261, 259)), + 268 -> Seq(Set(268, 243), Set(268, 267, 264, 258)), + 269 -> Seq(Set(269, 268, 263, 262)), + 270 -> Seq(Set(270, 217), Set(270, 267, 263, 260)), + 271 -> Seq(Set(271, 213), Set(271, 265, 264, 260)), + 272 -> Seq(Set(272, 270, 266, 263)), + 273 -> Seq(Set(273, 250), Set(273, 272, 271, 266)), + 274 -> Seq(Set(274, 207), Set(274, 272, 267, 265)), + 275 -> Seq(Set(275, 266, 265, 264)), + 276 -> Seq(Set(276, 275, 273, 270)), + 277 -> Seq(Set(277, 274, 271, 265)), + 278 -> Seq(Set(278, 273), Set(278, 277, 274, 273)), + 279 -> Seq(Set(279, 274), Set(279, 278, 275, 274)), + 280 -> Seq(Set(280, 278, 275, 271)), + 281 -> Seq(Set(281, 188), Set(281, 280, 277, 272)), + 282 -> Seq(Set(282, 247), Set(282, 278, 277, 272)), + 283 -> Seq(Set(283, 278, 276, 271)), + 284 -> Seq(Set(284, 165), Set(284, 279, 278, 276)), + 285 -> Seq(Set(285, 280, 278, 275)), + 286 -> Seq(Set(286, 217), Set(286, 285, 276, 271)), + 287 -> Seq(Set(287, 216), Set(287, 285, 282, 281)), + 288 -> Seq(Set(288, 287, 278, 277)), + 289 -> Seq(Set(289, 268), Set(289, 286, 285, 277)), + 290 -> Seq(Set(290, 288, 287, 285)), + 291 -> Seq(Set(291, 286, 280, 279)), + 292 -> Seq(Set(292, 195), Set(292, 291, 289, 285)), + 293 -> Seq(Set(293, 292, 287, 282)), + 294 -> Seq(Set(294, 233), Set(294, 292, 291, 285)), + 295 -> Seq(Set(295, 247), Set(295, 293, 291, 290)), + 296 -> Seq(Set(296, 292, 287, 285)), + 297 -> Seq(Set(297, 292), Set(297, 296, 293, 292)), + 298 -> Seq(Set(298, 294, 290, 287)), + 299 -> Seq(Set(299, 295, 293, 288)), + 300 -> Seq(Set(300, 293), Set(300, 290, 288, 287)), + 301 -> Seq(Set(301, 299, 296, 292)), + 302 -> Seq(Set(302, 261), Set(302, 297, 293, 290)), + 303 -> Seq(Set(303, 297, 291, 290)), + 304 -> Seq(Set(304, 303, 302, 293)), + 305 -> Seq(Set(305, 203), Set(305, 303, 299, 298)), + 306 -> Seq(Set(306, 305, 303, 299)), + 307 -> Seq(Set(307, 305, 303, 299)), + 308 -> Seq(Set(308, 306, 299, 293)), + 309 -> Seq(Set(309, 307, 302, 299)), + 310 -> Seq(Set(310, 309, 305, 302)), + 311 -> Seq(Set(311, 308, 306, 304)), + 312 -> Seq(Set(312, 307, 302, 301)), + 313 -> Seq(Set(313, 234), Set(313, 312, 310, 306)), + 314 -> Seq(Set(314, 299), Set(314, 311, 305, 300)), + 315 -> Seq(Set(315, 314, 306, 305)), + 316 -> Seq(Set(316, 181), Set(316, 309, 305, 304)), + 317 -> Seq(Set(317, 315, 313, 310)), + 318 -> Seq(Set(318, 313, 312, 310)), + 319 -> Seq(Set(319, 283), Set(319, 318, 317, 308)), + 320 -> Seq(Set(320, 319, 317, 316)), + 321 -> Seq(Set(321, 290), Set(321, 319, 316, 314)), + 322 -> Seq(Set(322, 255), Set(322, 321, 320, 305)), + 323 -> Seq(Set(323, 322, 320, 313)), + 324 -> Seq(Set(324, 321, 320, 318)), + 325 -> Seq(Set(325, 323, 320, 315)), + 326 -> Seq(Set(326, 325, 323, 316)), + 327 -> Seq(Set(327, 293), Set(327, 325, 322, 319)), + 328 -> Seq(Set(328, 323, 321, 319)), + 329 -> Seq(Set(329, 279), Set(329, 326, 323, 321)), + 330 -> Seq(Set(330, 328, 323, 322)), + 331 -> Seq(Set(331, 329, 325, 321)), + 332 -> Seq(Set(332, 209), Set(332, 325, 321, 320)), + 333 -> Seq(Set(333, 331), Set(333, 331, 329, 325)), + 334 -> Seq(Set(334, 333, 330, 327)), + 335 -> Seq(Set(335, 333, 328, 325)), + 336 -> Seq(Set(336, 335, 332, 329)), + 337 -> Seq(Set(337, 282), Set(337, 336, 331, 327)), + 338 -> Seq(Set(338, 336, 335, 332)), + 339 -> Seq(Set(339, 332, 329, 323)), + 340 -> Seq(Set(340, 337, 336, 329)), + 341 -> Seq(Set(341, 336, 330, 327)), + 342 -> Seq(Set(342, 217), Set(342, 341, 340, 331)), + 343 -> Seq(Set(343, 268), Set(343, 338, 335, 333)), + 344 -> Seq(Set(344, 338, 334, 333)), + 345 -> Seq(Set(345, 323), Set(345, 343, 341, 337)), + 346 -> Seq(Set(346, 344, 339, 335)), + 347 -> Seq(Set(347, 344, 337, 336)), + 348 -> Seq(Set(348, 344, 341, 340)), + 349 -> Seq(Set(349, 347, 344, 343)), + 350 -> Seq(Set(350, 297), Set(350, 340, 337, 336)), + 351 -> Seq(Set(351, 317), Set(351, 348, 345, 343)), + 352 -> Seq(Set(352, 346, 341, 339)), + 353 -> Seq(Set(353, 284), Set(353, 349, 346, 344)), + 354 -> Seq(Set(354, 349, 341, 340)), + 355 -> Seq(Set(355, 354, 350, 349)), + 356 -> Seq(Set(356, 349, 347, 346)), + 357 -> Seq(Set(357, 355, 347, 346)), + 358 -> Seq(Set(358, 351, 350, 344)), + 359 -> Seq(Set(359, 291), Set(359, 358, 352, 350)), + 360 -> Seq(Set(360, 359, 335, 334)), + 361 -> Seq(Set(361, 360, 357, 354)), + 362 -> Seq(Set(362, 299), Set(362, 360, 351, 344)), + 363 -> Seq(Set(363, 362, 356, 355)), + 364 -> Seq(Set(364, 297), Set(364, 363, 359, 352)), + 365 -> Seq(Set(365, 360, 359, 356)), + 366 -> Seq(Set(366, 337), Set(366, 362, 359, 352)), + 367 -> Seq(Set(367, 346), Set(367, 365, 363, 358)), + 368 -> Seq(Set(368, 361, 359, 351)), + 369 -> Seq(Set(369, 278), Set(369, 367, 359, 358)), + 370 -> Seq(Set(370, 231), Set(370, 368, 367, 365)), + 371 -> Seq(Set(371, 369, 368, 363)), + 372 -> Seq(Set(372, 369, 365, 357)), + 373 -> Seq(Set(373, 371, 366, 365)), + 374 -> Seq(Set(374, 369, 368, 366)), + 375 -> Seq(Set(375, 359), Set(375, 374, 368, 367)), + 376 -> Seq(Set(376, 371, 369, 368)), + 377 -> Seq(Set(377, 336), Set(377, 376, 374, 369)), + 378 -> Seq(Set(378, 335), Set(378, 374, 365, 363)), + 379 -> Seq(Set(379, 375, 370, 369)), + 380 -> Seq(Set(380, 333), Set(380, 377, 374, 366)), + 381 -> Seq(Set(381, 380, 379, 376)), + 382 -> Seq(Set(382, 301), Set(382, 379, 375, 364)), + 383 -> Seq(Set(383, 293), Set(383, 382, 378, 374)), + 384 -> Seq(Set(384, 378, 369, 368)), + 385 -> Seq(Set(385, 379), Set(385, 383, 381, 379)), + 386 -> Seq(Set(386, 303), Set(386, 381, 380, 376)), + 387 -> Seq(Set(387, 385, 379, 378)), + 388 -> Seq(Set(388, 387, 385, 374)), + 389 -> Seq(Set(389, 384, 380, 379)), + 390 -> Seq(Set(390, 301), Set(390, 388, 380, 377)), + 391 -> Seq(Set(391, 363), Set(391, 390, 389, 385)), + 392 -> Seq(Set(392, 386, 382, 379)), + 393 -> Seq(Set(393, 386), Set(393, 392, 391, 386)), + 394 -> Seq(Set(394, 259), Set(394, 392, 387, 386)) ) + + /** Second portion of known taps (a combined map hits the 64KB JVM method limit) */ + private def tapsSecond = Map( + 395 -> Seq(Set(395, 390, 389, 384)), + 396 -> Seq(Set(396, 371), Set(396, 392, 390, 389)), + 397 -> Seq(Set(397, 392, 387, 385)), + 398 -> Seq(Set(398, 393, 392, 384)), + 399 -> Seq(Set(399, 313), Set(399, 397, 390, 388)), + 400 -> Seq(Set(400, 398, 397, 395)), + 401 -> Seq(Set(401, 249), Set(401, 399, 392, 389)), + 402 -> Seq(Set(402, 399, 398, 393)), + 403 -> Seq(Set(403, 398, 395, 394)), + 404 -> Seq(Set(404, 215), Set(404, 400, 398, 397)), + 405 -> Seq(Set(405, 398, 397, 388)), + 406 -> Seq(Set(406, 249), Set(406, 402, 397, 393)), + 407 -> Seq(Set(407, 336), Set(407, 402, 400, 398)), + 408 -> Seq(Set(408, 407, 403, 401)), + 409 -> Seq(Set(409, 322), Set(409, 406, 404, 402)), + 410 -> Seq(Set(410, 407, 406, 400)), + 411 -> Seq(Set(411, 408, 401, 399)), + 412 -> Seq(Set(412, 265), Set(412, 409, 404, 401)), + 413 -> Seq(Set(413, 407, 406, 403)), + 414 -> Seq(Set(414, 405, 401, 398)), + 415 -> Seq(Set(415, 313), Set(415, 413, 411, 406)), + 416 -> Seq(Set(416, 414, 411, 407)), + 417 -> Seq(Set(417, 310), Set(417, 416, 414, 407)), + 418 -> Seq(Set(418, 417, 415, 403)), + 419 -> Seq(Set(419, 415, 414, 404)), + 420 -> Seq(Set(420, 412, 410, 407)), + 421 -> Seq(Set(421, 419, 417, 416)), + 422 -> Seq(Set(422, 273), Set(422, 421, 416, 412)), + 423 -> Seq(Set(423, 398), Set(423, 420, 418, 414)), + 424 -> Seq(Set(424, 422, 417, 415)), + 425 -> Seq(Set(425, 413), Set(425, 422, 421, 418)), + 426 -> Seq(Set(426, 415, 414, 412)), + 427 -> Seq(Set(427, 422, 421, 416)), + 428 -> Seq(Set(428, 323), Set(428, 426, 425, 417)), + 429 -> Seq(Set(429, 422, 421, 419)), + 430 -> Seq(Set(430, 419, 417, 415)), + 431 -> Seq(Set(431, 311), Set(431, 430, 428, 426)), + 432 -> Seq(Set(432, 429, 428, 419)), + 433 -> Seq(Set(433, 400), Set(433, 430, 428, 422)), + 434 -> Seq(Set(434, 429, 423, 422)), + 435 -> Seq(Set(435, 430, 426, 423)), + 436 -> Seq(Set(436, 271), Set(436, 432, 431, 430)), + 437 -> Seq(Set(437, 436, 435, 431)), + 438 -> Seq(Set(438, 373), Set(438, 436, 432, 421)), + 439 -> Seq(Set(439, 390), Set(439, 437, 436, 431)), + 440 -> Seq(Set(440, 439, 437, 436)), + 441 -> Seq(Set(441, 410), Set(441, 440, 433, 430)), + 442 -> Seq(Set(442, 440, 437, 435)), + 443 -> Seq(Set(443, 442, 437, 433)), + 444 -> Seq(Set(444, 435, 432, 431)), + 445 -> Seq(Set(445, 441, 439, 438)), + 446 -> Seq(Set(446, 341), Set(446, 442, 439, 431)), + 447 -> Seq(Set(447, 374), Set(447, 446, 441, 438)), + 448 -> Seq(Set(448, 444, 442, 437)), + 449 -> Seq(Set(449, 315), Set(449, 446, 440, 438)), + 450 -> Seq(Set(450, 371), Set(450, 443, 438, 434)), + 451 -> Seq(Set(451, 450, 441, 435)), + 452 -> Seq(Set(452, 448, 447, 446)), + 453 -> Seq(Set(453, 449, 447, 438)), + 454 -> Seq(Set(454, 449, 445, 444)), + 455 -> Seq(Set(455, 417), Set(455, 453, 449, 444)), + 456 -> Seq(Set(456, 454, 445, 433)), + 457 -> Seq(Set(457, 441), Set(457, 454, 449, 446)), + 458 -> Seq(Set(458, 255), Set(458, 453, 448, 445)), + 459 -> Seq(Set(459, 457, 454, 447)), + 460 -> Seq(Set(460, 399), Set(460, 459, 455, 451)), + 461 -> Seq(Set(461, 460, 455, 454)), + 462 -> Seq(Set(462, 389), Set(462, 457, 451, 450)), + 463 -> Seq(Set(463, 370), Set(463, 456, 455, 452)), + 464 -> Seq(Set(464, 460, 455, 441)), + 465 -> Seq(Set(465, 406), Set(465, 463, 462, 457)), + 466 -> Seq(Set(466, 460, 455, 452)), + 467 -> Seq(Set(467, 466, 461, 456)), + 468 -> Seq(Set(468, 464, 459, 453)), + 469 -> Seq(Set(469, 467, 464, 460)), + 470 -> Seq(Set(470, 321), Set(470, 468, 462, 461)), + 471 -> Seq(Set(471, 470), Set(471, 469, 468, 465)), + 472 -> Seq(Set(472, 470, 469, 461)), + 473 -> Seq(Set(473, 470, 467, 465)), + 474 -> Seq(Set(474, 283), Set(474, 465, 463, 456)), + 475 -> Seq(Set(475, 471, 467, 466)), + 476 -> Seq(Set(476, 461), Set(476, 475, 468, 466)), + 477 -> Seq(Set(477, 470, 462, 461)), + 478 -> Seq(Set(478, 357), Set(478, 477, 474, 472)), + 479 -> Seq(Set(479, 375), Set(479, 475, 472, 470)), + 480 -> Seq(Set(480, 473, 467, 464)), + 481 -> Seq(Set(481, 343), Set(481, 480, 472, 471)), + 482 -> Seq(Set(482, 477, 476, 473)), + 483 -> Seq(Set(483, 479, 477, 474)), + 484 -> Seq(Set(484, 379), Set(484, 483, 482, 470)), + 485 -> Seq(Set(485, 479, 469, 468)), + 486 -> Seq(Set(486, 481, 478, 472)), + 487 -> Seq(Set(487, 393), Set(487, 485, 483, 478)), + 488 -> Seq(Set(488, 487, 485, 484)), + 489 -> Seq(Set(489, 406), Set(489, 484, 483, 480)), + 490 -> Seq(Set(490, 271), Set(490, 485, 483, 481)), + 491 -> Seq(Set(491, 488, 485, 480)), + 492 -> Seq(Set(492, 491, 485, 484)), + 493 -> Seq(Set(493, 490, 488, 483)), + 494 -> Seq(Set(494, 357), Set(494, 493, 489, 481)), + 495 -> Seq(Set(495, 419), Set(495, 494, 486, 480)), + 496 -> Seq(Set(496, 494, 491, 480)), + 497 -> Seq(Set(497, 419), Set(497, 493, 488, 486)), + 498 -> Seq(Set(498, 495, 489, 487)), + 499 -> Seq(Set(499, 494, 493, 488)), + 500 -> Seq(Set(500, 499, 494, 490)), + 501 -> Seq(Set(501, 499, 497, 496)), + 502 -> Seq(Set(502, 498, 497, 494)), + 503 -> Seq(Set(503, 500), Set(503, 502, 501, 500)), + 504 -> Seq(Set(504, 502, 490, 483)), + 505 -> Seq(Set(505, 349), Set(505, 500, 497, 493)), + 506 -> Seq(Set(506, 411), Set(506, 501, 494, 491)), + 507 -> Seq(Set(507, 504, 501, 494)), + 508 -> Seq(Set(508, 399), Set(508, 505, 500, 495)), + 509 -> Seq(Set(509, 506, 502, 501)), + 510 -> Seq(Set(510, 501, 500, 498)), + 511 -> Seq(Set(511, 501), Set(511, 509, 503, 501)), + 512 -> Seq(Set(512, 510, 507, 504)), + 513 -> Seq(Set(513, 428), Set(513, 505, 503, 500)), + 514 -> Seq(Set(514, 511, 509, 507)), + 515 -> Seq(Set(515, 511, 508, 501)), + 516 -> Seq(Set(516, 514, 511, 509)), + 517 -> Seq(Set(517, 515, 507, 505)), + 518 -> Seq(Set(518, 485), Set(518, 516, 515, 507)), + 519 -> Seq(Set(519, 440), Set(519, 517, 511, 507)), + 520 -> Seq(Set(520, 509, 507, 503)), + 521 -> Seq(Set(521, 489), Set(521, 519, 514, 512)), + 522 -> Seq(Set(522, 518, 509, 507)), + 523 -> Seq(Set(523, 521, 517, 510)), + 524 -> Seq(Set(524, 357), Set(524, 523, 519, 515)), + 525 -> Seq(Set(525, 524, 521, 519)), + 526 -> Seq(Set(526, 525, 521, 517)), + 527 -> Seq(Set(527, 480), Set(527, 526, 520, 518)), + 528 -> Seq(Set(528, 526, 522, 517)), + 529 -> Seq(Set(529, 487), Set(529, 528, 525, 522)), + 530 -> Seq(Set(530, 527, 523, 520)), + 531 -> Seq(Set(531, 529, 525, 519)), + 532 -> Seq(Set(532, 531), Set(532, 529, 528, 522)), + 533 -> Seq(Set(533, 531, 530, 529)), + 534 -> Seq(Set(534, 533, 529, 527)), + 535 -> Seq(Set(535, 533, 529, 527)), + 536 -> Seq(Set(536, 533, 531, 529)), + 537 -> Seq(Set(537, 443), Set(537, 536, 535, 527)), + 538 -> Seq(Set(538, 537, 536, 533)), + 539 -> Seq(Set(539, 535, 534, 529)), + 540 -> Seq(Set(540, 361), Set(540, 537, 534, 529)), + 541 -> Seq(Set(541, 537, 531, 528)), + 542 -> Seq(Set(542, 540, 539, 533)), + 543 -> Seq(Set(543, 527), Set(543, 538, 536, 532)), + 544 -> Seq(Set(544, 538, 535, 531)), + 545 -> Seq(Set(545, 423), Set(545, 539, 537, 532)), + 546 -> Seq(Set(546, 545, 544, 538)), + 547 -> Seq(Set(547, 543, 540, 534)), + 548 -> Seq(Set(548, 545, 543, 538)), + 549 -> Seq(Set(549, 546, 545, 533)), + 550 -> Seq(Set(550, 357), Set(550, 546, 533, 529)), + 551 -> Seq(Set(551, 416), Set(551, 550, 547, 542)), + 552 -> Seq(Set(552, 550, 547, 532)), + 553 -> Seq(Set(553, 514), Set(553, 550, 549, 542)), + 554 -> Seq(Set(554, 551, 546, 543)), + 555 -> Seq(Set(555, 551, 546, 545)), + 556 -> Seq(Set(556, 403), Set(556, 549, 546, 540)), + 557 -> Seq(Set(557, 552, 551, 550)), + 558 -> Seq(Set(558, 553, 549, 544)), + 559 -> Seq(Set(559, 525), Set(559, 557, 552, 550)), + 560 -> Seq(Set(560, 554, 551, 549)), + 561 -> Seq(Set(561, 490), Set(561, 558, 552, 550)), + 562 -> Seq(Set(562, 560, 558, 551)), + 563 -> Seq(Set(563, 561, 554, 549)), + 564 -> Seq(Set(564, 401), Set(564, 563, 561, 558)), + 565 -> Seq(Set(565, 564, 559, 554)), + 566 -> Seq(Set(566, 413), Set(566, 564, 561, 560)), + 567 -> Seq(Set(567, 424), Set(567, 563, 557, 556)), + 568 -> Seq(Set(568, 558, 557, 551)), + 569 -> Seq(Set(569, 492), Set(569, 568, 559, 557)), + 570 -> Seq(Set(570, 503), Set(570, 563, 558, 552)), + 571 -> Seq(Set(571, 569, 566, 561)), + 572 -> Seq(Set(572, 571, 564, 560)), + 573 -> Seq(Set(573, 569, 567, 563)), + 574 -> Seq(Set(574, 561), Set(574, 569, 565, 560)), + 575 -> Seq(Set(575, 429), Set(575, 572, 570, 569)), + 576 -> Seq(Set(576, 573, 572, 563)), + 577 -> Seq(Set(577, 552), Set(577, 575, 574, 569)), + 578 -> Seq(Set(578, 562, 556, 555)), + 579 -> Seq(Set(579, 572, 570, 567)), + 580 -> Seq(Set(580, 579, 576, 574)), + 581 -> Seq(Set(581, 575, 574, 568)), + 582 -> Seq(Set(582, 497), Set(582, 579, 576, 571)), + 583 -> Seq(Set(583, 453), Set(583, 581, 577, 575)), + 584 -> Seq(Set(584, 581, 571, 570)), + 585 -> Seq(Set(585, 464), Set(585, 583, 582, 577)), + 586 -> Seq(Set(586, 584, 581, 579)), + 587 -> Seq(Set(587, 586, 581, 576)), + 588 -> Seq(Set(588, 437), Set(588, 577, 572, 571)), + 589 -> Seq(Set(589, 586, 585, 579)), + 590 -> Seq(Set(590, 497), Set(590, 588, 587, 578)), + 591 -> Seq(Set(591, 587, 585, 582)), + 592 -> Seq(Set(592, 591, 573, 568)), + 593 -> Seq(Set(593, 507), Set(593, 588, 585, 584)), + 594 -> Seq(Set(594, 575), Set(594, 586, 584, 583)), + 595 -> Seq(Set(595, 594, 593, 586)), + 596 -> Seq(Set(596, 592, 591, 590)), + 597 -> Seq(Set(597, 588, 585, 583)), + 598 -> Seq(Set(598, 597, 592, 591)), + 599 -> Seq(Set(599, 569), Set(599, 593, 591, 590)), + 600 -> Seq(Set(600, 599, 590, 589)), + 601 -> Seq(Set(601, 400), Set(601, 600, 597, 589)), + 602 -> Seq(Set(602, 596, 594, 591)), + 603 -> Seq(Set(603, 600, 599, 597)), + 604 -> Seq(Set(604, 600, 598, 589)), + 605 -> Seq(Set(605, 600, 598, 595)), + 606 -> Seq(Set(606, 602, 599, 591)), + 607 -> Seq(Set(607, 502), Set(607, 600, 598, 595)), + 608 -> Seq(Set(608, 606, 602, 585)), + 609 -> Seq(Set(609, 578), Set(609, 601, 600, 597)), + 610 -> Seq(Set(610, 483), Set(610, 602, 600, 599)), + 611 -> Seq(Set(611, 609, 607, 601)), + 612 -> Seq(Set(612, 607, 602, 598)), + 613 -> Seq(Set(613, 609, 603, 594)), + 614 -> Seq(Set(614, 613, 612, 607)), + 615 -> Seq(Set(615, 404), Set(615, 614, 609, 608)), + 616 -> Seq(Set(616, 614, 602, 597)), + 617 -> Seq(Set(617, 417), Set(617, 612, 608, 607)), + 618 -> Seq(Set(618, 615, 604, 598)), + 619 -> Seq(Set(619, 614, 611, 610)), + 620 -> Seq(Set(620, 619, 618, 611)), + 621 -> Seq(Set(621, 616, 615, 609)), + 622 -> Seq(Set(622, 325), Set(622, 612, 610, 605)), + 623 -> Seq(Set(623, 555), Set(623, 614, 613, 612)), + 624 -> Seq(Set(624, 617, 615, 612)), + 625 -> Seq(Set(625, 492), Set(625, 620, 617, 613)), + 626 -> Seq(Set(626, 623, 621, 613)), + 627 -> Seq(Set(627, 622, 617, 613)), + 628 -> Seq(Set(628, 405), Set(628, 626, 617, 616)), + 629 -> Seq(Set(629, 627, 624, 623)), + 630 -> Seq(Set(630, 628, 626, 623)), + 631 -> Seq(Set(631, 324), Set(631, 625, 623, 617)), + 632 -> Seq(Set(632, 629, 619, 613)), + 633 -> Seq(Set(633, 532), Set(633, 632, 631, 626)), + 634 -> Seq(Set(634, 319), Set(634, 631, 629, 627)), + 635 -> Seq(Set(635, 631, 625, 621)), + 636 -> Seq(Set(636, 632, 628, 623)), + 637 -> Seq(Set(637, 636, 628, 623)), + 638 -> Seq(Set(638, 637, 633, 632)), + 639 -> Seq(Set(639, 623), Set(639, 636, 635, 629)), + 640 -> Seq(Set(640, 638, 637, 626)), + 641 -> Seq(Set(641, 630), Set(641, 640, 636, 622)), + 642 -> Seq(Set(642, 523), Set(642, 636, 633, 632)), + 643 -> Seq(Set(643, 641, 640, 632)), + 644 -> Seq(Set(644, 634, 633, 632)), + 645 -> Seq(Set(645, 641, 637, 634)), + 646 -> Seq(Set(646, 397), Set(646, 635, 634, 633)), + 647 -> Seq(Set(647, 642), Set(647, 646, 643, 642)), + 648 -> Seq(Set(648, 647, 626, 625)), + 649 -> Seq(Set(649, 612), Set(649, 648, 644, 638)), + 650 -> Seq(Set(650, 647), Set(650, 644, 635, 632)), + 651 -> Seq(Set(651, 646, 638, 637)), + 652 -> Seq(Set(652, 559), Set(652, 647, 643, 641)), + 653 -> Seq(Set(653, 646, 645, 643)), + 654 -> Seq(Set(654, 649, 643, 640)), + 655 -> Seq(Set(655, 567), Set(655, 653, 639, 638)), + 656 -> Seq(Set(656, 646, 638, 637)), + 657 -> Seq(Set(657, 619), Set(657, 656, 650, 649)), + 658 -> Seq(Set(658, 603), Set(658, 651, 648, 646)), + 659 -> Seq(Set(659, 657, 655, 644)), + 660 -> Seq(Set(660, 657, 656, 648)), + 661 -> Seq(Set(661, 657, 650, 649)), + 662 -> Seq(Set(662, 365), Set(662, 659, 656, 650)), + 663 -> Seq(Set(663, 406), Set(663, 655, 652, 649)), + 664 -> Seq(Set(664, 662, 660, 649)), + 665 -> Seq(Set(665, 632), Set(665, 661, 659, 654)), + 666 -> Seq(Set(666, 664, 659, 656)), + 667 -> Seq(Set(667, 664, 660, 649)), + 668 -> Seq(Set(668, 658, 656, 651)), + 669 -> Seq(Set(669, 667, 665, 664)), + 670 -> Seq(Set(670, 517), Set(670, 669, 665, 664)), + 671 -> Seq(Set(671, 656), Set(671, 669, 665, 662)), + 672 -> Seq(Set(672, 667, 666, 661)), + 673 -> Seq(Set(673, 645), Set(673, 666, 664, 663)), + 674 -> Seq(Set(674, 671, 665, 660)), + 675 -> Seq(Set(675, 674, 672, 669)), + 676 -> Seq(Set(676, 435), Set(676, 675, 671, 664)), + 677 -> Seq(Set(677, 674, 673, 669)), + 678 -> Seq(Set(678, 675, 673, 663)), + 679 -> Seq(Set(679, 613), Set(679, 676, 667, 661)), + 680 -> Seq(Set(680, 679, 650, 645)), + 681 -> Seq(Set(681, 678, 672, 670)), + 682 -> Seq(Set(682, 681, 679, 675)), + 683 -> Seq(Set(683, 682, 677, 672)), + 684 -> Seq(Set(684, 681, 671, 666)), + 685 -> Seq(Set(685, 684, 682, 681)), + 686 -> Seq(Set(686, 489), Set(686, 684, 674, 673)), + 687 -> Seq(Set(687, 674), Set(687, 682, 675, 673)), + 688 -> Seq(Set(688, 682, 674, 669)), + 689 -> Seq(Set(689, 675), Set(689, 686, 683, 681)), + 690 -> Seq(Set(690, 687, 683, 680)), + 691 -> Seq(Set(691, 689, 685, 678)), + 692 -> Seq(Set(692, 393), Set(692, 687, 686, 678)), + 693 -> Seq(Set(693, 691, 685, 678)), + 694 -> Seq(Set(694, 691, 681, 677)), + 695 -> Seq(Set(695, 483), Set(695, 694, 691, 686)), + 696 -> Seq(Set(696, 694, 686, 673)), + 697 -> Seq(Set(697, 430), Set(697, 689, 685, 681)), + 698 -> Seq(Set(698, 483), Set(698, 690, 689, 688)), + 699 -> Seq(Set(699, 698, 689, 684)), + 700 -> Seq(Set(700, 698, 695, 694)), + 701 -> Seq(Set(701, 699, 697, 685)), + 702 -> Seq(Set(702, 665), Set(702, 701, 699, 695)), + 703 -> Seq(Set(703, 702, 696, 691)), + 704 -> Seq(Set(704, 701, 699, 692)), + 705 -> Seq(Set(705, 686), Set(705, 704, 698, 697)), + 706 -> Seq(Set(706, 697, 695, 692)), + 707 -> Seq(Set(707, 702, 699, 692)), + 708 -> Seq(Set(708, 421), Set(708, 706, 704, 703)), + 709 -> Seq(Set(709, 708, 706, 705)), + 710 -> Seq(Set(710, 709, 696, 695)), + 711 -> Seq(Set(711, 619), Set(711, 704, 703, 700)), + 712 -> Seq(Set(712, 709, 708, 707)), + 713 -> Seq(Set(713, 672), Set(713, 706, 703, 696)), + 714 -> Seq(Set(714, 691), Set(714, 709, 707, 701)), + 715 -> Seq(Set(715, 714, 711, 708)), + 716 -> Seq(Set(716, 533), Set(716, 706, 705, 704)), + 717 -> Seq(Set(717, 716, 710, 701)), + 718 -> Seq(Set(718, 717, 716, 713)), + 719 -> Seq(Set(719, 569), Set(719, 711, 710, 707)), + 720 -> Seq(Set(720, 718, 712, 709)), + 721 -> Seq(Set(721, 712), Set(721, 720, 713, 712)), + 722 -> Seq(Set(722, 491), Set(722, 721, 718, 707)), + 723 -> Seq(Set(723, 717, 710, 707)), + 724 -> Seq(Set(724, 719, 716, 711)), + 725 -> Seq(Set(725, 720, 719, 716), Set(758)), + 726 -> Seq(Set(726, 721), Set(726, 725, 722, 721)), + 727 -> Seq(Set(727, 547), Set(727, 721, 719, 716)), + 728 -> Seq(Set(728, 726, 725, 724), Set(761)), + 729 -> Seq(Set(729, 671), Set(729, 726, 724, 718)), + 730 -> Seq(Set(730, 583), Set(730, 726, 715, 711)), + 731 -> Seq(Set(731, 729, 725, 723), Set(764)), + 732 -> Seq(Set(732, 729, 728, 725), Set(765)), + 733 -> Seq(Set(733, 731, 726, 725), Set(766)), + 734 -> Seq(Set(734, 724, 721, 720), Set(767)), + 735 -> Seq(Set(735, 691), Set(735, 733, 728, 727)), + 736 -> Seq(Set(736, 730, 728, 723), Set(769)), + 737 -> Seq(Set(737, 732), Set(737, 736, 733, 732)), + 738 -> Seq(Set(738, 391), Set(738, 730, 729, 727)), + 739 -> Seq(Set(739, 731, 723, 721), Set(772)), + 740 -> Seq(Set(740, 587), Set(740, 737, 728, 716)), + 741 -> Seq(Set(741, 738, 733, 732), Set(774)), + 742 -> Seq(Set(742, 741, 738, 730), Set(775)), + 743 -> Seq(Set(743, 653), Set(743, 742, 731, 730)), + 744 -> Seq(Set(744, 743, 733, 731), Set(777)), + 745 -> Seq(Set(745, 487), Set(745, 740, 738, 737)), + 746 -> Seq(Set(746, 395), Set(746, 738, 733, 728)), + 747 -> Seq(Set(747, 743, 741, 737), Set(780)), + 748 -> Seq(Set(748, 744, 743, 733), Set(781)), + 749 -> Seq(Set(749, 748, 743, 742), Set(782)), + 750 -> Seq(Set(750, 746, 741, 734), Set(783)), + 751 -> Seq(Set(751, 733), Set(751, 750, 748, 740)), + 752 -> Seq(Set(752, 749, 732, 731), Set(785)), + 753 -> Seq(Set(753, 595), Set(753, 748, 745, 740)), + 754 -> Seq(Set(754, 735), Set(754, 742, 740, 735)), + 755 -> Seq(Set(755, 754, 745, 743), Set(2048)), + 756 -> Seq(Set(756, 407), Set(756, 755, 747, 740)), + 757 -> Seq(Set(757, 756, 751, 750)), + 758 -> Seq(Set(758, 757, 746, 741)), + 759 -> Seq(Set(759, 661), Set(759, 757, 756, 750)), + 760 -> Seq(Set(760, 757, 747, 734)), + 761 -> Seq(Set(761, 758), Set(761, 760, 759, 758)), + 762 -> Seq(Set(762, 679), Set(762, 761, 755, 745)), + 763 -> Seq(Set(763, 754, 749, 747)), + 764 -> Seq(Set(764, 761, 759, 758)), + 765 -> Seq(Set(765, 760, 755, 754)), + 766 -> Seq(Set(766, 757, 747, 744)), + 767 -> Seq(Set(767, 599), Set(767, 763, 760, 759)), + 768 -> Seq(Set(768, 764, 751, 749)), + 769 -> Seq(Set(769, 649), Set(769, 763, 762, 760)), + 770 -> Seq(Set(770, 768, 765, 756)), + 771 -> Seq(Set(771, 765, 756, 754)), + 772 -> Seq(Set(772, 765), Set(772, 767, 766, 764)), + 773 -> Seq(Set(773, 767, 765, 763)), + 774 -> Seq(Set(774, 589), Set(774, 767, 760, 758)), + 775 -> Seq(Set(775, 408), Set(775, 771, 769, 768)), + 776 -> Seq(Set(776, 773, 764, 759)), + 777 -> Seq(Set(777, 748), Set(777, 776, 767, 761)), + 778 -> Seq(Set(778, 403), Set(778, 775, 762, 759)), + 779 -> Seq(Set(779, 776, 771, 769)), + 780 -> Seq(Set(780, 775, 772, 764)), + 781 -> Seq(Set(781, 779, 765, 764)), + 782 -> Seq(Set(782, 453), Set(782, 780, 779, 773)), + 783 -> Seq(Set(783, 715), Set(783, 782, 776, 773)), + 784 -> Seq(Set(784, 778, 775, 771)), + 785 -> Seq(Set(785, 693), Set(785, 780, 776, 775)), + 786 -> Seq(Set(786, 782, 780, 771)), + 1024 -> Seq(Set(1024, 1015, 1002, 1001)), + 2048 -> Seq(Set(2048, 2035, 2034, 2029)), + 4096 -> Seq(Set(4096, 4095, 4081, 4069)) ) // scalastyle:on magic.number + +} diff --git a/src/main/scala/chisel3/util/random/PRNG.scala b/src/main/scala/chisel3/util/random/PRNG.scala new file mode 100644 index 00000000..e665648c --- /dev/null +++ b/src/main/scala/chisel3/util/random/PRNG.scala @@ -0,0 +1,86 @@ +// See LICENSE for license details. + +package chisel3.util.random + +import chisel3._ +import chisel3.util.Valid + +/** Pseudo Random Number Generators (PRNG) interface + * @param n the width of the LFSR + */ +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))) + + /** When asserted, the PRNG will increment by one */ + val increment = Input(Bool()) + + /** The current state of the PRNG */ + val out = Output(UInt(n.W)) +} + +/** An abstract class representing a Pseudo Random Number Generator (PRNG) + * @param width the width of the PRNG + * @param seed the initial state of the PRNG + * @param step the number of state updates per cycle + * @param updateSeed if true, when loading the seed the state will be updated as if the seed were the current state, if + * false, the state will be set to the seed + */ +abstract class PRNG(val width: Int, val seed: Option[BigInt], step: Int = 1, updateSeed: Boolean = false) extends Module { + require(width > 0, s"Width must be greater than zero! (Found '$width')") + require(step > 0, s"Step size must be greater than one! (Found '$step')") + + val io: PRNGIO = IO(new PRNGIO(width)) + + /** 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. + */ + val state: UInt = seed match { + case Some(s) => RegInit(s.U(width.W)) + case None => Reg(UInt(width.W)) + } + + /** State update function + * @param s input state + * @return the next state + */ + def delta(s: UInt): UInt + + /** 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) } + + when (io.increment) { + state := nextState(state) + } + + when (io.seed.fire()) { + state := (if (updateSeed) { nextState(io.seed.bits) } else { io.seed.bits }) + } + + io.out := state + +} + +/** Helper utilities related to the construction of Pseudo Random Number Generators (PRNGs) */ +object PRNG { + + /** Wrap a [[PRNG]] to only return a pseudo-random [[UInt]] + * @param gen a pseudo random number generator + * @param increment when asserted the [[PRNG]] will increment + * @return the output (internal state) of the [[PRNG]] + */ + def apply(gen: => PRNG, increment: Bool = true.B): UInt = { + val prng = Module(gen) + prng.io.seed.valid := false.B + prng.io.seed.bits := DontCare + prng.io.increment := increment + prng.io.out + } + +} 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') 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/main/scala/chisel3/util/LFSR.scala | 17 +++++++++------- src/test/scala/chiselTests/LFSR16.scala | 31 +++++++++++++++++++++++++++++- src/test/scala/chiselTests/QueueSpec.scala | 13 +++++++------ 3 files changed, 47 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/main/scala/chisel3/util/LFSR.scala b/src/main/scala/chisel3/util/LFSR.scala index 3b112973..6ee6be5d 100644 --- a/src/main/scala/chisel3/util/LFSR.scala +++ b/src/main/scala/chisel3/util/LFSR.scala @@ -7,6 +7,7 @@ package chisel3.util import chisel3._ import chisel3.internal.naming.chiselName // can't use chisel3_ version because of compile order +import chisel3.util.random.FibonacciLFSR /** LFSR16 generates a 16-bit linear feedback shift register, returning the register contents. * This is useful for generating a pseudo-random sequence. @@ -27,17 +28,19 @@ import chisel3.internal.naming.chiselName // can't use chisel3_ version because * }}} */ // scalastyle:off magic.number +@deprecated("LFSR16 is deprecated in favor of the parameterized chisel3.util.random.LFSR", "3.3") object LFSR16 { /** Generates a 16-bit linear feedback shift register, returning the register contents. * @param increment optional control to gate when the LFSR updates. */ + @deprecated("Use chisel3.util.random.LFSR(16) for a 16-bit LFSR", "3.3") @chiselName - def apply(increment: Bool = true.B): UInt = { - val width = 16 - val lfsr = RegInit(1.U(width.W)) - when (increment) { lfsr := Cat(lfsr(0)^lfsr(2)^lfsr(3)^lfsr(5), lfsr(width-1,1)) } - lfsr - } + def apply(increment: Bool = true.B): UInt = + Vec( FibonacciLFSR + .maxPeriod(16, seed = Some(BigInt(1) << 15)) + .asBools + .reverse ) + .asUInt + } // scalastyle:on magic.number - 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