Line data    Source code

       1             : import { Engine } from "../types.ts";
       2           1 : import { INT32_MAX, INT32_SIZE } from "../utils/constants.ts";
       3           1 : import { createEntropy } from "../utils/createEntropy.ts";
       4           1 : import { imul } from "../utils/imul.ts";
       5           1 : import { Int32Array } from "../utils/Int32Array.ts";
       6             : 
       7           1 : const ARRAY_SIZE = 624;
       8           1 : const ARRAY_MAX = ARRAY_SIZE - 1;
       9           1 : const M = 397;
      10           1 : const ARRAY_SIZE_MINUS_M = ARRAY_SIZE - M;
      11           1 : const A = 0x9908b0df;
      12             : 
      13             : /**
      14             :  * An Engine that is a pseudorandom number generator using the Mersenne
      15             :  * Twister algorithm based on the prime 2**19937 − 1
      16             :  *
      17             :  * See http://en.wikipedia.org/wiki/Mersenne_twister
      18             :  */
      19           1 : export class MersenneTwister19937 implements Engine {
      20             : 
      21             :   /**
      22             :    * Returns a MersenneTwister19937 seeded with an initial int32 value
      23             :    * @param initial the initial seed value
      24             :    */
      25           0 :   public static seed(initial: number): MersenneTwister19937 {
      26           0 :     return new MersenneTwister19937().seed(initial);
      27           0 :   }
      28             : 
      29             :   /**
      30             :    * Returns a MersenneTwister19937 seeded with zero or more int32 values
      31             :    * @param source A series of int32 values
      32             :    */
      33           0 :   public static seedWithArray(source: ArrayLike<number>): MersenneTwister19937 {
      34           0 :     return new MersenneTwister19937().seedWithArray(source);
      35           0 :   }
      36             : 
      37             :   /**
      38             :    * Returns a MersenneTwister19937 seeded with the current time and
      39             :    * a series of natively-generated random values
      40             :    */
      41           0 :   public static autoSeed(): MersenneTwister19937 {
      42           0 :     return MersenneTwister19937.seedWithArray(createEntropy());
      43           0 :   }
      44             : 
      45           0 :   private readonly data = new Int32Array(ARRAY_SIZE);
      46           0 :   private index = 0; // integer within [0, 624]
      47           0 :   private uses = 0;
      48             : 
      49             :   /**
      50             :    * MersenneTwister19937 should not be instantiated directly.
      51             :    * Instead, use the static methods `seed`, `seedWithArray`, or `autoSeed`.
      52             :    */
      53           0 :   private constructor() {}
      54             : 
      55             :   /**
      56             :    * Returns the next int32 value of the sequence
      57             :    */
      58           0 :   public next(): number {
      59           0 :     if ((this.index | 0) >= ARRAY_SIZE) {
      60           0 :       refreshData(this.data);
      61           0 :       this.index = 0;
      62           0 :     }
      63             : 
      64           0 :     const value = this.data[this.index];
      65           0 :     this.index = (this.index + 1) | 0;
      66           0 :     this.uses += 1;
      67           0 :     return temper(value) | 0;
      68           0 :   }
      69             : 
      70             :   /**
      71             :    * Returns the number of times that the Engine has been used.
      72             :    *
      73             :    * This can be provided to an unused MersenneTwister19937 with the same
      74             :    * seed, bringing it to the exact point that was left off.
      75             :    */
      76           0 :   public getUseCount(): number {
      77           0 :     return this.uses;
      78           0 :   }
      79             : 
      80             :   /**
      81             :    * Discards one or more items from the engine
      82             :    * @param count The count of items to discard
      83             :    */
      84           0 :   public discard(count: number): this {
      85           0 :     if (count <= 0) {
      86           0 :       return this;
      87           0 :     }
      88           0 :     this.uses += count;
      89           0 :     if ((this.index | 0) >= ARRAY_SIZE) {
      90           0 :       refreshData(this.data);
      91           0 :       this.index = 0;
      92           0 :     }
      93           0 :     while (count + this.index > ARRAY_SIZE) {
      94           0 :       count -= ARRAY_SIZE - this.index;
      95           0 :       refreshData(this.data);
      96           0 :       this.index = 0;
      97           0 :     }
      98           0 :     this.index = (this.index + count) | 0;
      99           0 :     return this;
     100           0 :   }
     101             : 
     102           0 :   private seed(initial: number): this {
     103           0 :     let previous = 0;
     104           0 :     this.data[0] = previous = initial | 0;
     105             : 
     106           0 :     for (let i = 1; i < ARRAY_SIZE; i = (i + 1) | 0) {
     107           0 :       this.data[i] = previous =
     108           0 :         (imul(previous ^ (previous >>> 30), 0x6c078965) + i) | 0;
     109           0 :     }
     110           0 :     this.index = ARRAY_SIZE;
     111           0 :     this.uses = 0;
     112           0 :     return this;
     113           0 :   }
     114             : 
     115           0 :   private seedWithArray(source: ArrayLike<number>): this {
     116           0 :     this.seed(0x012bd6aa);
     117           0 :     seedWithArray(this.data, source);
     118           0 :     return this;
     119           0 :   }
     120           1 : }
     121             : 
     122           0 : function refreshData(data: Int32Array) {
     123           0 :   let k = 0;
     124           0 :   let tmp = 0;
     125           0 :   for (; (k | 0) < ARRAY_SIZE_MINUS_M; k = (k + 1) | 0) {
     126           0 :     tmp = (data[k] & INT32_SIZE) | (data[(k + 1) | 0] & INT32_MAX);
     127           0 :     data[k] = data[(k + M) | 0] ^ (tmp >>> 1) ^ (tmp & 0x1 ? A : 0);
     128           0 :   }
     129             : 
     130           0 :   for (; (k | 0) < ARRAY_MAX; k = (k + 1) | 0) {
     131           0 :     tmp = (data[k] & INT32_SIZE) | (data[(k + 1) | 0] & INT32_MAX);
     132           0 :     data[k] =
     133           0 :       data[(k - ARRAY_SIZE_MINUS_M) | 0] ^ (tmp >>> 1) ^ (tmp & 0x1 ? A : 0);
     134           0 :   }
     135             : 
     136           0 :   tmp = (data[ARRAY_MAX] & INT32_SIZE) | (data[0] & INT32_MAX);
     137           0 :   data[ARRAY_MAX] = data[M - 1] ^ (tmp >>> 1) ^ (tmp & 0x1 ? A : 0);
     138           0 : }
     139             : 
     140           0 : function temper(value: number) {
     141           0 :   value ^= value >>> 11;
     142           0 :   value ^= (value << 7) & 0x9d2c5680;
     143           0 :   value ^= (value << 15) & 0xefc60000;
     144           0 :   return value ^ (value >>> 18);
     145           0 : }
     146             : 
     147           0 : function seedWithArray(data: Int32Array, source: ArrayLike<number>) {
     148           0 :   let i = 1;
     149           0 :   let j = 0;
     150           0 :   const sourceLength = source.length;
     151           0 :   let k = Math.max(sourceLength, ARRAY_SIZE) | 0;
     152           0 :   let previous = data[0] | 0;
     153           0 :   for (; (k | 0) > 0; --k) {
     154           0 :     data[i] = previous =
     155           0 :       ((data[i] ^ imul(previous ^ (previous >>> 30), 0x0019660d)) +
     156           0 :         (source[j] | 0) +
     157           0 :         (j | 0)) |
     158           0 :       0;
     159           0 :     i = (i + 1) | 0;
     160           0 :     ++j;
     161           0 :     if ((i | 0) > ARRAY_MAX) {
     162           0 :       data[0] = data[ARRAY_MAX];
     163           0 :       i = 1;
     164           0 :     }
     165           0 :     if (j >= sourceLength) {
     166           0 :       j = 0;
     167           0 :     }
     168           0 :   }
     169           0 :   for (k = ARRAY_MAX; (k | 0) > 0; --k) {
     170           0 :     data[i] = previous =
     171           0 :       ((data[i] ^ imul(previous ^ (previous >>> 30), 0x5d588b65)) - i) | 0;
     172           0 :     i = (i + 1) | 0;
     173           0 :     if ((i | 0) > ARRAY_MAX) {
     174           0 :       data[0] = data[ARRAY_MAX];
     175           0 :       i = 1;
     176           0 :     }
     177           0 :   }
     178           0 :   data[0] = INT32_SIZE;
     179           0 : }