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}