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.rng.core.source32;
019
020import java.util.Arrays;
021import org.apache.commons.rng.core.util.NumberFactory;
022
023/**
024 * A fast cryptographic pseudo-random number generator.
025 * <p>
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 * <p>
035 * This code is based (with minor changes and improvements) on the original
036 * implementation of the algorithm by Bob Jenkins.
037 *
038 * @see <a href="http://burtleburtle.net/bob/rand/isaacafa.html">
039 * ISAAC: a fast cryptographic pseudo-random number generator</a>
040 *
041 * @see <a href="https://en.wikipedia.org/wiki/ISAAC_(cipher)">ISAAC (Wikipedia)</a>
042 * @since 1.0
043 */
044public class ISAACRandom extends IntProvider {
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     * Creates a new ISAAC random number generator.
078     *
079     * @param seed Initial seed
080     */
081    public ISAACRandom(int[] seed) {
082        setSeedInternal(seed);
083    }
084
085    /** {@inheritDoc} */
086    @Override
087    protected byte[] getStateInternal() {
088        final int[] sRsl = Arrays.copyOf(rsl, SIZE);
089        final int[] sMem = Arrays.copyOf(mem, SIZE);
090        final int[] sRem = Arrays.copyOf(new int[] { count, isaacA, isaacB, isaacC }, 4);
091
092        final int[] s = new int[2 * SIZE + sRem.length];
093        System.arraycopy(sRsl, 0, s, 0, SIZE);
094        System.arraycopy(sMem, 0, s, SIZE, SIZE);
095        System.arraycopy(sRem, 0, s, 2 * SIZE, sRem.length);
096
097        return NumberFactory.makeByteArray(s);
098    }
099
100    /** {@inheritDoc} */
101    @Override
102    protected void setStateInternal(byte[] s) {
103        checkStateSize(s, (2 * SIZE + 4) * 4);
104
105        final int[] tmp = NumberFactory.makeIntArray(s);
106        System.arraycopy(tmp, 0, rsl, 0, SIZE);
107        System.arraycopy(tmp, SIZE, mem, 0, SIZE);
108        final int offset = 2 * SIZE;
109        count = tmp[offset];
110        isaacA = tmp[offset + 1];
111        isaacB = tmp[offset + 2];
112        isaacC = tmp[offset + 3];
113    }
114
115    /**
116     * Reseeds the RNG.
117     *
118     * @param seed Seed. Cannot be null.
119     */
120    private void setSeedInternal(int[] seed) {
121        final int seedLen = seed.length;
122        final int rslLen = rsl.length;
123        System.arraycopy(seed, 0, rsl, 0, Math.min(seedLen, rslLen));
124        if (seedLen < rslLen) {
125            for (int j = seedLen; j < rslLen; j++) {
126                long k = rsl[j - seedLen];
127                rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL);
128            }
129        }
130        initState();
131    }
132
133    /** {@inheritDoc} */
134    @Override
135    public int next() {
136        if (count < 0) {
137            isaac();
138            count = SIZE - 1;
139        }
140        return rsl[count--];
141    }
142
143    /** Generate 256 results */
144    private void isaac() {
145        isaacI = 0;
146        isaacJ = H_SIZE;
147        isaacB += ++isaacC;
148        while (isaacI < H_SIZE) {
149            isaac2();
150        }
151        isaacJ = 0;
152        while (isaacJ < H_SIZE) {
153            isaac2();
154        }
155    }
156
157    /** Intermediate internal loop. */
158    private void isaac2() {
159        isaacX = mem[isaacI];
160        isaacA ^= isaacA << 13;
161        isaacA += mem[isaacJ++];
162        isaac3();
163        isaacX = mem[isaacI];
164        isaacA ^= isaacA >>> 6;
165        isaacA += mem[isaacJ++];
166        isaac3();
167        isaacX = mem[isaacI];
168        isaacA ^= isaacA << 2;
169        isaacA += mem[isaacJ++];
170        isaac3();
171        isaacX = mem[isaacI];
172        isaacA ^= isaacA >>> 16;
173        isaacA += mem[isaacJ++];
174        isaac3();
175    }
176
177    /** Lowest level internal loop. */
178    private void isaac3() {
179        mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB;
180        isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX;
181        rsl[isaacI++] = isaacB;
182    }
183
184    /** Initialize, or reinitialize, this instance of rand. */
185    private void initState() {
186        isaacA = 0;
187        isaacB = 0;
188        isaacC = 0;
189        for (int j = 0; j < arr.length; j++) {
190            arr[j] = GLD_RATIO;
191        }
192        for (int j = 0; j < 4; j++) {
193            shuffle();
194        }
195        // fill in mem[] with messy stuff
196        for (int j = 0; j < SIZE; j += 8) {
197            arr[0] += rsl[j];
198            arr[1] += rsl[j + 1];
199            arr[2] += rsl[j + 2];
200            arr[3] += rsl[j + 3];
201            arr[4] += rsl[j + 4];
202            arr[5] += rsl[j + 5];
203            arr[6] += rsl[j + 6];
204            arr[7] += rsl[j + 7];
205            shuffle();
206            setState(j);
207        }
208        // second pass makes all of seed affect all of mem
209        for (int j = 0; j < SIZE; j += 8) {
210            arr[0] += mem[j];
211            arr[1] += mem[j + 1];
212            arr[2] += mem[j + 2];
213            arr[3] += mem[j + 3];
214            arr[4] += mem[j + 4];
215            arr[5] += mem[j + 5];
216            arr[6] += mem[j + 6];
217            arr[7] += mem[j + 7];
218            shuffle();
219            setState(j);
220        }
221        isaac();
222        count = SIZE - 1;
223    }
224
225    /** Shuffle array. */
226    private void shuffle() {
227        arr[0] ^= arr[1] << 11;
228        arr[3] += arr[0];
229        arr[1] += arr[2];
230        arr[1] ^= arr[2] >>> 2;
231        arr[4] += arr[1];
232        arr[2] += arr[3];
233        arr[2] ^= arr[3] << 8;
234        arr[5] += arr[2];
235        arr[3] += arr[4];
236        arr[3] ^= arr[4] >>> 16;
237        arr[6] += arr[3];
238        arr[4] += arr[5];
239        arr[4] ^= arr[5] << 10;
240        arr[7] += arr[4];
241        arr[5] += arr[6];
242        arr[5] ^= arr[6] >>> 4;
243        arr[0] += arr[5];
244        arr[6] += arr[7];
245        arr[6] ^= arr[7] << 8;
246        arr[1] += arr[6];
247        arr[7] += arr[0];
248        arr[7] ^= arr[0] >>> 9;
249        arr[2] += arr[7];
250        arr[0] += arr[1];
251    }
252
253    /** Set the state by copying the internal arrays.
254     *
255     * @param start First index into {@link #mem} array.
256     */
257    private void setState(int start) {
258        mem[start] = arr[0];
259        mem[start + 1] = arr[1];
260        mem[start + 2] = arr[2];
261        mem[start + 3] = arr[3];
262        mem[start + 4] = arr[4];
263        mem[start + 5] = arr[5];
264        mem[start + 6] = arr[6];
265        mem[start + 7] = arr[7];
266    }
267}