001package squidpony.squidmath; 002 003import squidpony.annotation.GwtIncompatible; 004 005import java.security.SecureRandom; 006import java.util.Arrays; 007import java.util.concurrent.locks.ReentrantLock; 008 009/** 010 * Customized extension of Random to allow for common roguelike operations. 011 * 012 * Uses the Mersenne Twister algorithm to provide superior results. Because of 013 * the seed requirements for the MT, the seed setting methods and constructors 014 * that take a long do not set the seed. The methods that use a byte[] to set 015 * the seed must be used instead if a custom seed is desired. 016 * 017 * @author Daniel Dyer (Java Port) 018 * @author Makoto Matsumoto and Takuji Nishimura (original C version) 019 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 020 * @author Lewis Potter 021 */ 022@GwtIncompatible /* Because of SecureRandom */ 023public class MersenneTwister implements RandomnessSource { 024 025 // The actual seed size isn't that important, but it should be a multiple of 4. 026 private static final int SEED_SIZE_BYTES = 16; 027 // Magic numbers from original C version. 028 private static final int N = 624; 029 private static final int M = 397; 030 private static final int[] MAG01 = {0, 0x9908b0df}; 031 private static final int UPPER_MASK = 0x80000000; 032 private static final int LOWER_MASK = 0x7fffffff; 033 private static final int BOOTSTRAP_SEED = 19650218; 034 private static final int BOOTSTRAP_FACTOR = 1812433253; 035 private static final int SEED_FACTOR1 = 1664525; 036 private static final int SEED_FACTOR2 = 1566083941; 037 private static final int GENERATE_MASK1 = 0x9d2c5680; 038 private static final int GENERATE_MASK2 = 0xefc60000; 039 private final byte[] seed; 040 // Lock to prevent concurrent modification of the RNG's internal state. 041 private final ReentrantLock lock = new ReentrantLock(); 042 private final int[] mt = new int[N]; // State vector. 043 private int mtIndex = 0; // Index into state vector. 044 private static final int BITWISE_BYTE_TO_INT = 0x000000FF; 045 046 private static final long serialVersionUID = 217351968847857679L; 047 048 /** 049 * Creates a new RNG and seeds it using the default seeding strategy. 050 */ 051 public MersenneTwister() { 052 this((new SecureRandom()).generateSeed(SEED_SIZE_BYTES)); 053 } 054 055 /** 056 * Creates an RNG and seeds it with the specified seed data. 057 * 058 * @param seed The seed data used to initialize the RNG. 059 */ 060 public MersenneTwister(byte[] seed) { 061 if (seed == null || seed.length != SEED_SIZE_BYTES) { 062 throw new IllegalArgumentException("Mersenne Twister RNG requires a 128-bit (16-byte) seed."); 063 } 064 this.seed = Arrays.copyOf(seed, seed.length); 065 066 int[] seedInts = convertBytesToInts(this.seed); 067 068 // This section is translated from the init_genrand code in the C version. 069 mt[0] = BOOTSTRAP_SEED; 070 for (mtIndex = 1; mtIndex < N; mtIndex++) { 071 mt[mtIndex] = (BOOTSTRAP_FACTOR 072 * (mt[mtIndex - 1] ^ (mt[mtIndex - 1] >>> 30)) 073 + mtIndex); 074 } 075 076 // This section is translated from the init_by_array code in the C version. 077 int i = 1; 078 int j = 0; 079 for (int k = Math.max(N, seedInts.length); k > 0; k--) { 080 mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * SEED_FACTOR1)) + seedInts[j] + j; 081 i++; 082 j++; 083 if (i >= N) { 084 mt[0] = mt[N - 1]; 085 i = 1; 086 } 087 if (j >= seedInts.length) { 088 j = 0; 089 } 090 } 091 for (int k = N - 1; k > 0; k--) { 092 mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * SEED_FACTOR2)) - i; 093 i++; 094 if (i >= N) { 095 mt[0] = mt[N - 1]; 096 i = 1; 097 } 098 } 099 mt[0] = UPPER_MASK; // Most significant bit is 1 - guarantees non-zero initial array. 100 } 101 102 /** 103 * Take four bytes from the specified position in the specified block and 104 * convert them into a 32-bit int, using the big-endian convention. 105 * 106 * @param bytes The data to read from. 107 * @param offset The position to start reading the 4-byte int from. 108 * @return The 32-bit integer represented by the four bytes. 109 */ 110 public static int convertBytesToInt(byte[] bytes, int offset) { 111 return (BITWISE_BYTE_TO_INT & bytes[offset + 3]) 112 | ((BITWISE_BYTE_TO_INT & bytes[offset + 2]) << 8) 113 | ((BITWISE_BYTE_TO_INT & bytes[offset + 1]) << 16) 114 | ((BITWISE_BYTE_TO_INT & bytes[offset]) << 24); 115 } 116 117 /** 118 * Convert an array of bytes into an array of ints. 4 bytes from the input 119 * data map to a single int in the output data. 120 * 121 * @param bytes The data to read from. 122 * @return An array of 32-bit integers constructed from the data. 123 * @since 1.1 124 */ 125 public static int[] convertBytesToInts(byte[] bytes) { 126 if (bytes.length % 4 != 0) { 127 throw new IllegalArgumentException("Number of input bytes must be a multiple of 4."); 128 } 129 int[] ints = new int[bytes.length / 4]; 130 for (int i = 0; i < ints.length; i++) { 131 ints[i] = convertBytesToInt(bytes, i * 4); 132 } 133 return ints; 134 } 135 136 public byte[] getSeed() { 137 return Arrays.copyOf(seed, seed.length); 138 } 139 140 @Override 141 public final int next(int bits) { 142 int y; 143 try { 144 lock.lock(); 145 if (mtIndex >= N) // Generate N ints at a time. 146 { 147 int kk; 148 for (kk = 0; kk < N - M; kk++) { 149 y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK); 150 mt[kk] = mt[kk + M] ^ (y >>> 1) ^ MAG01[y & 0x1]; 151 } 152 for (; kk < N - 1; kk++) { 153 y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK); 154 mt[kk] = mt[kk + (M - N)] ^ (y >>> 1) ^ MAG01[y & 0x1]; 155 } 156 y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK); 157 mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ MAG01[y & 0x1]; 158 159 mtIndex = 0; 160 } 161 162 y = mt[mtIndex++]; 163 } finally { 164 lock.unlock(); 165 } 166 // Tempering 167 y ^= (y >>> 11); 168 y ^= (y << 7) & GENERATE_MASK1; 169 y ^= (y << 15) & GENERATE_MASK2; 170 y ^= (y >>> 18); 171 172 return y >>> (32 - bits); 173 } 174 @Override 175 public final long nextLong() { 176 return ((next(32) & 0xffffffffL) << 32) | (next(32) & 0xffffffffL); 177 } 178 179 /** 180 * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the 181 * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to 182 * copy the state so it isn't shared, usually, and produce a new value with the same exact state. 183 * 184 * @return a copy of this RandomnessSource 185 */ 186 @Override 187 public RandomnessSource copy() { 188 MersenneTwister next = new MersenneTwister(seed); 189 System.arraycopy(mt, 0, next.mt, 0, mt.length); 190 next.mtIndex = mtIndex; 191 return next; 192 } 193 194}