| /* |
| * 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.simple.internal; |
| |
| import java.security.SecureRandom; |
| import java.util.concurrent.locks.ReentrantLock; |
| |
| import org.apache.commons.rng.core.util.NumberFactory; |
| import org.apache.commons.rng.UniformRandomProvider; |
| import org.apache.commons.rng.core.source64.RandomLongSource; |
| import org.apache.commons.rng.core.source64.SplitMix64; |
| import org.apache.commons.rng.core.source64.XoRoShiRo1024PlusPlus; |
| |
| /** |
| * Utilities related to seeding. |
| * |
| * <p> |
| * This class provides methods to generate random seeds (single values |
| * or arrays of values, of {@code int} or {@code long} types) that can |
| * be passed to the {@link org.apache.commons.rng.simple.RandomSource |
| * methods that create a generator instance}. |
| * <br> |
| * Although the seed-generating methods defined in this class will likely |
| * return different values for all calls, there is no guarantee that the |
| * produced seed will result always in a "good" sequence of numbers (even |
| * if the generator initialized with that seed is good). |
| * <br> |
| * There is <i>no guarantee</i> that sequences will not overlap. |
| * </p> |
| * |
| * @since 1.0 |
| */ |
| public final class SeedFactory { |
| /** Size of the state array of "XoRoShiRo1024PlusPlus". */ |
| private static final int XO_RO_SHI_RO_1024_STATE_SIZE = 16; |
| /** Size of block to fill in an {@code int[]} seed per synchronized operation. */ |
| private static final int INT_ARRAY_BLOCK_SIZE = 8; |
| /** Size of block to fill in a {@code long[]} seed per synchronized operation. */ |
| private static final int LONG_ARRAY_BLOCK_SIZE = 4; |
| |
| /** |
| * The lock to own when using the seed generator. This lock is unfair and there is no |
| * particular access order for waiting threads. |
| * |
| * <p>This is used as an alternative to {@code synchronized} statements to guard access |
| * to the seed generator.</p> |
| */ |
| private static final ReentrantLock LOCK = new ReentrantLock(false); |
| |
| /** Generator with a long period. */ |
| private static final UniformRandomProvider SEED_GENERATOR; |
| |
| static { |
| // Use a secure RNG so that different instances (e.g. in multiple JVM |
| // instances started in rapid succession) will have different seeds. |
| final SecureRandom seedGen = new SecureRandom(); |
| final byte[] bytes = new byte[8 * XO_RO_SHI_RO_1024_STATE_SIZE]; |
| seedGen.nextBytes(bytes); |
| final long[] seed = NumberFactory.makeLongArray(bytes); |
| // The XoRoShiRo1024PlusPlus generator cannot recover from an all zero seed and |
| // will produce low quality initial output if initialized with some zeros. |
| // Ensure it is non zero at all array positions using a SplitMix64 |
| // generator (this is insensitive to a zero seed so can use the first seed value). |
| final SplitMix64 rng = new SplitMix64(seed[0]); |
| for (int i = 0; i < seed.length; i++) { |
| seed[i] = ensureNonZero(rng, seed[i]); |
| } |
| |
| SEED_GENERATOR = new XoRoShiRo1024PlusPlus(seed); |
| } |
| |
| /** |
| * Class contains only static methods. |
| */ |
| private SeedFactory() {} |
| |
| /** |
| * Creates an {@code int} number for use as a seed. |
| * |
| * @return a random number. |
| */ |
| public static int createInt() { |
| LOCK.lock(); |
| try { |
| return SEED_GENERATOR.nextInt(); |
| } finally { |
| LOCK.unlock(); |
| } |
| } |
| |
| /** |
| * Creates a {@code long} number for use as a seed. |
| * |
| * @return a random number. |
| */ |
| public static long createLong() { |
| LOCK.lock(); |
| try { |
| return SEED_GENERATOR.nextLong(); |
| } finally { |
| LOCK.unlock(); |
| } |
| } |
| |
| /** |
| * Creates an array of {@code int} numbers for use as a seed. |
| * |
| * @param n Size of the array to create. |
| * @return an array of {@code n} random numbers. |
| */ |
| public static int[] createIntArray(int n) { |
| // Behaviour from v1.3 is to ensure the first position is non-zero |
| return createIntArray(n, 0, Math.min(n, 1)); |
| } |
| |
| /** |
| * Creates an array of {@code int} numbers for use as a seed. |
| * Optionally ensure a sub-range of the array is not all-zero. |
| * |
| * <p>This method is package-private for use by {@link NativeSeedType}. |
| * |
| * @param n Size of the array to create. |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @return an array of {@code n} random numbers. |
| * @throws IndexOutOfBoundsException if the sub-range is invalid |
| * @since 1.5 |
| */ |
| static int[] createIntArray(int n, int from, int to) { |
| final int[] seed = new int[n]; |
| // Compute the size that can be filled with complete blocks |
| final int blockSize = INT_ARRAY_BLOCK_SIZE * (n / INT_ARRAY_BLOCK_SIZE); |
| int i = 0; |
| while (i < blockSize) { |
| final int end = i + INT_ARRAY_BLOCK_SIZE; |
| fillIntArray(seed, i, end); |
| i = end; |
| } |
| // Final fill only if required |
| if (i != n) { |
| fillIntArray(seed, i, n); |
| } |
| ensureNonZero(seed, from, to); |
| return seed; |
| } |
| |
| /** |
| * Creates an array of {@code long} numbers for use as a seed. |
| * |
| * @param n Size of the array to create. |
| * @return an array of {@code n} random numbers. |
| */ |
| public static long[] createLongArray(int n) { |
| // Behaviour from v1.3 is to ensure the first position is non-zero |
| return createLongArray(n, 0, Math.min(n, 1)); |
| } |
| |
| /** |
| * Creates an array of {@code long} numbers for use as a seed. |
| * Optionally ensure a sub-range of the array is not all-zero. |
| * |
| * <p>This method is package-private for use by {@link NativeSeedType}. |
| * |
| * @param n Size of the array to create. |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @return an array of {@code n} random numbers. |
| * @throws IndexOutOfBoundsException if the sub-range is invalid |
| * @since 1.5 |
| */ |
| static long[] createLongArray(int n, int from, int to) { |
| final long[] seed = new long[n]; |
| // Compute the size that can be filled with complete blocks |
| final int blockSize = LONG_ARRAY_BLOCK_SIZE * (n / LONG_ARRAY_BLOCK_SIZE); |
| int i = 0; |
| while (i < blockSize) { |
| final int end = i + LONG_ARRAY_BLOCK_SIZE; |
| fillLongArray(seed, i, end); |
| i = end; |
| } |
| // Final fill only if required |
| if (i != n) { |
| fillLongArray(seed, i, n); |
| } |
| ensureNonZero(seed, from, to); |
| return seed; |
| } |
| |
| /** |
| * Fill the array between {@code start} inclusive and {@code end} exclusive from the |
| * seed generator. The lock is used to guard access to the generator. |
| * |
| * @param array Array data. |
| * @param start Start (inclusive). |
| * @param end End (exclusive). |
| */ |
| private static void fillIntArray(int[] array, int start, int end) { |
| LOCK.lock(); |
| try { |
| for (int i = start; i < end; i++) { |
| array[i] = SEED_GENERATOR.nextInt(); |
| } |
| } finally { |
| LOCK.unlock(); |
| } |
| } |
| |
| /** |
| * Fill the array between {@code start} inclusive and {@code end} exclusive from the |
| * seed generator. The lock is used to guard access to the generator. |
| * |
| * @param array Array data. |
| * @param start Start (inclusive). |
| * @param end End (exclusive). |
| */ |
| private static void fillLongArray(long[] array, int start, int end) { |
| LOCK.lock(); |
| try { |
| for (int i = start; i < end; i++) { |
| array[i] = SEED_GENERATOR.nextLong(); |
| } |
| } finally { |
| LOCK.unlock(); |
| } |
| } |
| |
| /** |
| * Creates an array of {@code byte} numbers for use as a seed using the supplied source of |
| * randomness. A sub-range can be specified that must not contain all zeros. |
| * |
| * @param source Source of randomness. |
| * @param n Size of the array to create. |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @return an array of {@code n} random numbers. |
| */ |
| static byte[] createByteArray(UniformRandomProvider source, |
| int n, |
| int from, |
| int to) { |
| final byte[] seed = new byte[n]; |
| source.nextBytes(seed); |
| ensureNonZero(seed, from, to, source); |
| return seed; |
| } |
| |
| /** |
| * Ensure the seed is not all-zero within the specified sub-range. |
| * |
| * <p>This method will check the sub-range and if all are zero it will fill the range |
| * with a random sequence seeded from the default source of random int values. The |
| * fill ensures position {@code from} has a non-zero value; and the entire sub-range |
| * has a maximum of one zero. The method ensures any length sub-range contains |
| * non-zero bits. The output seed is suitable for generators that cannot be seeded |
| * with all zeros in the specified sub-range.</p> |
| * |
| * @param seed Seed array (modified in place). |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @throws IndexOutOfBoundsException if the sub-range is invalid |
| * @see #createInt() |
| */ |
| static void ensureNonZero(int[] seed, int from, int to) { |
| if (from >= to) { |
| return; |
| } |
| // No check on the range so an IndexOutOfBoundsException will occur if invalid |
| for (int i = from; i < to; i++) { |
| if (seed[i] != 0) { |
| return; |
| } |
| } |
| // Fill with non-zero values using a SplitMix-style PRNG. |
| // The range is at least 1. |
| // To ensure the first value is not zero requires the input to the mix function |
| // to be non-zero. This is ensured if the start is even since the increment is odd. |
| int x = createInt() << 1; |
| for (int i = from; i < to; i++) { |
| seed[i] = MixFunctions.murmur3(x += MixFunctions.GOLDEN_RATIO_32); |
| } |
| } |
| |
| /** |
| * Ensure the seed is not all-zero within the specified sub-range. |
| * |
| * <p>This method will check the sub-range and if all are zero it will fill the range |
| * with a random sequence seeded from the default source of random long values. The |
| * fill ensures position {@code from} has a non-zero value; and the entire sub-range |
| * has a maximum of one zero. The method ensures any length sub-range contains |
| * non-zero bits. The output seed is suitable for generators that cannot be seeded |
| * with all zeros in the specified sub-range.</p> |
| * |
| * @param seed Seed array (modified in place). |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @throws IndexOutOfBoundsException if the sub-range is invalid |
| * @see #createLong() |
| */ |
| static void ensureNonZero(long[] seed, int from, int to) { |
| if (from >= to) { |
| return; |
| } |
| // No check on the range so an IndexOutOfBoundsException will occur if invalid |
| for (int i = from; i < to; i++) { |
| if (seed[i] != 0) { |
| return; |
| } |
| } |
| // Fill with non-zero values using a SplitMix-style PRNG. |
| // The range is at least 1. |
| // To ensure the first value is not zero requires the input to the mix function |
| // to be non-zero. This is ensured if the start is even since the increment is odd. |
| long x = createLong() << 1; |
| for (int i = from; i < to; i++) { |
| seed[i] = MixFunctions.stafford13(x += MixFunctions.GOLDEN_RATIO_64); |
| } |
| } |
| |
| /** |
| * Ensure the seed is not all-zero within the specified sub-range. |
| * |
| * <p>This method will check the sub-range and if all are zero it will fill the range |
| * with a random sequence seeded from the provided source of randomness. If the range |
| * length is above 8 then the first 8 bytes in the range are ensured to not all be |
| * zero. If the range length is below 8 then the first byte in the range is ensured to |
| * be non-zero. The method ensures any length sub-range contains non-zero bits. The |
| * output seed is suitable for generators that cannot be seeded with all zeros in the |
| * specified sub-range.</p> |
| * |
| * @param seed Seed array (modified in place). |
| * @param from The start of the not all-zero sub-range (inclusive). |
| * @param to The end of the not all-zero sub-range (exclusive). |
| * @param source Source of randomness. |
| * @throws IndexOutOfBoundsException if the sub-range is invalid |
| */ |
| static void ensureNonZero(byte[] seed, int from, int to, UniformRandomProvider source) { |
| if (from >= to) { |
| return; |
| } |
| // No check on the range so an IndexOutOfBoundsException will occur if invalid |
| for (int i = from; i < to; i++) { |
| if (seed[i] != 0) { |
| return; |
| } |
| } |
| // Defend against a faulty source of randomness (which supplied all zero bytes) |
| // by filling with non-zero values using a SplitMix-style PRNG seeded from the source. |
| // The range is at least 1. |
| // To ensure the first value is not zero requires the input to the mix function |
| // to be non-zero. This is ensured if the start is even since the increment is odd. |
| long x = source.nextLong() << 1; |
| |
| // Process in blocks of 8. |
| // Get the length without the final 3 bits set for a multiple of 8. |
| final int len = (to - from) & ~0x7; |
| final int end = from + len; |
| int i = from; |
| while (i < end) { |
| long v = MixFunctions.stafford13(x += MixFunctions.GOLDEN_RATIO_64); |
| for (int j = 0; j < 8; j++) { |
| seed[i++] = (byte) v; |
| v >>>= 8; |
| } |
| } |
| |
| if (i < to) { |
| // The final bytes. |
| long v = MixFunctions.stafford13(x + MixFunctions.GOLDEN_RATIO_64); |
| // Note the special case where no blocks have been processed requires these |
| // bytes to be non-zero, i.e. (to - from) < 8. In this case the value 'v' will |
| // be non-zero due to the initialisation of 'x' as even. |
| // Rotate the value so the least significant byte is non-zero. The rotation |
| // in bits is rounded down to the nearest 8-bit block to ensure a byte rotation. |
| if (len == 0) { |
| v = Long.rotateRight(v, Long.numberOfTrailingZeros(v) & ~0x7); |
| } |
| while (i < to) { |
| seed[i++] = (byte) v; |
| v >>>= 8; |
| } |
| } |
| } |
| |
| /** |
| * Ensure the value is non-zero. |
| * |
| * <p>This method will replace a zero with a non-zero random number from the random source.</p> |
| * |
| * @param source Source of randomness. |
| * @param value Value. |
| * @return {@code value} if non-zero; else a new random number |
| */ |
| static long ensureNonZero(RandomLongSource source, |
| long value) { |
| long result = value; |
| while (result == 0) { |
| result = source.next(); |
| } |
| return result; |
| } |
| } |