1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.math3.random; 19 20 import org.apache.commons.math3.util.FastMath; 21 22 import java.io.Serializable; 23 24 /** 25 * <a href="http://burtleburtle.net/bob/rand/isaacafa.html">ISAAC: a fast cryptographic 26 * pseudo-random number generator</a> <br> 27 * ISAAC (Indirection, Shift, Accumulate, Add, and Count) generates 32-bit random numbers. ISAAC has 28 * been designed to be cryptographically secure and is inspired by RC4. Cycles are guaranteed to be 29 * at least 2<sup>40</sup> values long, and they are 2<sup>8295</sup> values long on average. The 30 * results are uniformly distributed, unbiased, and unpredictable unless you know the seed. <br> 31 * This code is based (with minor changes and improvements) on the original implementation of the 32 * algorithm by Bob Jenkins. <br> 33 * 34 * @since 3.0 35 */ 36 public class ISAACRandom extends BitsStreamGenerator implements Serializable { 37 /** Serializable version identifier */ 38 private static final long serialVersionUID = 7288197941165002400L; 39 40 /** Log of size of rsl[] and mem[] */ 41 private static final int SIZE_L = 8; 42 43 /** Size of rsl[] and mem[] */ 44 private static final int SIZE = 1 << SIZE_L; 45 46 /** Half-size of rsl[] and mem[] */ 47 private static final int H_SIZE = SIZE >> 1; 48 49 /** For pseudo-random lookup */ 50 private static final int MASK = SIZE - 1 << 2; 51 52 /** The golden ratio */ 53 private static final int GLD_RATIO = 0x9e3779b9; 54 55 /** The results given to the user */ 56 private final int[] rsl = new int[SIZE]; 57 58 /** The internal state */ 59 private final int[] mem = new int[SIZE]; 60 61 /** Count through the results in rsl[] */ 62 private int count; 63 64 /** Accumulator */ 65 private int isaacA; 66 67 /** The last result */ 68 private int isaacB; 69 70 /** Counter, guarantees cycle is at least 2^40 */ 71 private int isaacC; 72 73 /** Service variable. */ 74 private final int[] arr = new int[8]; 75 76 /** Service variable. */ 77 private int isaacX; 78 79 /** Service variable. */ 80 private int isaacI; 81 82 /** Service variable. */ 83 private int isaacJ; 84 85 /** 86 * Creates a new ISAAC random number generator. <br> 87 * The instance is initialized using a combination of the current time and system hash code of 88 * the instance as the seed. 89 */ ISAACRandom()90 public ISAACRandom() { 91 setSeed(System.currentTimeMillis() + System.identityHashCode(this)); 92 } 93 94 /** 95 * Creates a new ISAAC random number generator using a single long seed. 96 * 97 * @param seed Initial seed. 98 */ ISAACRandom(long seed)99 public ISAACRandom(long seed) { 100 setSeed(seed); 101 } 102 103 /** 104 * Creates a new ISAAC random number generator using an int array seed. 105 * 106 * @param seed Initial seed. If {@code null}, the seed will be related to the current time. 107 */ ISAACRandom(int[] seed)108 public ISAACRandom(int[] seed) { 109 setSeed(seed); 110 } 111 112 /** {@inheritDoc} */ 113 @Override setSeed(int seed)114 public void setSeed(int seed) { 115 setSeed(new int[] {seed}); 116 } 117 118 /** {@inheritDoc} */ 119 @Override setSeed(long seed)120 public void setSeed(long seed) { 121 setSeed(new int[] {(int) (seed >>> 32), (int) (seed & 0xffffffffL)}); 122 } 123 124 /** {@inheritDoc} */ 125 @Override setSeed(int[] seed)126 public void setSeed(int[] seed) { 127 if (seed == null) { 128 setSeed(System.currentTimeMillis() + System.identityHashCode(this)); 129 return; 130 } 131 final int seedLen = seed.length; 132 final int rslLen = rsl.length; 133 System.arraycopy(seed, 0, rsl, 0, FastMath.min(seedLen, rslLen)); 134 if (seedLen < rslLen) { 135 for (int j = seedLen; j < rslLen; j++) { 136 long k = rsl[j - seedLen]; 137 rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL); 138 } 139 } 140 initState(); 141 } 142 143 /** {@inheritDoc} */ 144 @Override next(int bits)145 protected int next(int bits) { 146 if (count < 0) { 147 isaac(); 148 count = SIZE - 1; 149 } 150 return rsl[count--] >>> 32 - bits; 151 } 152 153 /** Generate 256 results */ isaac()154 private void isaac() { 155 isaacI = 0; 156 isaacJ = H_SIZE; 157 isaacB += ++isaacC; 158 while (isaacI < H_SIZE) { 159 isaac2(); 160 } 161 isaacJ = 0; 162 while (isaacJ < H_SIZE) { 163 isaac2(); 164 } 165 } 166 167 /** Intermediate internal loop. */ isaac2()168 private void isaac2() { 169 isaacX = mem[isaacI]; 170 isaacA ^= isaacA << 13; 171 isaacA += mem[isaacJ++]; 172 isaac3(); 173 isaacX = mem[isaacI]; 174 isaacA ^= isaacA >>> 6; 175 isaacA += mem[isaacJ++]; 176 isaac3(); 177 isaacX = mem[isaacI]; 178 isaacA ^= isaacA << 2; 179 isaacA += mem[isaacJ++]; 180 isaac3(); 181 isaacX = mem[isaacI]; 182 isaacA ^= isaacA >>> 16; 183 isaacA += mem[isaacJ++]; 184 isaac3(); 185 } 186 187 /** Lowest level internal loop. */ isaac3()188 private void isaac3() { 189 mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB; 190 isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX; 191 rsl[isaacI++] = isaacB; 192 } 193 194 /** Initialize, or reinitialize, this instance of rand. */ initState()195 private void initState() { 196 isaacA = 0; 197 isaacB = 0; 198 isaacC = 0; 199 for (int j = 0; j < arr.length; j++) { 200 arr[j] = GLD_RATIO; 201 } 202 for (int j = 0; j < 4; j++) { 203 shuffle(); 204 } 205 // fill in mem[] with messy stuff 206 for (int j = 0; j < SIZE; j += 8) { 207 arr[0] += rsl[j]; 208 arr[1] += rsl[j + 1]; 209 arr[2] += rsl[j + 2]; 210 arr[3] += rsl[j + 3]; 211 arr[4] += rsl[j + 4]; 212 arr[5] += rsl[j + 5]; 213 arr[6] += rsl[j + 6]; 214 arr[7] += rsl[j + 7]; 215 shuffle(); 216 setState(j); 217 } 218 // second pass makes all of seed affect all of mem 219 for (int j = 0; j < SIZE; j += 8) { 220 arr[0] += mem[j]; 221 arr[1] += mem[j + 1]; 222 arr[2] += mem[j + 2]; 223 arr[3] += mem[j + 3]; 224 arr[4] += mem[j + 4]; 225 arr[5] += mem[j + 5]; 226 arr[6] += mem[j + 6]; 227 arr[7] += mem[j + 7]; 228 shuffle(); 229 setState(j); 230 } 231 isaac(); 232 count = SIZE - 1; 233 clear(); 234 } 235 236 /** Shuffle array. */ shuffle()237 private void shuffle() { 238 arr[0] ^= arr[1] << 11; 239 arr[3] += arr[0]; 240 arr[1] += arr[2]; 241 arr[1] ^= arr[2] >>> 2; 242 arr[4] += arr[1]; 243 arr[2] += arr[3]; 244 arr[2] ^= arr[3] << 8; 245 arr[5] += arr[2]; 246 arr[3] += arr[4]; 247 arr[3] ^= arr[4] >>> 16; 248 arr[6] += arr[3]; 249 arr[4] += arr[5]; 250 arr[4] ^= arr[5] << 10; 251 arr[7] += arr[4]; 252 arr[5] += arr[6]; 253 arr[5] ^= arr[6] >>> 4; 254 arr[0] += arr[5]; 255 arr[6] += arr[7]; 256 arr[6] ^= arr[7] << 8; 257 arr[1] += arr[6]; 258 arr[7] += arr[0]; 259 arr[7] ^= arr[0] >>> 9; 260 arr[2] += arr[7]; 261 arr[0] += arr[1]; 262 } 263 264 /** 265 * Set the state by copying the internal arrays. 266 * 267 * @param start First index into {@link #mem} array. 268 */ setState(int start)269 private void setState(int start) { 270 mem[start] = arr[0]; 271 mem[start + 1] = arr[1]; 272 mem[start + 2] = arr[2]; 273 mem[start + 3] = arr[3]; 274 mem[start + 4] = arr[4]; 275 mem[start + 5] = arr[5]; 276 mem[start + 6] = arr[6]; 277 mem[start + 7] = arr[7]; 278 } 279 } 280