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