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 composeStateInternal(NumberFactory.makeByteArray(s), 098 super.getStateInternal()); 099 } 100 101 /** {@inheritDoc} */ 102 @Override 103 protected void setStateInternal(byte[] s) { 104 final byte[][] c = splitStateInternal(s, (2 * SIZE + 4) * 4); 105 106 final int[] tmp = NumberFactory.makeIntArray(c[0]); 107 System.arraycopy(tmp, 0, rsl, 0, SIZE); 108 System.arraycopy(tmp, SIZE, mem, 0, SIZE); 109 final int offset = 2 * SIZE; 110 count = tmp[offset]; 111 isaacA = tmp[offset + 1]; 112 isaacB = tmp[offset + 2]; 113 isaacC = tmp[offset + 3]; 114 115 super.setStateInternal(c[1]); 116 } 117 118 /** 119 * Reseeds the RNG. 120 * 121 * @param seed Seed. Cannot be null. 122 */ 123 private void setSeedInternal(int[] seed) { 124 final int seedLen = seed.length; 125 final int rslLen = rsl.length; 126 System.arraycopy(seed, 0, rsl, 0, Math.min(seedLen, rslLen)); 127 if (seedLen < rslLen) { 128 for (int j = seedLen; j < rslLen; j++) { 129 final long k = rsl[j - seedLen]; 130 rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL); 131 } 132 } 133 initState(); 134 } 135 136 /** {@inheritDoc} */ 137 @Override 138 public int next() { 139 if (count < 0) { 140 isaac(); 141 count = SIZE - 1; 142 } 143 return rsl[count--]; 144 } 145 146 /** Generate 256 results. */ 147 private void isaac() { 148 isaacI = 0; 149 isaacJ = H_SIZE; 150 isaacB += ++isaacC; 151 while (isaacI < H_SIZE) { 152 isaac2(); 153 } 154 isaacJ = 0; 155 while (isaacJ < H_SIZE) { 156 isaac2(); 157 } 158 } 159 160 /** Intermediate internal loop. */ 161 private void isaac2() { 162 isaacX = mem[isaacI]; 163 isaacA ^= isaacA << 13; 164 isaacA += mem[isaacJ++]; 165 isaac3(); 166 isaacX = mem[isaacI]; 167 isaacA ^= isaacA >>> 6; 168 isaacA += mem[isaacJ++]; 169 isaac3(); 170 isaacX = mem[isaacI]; 171 isaacA ^= isaacA << 2; 172 isaacA += mem[isaacJ++]; 173 isaac3(); 174 isaacX = mem[isaacI]; 175 isaacA ^= isaacA >>> 16; 176 isaacA += mem[isaacJ++]; 177 isaac3(); 178 } 179 180 /** Lowest level internal loop. */ 181 private void isaac3() { 182 mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB; 183 isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX; 184 rsl[isaacI++] = isaacB; 185 } 186 187 /** Initialize, or reinitialize, this instance of rand. */ 188 private void initState() { 189 isaacA = 0; 190 isaacB = 0; 191 isaacC = 0; 192 Arrays.fill(arr, GLD_RATIO); 193 for (int j = 0; j < 4; j++) { 194 shuffle(); 195 } 196 // fill in mem[] with messy stuff 197 for (int j = 0; j < SIZE; j += 8) { 198 arr[0] += rsl[j]; 199 arr[1] += rsl[j + 1]; 200 arr[2] += rsl[j + 2]; 201 arr[3] += rsl[j + 3]; 202 arr[4] += rsl[j + 4]; 203 arr[5] += rsl[j + 5]; 204 arr[6] += rsl[j + 6]; 205 arr[7] += rsl[j + 7]; 206 shuffle(); 207 setState(j); 208 } 209 // second pass makes all of seed affect all of mem 210 for (int j = 0; j < SIZE; j += 8) { 211 arr[0] += mem[j]; 212 arr[1] += mem[j + 1]; 213 arr[2] += mem[j + 2]; 214 arr[3] += mem[j + 3]; 215 arr[4] += mem[j + 4]; 216 arr[5] += mem[j + 5]; 217 arr[6] += mem[j + 6]; 218 arr[7] += mem[j + 7]; 219 shuffle(); 220 setState(j); 221 } 222 isaac(); 223 count = SIZE - 1; 224 } 225 226 /** Shuffle array. */ 227 private void shuffle() { 228 arr[0] ^= arr[1] << 11; 229 arr[3] += arr[0]; 230 arr[1] += arr[2]; 231 arr[1] ^= arr[2] >>> 2; 232 arr[4] += arr[1]; 233 arr[2] += arr[3]; 234 arr[2] ^= arr[3] << 8; 235 arr[5] += arr[2]; 236 arr[3] += arr[4]; 237 arr[3] ^= arr[4] >>> 16; 238 arr[6] += arr[3]; 239 arr[4] += arr[5]; 240 arr[4] ^= arr[5] << 10; 241 arr[7] += arr[4]; 242 arr[5] += arr[6]; 243 arr[5] ^= arr[6] >>> 4; 244 arr[0] += arr[5]; 245 arr[6] += arr[7]; 246 arr[6] ^= arr[7] << 8; 247 arr[1] += arr[6]; 248 arr[7] += arr[0]; 249 arr[7] ^= arr[0] >>> 9; 250 arr[2] += arr[7]; 251 arr[0] += arr[1]; 252 } 253 254 /** Set the state by copying the internal arrays. 255 * 256 * @param start First index into {@link #mem} array. 257 */ 258 private void setState(int start) { 259 mem[start] = arr[0]; 260 mem[start + 1] = arr[1]; 261 mem[start + 2] = arr[2]; 262 mem[start + 3] = arr[3]; 263 mem[start + 4] = arr[4]; 264 mem[start + 5] = arr[5]; 265 mem[start + 6] = arr[6]; 266 mem[start + 7] = arr[7]; 267 } 268}