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}