SeedFactory.java
/*
* 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;
}
}