001/* 002 ------------------------------------------------------------------------------ 003 Rand.java: By Bob Jenkins. My random number generator, ISAAC. 004 rand.init() -- initialize 005 rand.val() -- get a random value 006 MODIFIED: 007 960327: Creation (addition of randinit, really) 008 970719: use context, not global variables, for internal state 009 980224: Translate to Java 010 ------------------------------------------------------------------------------ 011 */ 012 013package squidpony.squidmath; 014 015import java.util.Arrays; 016/** 017 * This is a port of the public domain Isaac64 (cryptographic) random number generator to Java. 018 * It is a RandomnessSource here, so it should generally be used to make an RNG, which has more 019 * features. IsaacRNG is slower than the non-cryptographic RNGs in SquidLib, but much faster 020 * than cryptographic RNGs that need SecureRandom, plus it's compatible with GWT and Android! 021 * Created by Tommy Ettinger on 8/1/2016. 022 */ 023public class IsaacRNG implements RandomnessSource { 024 private int count; /* count through the results in results[] */ 025 private long[] results; /* the results given to the user */ 026 private long[] mem; /* the internal state */ 027 private long a; /* accumulator */ 028 private long b; /* the last result */ 029 private long c; /* counter, guarantees cycle is at least 2^^72 */ 030 031 032 /** 033 * Constructs an IsaacRNG with no seed; this will produce one sequence of numbers as if the seed were 0 034 * (which it essentially is, though passing 0 to the constructor that takes a long will produce a different 035 * sequence) instead of what the other RandomnessSources do (initialize with a low-quality random number 036 * from Math.random()). 037 */ 038 public IsaacRNG() { 039 mem = new long[256]; 040 results = new long[256]; 041 init(false); 042 } 043 044 045 /** 046 * Constructs an IsaacRNG with the given seed, which should be a rather large array of long values. 047 * You should try to make seed a long[256], but smaller arrays will be tolerated without error. 048 * Arrays larger than 256 items will only have the first 256 used. 049 * @param seed an array of longs to use as a seed; ideally it should be 256 individual longs 050 */ 051 public IsaacRNG(long[] seed) { 052 mem = new long[256]; 053 results = new long[256]; 054 if(seed == null) 055 init(false); 056 else { 057 System.arraycopy(seed, 0, results, 0, Math.min(256, seed.length)); 058 init(true); 059 } 060 } 061 062 /** 063 * Constructs an IsaacRNG with its state filled by the value of seed, run through the LightRNG algorithm. 064 * @param seed any long; will have equal influence on all bits of state 065 */ 066 public IsaacRNG(long seed) { 067 mem = new long[256]; 068 results = new long[256]; 069 long z; 070 for (int i = 0; i < 256; i++) { 071 z = ( seed += 0x9E3779B97F4A7C15L ); 072 z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; 073 z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; 074 results[i] = z ^ (z >>> 31); 075 } 076 init(true); 077 } 078 079 /** 080 * Constructs an IsaacRNG with its state filled by repeated hashing of seed. 081 * @param seed a String that should be exceptionally long to get the best results. 082 */ 083 public IsaacRNG(String seed) { 084 mem = new long[256]; 085 results = new long[256]; 086 if(seed == null) 087 init(false); 088 else { 089 char[] chars = seed.toCharArray(); 090 int slen = seed.length(), i = 0; 091 for (; i < 256 && i < slen; i++) { 092 results[i] = CrossHash.hash64(chars, i, slen); 093 } 094 for (; i < 256; i++) { 095 results[i] = CrossHash.hash64(results); 096 } 097 init(true); 098 } 099 } 100 101 private IsaacRNG(IsaacRNG other) 102 { 103 this(other.results); 104 } 105 106 /** 107 * Generates 256 results to be used by later calls to next() or nextLong(). 108 * This is a fast (not small) implementation. 109 * */ 110 public final void regen() { 111 int i, j; 112 long x, y; 113 114 b += ++c; 115 for (i=0, j=128; i<128;) { 116 x = mem[i]; 117 a = ~(a ^ a << 21) + mem[j++]; 118 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 119 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 120 121 x = mem[i]; 122 a = (a ^ a >>> 5) + mem[j++]; 123 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 124 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 125 126 x = mem[i]; 127 a = (a ^ a << 12) + mem[j++]; 128 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 129 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 130 131 x = mem[i]; 132 a = (a ^ a >>> 33) + mem[j++]; 133 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 134 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 135 } 136 137 for (j=0; j<128;) { 138 x = mem[i]; 139 a = ~(a ^ a << 21) + mem[j++]; 140 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 141 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 142 143 x = mem[i]; 144 a = (a ^ a >>> 5) + mem[j++]; 145 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 146 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 147 148 x = mem[i]; 149 a = (a ^ a << 12) + mem[j++]; 150 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 151 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 152 153 x = mem[i]; 154 a = (a ^ a >>> 33) + mem[j++]; 155 mem[i] = y = mem[(int)(x >> 3 & 255)] + a + b; 156 results[i++] = b = mem[(int)(y >> 11 & 255)] + x; 157 } 158 } 159 /** 160 * Can be used to re-initialize this IsaacRNG as if using the long-array constructor. 161 * The given seed should be a rather large array of long values. 162 * You should try to make seed a long[256], but smaller arrays will be tolerated without error. 163 * Arrays larger than 256 items will only have the first 256 used. 164 * @param seed an array of longs to use as a seed; ideally it should be 256 individual longs 165 */ 166 public void init(long[] seed) { 167 if(seed == null) 168 init(false); 169 else { 170 System.arraycopy(seed, 0, results, 0, Math.min(256, seed.length)); 171 init(true); 172 } 173 } 174 175 /** 176 * Can be used to re-initialize this IsaacRNG as if using the single-long constructor. 177 * @param seed any long; will have equal influence on all bits of state 178 */ 179 public void init(long seed) { 180 long z; 181 for (int i = 0; i < 256; i++) { 182 z = ( seed += 0x9E3779B97F4A7C15L ); 183 z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; 184 z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; 185 results[i] = z ^ (z >>> 31); 186 } 187 init(true); 188 } 189 190 /** 191 * Can be used to re-initialize this IsaacRNG as if using the single-String constructor. 192 * @param seed a String; if non-null, its contents will be used as a seed 193 */ 194 public final void init(String seed) 195 { 196 if(seed == null) 197 init(false); 198 else { 199 char[] chars = seed.toCharArray(); 200 int slen = seed.length(), i = 0; 201 for (; i < 256 && i < slen; i++) { 202 results[i] = CrossHash.hash64(chars, i, slen); 203 } 204 for (; i < 256; i++) { 205 results[i] = CrossHash.hash64(results); 206 } 207 init(true); 208 } 209 210 } 211 212 /** 213 * Initializes this IsaacRNG; typically used from the constructor but can be called externally. 214 * @param flag if true, use data from seed; if false, initializes this to unseeded random state 215 */ 216 public final void init(boolean flag) { 217 int i; 218 long a,b,c,d,e,f,g,h; 219 a=b=c=d=e=f=g=h=0x9e3779b97f4a7c13L; /* the golden ratio */ 220 221 for (i=0; i<4; ++i) { 222 a-=e; f^=h>>>9; h+=a; 223 b-=f; g^=a<<9; a+=b; 224 c-=g; h^=b>>>23; b+=c; 225 d-=h; a^=c<<15; c+=d; 226 e-=a; b^=d>>>14; d+=e; 227 f-=b; c^=e<<20; e+=f; 228 g-=c; d^=f>>>17; f+=g; 229 h-=d; e^=g<<14; g+=h; 230 /* 231 a^=b<<11; d+=a; b+=c; 232 b^=c>>>3; e+=b; c+=d; 233 c^=d<<8; f+=c; d+=e; 234 d^=e>>>16; g+=d; e+=f; 235 e^=f<<10; h+=e; f+=g; 236 f^=g>>>4; a+=f; g+=h; 237 g^=h<<8; b+=g; h+=a; 238 h^=a>>>9; c+=h; a+=b; 239 */ 240 } 241 242 for (i=0; i<256; i+=8) { /* fill in mem[] with messy stuff */ 243 if (flag) { 244 a+= results[i ]; b+= results[i+1]; c+= results[i+2]; d+= results[i+3]; 245 e+= results[i+4]; f+= results[i+5]; g+= results[i+6]; h+= results[i+7]; 246 } 247 a-=e; f^=h>>>9; h+=a; 248 b-=f; g^=a<<9; a+=b; 249 c-=g; h^=b>>>23; b+=c; 250 d-=h; a^=c<<15; c+=d; 251 e-=a; b^=d>>>14; d+=e; 252 f-=b; c^=e<<20; e+=f; 253 g-=c; d^=f>>>17; f+=g; 254 h-=d; e^=g<<14; g+=h; 255 mem[i ]=a; mem[i+1]=b; mem[i+2]=c; mem[i+3]=d; 256 mem[i+4]=e; mem[i+5]=f; mem[i+6]=g; mem[i+7]=h; 257 } 258 259 if (flag) { /* second pass makes all of seed affect all of mem */ 260 for (i=0; i<256; i+=8) { 261 a+=mem[i ]; b+=mem[i+1]; c+=mem[i+2]; d+=mem[i+3]; 262 e+=mem[i+4]; f+=mem[i+5]; g+=mem[i+6]; h+=mem[i+7]; 263 a-=e; f^=h>>>9; h+=a; 264 b-=f; g^=a<<9; a+=b; 265 c-=g; h^=b>>>23; b+=c; 266 d-=h; a^=c<<15; c+=d; 267 e-=a; b^=d>>>14; d+=e; 268 f-=b; c^=e<<20; e+=f; 269 g-=c; d^=f>>>17; f+=g; 270 h-=d; e^=g<<14; g+=h; 271 mem[i ]=a; mem[i+1]=b; mem[i+2]=c; mem[i+3]=d; 272 mem[i+4]=e; mem[i+5]=f; mem[i+6]=g; mem[i+7]=h; 273 } 274 } 275 276 regen(); 277 count = 256; 278 } 279 280 281 @Override 282 public final long nextLong() { 283 if (0 == count--) { 284 regen(); 285 count = 255; 286 } 287 return results[count]; 288 } 289 290 /** 291 * Generates and returns a block of 256 pseudo-random long values. 292 * @return a freshly-allocated array of 256 pseudo-random longs, with all bits possible 293 */ 294 public final long[] nextBlock() 295 { 296 regen(); 297 final long[] block = new long[256]; 298 System.arraycopy(results, 0, block, 0, 256); 299 count = 0; 300 return block; 301 } 302 303 /** 304 * Generates enough pseudo-random long values to fill {@code data} and assigns them to it. 305 */ 306 public final void fillBlock(final long[] data) 307 { 308 int len, i; 309 if(data == null || (len = data.length) == 0) return; 310 for (i = 0; len > 256; i += 256, len -= 256) { 311 regen(); 312 System.arraycopy(results, 0, data, i, 256); 313 } 314 regen(); 315 System.arraycopy(results, 0, data, i, len); 316 count = len & 255; 317 } 318 319 @Override 320 public final int next( int bits ) { 321 //return (int)( nextLong() >>> (64 - bits) ); 322 return (int)( nextLong() & ( 1L << bits ) - 1 ); 323 } 324 325 /** 326 * Produces another RandomnessSource, but the new one will not produce the same data as this one. 327 * This is meant to be a "more-secure" generator, so this helps reduce the ability to guess future 328 * results from a given sequence of output. 329 * @return another RandomnessSource with the same implementation but no guarantees as to generation 330 */ 331 @Override 332 public final IsaacRNG copy() { 333 return new IsaacRNG(results); 334 } 335 336 @Override 337 public boolean equals(Object o) { 338 if (this == o) return true; 339 if (o == null || getClass() != o.getClass()) return false; 340 341 IsaacRNG isaacRNG = (IsaacRNG) o; 342 343 if (count != isaacRNG.count) return false; 344 if (a != isaacRNG.a) return false; 345 if (b != isaacRNG.b) return false; 346 if (c != isaacRNG.c) return false; 347 if (!Arrays.equals(results, isaacRNG.results)) return false; 348 return Arrays.equals(mem, isaacRNG.mem); 349 } 350 351 @Override 352 public String toString() 353 { 354 return "IsaacRNG with a hidden state (id is " + System.identityHashCode(this) + ')'; 355 } 356}