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).

5 files changed, 1208 insertions, 1 deletions

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
 }