/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.apache.commons.rng.core.source32;
  
  import java.util.Arrays;
  import org.apache.commons.rng.core.util.NumberFactory;
  
  /**
   * A fast cryptographic pseudo-random number generator.
   * <p>
   * ISAAC (Indirection, Shift, Accumulate, Add, and Count) generates 32-bit
   * random numbers.
   * ISAAC has been designed to be cryptographically secure and is inspired
   * by RC4.
   * Cycles are guaranteed to be at least 2<sup>40</sup> values long, and they
   * are 2<sup>8295</sup> values long on average.
   * The results are uniformly distributed, unbiased, and unpredictable unless
   * you know the seed.
   * <p>
   * This code is based (with minor changes and improvements) on the original
   * implementation of the algorithm by Bob Jenkins.
   *
   * @see <a href="http://burtleburtle.net/bob/rand/isaacafa.html">
   * ISAAC: a fast cryptographic pseudo-random number generator</a>
   *
   * @see <a href="https://en.wikipedia.org/wiki/ISAAC_(cipher)">ISAAC (Wikipedia)</a>
   * @since 1.0
   */
  public class ISAACRandom extends IntProvider {
      /** Log of size of rsl[] and mem[]. */
      private static final int SIZE_L = 8;
      /** Size of rsl[] and mem[]. */
      private static final int SIZE = 1 << SIZE_L;
      /** Half-size of rsl[] and mem[]. */
      private static final int H_SIZE = SIZE >> 1;
      /** For pseudo-random lookup. */
      private static final int MASK = SIZE - 1 << 2;
      /** The golden ratio. */
      private static final int GLD_RATIO = 0x9e3779b9;
      /** The results given to the user. */
      private final int[] rsl = new int[SIZE];
      /** The internal state. */
      private final int[] mem = new int[SIZE];
      /** Count through the results in rsl[]. */
      private int count;
      /** Accumulator. */
      private int isaacA;
      /** The last result. */
      private int isaacB;
      /** Counter, guarantees cycle is at least 2^40. */
      private int isaacC;
      /** Service variable. */
      private final int[] arr = new int[8];
      /** Service variable. */
      private int isaacX;
      /** Service variable. */
      private int isaacI;
      /** Service variable. */
      private int isaacJ;
  
      /**
       * Creates a new ISAAC random number generator.
       *
       * @param seed Initial seed
       */
      public ISAACRandom(int[] seed) {
          setSeedInternal(seed);
      }
  
      /** {@inheritDoc} */
      @Override
      protected byte[] getStateInternal() {
          final int[] sRsl = Arrays.copyOf(rsl, SIZE);
          final int[] sMem = Arrays.copyOf(mem, SIZE);
          final int[] sRem = Arrays.copyOf(new int[] {count, isaacA, isaacB, isaacC}, 4);
  
          final int[] s = new int[2 * SIZE + sRem.length];
          System.arraycopy(sRsl, 0, s, 0, SIZE);
          System.arraycopy(sMem, 0, s, SIZE, SIZE);
          System.arraycopy(sRem, 0, s, 2 * SIZE, sRem.length);
  
          return composeStateInternal(NumberFactory.makeByteArray(s),
                                      super.getStateInternal());
      }
 
     /** {@inheritDoc} */
     @Override
     protected void setStateInternal(byte[] s) {
         final byte[][] c = splitStateInternal(s, (2 * SIZE + 4) * 4);
 
         final int[] tmp = NumberFactory.makeIntArray(c[0]);
         System.arraycopy(tmp, 0, rsl, 0, SIZE);
         System.arraycopy(tmp, SIZE, mem, 0, SIZE);
         final int offset = 2 * SIZE;
         count = tmp[offset];
         isaacA = tmp[offset + 1];
         isaacB = tmp[offset + 2];
         isaacC = tmp[offset + 3];
 
         super.setStateInternal(c[1]);
     }
 
     /**
      * Reseeds the RNG.
      *
      * @param seed Seed. Cannot be null.
      */
     private void setSeedInternal(int[] seed) {
         final int seedLen = seed.length;
         final int rslLen = rsl.length;
         System.arraycopy(seed, 0, rsl, 0, Math.min(seedLen, rslLen));
         if (seedLen < rslLen) {
             for (int j = seedLen; j < rslLen; j++) {
                 final long k = rsl[j - seedLen];
                 rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL);
             }
         }
         initState();
     }
 
     /** {@inheritDoc} */
     @Override
     public int next() {
         if (count < 0) {
             isaac();
             count = SIZE - 1;
         }
         return rsl[count--];
     }
 
     /** Generate 256 results. */
     private void isaac() {
         isaacI = 0;
         isaacJ = H_SIZE;
         isaacB += ++isaacC;
         while (isaacI < H_SIZE) {
             isaac2();
         }
         isaacJ = 0;
         while (isaacJ < H_SIZE) {
             isaac2();
         }
     }
 
     /** Intermediate internal loop. */
     private void isaac2() {
         isaacX = mem[isaacI];
         isaacA ^= isaacA << 13;
         isaacA += mem[isaacJ++];
         isaac3();
         isaacX = mem[isaacI];
         isaacA ^= isaacA >>> 6;
         isaacA += mem[isaacJ++];
         isaac3();
         isaacX = mem[isaacI];
         isaacA ^= isaacA << 2;
         isaacA += mem[isaacJ++];
         isaac3();
         isaacX = mem[isaacI];
         isaacA ^= isaacA >>> 16;
         isaacA += mem[isaacJ++];
         isaac3();
     }
 
     /** Lowest level internal loop. */
     private void isaac3() {
         mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB;
         isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX;
         rsl[isaacI++] = isaacB;
     }
 
     /** Initialize, or reinitialize, this instance of rand. */
     private void initState() {
         isaacA = 0;
         isaacB = 0;
         isaacC = 0;
         Arrays.fill(arr, GLD_RATIO);
         for (int j = 0; j < 4; j++) {
             shuffle();
         }
         // fill in mem[] with messy stuff
         for (int j = 0; j < SIZE; j += 8) {
             arr[0] += rsl[j];
             arr[1] += rsl[j + 1];
             arr[2] += rsl[j + 2];
             arr[3] += rsl[j + 3];
             arr[4] += rsl[j + 4];
             arr[5] += rsl[j + 5];
             arr[6] += rsl[j + 6];
             arr[7] += rsl[j + 7];
             shuffle();
             setState(j);
         }
         // second pass makes all of seed affect all of mem
         for (int j = 0; j < SIZE; j += 8) {
             arr[0] += mem[j];
             arr[1] += mem[j + 1];
             arr[2] += mem[j + 2];
             arr[3] += mem[j + 3];
             arr[4] += mem[j + 4];
             arr[5] += mem[j + 5];
             arr[6] += mem[j + 6];
             arr[7] += mem[j + 7];
             shuffle();
             setState(j);
         }
         isaac();
         count = SIZE - 1;
     }
 
     /** Shuffle array. */
     private void shuffle() {
         arr[0] ^= arr[1] << 11;
         arr[3] += arr[0];
         arr[1] += arr[2];
         arr[1] ^= arr[2] >>> 2;
         arr[4] += arr[1];
         arr[2] += arr[3];
         arr[2] ^= arr[3] << 8;
         arr[5] += arr[2];
         arr[3] += arr[4];
         arr[3] ^= arr[4] >>> 16;
         arr[6] += arr[3];
         arr[4] += arr[5];
         arr[4] ^= arr[5] << 10;
         arr[7] += arr[4];
         arr[5] += arr[6];
         arr[5] ^= arr[6] >>> 4;
         arr[0] += arr[5];
         arr[6] += arr[7];
         arr[6] ^= arr[7] << 8;
         arr[1] += arr[6];
         arr[7] += arr[0];
         arr[7] ^= arr[0] >>> 9;
         arr[2] += arr[7];
         arr[0] += arr[1];
     }
 
     /** Set the state by copying the internal arrays.
      *
      * @param start First index into {@link #mem} array.
      */
     private void setState(int start) {
         mem[start] = arr[0];
         mem[start + 1] = arr[1];
         mem[start + 2] = arr[2];
         mem[start + 3] = arr[3];
         mem[start + 4] = arr[4];
         mem[start + 5] = arr[5];
         mem[start + 6] = arr[6];
         mem[start + 7] = arr[7];
     }
 }