This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
The following commit(s) were added to refs/heads/master by this push:
new ab6050d9 RNG-174: Improve support for non-zero seeds
ab6050d9 is described below
commit ab6050d992dd9e8057e0d3e3e29d534839c51440
Author: aherbert <[email protected]>
AuthorDate: Fri Apr 1 17:46:12 2022 +0100
RNG-174: Improve support for non-zero seeds
Allow specification of a range for array seeds that must be non-zero.
The values for the range are based on the result of
o.a.c.rng.simple.ProvidersCommonParametricTest.testZeroIntArraySeed.
See also the core module for tests using:
- RandomAssert.assertNextIntZeroOutput
- RandomAssert.assertIntArrayConstructorWithSingleBitInPoolIsFunctional
Any generator that fails these tests requires a non-zero seed. In most
cases this was set as the full seed length, or one less for generators
that do not use all the bits of the seed array (WELL_19937_x,
WELL_44497_x).
Notable exceptions:
The KISS generator is reduced to a simple LCG when positions [0, 3) are
all zero. Added a test to demonstrate this. With a zero seed the KISS
LCG passes testZeroIntArraySeed. To avoid a poor generator the seed will
be checked to be non-zero in [0, 3).
The MSWS generator is sensitive to the initial state. Added a test to
show that a zero seed creates zero output. Updating RandomAssert to add
an assertLongArrayConstructorWithSingleBitInPoolIsFunctional test shows
the MSWS fails with single bit seeds. The sub-range has been set to [2,
3) to ensure a non-zero Weyl increment which is the best way to escape a
bad seed. This is a functionally breaking change.
---
.../org/apache/commons/rng/core/RandomAssert.java | 30 ++-
.../commons/rng/core/source32/KISSRandomTest.java | 17 ++
.../source32/MiddleSquareWeylSequenceTest.java | 8 +
.../commons/rng/simple/internal/Conversions.java | 28 +-
.../commons/rng/simple/internal/MixFunctions.java | 73 ++++++
.../rng/simple/internal/NativeSeedType.java | 33 ++-
.../rng/simple/internal/ProviderBuilder.java | 115 ++++++---
.../commons/rng/simple/internal/SeedFactory.java | 208 +++++++++++----
.../rng/simple/ProvidersCommonParametricTest.java | 28 +-
.../rng/simple/internal/MixFunctionsTest.java | 119 +++++++++
.../internal/NativeSeedTypeParametricTest.java | 25 ++
.../rng/simple/internal/SeedFactoryTest.java | 281 +++++++++++++++++----
src/changes/changes.xml | 8 +-
src/main/resources/pmd/pmd-ruleset.xml | 2 +-
14 files changed, 800 insertions(+), 175 deletions(-)
diff --git
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
index e72b225a..a2aec6ca 100644
---
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
+++
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/RandomAssert.java
@@ -353,7 +353,7 @@ public final class RandomAssert {
final int[] seed = new int[size];
int remaining = k;
for (int i = 0; i < seed.length; i++) {
- seed[i] = 0x80000000;
+ seed[i] = Integer.MIN_VALUE;
for (int j = 0; j < 32; j++) {
final UniformRandomProvider rng =
constructor.newInstance(seed);
RandomAssert.assertNextLongNonZeroOutputFromSingleBitSeed(rng, 2 * size, 2 *
size, i, 31 - j);
@@ -383,17 +383,41 @@ public final class RandomAssert {
*/
public static <T extends UniformRandomProvider> void
assertLongArrayConstructorWithSingleBitSeedIsFunctional(Class<T> type,
int size) {
+ assertLongArrayConstructorWithSingleBitInPoolIsFunctional(type, 64 *
size);
+ }
+
+ /**
+ * Assert that the random generator created using an {@code long[]} seed
with a
+ * single bit set is functional. This is tested using the
+ * {@link #assertNextLongNonZeroOutput(UniformRandomProvider, int, int)}
using
+ * two times the seed size as the warm-up and test cycles.
+ *
+ * <p>The seed size is determined from the size of the bit pool. Bits are
set for every position
+ * in the pool from most significant first. If the pool size is not a
multiple of 64 then the
+ * remaining lower significant bits of the last seed position are not
tested.</p>
+ *
+ * @param type Class of the generator.
+ * @param k Number of bits in the pool (not necessarily a multiple of 64).
+ */
+ public static <T extends UniformRandomProvider> void
+ assertLongArrayConstructorWithSingleBitInPoolIsFunctional(Class<T>
type, int k) {
try {
// Find the long[] constructor
final Constructor<T> constructor =
type.getConstructor(long[].class);
+ final int size = (k + 63) / 64;
final long[] seed = new long[size];
- for (int i = 0; i < size; i++) {
- seed[i] = 0x8000000000000000L;
+ int remaining = k;
+ for (int i = 0; i < seed.length; i++) {
+ seed[i] = Long.MIN_VALUE;
for (int j = 0; j < 64; j++) {
final UniformRandomProvider rng =
constructor.newInstance(seed);
RandomAssert.assertNextLongNonZeroOutputFromSingleBitSeed(rng, 2 * size, 2 *
size, i, 63 - j);
// Eventually reset to zero
seed[i] >>>= 1;
+ // Terminate when the entire bit pool has been tested
+ if (--remaining == 0) {
+ return;
+ }
}
Assertions.assertEquals(0L, seed[i], "Seed element was not
reset");
}
diff --git
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/KISSRandomTest.java
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/KISSRandomTest.java
index b26fcafb..5af35069 100644
---
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/KISSRandomTest.java
+++
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/KISSRandomTest.java
@@ -17,6 +17,7 @@
package org.apache.commons.rng.core.source32;
import org.apache.commons.rng.core.RandomAssert;
+import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
class KISSRandomTest {
@@ -162,4 +163,20 @@ class KISSRandomTest {
RandomAssert.assertEquals(expectedSequence, new KISSRandom(seed));
}
+
+ @Test
+ void testConstructorWithZeroSeedInSubRangeIsPartiallyFunctional() {
+ // If the first 3 positions are zero then the output is a simple LCG.
+ // The seeding routine in commons-rng-simple should ensure the first 3
seed
+ // positions are not all zero.
+ final int m = 69069;
+ final int c = 1234567;
+ int s = 42;
+ final int[] seed = new int[] {0, 0, 0, s};
+ final KISSRandom rng = new KISSRandom(seed);
+ for (int i = 0; i < 200; i++) {
+ s = m * s + c;
+ Assertions.assertEquals(s, rng.nextInt());
+ }
+ }
}
diff --git
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
index 23235698..2b7490dd 100644
---
a/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
+++
b/commons-rng-core/src/test/java/org/apache/commons/rng/core/source32/MiddleSquareWeylSequenceTest.java
@@ -22,6 +22,9 @@ import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
class MiddleSquareWeylSequenceTest {
+ /** The size of the array seed. */
+ private static final int SEED_SIZE = 3;
+
@Test
void testReferenceCode() {
/*
@@ -97,4 +100,9 @@ class MiddleSquareWeylSequenceTest {
rng2.nextLong());
}
}
+
+ @Test
+ void testConstructorWithZeroSeedIsNonFunctional() {
+ RandomAssert.assertNextIntZeroOutput(new MiddleSquareWeylSequence(new
long[SEED_SIZE]), 2 * SEED_SIZE);
+ }
}
diff --git
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java
index 2eff8c08..e107c92f 100644
---
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java
+++
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java
@@ -34,7 +34,7 @@ final class Conversions {
* </pre>
* @see <a href="https://en.wikipedia.org/wiki/Golden_ratio";>Golden
ratio</a>
*/
- private static final long GOLDEN_RATIO = 0x9e3779b97f4a7c15L;
+ private static final long GOLDEN_RATIO = MixFunctions.GOLDEN_RATIO_64;
/** No instances. */
private Conversions() {}
@@ -100,24 +100,6 @@ final class Conversions {
return (size + 1) >>> 1;
}
- /**
- * Perform variant 13 of David Stafford's 64-bit mix function.
- * This is the mix function used in the {@link SplitMix64} RNG.
- *
- * <p>This is ranked first of the top 14 Stafford mixers.
- *
- * @param z the input value
- * @return the output value
- * @see <a
href="http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html";>Better
- * Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a>
- */
- private static long stafford13(long z) {
- long x = z;
- x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L;
- x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL;
- return x ^ (x >>> 31);
- }
-
/**
* Creates a {@code long} value from an {@code int}. The conversion
* is made as if seeding a SplitMix64 RNG and calling nextLong().
@@ -126,7 +108,7 @@ final class Conversions {
* @return a {@code long}.
*/
static long int2Long(int input) {
- return stafford13(input + GOLDEN_RATIO);
+ return MixFunctions.stafford13(input + GOLDEN_RATIO);
}
/**
@@ -189,13 +171,13 @@ final class Conversions {
// Process pairs
final int n = length & ~0x1;
for (int i = 0; i < n; i += 2) {
- final long x = stafford13(v += GOLDEN_RATIO);
+ final long x = MixFunctions.stafford13(v += GOLDEN_RATIO);
output[i] = (int) x;
output[i + 1] = (int) (x >>> 32);
}
// Final value
if (n < length) {
- output[n] = (int) stafford13(v + GOLDEN_RATIO);
+ output[n] = (int) MixFunctions.stafford13(v + GOLDEN_RATIO);
}
return output;
}
@@ -213,7 +195,7 @@ final class Conversions {
long v = input;
final long[] output = new long[length];
for (int i = 0; i < length; i++) {
- output[i] = stafford13(v += GOLDEN_RATIO);
+ output[i] = MixFunctions.stafford13(v += GOLDEN_RATIO);
}
return output;
}
diff --git
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/MixFunctions.java
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/MixFunctions.java
new file mode 100644
index 00000000..eb8f4fc7
--- /dev/null
+++
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/MixFunctions.java
@@ -0,0 +1,73 @@
+/*
+ * 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;
+
+/**
+ * Performs mixing of bits.
+ *
+ * @since 1.5
+ */
+final class MixFunctions {
+ /**
+ * The fractional part of the the golden ratio, phi, scaled to 64-bits and
rounded to odd.
+ * This can be used as an increment for a Weyl sequence.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio";>Golden
ratio</a>
+ */
+ static final long GOLDEN_RATIO_64 = 0x9e3779b97f4a7c15L;
+ /**
+ * The fractional part of the the golden ratio, phi, scaled to 32-bits and
rounded to odd.
+ * This can be used as an increment for a Weyl sequence.
+ *
+ * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio";>Golden
ratio</a>
+ */
+ static final int GOLDEN_RATIO_32 = 0x9e3779b9;
+
+ /** No instances. */
+ private MixFunctions() {}
+
+ /**
+ * Perform variant 13 of David Stafford's 64-bit mix function.
+ * This is the mix function used in the
+ * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} RNG.
+ *
+ * <p>This is ranked first of the top 14 Stafford mixers.
+ *
+ * @param x the input value
+ * @return the output value
+ * @see <a
href="http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html";>Better
+ * Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a>
+ */
+ static long stafford13(long x) {
+ x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L;
+ x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL;
+ return x ^ (x >>> 31);
+ }
+
+ /**
+ * Perform the finalising 32-bit mix function of Austin Appleby's
MurmurHash3.
+ *
+ * @param x the input value
+ * @return the output value
+ * @see <a href="https://github.com/aappleby/smhasher";>SMHasher</a>
+ */
+ static int murmur3(int x) {
+ x = (x ^ (x >>> 16)) * 0x85ebca6b;
+ x = (x ^ (x >>> 13)) * 0xc2b2ae35;
+ return x ^ (x >>> 16);
+ }
+}
diff --git
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java
index 8639b4da..231e2db0 100644
---
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java
+++
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java
@@ -45,7 +45,7 @@ public enum NativeSeedType {
/** The seed type is {@code Integer}. */
INT(Integer.class, 4) {
@Override
- public Integer createSeed(int size) {
+ public Integer createSeed(int size, int from, int to) {
return SeedFactory.createInt();
}
@Override
@@ -72,7 +72,7 @@ public enum NativeSeedType {
/** The seed type is {@code Long}. */
LONG(Long.class, 8) {
@Override
- public Long createSeed(int size) {
+ public Long createSeed(int size, int from, int to) {
return SeedFactory.createLong();
}
@Override
@@ -99,10 +99,11 @@ public enum NativeSeedType {
/** The seed type is {@code int[]}. */
INT_ARRAY(int[].class, 4) {
@Override
- public int[] createSeed(int size) {
+ public int[] createSeed(int size, int from, int to) {
// Limit the number of calls to the synchronized method. The
generator
// will support self-seeding.
- return SeedFactory.createIntArray(Math.min(size,
RANDOM_SEED_ARRAY_SIZE));
+ return SeedFactory.createIntArray(Math.min(size,
RANDOM_SEED_ARRAY_SIZE),
+ from, to);
}
@Override
protected int[] convert(Integer seed, int size) {
@@ -132,10 +133,11 @@ public enum NativeSeedType {
/** The seed type is {@code long[]}. */
LONG_ARRAY(long[].class, 8) {
@Override
- public long[] createSeed(int size) {
+ public long[] createSeed(int size, int from, int to) {
// Limit the number of calls to the synchronized method. The
generator
// will support self-seeding.
- return SeedFactory.createLongArray(Math.min(size,
RANDOM_SEED_ARRAY_SIZE));
+ return SeedFactory.createLongArray(Math.min(size,
RANDOM_SEED_ARRAY_SIZE),
+ from, to);
}
@Override
protected long[] convert(Integer seed, int size) {
@@ -214,7 +216,24 @@ public enum NativeSeedType {
* @param size The size of the seed (array types only).
* @return the seed
*/
- public abstract Object createSeed(int size);
+ public Object createSeed(int size) {
+ // Maintain behaviour since 1.3 to ensure position [0] of array seeds
is non-zero.
+ return createSeed(size, 0, Math.min(size, 1));
+ }
+
+ /**
+ * Creates the seed. The output seed type is determined by the native seed
type. If
+ * the output is an array the required size of the array can be specified
and a
+ * sub-range that must not be all-zero.
+ *
+ * @param size The size of the seed (array types only).
+ * @param from The start of the not all-zero sub-range (inclusive; array
types only).
+ * @param to The end of the not all-zero sub-range (exclusive; array types
only).
+ * @return the seed
+ * @throws IndexOutOfBoundsException if the sub-range is out of bounds
+ * @since 1.5
+ */
+ public abstract Object createSeed(int size, int from, int to);
/**
* Converts the input seed from any of the supported seed types to the
native seed type.
diff --git
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
index 78e76548..cd3c437b 100644
---
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
+++
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/ProviderBuilder.java
@@ -132,27 +132,27 @@ public final class ProviderBuilder {
NativeSeedType.LONG),
/** Source of randomness is {@link Well512a}. */
WELL_512_A(Well512a.class,
- 16,
+ 16, 0, 16,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link Well1024a}. */
WELL_1024_A(Well1024a.class,
- 32,
+ 32, 0, 32,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link Well19937a}. */
WELL_19937_A(Well19937a.class,
- 624,
+ 624, 0, 623,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link Well19937c}. */
WELL_19937_C(Well19937c.class,
- 624,
+ 624, 0, 623,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link Well44497a}. */
WELL_44497_A(Well44497a.class,
- 1391,
+ 1391, 0, 1390,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link Well44497b}. */
WELL_44497_B(Well44497b.class,
- 1391,
+ 1391, 0, 1390,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link MersenneTwister}. */
MT(MersenneTwister.class,
@@ -168,7 +168,7 @@ public final class ProviderBuilder {
NativeSeedType.LONG),
/** Source of randomness is {@link XorShift1024Star}. */
XOR_SHIFT_1024_S(XorShift1024Star.class,
- 16,
+ 16, 0, 16,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link TwoCmres}. */
TWO_CMRES(TwoCmres.class,
@@ -189,55 +189,56 @@ public final class ProviderBuilder {
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link MultiplyWithCarry256}. */
MWC_256(MultiplyWithCarry256.class,
- 257,
+ 257, 0, 257,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link KISSRandom}. */
KISS(KISSRandom.class,
- 4,
+ // If zero in initial 3 positions the output is a simple LCG
+ 4, 0, 3,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XorShift1024StarPhi}. */
XOR_SHIFT_1024_S_PHI(XorShift1024StarPhi.class,
- 16,
+ 16, 0, 16,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoRoShiRo64Star}. */
XO_RO_SHI_RO_64_S(XoRoShiRo64Star.class,
- 2,
+ 2, 0, 2,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XoRoShiRo64StarStar}. */
XO_RO_SHI_RO_64_SS(XoRoShiRo64StarStar.class,
- 2,
+ 2, 0, 2,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XoShiRo128Plus}. */
XO_SHI_RO_128_PLUS(XoShiRo128Plus.class,
- 4,
+ 4, 0, 4,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XoShiRo128StarStar}. */
XO_SHI_RO_128_SS(XoShiRo128StarStar.class,
- 4,
+ 4, 0, 4,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XoRoShiRo128Plus}. */
XO_RO_SHI_RO_128_PLUS(XoRoShiRo128Plus.class,
- 2,
+ 2, 0, 2,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoRoShiRo128StarStar}. */
XO_RO_SHI_RO_128_SS(XoRoShiRo128StarStar.class,
- 2,
+ 2, 0, 2,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo256Plus}. */
XO_SHI_RO_256_PLUS(XoShiRo256Plus.class,
- 4,
+ 4, 0, 4,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo256StarStar}. */
XO_SHI_RO_256_SS(XoShiRo256StarStar.class,
- 4,
+ 4, 0, 4,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo512Plus}. */
XO_SHI_RO_512_PLUS(XoShiRo512Plus.class,
- 8,
+ 8, 0, 8,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo512StarStar}. */
XO_SHI_RO_512_SS(XoShiRo512StarStar.class,
- 8,
+ 8, 0, 8,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link PcgXshRr32}. */
PCG_XSH_RR_32(PcgXshRr32.class,
@@ -261,7 +262,10 @@ public final class ProviderBuilder {
NativeSeedType.LONG),
/** Source of randomness is {@link MiddleSquareWeylSequence}. */
MSWS(MiddleSquareWeylSequence.class,
- 3,
+ // Many partially zero seeds can create low quality initial
output.
+ // The Weyl increment cascades bits into the random state so
ideally it
+ // has a high number of bit transitions. Minimally ensure it is
non-zero.
+ 3, 2, 3,
NativeSeedType.LONG_ARRAY) {
@Override
protected Object createSeed() {
@@ -356,31 +360,31 @@ public final class ProviderBuilder {
NativeSeedType.LONG),
/** Source of randomness is {@link XoShiRo128PlusPlus}. */
XO_SHI_RO_128_PP(XoShiRo128PlusPlus.class,
- 4,
+ 4, 0, 4,
NativeSeedType.INT_ARRAY),
/** Source of randomness is {@link XoRoShiRo128PlusPlus}. */
XO_RO_SHI_RO_128_PP(XoRoShiRo128PlusPlus.class,
- 2,
+ 2, 0, 2,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo256PlusPlus}. */
XO_SHI_RO_256_PP(XoShiRo256PlusPlus.class,
- 4,
+ 4, 0, 4,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoShiRo512PlusPlus}. */
XO_SHI_RO_512_PP(XoShiRo512PlusPlus.class,
- 8,
+ 8, 0, 8,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoRoShiRo1024PlusPlus}. */
XO_RO_SHI_RO_1024_PP(XoRoShiRo1024PlusPlus.class,
- 16,
+ 16, 0, 16,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoRoShiRo1024Star}. */
XO_RO_SHI_RO_1024_S(XoRoShiRo1024Star.class,
- 16,
+ 16, 0, 16,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link XoRoShiRo1024StarStar}. */
XO_RO_SHI_RO_1024_SS(XoRoShiRo1024StarStar.class,
- 16,
+ 16, 0, 16,
NativeSeedType.LONG_ARRAY),
/** Source of randomness is {@link PcgXshRr32}. */
PCG_XSH_RR_32_OS(PcgXshRr32.class,
@@ -399,6 +403,10 @@ public final class ProviderBuilder {
private final Class<? extends UniformRandomProvider> rng;
/** Native seed size. Used for array seeds. */
private final int nativeSeedSize;
+ /** Start of the not all-zero sub-range for array seeds (inclusive). */
+ private final int notAllZeroFrom;
+ /** End of the not all-zero sub-range for array seeds (exclusive). */
+ private final int notAllZeroTo;
/** Define the parameter types of the data needed to build the
generator. */
private final Class<?>[] args;
/** Native seed type. Used to create a seed or convert input seeds. */
@@ -412,6 +420,8 @@ public final class ProviderBuilder {
/**
* Create a new instance.
*
+ * <p>Used when the seed array has no requirement for a not all-zero
sub-range.
+ *
* @param rng Source type.
* @param nativeSeedSize Native seed size (array types only).
* @param nativeSeedType Native seed type.
@@ -421,8 +431,36 @@ public final class ProviderBuilder {
int nativeSeedSize,
NativeSeedType nativeSeedType,
Class<?>... args) {
+ this(rng, nativeSeedSize, 0, 0, nativeSeedType, args);
+ }
+
+ /**
+ * Create a new instance.
+ *
+ * <p>Note: The sub-range of an array seed that is not all-zero can be
specified.
+ * If the native seed array is used to represent a number of bits
+ * that is not an exact multiple of the number of bytes in the seed,
then a
+ * safe approach is to specify the sub-range using a smaller size than
the
+ * full length seed. For example a {@link Well19937a} generator uses
19937
+ * bits and has a seed bit length of 19968. A safe range is [0, 19937
/ 32).
+ *
+ * @param rng Source type.
+ * @param nativeSeedSize Native seed size (array types only).
+ * @param notAllZeroFrom The start of the not all-zero sub-range
(inclusive).
+ * @param notAllZeroTo The end of the not all-zero sub-range
(exclusive).
+ * @param nativeSeedType Native seed type.
+ * @param args Additional data needed to create a generator instance.
+ */
+ RandomSourceInternal(Class<? extends UniformRandomProvider> rng,
+ int nativeSeedSize,
+ int notAllZeroFrom,
+ int notAllZeroTo,
+ NativeSeedType nativeSeedType,
+ Class<?>... args) {
this.rng = rng;
this.nativeSeedSize = nativeSeedSize;
+ this.notAllZeroFrom = notAllZeroFrom;
+ this.notAllZeroTo = notAllZeroTo;
this.nativeSeedType = nativeSeedType;
// Build the complete list of class types for the constructor
this.args = (Class<?>[])
Array.newInstance(args.getClass().getComponentType(), 1 + args.length);
@@ -471,16 +509,6 @@ public final class ProviderBuilder {
return seed != null && getSeed().equals(seed.getClass());
}
- /**
- * Gets the number of seed bytes required to seed the implementing
class represented by
- * this random source.
- *
- * @return the number of seed bytes
- */
- private int getSeedByteSize() {
- return nativeSeedSize * nativeSeedType.getBytes();
- }
-
/**
* Creates a RNG instance.
*
@@ -550,7 +578,8 @@ public final class ProviderBuilder {
* @since 1.3
*/
protected Object createSeed() {
- return nativeSeedType.createSeed(nativeSeedSize);
+ // Ensure the seed is not all-zero in the sub-range
+ return nativeSeedType.createSeed(nativeSeedSize, notAllZeroFrom,
notAllZeroTo);
}
/**
@@ -566,7 +595,13 @@ public final class ProviderBuilder {
* @since 1.3
*/
protected byte[] createByteArraySeed(UniformRandomProvider source) {
- return SeedFactory.createByteArray(source, getSeedByteSize());
+ // Ensure the seed is not all-zero in the sub-range.
+ // Note: Convert the native seed array size/positions to byte
size/positions.
+ final int bytes = nativeSeedType.getBytes();
+ return SeedFactory.createByteArray(source,
+ bytes * nativeSeedSize,
+ bytes * notAllZeroFrom,
+ bytes * notAllZeroTo);
}
/**
diff --git
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
index ed92cc91..5139125f 100644
---
a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
+++
b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/SeedFactory.java
@@ -123,6 +123,24 @@ public final class SeedFactory {
* @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);
@@ -136,7 +154,7 @@ public final class SeedFactory {
if (i != n) {
fillIntArray(seed, i, n);
}
- ensureNonZero(seed);
+ ensureNonZero(seed, from, to);
return seed;
}
@@ -147,6 +165,24 @@ public final class SeedFactory {
* @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);
@@ -160,7 +196,7 @@ public final class SeedFactory {
if (i != n) {
fillLongArray(seed, i, n);
}
- ensureNonZero(seed);
+ ensureNonZero(seed, from, to);
return seed;
}
@@ -204,97 +240,159 @@ public final class SeedFactory {
/**
* Creates an array of {@code byte} numbers for use as a seed using the
supplied source of
- * randomness. The result will not be all zeros.
+ * 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 n,
+ int from,
+ int to) {
final byte[] seed = new byte[n];
source.nextBytes(seed);
- // If the seed is zero it is assumed the input source RNG is either
broken
- // or the seed is small and it was zero by chance. Revert to the
built-in
- // source of randomness to ensure it is non-zero.
- ensureNonZero(seed);
+ ensureNonZero(seed, from, to, source);
return seed;
}
/**
- * Ensure the seed is non-zero at the first position in the array.
+ * Ensure the seed is not all-zero within the specified sub-range.
*
- * <p>This method will replace a zero at index 0 in the array with
- * a non-zero random number. The method ensures any length seed
- * contains non-zero bits. The output seed is suitable for generators
- * that cannot be seeded with all zeros.</p>
+ * <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) {
- // Zero occurs 1 in 2^32
- if (seed.length != 0 && seed[0] == 0) {
- do {
- seed[0] = createInt();
- } while (seed[0] == 0);
+ 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 non-zero at the first position in the array.
+ * Ensure the seed is not all-zero within the specified sub-range.
*
- * <p>This method will replace a zero at index 0 in the array with
- * a non-zero random number. The method ensures any length seed
- * contains non-zero bits. The output seed is suitable for generators
- * that cannot be seeded with all zeros.</p>
+ * <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) {
- // Zero occurs 1 in 2^64
- if (seed.length != 0 && seed[0] == 0) {
- do {
- seed[0] = createLong();
- } while (seed[0] == 0);
+ 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 zero at all positions in the array.
+ * Ensure the seed is not all-zero within the specified sub-range.
*
- * <p>This method will check all positions in the array and if all
- * are zero it will replace index 0 in the array with
- * a non-zero random number. The method ensures any length seed
- * contains non-zero bits. The output seed is suitable for generators
- * that cannot be seeded with all zeros.</p>
+ * <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).
- * @see #createInt()
+ * @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
*/
- private static void ensureNonZero(byte[] seed) {
- // Since zero occurs 1 in 2^8 for a single byte this checks the entire
array for zeros.
- if (seed.length != 0 && isAllZero(seed)) {
- do {
- seed[0] = (byte) createInt();
- } while (seed[0] == 0);
+ 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;
- /**
- * Test if each position in the array is zero.
- *
- * @param array Array data.
- * @return true if all position are zero
- */
- private static boolean isAllZero(byte[] array) {
- for (final byte value : array) {
- if (value != 0) {
- return false;
+ // 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;
}
}
- return true;
}
/**
diff --git
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
index 6a0ef5fe..4fc5e20a 100644
---
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
+++
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/ProvidersCommonParametricTest.java
@@ -38,6 +38,7 @@ import
org.apache.commons.rng.LongJumpableUniformRandomProvider;
import org.apache.commons.rng.RandomProviderState;
import org.apache.commons.rng.RestorableUniformRandomProvider;
import org.apache.commons.rng.core.RandomProviderDefaultState;
+import org.apache.commons.rng.core.source64.LongProvider;
import org.apache.commons.rng.core.source64.SplitMix64;
/**
@@ -190,8 +191,6 @@ class ProvidersCommonParametricTest {
final Object[] originalArgs = data.getArgs();
final long[] empty = new long[0];
Assumptions.assumeTrue(originalSource.isNativeSeed(empty));
- // The Middle-Square Weyl Sequence generator cannot self-seed
- Assumptions.assumeFalse(originalSource == RandomSource.MSWS);
// Exercise the default seeding procedure.
final UniformRandomProvider rng = originalSource.create(empty,
originalArgs);
@@ -244,6 +243,31 @@ class ProvidersCommonParametricTest {
checkNextIntegerInRange(rng, 10, 10000);
}
+ @ParameterizedTest
+ @MethodSource("getProvidersTestData")
+ void testRandomSourceCreateSeedFromInvalidRNG(ProvidersList.Data data) {
+ // Create a RNG that will fill a byte[] seed with all zeros.
+ // The ensure non-zero range checks in the RandomSource should
+ // create a good seed and a functional RNG.
+ final LongProvider badRng = new LongProvider() {
+ @Override
+ public long next() {
+ return 0;
+ }
+ };
+
+ final RandomSource originalSource = data.getSource();
+ final byte[] seed = originalSource.createSeed(badRng);
+
+ // The seed generation should be repeatable
+ Assertions.assertArrayEquals(seed, originalSource.createSeed(badRng));
+
+ // The RNG seed will create a functional generator
+ final Object[] originalArgs = data.getArgs();
+ final UniformRandomProvider rng = originalSource.create(seed,
originalArgs);
+ checkNextIntegerInRange(rng, 10, 10000);
+ }
+
// State save and restore tests.
@SuppressWarnings("unused")
diff --git
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/MixFunctionsTest.java
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/MixFunctionsTest.java
new file mode 100644
index 00000000..c291c077
--- /dev/null
+++
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/MixFunctionsTest.java
@@ -0,0 +1,119 @@
+/*
+ * 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.util.SplittableRandom;
+import org.apache.commons.rng.core.source64.SplitMix64;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
+
+/**
+ * Tests for {@link MixFunctions}.
+ */
+class MixFunctionsTest {
+ @ParameterizedTest
+ @ValueSource(longs = {0, -1, 1, 63812881278371L, -236812734617872L})
+ void testStafford13(long seed) {
+ // Reference output is from a SplitMix64 generator
+ final SplitMix64 rng = new SplitMix64(seed);
+
+ long x = seed;
+ for (int i = 0; i < 20; i++) {
+ Assertions.assertEquals(rng.nextLong(), MixFunctions.stafford13(x
+= MixFunctions.GOLDEN_RATIO_64));
+ }
+ }
+
+ @Test
+ void testMurmur3() {
+ // Reference output from the c++ function fmix32(uint32_t) in smhasher.
+ // https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ final int seedA = 0x012de1ba;
+ final int[] valuesA = {
+ 0x2f66c8b6, 0x256c0269, 0x054ef409, 0x402425ba, 0x78ebf590,
0x76bea1db,
+ 0x8bf5dcbe, 0x104ecdd4, 0x43cfc87e, 0xa33c7643, 0x4d210f56,
0xfa12093d,
+ };
+
+ int x = seedA;
+ for (int z : valuesA) {
+ Assertions.assertEquals(z, MixFunctions.murmur3(x +=
MixFunctions.GOLDEN_RATIO_32));
+ }
+
+ // Values from a seed of zero
+ final int[] values0 = {
+ 0x92ca2f0e, 0x3cd6e3f3, 0x1b147dcc, 0x4c081dbf, 0x487981ab,
0xdb408c9d,
+ 0x78bc1b8f, 0xd83072e5, 0x65cbdd54, 0x1f4b8cef, 0x91783bb0,
0x0231739b,
+ };
+
+ x = 0;
+ for (int z : values0) {
+ Assertions.assertEquals(z, MixFunctions.murmur3(x +=
MixFunctions.GOLDEN_RATIO_32));
+ }
+ }
+
+ /**
+ * Test the reverse of the Stafford 13 mix function.
+ */
+ @Test
+ void testUnmixStafford13() {
+ final SplittableRandom rng = new SplittableRandom();
+ for (int i = 0; i < 100; i++) {
+ final long x = rng.nextLong();
+ final long y = MixFunctions.stafford13(x);
+ Assertions.assertEquals(x, unmixStafford13(y));
+ }
+ }
+
+ /**
+ * Reverse the Stafford 13 mix function.
+ *
+ * <p>This can be used to generate specific seed values for a
SplitMix-style RNG using
+ * the Stafford 13 mix constants, for example in the SeedFactoryTest. It
is left in
+ * the test source code as a reference to allow computation of test seeds.
+ *
+ * @param x Argument
+ * @return the result
+ */
+ private static long unmixStafford13(long x) {
+ // Multiplicative inverse:
+ //
https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
+ // Invert 0xbf58476d1ce4e5b9L
+ final long u1 = 0x96de1b173f119089L;
+ // Invert 0x94d049bb133111ebL
+ final long u2 = 0x319642b2d24d8ec3L;
+ // Inversion of xor right-shift operations exploits the facts:
+ // 1. A xor operation can be used to recover itself:
+ // x ^ y = z
+ // z ^ y = x
+ // z ^ x = y
+ // 2. During xor right-shift of size n the top n-bits are unchanged.
+ // 3. Known values from the top bits can be used to recover the next
set of n-bits.
+ // Recovery is done by xoring with the shifted argument, then doubling
the right shift.
+ // This is iterated until all bits are recovered. With initial large
shifts only one
+ // doubling is required.
+ x = x ^ (x >>> 31);
+ x ^= x >>> 62;
+ x *= u2;
+ x = x ^ (x >>> 27);
+ x ^= x >>> 54;
+ x *= u1;
+ x = x ^ (x >>> 30);
+ x ^= x >>> 60;
+ return x;
+ }
+}
diff --git
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeParametricTest.java
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeParametricTest.java
index 1022d3c2..c314303a 100644
---
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeParametricTest.java
+++
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeParametricTest.java
@@ -17,6 +17,7 @@
package org.apache.commons.rng.simple.internal;
import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Assumptions;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.EnumSource;
import org.junit.jupiter.api.Test;
@@ -93,6 +94,30 @@ class NativeSeedTypeParametricTest {
}
}
+ /**
+ * Test the seed can be checked as non-zero in a sub-range. This uses a
bad range to
+ * generate an expected exception. The non-zero requirement is not tested
as random
+ * seeding is very unlikely to create even a single 32-bit integer that is
zero and
+ * requires correction. This test at least verifies the (from, to)
sub-range arguments
+ * are used.
+ *
+ * @param nativeSeedType Native seed type.
+ */
+ @ParameterizedTest
+ @EnumSource
+ void testCreateArraySeedWithNonZeroRangeThrows(NativeSeedType
nativeSeedType) {
+ Assumptions.assumeTrue(nativeSeedType.getType().isArray(), "Not an
array type");
+ // Arguments: (size, from, to)
+ // Since the seed is created randomly it is very likely non-zero.
+ // Use a sub-range that will throw on the first array access; otherwise
+ // if the array location is valid it will likely be non-zero and no
further
+ // checks are made.
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
nativeSeedType.createSeed(0, 0, 1));
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
nativeSeedType.createSeed(1, -1, 1));
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
nativeSeedType.createSeed(1, 1, 2));
+ Assertions.assertThrows(IndexOutOfBoundsException.class, () ->
nativeSeedType.createSeed(1, 2, 3));
+ }
+
/**
* Test the seed can be created, converted to a byte[] and then back to
the native type.
*
diff --git
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
index 02526675..5ed3eb7a 100644
---
a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
+++
b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/SeedFactoryTest.java
@@ -17,12 +17,18 @@
package org.apache.commons.rng.simple.internal;
import java.util.Map;
+import java.util.Arrays;
import java.util.HashMap;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+import org.junit.jupiter.params.provider.ValueSource;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.core.source32.IntProvider;
+import org.apache.commons.rng.core.source64.LongProvider;
import org.apache.commons.rng.core.source64.RandomLongSource;
+import org.apache.commons.rng.core.source64.SplitMix64;
import org.apache.commons.rng.core.util.NumberFactory;
/**
@@ -113,6 +119,11 @@ class SeedFactoryTest {
}
}
+ @Test
+ void testCreateIntArrayWithZeroSize() {
+ Assertions.assertArrayEquals(new int[0],
SeedFactory.createIntArray(0));
+ }
+
@Test
void testCreateIntArrayWithCompleteBlockSize() {
// Block size is 8 for int
@@ -144,6 +155,11 @@ class SeedFactoryTest {
assertMonobit(bitCount, numberOfBits);
}
+ @Test
+ void testCreateLongArrayWithZeroSize() {
+ Assertions.assertArrayEquals(new long[0],
SeedFactory.createLongArray(0));
+ }
+
@Test
void testCreateLongArrayWithCompleteBlockSize() {
// Block size is 4 for long
@@ -243,12 +259,12 @@ class SeedFactoryTest {
}
};
- final byte[] seed = SeedFactory.createByteArray(rng, expected.length);
+ final byte[] seed = SeedFactory.createByteArray(rng, expected.length,
0, expected.length);
Assertions.assertArrayEquals(expected, seed);
}
@Test
- void testCreateByteArrayWithAllZeroBytesUpdatesPosition0() {
+ void testCreateByteArrayWithAllZeroBytesUpdatesFromTo() {
final UniformRandomProvider rng = new IntProvider() {
@Override
public int next() {
@@ -256,75 +272,254 @@ class SeedFactoryTest {
return 0;
}
};
- // Test the method only replaces position 0
- final byte[] seed = SeedFactory.createByteArray(rng, 4);
- Assertions.assertNotEquals(0, seed[0], "Zero at position 0 should be
modified");
- for (int i = 1; i < seed.length; i++) {
- Assertions.assertEquals(0, seed[i], "Position above 0 should be
unmodified");
+ // Test the method only replaces the target sub-range.
+ // Test all sub-ranges.
+ final int size = 4;
+ for (int start = 0; start < size; start++) {
+ final int from = start;
+ for (int end = start; end < size; end++) {
+ final int to = end;
+ final byte[] seed = SeedFactory.createByteArray(rng, 4, from,
to);
+
+ // Validate
+ for (int i = 0; i < from; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ if (to > from) {
+ byte allBits = 0;
+ for (int i = from; i < to; i++) {
+ allBits |= seed[i];
+ }
+ Assertions.assertNotEquals(0, allBits,
+ () -> String.format("[%d, %d) should not be all zero",
from, to));
+ }
+ for (int i = to; i < size; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ }
}
}
@Test
void testEnsureNonZeroIntArrayIgnoresEmptySeed() {
final int[] seed = new int[0];
- SeedFactory.ensureNonZero(seed);
+ SeedFactory.ensureNonZero(seed, 0, 0);
// Note: Nothing to assert.
// This tests an ArrayIndexOutOfBoundsException does not occur.
}
- @Test
- void testEnsureNonZeroIntArrayIgnoresNonZeroPosition0() {
- final int position0 = 123;
- final int[] seed = new int[] {position0, 0, 0, 0};
- final int[] before = seed.clone();
- SeedFactory.ensureNonZero(seed);
- Assertions.assertEquals(position0, seed[0], "Non-zero at position 0
should be unmodified");
- for (int i = 1; i < seed.length; i++) {
- Assertions.assertEquals(before[i], seed[i], "Position above 0
should be unmodified");
- }
+ @ParameterizedTest
+ @CsvSource({
+ "0, 0, 1",
+ "1, -1, 1",
+ "1, 0, 2",
+ "1, 1, 2",
+ })
+ void testEnsureNonZeroIntArrayThrowsWithInvalidRange(int n, int from, int
to) {
+ final int[] seed = new int[n];
+ Assertions.assertThrows(IndexOutOfBoundsException.class,
+ () -> SeedFactory.ensureNonZero(seed, from, to));
}
+
@Test
- void testEnsureNonZeroIntArrayUpdatesZeroPosition0() {
- // Test the method replaces position 0 even if the rest of the array
is non-zero
- final int[] seed = new int[] {0, 123, 456, 789};
- final int[] before = seed.clone();
- SeedFactory.ensureNonZero(seed);
- Assertions.assertNotEquals(0, seed[0], "Zero at position 0 should be
modified");
- for (int i = 1; i < seed.length; i++) {
- Assertions.assertEquals(before[i], seed[i], "Position above 0
should be unmodified");
+ void testEnsureNonZeroIntArrayWithAllZeroBytesUpdatesFromTo() {
+ // Test the method only replaces the target sub-range.
+ // Test all sub-ranges.
+ final int size = 4;
+ final int[] seed = new int[size];
+ for (int start = 0; start < size; start++) {
+ final int from = start;
+ for (int end = start; end < size; end++) {
+ final int to = end;
+ Arrays.fill(seed, 0);
+ SeedFactory.ensureNonZero(seed, from, to);
+
+ // Validate
+ for (int i = 0; i < from; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ if (to > from) {
+ int allBits = 0;
+ for (int i = from; i < to; i++) {
+ allBits |= seed[i];
+ }
+ Assertions.assertNotEquals(0, allBits,
+ () -> String.format("[%d, %d) should not be all zero",
from, to));
+ }
+ for (int i = to; i < size; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ }
}
}
@Test
void testEnsureNonZeroLongArrayIgnoresEmptySeed() {
final long[] seed = new long[0];
- SeedFactory.ensureNonZero(seed);
+ SeedFactory.ensureNonZero(seed, 0, 0);
// Note: Nothing to assert.
// This tests an ArrayIndexOutOfBoundsException does not occur.
}
+ @ParameterizedTest
+ @CsvSource({
+ "0, 0, 1",
+ "1, -1, 1",
+ "1, 0, 2",
+ "1, 1, 2",
+ })
+ void testEnsureNonZeroLongArrayThrowsWithInvalidRange(int n, int from, int
to) {
+ final long[] seed = new long[n];
+ Assertions.assertThrows(IndexOutOfBoundsException.class,
+ () -> SeedFactory.ensureNonZero(seed, from, to));
+ }
+
+
@Test
- void testEnsureNonZeroLongArrayIgnoresNonZeroPosition0() {
- final long position0 = 123;
- final long[] seed = new long[] {position0, 0, 0, 0};
- final long[] before = seed.clone();
- SeedFactory.ensureNonZero(seed);
- Assertions.assertEquals(position0, seed[0], "Non-zero at position 0
should be unmodified");
- for (int i = 1; i < seed.length; i++) {
- Assertions.assertEquals(before[i], seed[i], "Position above 0
should be unmodified");
+ void testEnsureNonZeroLongArrayWithAllZeroBytesUpdatesFromTo() {
+ // Test the method only replaces the target sub-range.
+ // Test all sub-ranges.
+ final int size = 4;
+ final long[] seed = new long[size];
+ for (int start = 0; start < size; start++) {
+ final int from = start;
+ for (int end = start; end < size; end++) {
+ final int to = end;
+ Arrays.fill(seed, 0);
+ SeedFactory.ensureNonZero(seed, from, to);
+
+ // Validate
+ for (int i = 0; i < from; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ if (to > from) {
+ long allBits = 0;
+ for (int i = from; i < to; i++) {
+ allBits |= seed[i];
+ }
+ Assertions.assertNotEquals(0, allBits,
+ () -> String.format("[%d, %d) should not be all zero",
from, to));
+ }
+ for (int i = to; i < size; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ }
}
}
@Test
- void testEnsureNonZeroLongArrayUpdatesZeroPosition0() {
- // Test the method replaces position 0 even if the rest of the array
is non-zero
- final long[] seed = new long[] {0, 123, 456, 789};
- final long[] before = seed.clone();
- SeedFactory.ensureNonZero(seed);
- Assertions.assertNotEquals(0, seed[0], "Zero at position 0 should be
modified");
- for (int i = 1; i < seed.length; i++) {
- Assertions.assertEquals(before[i], seed[i], "Position above 0
should be unmodified");
+ void testEnsureNonZeroByteArrayIgnoresEmptySeed() {
+ final byte[] seed = new byte[0];
+ final UniformRandomProvider rng = new SplitMix64(123);
+ SeedFactory.ensureNonZero(seed, 0, 0, rng);
+ // Note: Nothing to assert.
+ // This tests an ArrayIndexOutOfBoundsException does not occur.
+ }
+
+ @ParameterizedTest
+ @CsvSource({
+ "0, 0, 1",
+ "1, -1, 1",
+ "1, 0, 2",
+ "1, 1, 2",
+ })
+ void testEnsureNonZeroByteArrayThrowsWithInvalidRange(int n, int from, int
to) {
+ final byte[] seed = new byte[n];
+ final UniformRandomProvider rng = new SplitMix64(123);
+ Assertions.assertThrows(IndexOutOfBoundsException.class,
+ () -> SeedFactory.ensureNonZero(seed, from, to, rng));
+ }
+
+ /**
+ * Test the fixed values returned for the zero byte array source of
randomness
+ * have specific properties.
+ */
+ @Test
+ void testZeroByteArraySourceOfRandomness() {
+ Assertions.assertEquals(0,
MixFunctions.stafford13(-MixFunctions.GOLDEN_RATIO_64 +
MixFunctions.GOLDEN_RATIO_64));
+ Assertions.assertEquals(0,
MixFunctions.stafford13((1463436497261722119L << 1) +
MixFunctions.GOLDEN_RATIO_64) & (-1L >>> 56));
+ Assertions.assertEquals(0,
MixFunctions.stafford13((4949471497809997598L << 1) +
MixFunctions.GOLDEN_RATIO_64) & (-1L >>> 48));
+ // Note:
+ // Finding a value x where MixFunctions.stafford13((x << 1) +
MixFunctions.GOLDEN_RATIO_64)
+ // is zero for the least significant 7 bytes used inversion of the mix
function.
+ // See the MixFunctionsTest for a routine to perform the unmixing.
+ Assertions.assertEquals(0,
MixFunctions.stafford13((953042962641938212L << 1) +
MixFunctions.GOLDEN_RATIO_64) & (-1L >>> 8));
+ }
+
+ @ParameterizedTest
+ @ValueSource(longs = {0, -MixFunctions.GOLDEN_RATIO_64,
1463436497261722119L, 4949471497809997598L, 953042962641938212L})
+ void testEnsureNonZeroByteArrayWithAllZeroBytesUpdatesFromTo(long next) {
+ // Use a fixed source of randomness to demonstrate the method is
robust.
+ // This should only be used when the sub-range is non-zero length.
+ int[] calls = {0};
+ final UniformRandomProvider rng = new LongProvider() {
+ @Override
+ public long next() {
+ calls[0]++;
+ return next;
+ }
+ };
+
+ // Test the method only replaces the target sub-range.
+ // Test all sub-ranges up to size.
+ final int size = 2 * Long.BYTES;
+ final byte[] seed = new byte[size];
+ for (int start = 0; start < size; start++) {
+ final int from = start;
+ for (int end = start; end < size; end++) {
+ final int to = end;
+ Arrays.fill(seed, (byte) 0);
+ final int before = calls[0];
+ SeedFactory.ensureNonZero(seed, from, to, rng);
+
+ // Validate
+ for (int i = 0; i < from; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ if (to > from) {
+ byte allBits = 0;
+ for (int i = from; i < to; i++) {
+ allBits |= seed[i];
+ }
+ Assertions.assertNotEquals(0, allBits,
+ () -> String.format("[%d, %d) should not be all zero",
from, to));
+ // Check the source was used to seed the sequence
+ Assertions.assertNotEquals(before, calls[0],
+ () -> String.format("[%d, %d) should use the random
source", from, to));
+ } else {
+ // Check the source was not used
+ Assertions.assertEquals(before, calls[0],
+ () -> String.format("[%d, %d) should not use the
random source", from, to));
+ }
+ for (int i = to; i < size; i++) {
+ final int index = i;
+ Assertions.assertEquals(0, seed[i],
+ () -> String.format("[%d, %d) zero at position %d
should not be modified",
+ from, to, index));
+ }
+ }
}
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index f986aae4..3d4e6874 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -86,6 +86,12 @@ behavioural compatibility between releases; derived types
may break behavioural compatibility. Any functional changes
will be recorded in the release notes.
">
+ <action dev="aherbert" type="add" issue="174">
+ "RandomSource": Improve support for non-zero seeds. Seeding has been
changed to specify
+ a sub-range of the seed that must not be all zero. Introduces a
functional change where
+ byte[] seeds generated by RandomSource with a fixed
UniformRandomProvider may be different.
+ Seeds are now reproducible across calls using an input random source
in an identical state.
+ </action>
<action dev="aherbert" type="fix" issue="175">
"RandomSource.MSWS": createSeed(UniformRandomProvider) to handle a bad
RNG.
This fixes an infinite loop when the RNG output is not suitably random
to create a seed.
@@ -95,7 +101,7 @@ will be recorded in the release notes.
minimum length.
</action>
<action dev="aherbert" type="update" issue="171">
- Recuce the memory footprint of the cached boolean and int source for
the IntProvider
+ Reduce the memory footprint of the cached boolean and int source for
the IntProvider
and LongProvider. This change has a performance improvement on some
JDKs.
Note: This introduces a functional compatibility change to the output
from the
nextInt method of any LongProvider; the output is now little-endian as
diff --git a/src/main/resources/pmd/pmd-ruleset.xml
b/src/main/resources/pmd/pmd-ruleset.xml
index 95a23d12..697be610 100644
--- a/src/main/resources/pmd/pmd-ruleset.xml
+++ b/src/main/resources/pmd/pmd-ruleset.xml
@@ -116,7 +116,7 @@
value="//ClassOrInterfaceDeclaration[@SimpleName='ListSampler' or
@SimpleName='ProviderBuilder'
or @SimpleName='ThreadLocalRandomSource' or @SimpleName='SeedFactory'
or @SimpleName='Coordinates' or @SimpleName='Hex' or
@SimpleName='SpecialMath'
- or @SimpleName='Conversions']"/>
+ or @SimpleName='Conversions' or @SimpleName='MixFunctions']"/>
<!-- Allow samplers to have only factory constructors -->
<property name="utilityClassPattern"
value="[A-Z][a-zA-Z0-9]+(Utils?|Helper|Sampler)" />
</properties>
