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