    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    }