Merge pull request #1088 from freechipsproject/lfsr

- Add chisel3.util.random package with Galois and Fibonacci LFSRs
- Add maximal period LFSR generation and maximal period taps
- Deprecate chisel3.util.LFSR16 in favor of chisel3.util.random.LFSR(16)

10 files changed, 1475 insertions, 24 deletions

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/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
 }
diff --git a/src/test/scala/chiselTests/LFSR16.scala b/src/test/scala/chiselTests/LFSR16.scala
index 54a3591f..992bb4bf 100644
--- a/src/test/scala/chiselTests/LFSR16.scala
+++ b/src/test/scala/chiselTests/LFSR16.scala
@@ -5,6 +5,7 @@ package chiselTests
 import chisel3._
 import chisel3.testers.BasicTester
 import chisel3.util._
+import chisel3.util.random.{PRNG, LFSR}
 
 /**
   * This test creates two 4 sided dice.
@@ -12,14 +13,16 @@ import chisel3.util._
   * The asserts check that the bins show the correct distribution.
   */
 //scalastyle:off magic.number
-class LFSRTester extends BasicTester {
+class LFSRDistribution(gen: => UInt, cycles: Int = 10000) extends BasicTester {
+
+  val rv = gen
   val bins = Reg(Vec(8, UInt(32.W)))
 
   // Use tap points on each LFSR so values are more independent
-  val die0 = Cat(Seq.tabulate(2) { i => LFSR16()(i) })
-  val die1 = Cat(Seq.tabulate(2) { i => LFSR16()(i + 2) })
+  val die0 = Cat(Seq.tabulate(2) { i => rv(i) })
+  val die1 = Cat(Seq.tabulate(2) { i => rv(i + 2) })
 
-  val (trial, done) = Counter(true.B, 10000)
+  val (trial, done) = Counter(true.B, cycles)
 
   val rollValue = die0 +& die1  // Note +& is critical because sum will need an extra bit.
 
@@ -41,24 +44,53 @@ class LFSRTester extends BasicTester {
   }
 }
 
-class LFSR16MaxPeriod extends BasicTester {
+class LFSRMaxPeriod(gen: => UInt) extends BasicTester {
 
-  val lfsr16 = LFSR16()
+  val rv = gen
   val started = RegNext(true.B, false.B)
+  val seed = withReset(!started) { RegInit(rv) }
 
-  val (_, wrap) = Counter(started, math.pow(2.0, 16).toInt - 1)
-  when (lfsr16 === 1.U && started) {
+  val (_, wrap) = Counter(started, math.pow(2.0, rv.getWidth).toInt - 1)
+  when (rv === seed && started) {
     chisel3.assert(wrap)
     stop()
   }
 }
 
+/** Check that the output of the new LFSR is the same asthe old LFSR */
+class MeetTheNewLFSR16SameAsTheOldLFSR16 extends BasicTester {
+
+  /** This is the exact implementation of the old LFSR16 algorithm */
+  val oldLfsr = {
+    val width = 16
+    val lfsr = RegInit(1.U(width.W))
+    lfsr := Cat(lfsr(0)^lfsr(2)^lfsr(3)^lfsr(5), lfsr(width-1,1))
+    lfsr
+  }
+
+  /** The new LFSR16 uses equivalent taps and a reverse so that it can use LFSR(16) under the hood. */
+  val newLfsr = LFSR16()
+
+  val (_, done) = Counter(true.B, 16)
+
+  assert(oldLfsr === newLfsr)
+
+  when (done) {
+    stop()
+  }
+
+}
+
 class LFSRSpec extends ChiselPropSpec {
   property("LFSR16 can be used to produce pseudo-random numbers, this tests the distribution") {
-    assertTesterPasses{ new LFSRTester }
+    assertTesterPasses{ new LFSRDistribution(LFSR16()) }
   }
 
   property("LFSR16 period tester, Period should 2^16 - 1") {
-    assertTesterPasses { new LFSR16MaxPeriod }
+    assertTesterPasses{ new LFSRMaxPeriod(LFSR16()) }
+  }
+
+  property("New LFSR16 is the same as the old LFSR16") {
+    assertTesterPasses{ new MeetTheNewLFSR16SameAsTheOldLFSR16 }
   }
 }
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()))
 
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))
+  }
+
+}