1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.rng.simple.internal; 18 19 import java.security.SecureRandom; 20 import java.util.concurrent.locks.ReentrantLock; 21 22 import org.apache.commons.rng.core.util.NumberFactory; 23 import org.apache.commons.rng.UniformRandomProvider; 24 import org.apache.commons.rng.core.source64.RandomLongSource; 25 import org.apache.commons.rng.core.source64.SplitMix64; 26 import org.apache.commons.rng.core.source64.XoRoShiRo1024PlusPlus; 27 28 /** 29 * Utilities related to seeding. 30 * 31 * <p> 32 * This class provides methods to generate random seeds (single values 33 * or arrays of values, of {@code int} or {@code long} types) that can 34 * be passed to the {@link org.apache.commons.rng.simple.RandomSource 35 * methods that create a generator instance}. 36 * <br> 37 * Although the seed-generating methods defined in this class will likely 38 * return different values for all calls, there is no guarantee that the 39 * produced seed will result always in a "good" sequence of numbers (even 40 * if the generator initialized with that seed is good). 41 * <br> 42 * There is <i>no guarantee</i> that sequences will not overlap. 43 * </p> 44 * 45 * @since 1.0 46 */ 47 public final class SeedFactory { 48 /** Size of the state array of "XoRoShiRo1024PlusPlus". */ 49 private static final int XO_RO_SHI_RO_1024_STATE_SIZE = 16; 50 /** Size of block to fill in an {@code int[]} seed per synchronized operation. */ 51 private static final int INT_ARRAY_BLOCK_SIZE = 8; 52 /** Size of block to fill in a {@code long[]} seed per synchronized operation. */ 53 private static final int LONG_ARRAY_BLOCK_SIZE = 4; 54 55 /** 56 * The lock to own when using the seed generator. This lock is unfair and there is no 57 * particular access order for waiting threads. 58 * 59 * <p>This is used as an alternative to {@code synchronized} statements to guard access 60 * to the seed generator.</p> 61 */ 62 private static final ReentrantLock LOCK = new ReentrantLock(false); 63 64 /** Generator with a long period. */ 65 private static final UniformRandomProvider SEED_GENERATOR; 66 67 static { 68 // Use a secure RNG so that different instances (e.g. in multiple JVM 69 // instances started in rapid succession) will have different seeds. 70 final SecureRandom seedGen = new SecureRandom(); 71 final byte[] bytes = new byte[8 * XO_RO_SHI_RO_1024_STATE_SIZE]; 72 seedGen.nextBytes(bytes); 73 final long[] seed = NumberFactory.makeLongArray(bytes); 74 // The XoRoShiRo1024PlusPlus generator cannot recover from an all zero seed and 75 // will produce low quality initial output if initialised with some zeros. 76 // Ensure it is non zero at all array positions using a SplitMix64 77 // generator (this is insensitive to a zero seed so can use the first seed value). 78 final SplitMix64 rng = new SplitMix64(seed[0]); 79 for (int i = 0; i < seed.length; i++) { 80 seed[i] = ensureNonZero(rng, seed[i]); 81 } 82 83 SEED_GENERATOR = new XoRoShiRo1024PlusPlus(seed); 84 } 85 86 /** 87 * Class contains only static methods. 88 */ 89 private SeedFactory() {} 90 91 /** 92 * Creates an {@code int} number for use as a seed. 93 * 94 * @return a random number. 95 */ 96 public static int createInt() { 97 LOCK.lock(); 98 try { 99 return SEED_GENERATOR.nextInt(); 100 } finally { 101 LOCK.unlock(); 102 } 103 } 104 105 /** 106 * Creates a {@code long} number for use as a seed. 107 * 108 * @return a random number. 109 */ 110 public static long createLong() { 111 LOCK.lock(); 112 try { 113 return SEED_GENERATOR.nextLong(); 114 } finally { 115 LOCK.unlock(); 116 } 117 } 118 119 /** 120 * Creates an array of {@code int} numbers for use as a seed. 121 * 122 * @param n Size of the array to create. 123 * @return an array of {@code n} random numbers. 124 */ 125 public static int[] createIntArray(int n) { 126 final int[] seed = new int[n]; 127 // Compute the size that can be filled with complete blocks 128 final int blockSize = INT_ARRAY_BLOCK_SIZE * (n / INT_ARRAY_BLOCK_SIZE); 129 int i = 0; 130 while (i < blockSize) { 131 final int end = i + INT_ARRAY_BLOCK_SIZE; 132 fillIntArray(seed, i, end); 133 i = end; 134 } 135 // Final fill only if required 136 if (i != n) { 137 fillIntArray(seed, i, n); 138 } 139 ensureNonZero(seed); 140 return seed; 141 } 142 143 /** 144 * Creates an array of {@code long} numbers for use as a seed. 145 * 146 * @param n Size of the array to create. 147 * @return an array of {@code n} random numbers. 148 */ 149 public static long[] createLongArray(int n) { 150 final long[] seed = new long[n]; 151 // Compute the size that can be filled with complete blocks 152 final int blockSize = LONG_ARRAY_BLOCK_SIZE * (n / LONG_ARRAY_BLOCK_SIZE); 153 int i = 0; 154 while (i < blockSize) { 155 final int end = i + LONG_ARRAY_BLOCK_SIZE; 156 fillLongArray(seed, i, end); 157 i = end; 158 } 159 // Final fill only if required 160 if (i != n) { 161 fillLongArray(seed, i, n); 162 } 163 ensureNonZero(seed); 164 return seed; 165 } 166 167 /** 168 * Fill the array between {@code start} inclusive and {@code end} exclusive from the 169 * seed generator. The lock is used to guard access to the generator. 170 * 171 * @param array Array data. 172 * @param start Start (inclusive). 173 * @param end End (exclusive). 174 */ 175 private static void fillIntArray(int[] array, int start, int end) { 176 LOCK.lock(); 177 try { 178 for (int i = start; i < end; i++) { 179 array[i] = SEED_GENERATOR.nextInt(); 180 } 181 } finally { 182 LOCK.unlock(); 183 } 184 } 185 186 /** 187 * Fill the array between {@code start} inclusive and {@code end} exclusive from the 188 * seed generator. The lock is used to guard access to the generator. 189 * 190 * @param array Array data. 191 * @param start Start (inclusive). 192 * @param end End (exclusive). 193 */ 194 private static void fillLongArray(long[] array, int start, int end) { 195 LOCK.lock(); 196 try { 197 for (int i = start; i < end; i++) { 198 array[i] = SEED_GENERATOR.nextLong(); 199 } 200 } finally { 201 LOCK.unlock(); 202 } 203 } 204 205 /** 206 * Creates an array of {@code byte} numbers for use as a seed using the supplied source of 207 * randomness. The result will not be all zeros. 208 * 209 * @param source Source of randomness. 210 * @param n Size of the array to create. 211 * @return an array of {@code n} random numbers. 212 */ 213 static byte[] createByteArray(UniformRandomProvider source, 214 int n) { 215 final byte[] seed = new byte[n]; 216 source.nextBytes(seed); 217 // If the seed is zero it is assumed the input source RNG is either broken 218 // or the seed is small and it was zero by chance. Revert to the built-in 219 // source of randomness to ensure it is non-zero. 220 ensureNonZero(seed); 221 return seed; 222 } 223 224 /** 225 * Ensure the seed is non-zero at the first position in the array. 226 * 227 * <p>This method will replace a zero at index 0 in the array with 228 * a non-zero random number. The method ensures any length seed 229 * contains non-zero bits. The output seed is suitable for generators 230 * that cannot be seeded with all zeros.</p> 231 * 232 * @param seed Seed array (modified in place). 233 * @see #createInt() 234 */ 235 static void ensureNonZero(int[] seed) { 236 // Zero occurs 1 in 2^32 237 if (seed.length != 0 && seed[0] == 0) { 238 do { 239 seed[0] = createInt(); 240 } while (seed[0] == 0); 241 } 242 } 243 244 /** 245 * Ensure the seed is non-zero at the first position in the array. 246 * 247 * <p>This method will replace a zero at index 0 in the array with 248 * a non-zero random number. The method ensures any length seed 249 * contains non-zero bits. The output seed is suitable for generators 250 * that cannot be seeded with all zeros.</p> 251 * 252 * @param seed Seed array (modified in place). 253 * @see #createLong() 254 */ 255 static void ensureNonZero(long[] seed) { 256 // Zero occurs 1 in 2^64 257 if (seed.length != 0 && seed[0] == 0) { 258 do { 259 seed[0] = createLong(); 260 } while (seed[0] == 0); 261 } 262 } 263 264 /** 265 * Ensure the seed is not zero at all positions in the array. 266 * 267 * <p>This method will check all positions in the array and if all 268 * are zero it will replace index 0 in the array with 269 * a non-zero random number. The method ensures any length seed 270 * contains non-zero bits. The output seed is suitable for generators 271 * that cannot be seeded with all zeros.</p> 272 * 273 * @param seed Seed array (modified in place). 274 * @see #createInt() 275 */ 276 private static void ensureNonZero(byte[] seed) { 277 // Since zero occurs 1 in 2^8 for a single byte this checks the entire array for zeros. 278 if (seed.length != 0 && isAllZero(seed)) { 279 do { 280 seed[0] = (byte) createInt(); 281 } while (seed[0] == 0); 282 } 283 } 284 285 /** 286 * Test if each position in the array is zero. 287 * 288 * @param array Array data. 289 * @return true if all position are zero 290 */ 291 private static boolean isAllZero(byte[] array) { 292 for (final byte value : array) { 293 if (value != 0) { 294 return false; 295 } 296 } 297 return true; 298 } 299 300 /** 301 * Ensure the value is non-zero. 302 * 303 * <p>This method will replace a zero with a non-zero random number from the random source.</p> 304 * 305 * @param source Source of randomness. 306 * @param value Value. 307 * @return {@code value} if non-zero; else a new random number 308 */ 309 static long ensureNonZero(RandomLongSource source, 310 long value) { 311 long result = value; 312 while (result == 0) { 313 result = source.next(); 314 } 315 return result; 316 } 317 }