001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math3.random;
019
020 import java.io.Serializable;
021
022 /**
023 * <a href="http://burtleburtle.net/bob/rand/isaacafa.html">
024 * ISAAC: a fast cryptographic pseudo-random number generator</a>
025 * <br/>
026 * ISAAC (Indirection, Shift, Accumulate, Add, and Count) generates 32-bit
027 * random numbers.
028 * ISAAC has been designed to be cryptographically secure and is inspired
029 * by RC4.
030 * Cycles are guaranteed to be at least 2<sup>40</sup> values long, and they
031 * are 2<sup>8295</sup> values long on average.
032 * The results are uniformly distributed, unbiased, and unpredictable unless
033 * you know the seed.
034 * <br/>
035 * This code is based (with minor changes and improvements) on the original
036 * implementation of the algorithm by Bob Jenkins.
037 * <br/>
038 *
039 * @version $Id: ISAACRandom.java 1416643 2012-12-03 19:37:14Z tn $
040 * @since 3.0
041 */
042 public class ISAACRandom extends BitsStreamGenerator implements Serializable {
043 /** Serializable version identifier */
044 private static final long serialVersionUID = 7288197941165002400L;
045 /** Log of size of rsl[] and mem[] */
046 private static final int SIZE_L = 8;
047 /** Size of rsl[] and mem[] */
048 private static final int SIZE = 1 << SIZE_L;
049 /** Half-size of rsl[] and mem[] */
050 private static final int H_SIZE = SIZE >> 1;
051 /** For pseudo-random lookup */
052 private static final int MASK = SIZE - 1 << 2;
053 /** The golden ratio */
054 private static final int GLD_RATIO = 0x9e3779b9;
055 /** The results given to the user */
056 private final int[] rsl = new int[SIZE];
057 /** The internal state */
058 private final int[] mem = new int[SIZE];
059 /** Count through the results in rsl[] */
060 private int count;
061 /** Accumulator */
062 private int isaacA;
063 /** The last result */
064 private int isaacB;
065 /** Counter, guarantees cycle is at least 2^40 */
066 private int isaacC;
067 /** Service variable. */
068 private final int[] arr = new int[8];
069 /** Service variable. */
070 private int isaacX;
071 /** Service variable. */
072 private int isaacI;
073 /** Service variable. */
074 private int isaacJ;
075
076
077 /**
078 * Creates a new ISAAC random number generator.
079 * <br/>
080 * The instance is initialized using a combination of the
081 * current time and system hash code of the instance as the seed.
082 */
083 public ISAACRandom() {
084 setSeed(System.currentTimeMillis() + System.identityHashCode(this));
085 }
086
087 /**
088 * Creates a new ISAAC random number generator using a single long seed.
089 *
090 * @param seed Initial seed.
091 */
092 public ISAACRandom(long seed) {
093 setSeed(seed);
094 }
095
096 /**
097 * Creates a new ISAAC random number generator using an int array seed.
098 *
099 * @param seed Initial seed. If {@code null}, the seed will be related
100 * to the current time.
101 */
102 public ISAACRandom(int[] seed) {
103 setSeed(seed);
104 }
105
106 /** {@inheritDoc} */
107 @Override
108 public void setSeed(int seed) {
109 setSeed(new int[]{seed});
110 }
111
112 /** {@inheritDoc} */
113 @Override
114 public void setSeed(long seed) {
115 setSeed(new int[]{(int) (seed >>> 32), (int) (seed & 0xffffffffL)});
116 }
117
118 /** {@inheritDoc} */
119 @Override
120 public void setSeed(int[] seed) {
121 if (seed == null) {
122 setSeed(System.currentTimeMillis() + System.identityHashCode(this));
123 return;
124 }
125 final int seedLen = seed.length;
126 final int rslLen = rsl.length;
127 System.arraycopy(seed, 0, rsl, 0, Math.min(seedLen, rslLen));
128 if (seedLen < rslLen) {
129 for (int j = seedLen; j < rslLen; j++) {
130 long k = rsl[j - seedLen];
131 rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL);
132 }
133 }
134 initState();
135 }
136
137 /** {@inheritDoc} */
138 @Override
139 protected int next(int bits) {
140 if (count < 0) {
141 isaac();
142 count = SIZE - 1;
143 }
144 return rsl[count--] >>> 32 - bits;
145 }
146
147 /** Generate 256 results */
148 private void isaac() {
149 isaacI = 0;
150 isaacJ = H_SIZE;
151 isaacB += ++isaacC;
152 while (isaacI < H_SIZE) {
153 isaac2();
154 }
155 isaacJ = 0;
156 while (isaacJ < H_SIZE) {
157 isaac2();
158 }
159 }
160
161 /** Intermediate internal loop. */
162 private void isaac2() {
163 isaacX = mem[isaacI];
164 isaacA ^= isaacA << 13;
165 isaacA += mem[isaacJ++];
166 isaac3();
167 isaacX = mem[isaacI];
168 isaacA ^= isaacA >>> 6;
169 isaacA += mem[isaacJ++];
170 isaac3();
171 isaacX = mem[isaacI];
172 isaacA ^= isaacA << 2;
173 isaacA += mem[isaacJ++];
174 isaac3();
175 isaacX = mem[isaacI];
176 isaacA ^= isaacA >>> 16;
177 isaacA += mem[isaacJ++];
178 isaac3();
179 }
180
181 /** Lowest level internal loop. */
182 private void isaac3() {
183 mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB;
184 isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX;
185 rsl[isaacI++] = isaacB;
186 }
187
188 /** Initialize, or reinitialize, this instance of rand. */
189 private void initState() {
190 isaacA = 0;
191 isaacB = 0;
192 isaacC = 0;
193 for (int j = 0; j < arr.length; j++) {
194 arr[j] = GLD_RATIO;
195 }
196 for (int j = 0; j < 4; j++) {
197 shuffle();
198 }
199 // fill in mem[] with messy stuff
200 for (int j = 0; j < SIZE; j += 8) {
201 arr[0] += rsl[j];
202 arr[1] += rsl[j + 1];
203 arr[2] += rsl[j + 2];
204 arr[3] += rsl[j + 3];
205 arr[4] += rsl[j + 4];
206 arr[5] += rsl[j + 5];
207 arr[6] += rsl[j + 6];
208 arr[7] += rsl[j + 7];
209 shuffle();
210 setState(j);
211 }
212 // second pass makes all of seed affect all of mem
213 for (int j = 0; j < SIZE; j += 8) {
214 arr[0] += mem[j];
215 arr[1] += mem[j + 1];
216 arr[2] += mem[j + 2];
217 arr[3] += mem[j + 3];
218 arr[4] += mem[j + 4];
219 arr[5] += mem[j + 5];
220 arr[6] += mem[j + 6];
221 arr[7] += mem[j + 7];
222 shuffle();
223 setState(j);
224 }
225 isaac();
226 count = SIZE - 1;
227 clear();
228 }
229
230 /** Shuffle array. */
231 private void shuffle() {
232 arr[0] ^= arr[1] << 11;
233 arr[3] += arr[0];
234 arr[1] += arr[2];
235 arr[1] ^= arr[2] >>> 2;
236 arr[4] += arr[1];
237 arr[2] += arr[3];
238 arr[2] ^= arr[3] << 8;
239 arr[5] += arr[2];
240 arr[3] += arr[4];
241 arr[3] ^= arr[4] >>> 16;
242 arr[6] += arr[3];
243 arr[4] += arr[5];
244 arr[4] ^= arr[5] << 10;
245 arr[7] += arr[4];
246 arr[5] += arr[6];
247 arr[5] ^= arr[6] >>> 4;
248 arr[0] += arr[5];
249 arr[6] += arr[7];
250 arr[6] ^= arr[7] << 8;
251 arr[1] += arr[6];
252 arr[7] += arr[0];
253 arr[7] ^= arr[0] >>> 9;
254 arr[2] += arr[7];
255 arr[0] += arr[1];
256 }
257
258 /** Set the state by copying the internal arrays.
259 *
260 * @param start First index into {@link #mem} array.
261 */
262 private void setState(int start) {
263 mem[start] = arr[0];
264 mem[start + 1] = arr[1];
265 mem[start + 2] = arr[2];
266 mem[start + 3] = arr[3];
267 mem[start + 4] = arr[4];
268 mem[start + 5] = arr[5];
269 mem[start + 6] = arr[6];
270 mem[start + 7] = arr[7];
271 }
272 }