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}