001package squidpony.squidmath;
002
003import squidpony.annotation.GwtIncompatible;
004
005import java.security.SecureRandom;
006
007/**
008 * An RNG that cannot be seeded and should be fairly hard to predict what it will return next. Useful for competitions
009 * where a seeded RNG is used for dungeon generation and enemy placement but an unpredictable RNG is needed for combat,
010 * so players can't abuse the RNG to make improbable events guaranteed or unfavorable outcomes impossible. The
011 * performance of this as a RandomnessSource is also fairly good, taking approximately 1.5x to 1.7x as long as LightRNG
012 * to produce random 64-bit data, and of course it is far faster than java.util.Random (which is 10x slower than this).
013 * In the secure random numbers category, where this isn't quite as secure as most, ChaosRNG is about 80x faster than
014 * SecureRandom once SecureRandom warms up, which takes about 10 minutes of continuous number generation. Before that,
015 * ChaosRNG is about 110x faster than SecureRandom for 64-bit data.
016 * <br>
017 * This is intended to be used as a RandomnessSource for an RNG, and does not have any methods other than those needed
018 * for that interface, with one exception -- the randomize() method, which can be used to completely change all 1024
019 * bits of state using cryptographic random numbers. If you create a ChaosRNG and keep it around for later, then you can
020 * pass it to the RNG constructor and later call randomize() on the ChaosRNG if you suspect it may be becoming
021 * predictable. The period on this RNG is (2 to the 1024) - 1, so predicting it may be essentially impossible unless the
022 * user can poke around in the application, use reflection, etc.
023 * Created by Tommy Ettinger on 3/17/2016.
024 */
025@GwtIncompatible
026public class ChaosRNG implements RandomnessSource{
027
028    private long[] state = new long[16];
029    private int choice;
030    private SecureRandom sec;
031    private static final long serialVersionUID = -254415589291474491L;
032
033    /**
034     * Builds a ChaosRNG with a cryptographically-random seed. Future random generation uses less secure methods but
035     * should still make it extremely difficult to "divine" the future RNG results.
036     */
037    public ChaosRNG()
038    {
039        sec = new SecureRandom();
040        byte[] bytes = new byte[128];
041        sec.nextBytes(bytes);
042        for (int i = sec.nextInt() & 127, c = 0; c < 128; c++, i = i + 1 & 127) {
043            state[i & 15] |= bytes[c] << ((i >> 4) << 3);
044        }
045        choice = sec.nextInt(16);
046    }
047
048    @Override
049    public int next( int bits ) {
050        return (int)( nextLong() & ( 1L << bits ) - 1 );
051    }
052
053    /**
054     * Can return any long, positive or negative, of any size permissible in a 64-bit signed integer.
055     * @return any long, all 64 bits are random
056     */
057    @Override
058    public long nextLong() {
059        final long s0 = state[choice];
060        long s1 = state[choice = (choice + 1) & 15];
061        s1 ^= s1 << 31; // a
062        state[choice] = s1 ^ s0 ^ (s1 >> 11) ^ (s0 >> 30); // b,c
063        return state[choice] * 1181783497276652981L;
064    }
065
066    /**
067     * Produces another ChaosRNG with no relation to this one; this breaks the normal rules that RandomnessSource.copy
068     * abides by because this class should never have its generated number sequence be predictable.
069     * @return a new, unrelated ChaosRNG as a RandomnessSource
070     */
071    @Override
072    public RandomnessSource copy() {
073        return new ChaosRNG();
074    }
075
076    /**
077     * Changes the internal state to a new, fully-random version that should have no relation to the previous state.
078     * May be somewhat slow; you shouldn't need to call this often.
079     */
080    public void randomize()
081    {
082        byte[] bytes = sec.generateSeed(128);
083        for (int i = sec.nextInt() & 127, c = 0; c < 128; c++, i = i + 1 & 127) {
084            state[i & 15] |= bytes[c] << ((i >> 4) << 3);
085        }
086        choice = sec.nextInt(16);
087    }
088
089    @Override
090    public String toString() {
091        return "ChaosRNG with state determined by the power of friendship";
092    }
093}