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    }