Trivial Description
The seeding routine for the Middle Square Weyl Sequence (MSWS) generator is a custom routine that generates a hex permutation for part of the seed. This requires a source of randomness.
The following public API method provides an input source of randomness to generate a byte[] seed:
public byte[] createSeed(UniformRandomProvider rng);
The method used by the MSWS routine will directly use the input UniformRandomProvider. If this is non functional then the routine will infinite loop. This test fails:
@Test
void testMSWSCreateSeed() {
final UniformRandomProvider broken = new LongProvider() {
@Override
public long next() {
return 0;
}
};
Assertions.assertTimeoutPreemptively(Duration.ofMillis(100), () -> {
RandomSource.MSWS.createSeed(broken);
});
}
This occurs as the seed generation uses an unbiased random permutation that uses the nextInt() method from the UniformRandomProvider to implement a custom shuffle routine. If the values from nextInt() generate rejections then another value is obtained. This will infinite loop if the values are always rejected.
Note
This issue was discovered when implementing RNG-174 which improves support for non-zero seeds. All RandomSource entries should allow construction of seeds with a source RNG that will may generate an all zero seed. To force generation of an all zero seed for testing is most easily done using a broken input RNG as above to the seeding routine.
Possible solutions
- Fix the routine to be robust to a broken input RNG
- Mark as won't fix. The use of a broken input RNG is an edge case. Any broken input RNG is incorrect usage of the API. If you do not provide a good source of randomness to create a seed then the seed routine will fail to create a suitable seed.
- Fix the infinite loop by raising an exception inside the seed generation routine after a set number of int values have been used.
I prefer option 1 as it satisfies the functionality to generate a seed, no matter how bad the source of randomness. Option 2 has the potential to infinite loop which should be avoided. Option3 will tell a user they have a bad RNG, but it will raise errors which may be unexpected.
The bug can be fixed by switching the source of randomness when the input source has proven to be invalid.
A small test provides a count of the mean, min, and max number of calls to nextInt(). This is 10 repeats of 2^20 calls to generate the hex permutation.
4.217280387878418 4 6 4.217123985290527 4 6 4.216763496398926 4 6 4.217494010925293 4 6 4.217161178588867 4 6 4.21730899810791 4 6 4.217828750610352 4 6 4.216683387756348 4 6 4.21721076965332 4 6 4.216983795166016 4 6
A suitable generator should have at least 32*4 bits of state and ideally be equidistributed over 6 ints. There are suitable generators in the library to provide this functionality. However in the correct usage the input generator will not be broken and ideally should be used directly. A solution would be to wrap the input generator and switch to a default implementation when the provided generator proves to be faulty:
@Override protected byte[] createByteArraySeed(UniformRandomProvider source) { // The seed requires approximately 4-6 calls to nextInt(). // Wrap the input and switch to a default if the input is faulty. final UniformRandomProvider wrapped = new IntProvider() { private int calls; private UniformRandomProvider backup; @Override public int next() { if (calls++ < 100) { return source.nextInt(); } // The input source is broken. if (backup == null) { backup = new SplitMix64(source.nextLong()); } return backup.nextInt(); } @Override public long nextLong() { // No specific requirements so always use the source return source.nextLong(); } }; return NativeSeedType.convertSeedToBytes(createMswsSeed(wrapped)); }
This solution should provide backward compatibility if the input RNG is functional. The routine will create the same seed bytes as previous versions of the library with a good RNG. Exceeding 100 calls to nextInt(int) is extremely unlikely if the output is a good random source. Switching to a default generator seeded from the input ensures the method will produce the same seed with repeat calls of the same generator (initialised at the same state).
Here a SplitMix64 is used. This is robust to any input seed. It is only 2 equidistributed for int output. Use of a 4-equidistributed generator (in long output) such as XoShiRo256PlusPlus is possible (this is 8-equidistributed for int output). However this is not robust to any seed as it cannot accept all zeros. If the input source RNG is broken then the seeding of the back-up RNG should be robust and the 4-equidistributed requirement has already been broken by the faulty input RNG.