001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.rng.simple.internal;
018
019import java.security.SecureRandom;
020import java.util.concurrent.locks.ReentrantLock;
021
022import org.apache.commons.rng.core.util.NumberFactory;
023import org.apache.commons.rng.UniformRandomProvider;
024import org.apache.commons.rng.core.source64.RandomLongSource;
025import org.apache.commons.rng.core.source64.SplitMix64;
026import org.apache.commons.rng.core.source64.XoRoShiRo1024PlusPlus;
027
028/**
029 * Utilities related to seeding.
030 *
031 * <p>
032 * This class provides methods to generate random seeds (single values
033 * or arrays of values, of {@code int} or {@code long} types) that can
034 * be passed to the {@link org.apache.commons.rng.simple.RandomSource
035 * methods that create a generator instance}.
036 * <br>
037 * Although the seed-generating methods defined in this class will likely
038 * return different values for all calls, there is no guarantee that the
039 * produced seed will result always in a "good" sequence of numbers (even
040 * if the generator initialized with that seed is good).
041 * <br>
042 * There is <i>no guarantee</i> that sequences will not overlap.
043 * </p>
044 *
045 * @since 1.0
046 */
047public final class SeedFactory {
048    /** Size of the state array of "XoRoShiRo1024PlusPlus". */
049    private static final int XO_RO_SHI_RO_1024_STATE_SIZE = 16;
050    /** Size of block to fill in an {@code int[]} seed per synchronized operation. */
051    private static final int INT_ARRAY_BLOCK_SIZE = 8;
052    /** Size of block to fill in a {@code long[]} seed per synchronized operation. */
053    private static final int LONG_ARRAY_BLOCK_SIZE = 4;
054
055    /**
056     * The lock to own when using the seed generator. This lock is unfair and there is no
057     * particular access order for waiting threads.
058     *
059     * <p>This is used as an alternative to {@code synchronized} statements to guard access
060     * to the seed generator.</p>
061     */
062    private static final ReentrantLock LOCK = new ReentrantLock(false);
063
064    /** Generator with a long period. */
065    private static final UniformRandomProvider SEED_GENERATOR;
066
067    static {
068        // Use a secure RNG so that different instances (e.g. in multiple JVM
069        // instances started in rapid succession) will have different seeds.
070        final SecureRandom seedGen = new SecureRandom();
071        final byte[] bytes = new byte[8 * XO_RO_SHI_RO_1024_STATE_SIZE];
072        seedGen.nextBytes(bytes);
073        final long[] seed = NumberFactory.makeLongArray(bytes);
074        // The XoRoShiRo1024PlusPlus generator cannot recover from an all zero seed and
075        // will produce low quality initial output if initialized with some zeros.
076        // Ensure it is non zero at all array positions using a SplitMix64
077        // generator (this is insensitive to a zero seed so can use the first seed value).
078        final SplitMix64 rng = new SplitMix64(seed[0]);
079        for (int i = 0; i < seed.length; i++) {
080            seed[i] = ensureNonZero(rng, seed[i]);
081        }
082
083        SEED_GENERATOR = new XoRoShiRo1024PlusPlus(seed);
084    }
085
086    /**
087     * Class contains only static methods.
088     */
089    private SeedFactory() {}
090
091    /**
092     * Creates an {@code int} number for use as a seed.
093     *
094     * @return a random number.
095     */
096    public static int createInt() {
097        LOCK.lock();
098        try {
099            return SEED_GENERATOR.nextInt();
100        } finally {
101            LOCK.unlock();
102        }
103    }
104
105    /**
106     * Creates a {@code long} number for use as a seed.
107     *
108     * @return a random number.
109     */
110    public static long createLong() {
111        LOCK.lock();
112        try {
113            return SEED_GENERATOR.nextLong();
114        } finally {
115            LOCK.unlock();
116        }
117    }
118
119    /**
120     * Creates an array of {@code int} numbers for use as a seed.
121     *
122     * @param n Size of the array to create.
123     * @return an array of {@code n} random numbers.
124     */
125    public static int[] createIntArray(int n) {
126        // Behaviour from v1.3 is to ensure the first position is non-zero
127        return createIntArray(n, 0, Math.min(n, 1));
128    }
129
130    /**
131     * Creates an array of {@code int} numbers for use as a seed.
132     * Optionally ensure a sub-range of the array is not all-zero.
133     *
134     * <p>This method is package-private for use by {@link NativeSeedType}.
135     *
136     * @param n Size of the array to create.
137     * @param from The start of the not all-zero sub-range (inclusive).
138     * @param to The end of the not all-zero sub-range (exclusive).
139     * @return an array of {@code n} random numbers.
140     * @throws IndexOutOfBoundsException if the sub-range is invalid
141     * @since 1.5
142     */
143    static int[] createIntArray(int n, int from, int to) {
144        final int[] seed = new int[n];
145        // Compute the size that can be filled with complete blocks
146        final int blockSize = INT_ARRAY_BLOCK_SIZE * (n / INT_ARRAY_BLOCK_SIZE);
147        int i = 0;
148        while (i < blockSize) {
149            final int end = i + INT_ARRAY_BLOCK_SIZE;
150            fillIntArray(seed, i, end);
151            i = end;
152        }
153        // Final fill only if required
154        if (i != n) {
155            fillIntArray(seed, i, n);
156        }
157        ensureNonZero(seed, from, to);
158        return seed;
159    }
160
161    /**
162     * Creates an array of {@code long} numbers for use as a seed.
163     *
164     * @param n Size of the array to create.
165     * @return an array of {@code n} random numbers.
166     */
167    public static long[] createLongArray(int n) {
168        // Behaviour from v1.3 is to ensure the first position is non-zero
169        return createLongArray(n, 0, Math.min(n, 1));
170    }
171
172    /**
173     * Creates an array of {@code long} numbers for use as a seed.
174     * Optionally ensure a sub-range of the array is not all-zero.
175     *
176     * <p>This method is package-private for use by {@link NativeSeedType}.
177     *
178     * @param n Size of the array to create.
179     * @param from The start of the not all-zero sub-range (inclusive).
180     * @param to The end of the not all-zero sub-range (exclusive).
181     * @return an array of {@code n} random numbers.
182     * @throws IndexOutOfBoundsException if the sub-range is invalid
183     * @since 1.5
184     */
185    static long[] createLongArray(int n, int from, int to) {
186        final long[] seed = new long[n];
187        // Compute the size that can be filled with complete blocks
188        final int blockSize = LONG_ARRAY_BLOCK_SIZE * (n / LONG_ARRAY_BLOCK_SIZE);
189        int i = 0;
190        while (i < blockSize) {
191            final int end = i + LONG_ARRAY_BLOCK_SIZE;
192            fillLongArray(seed, i, end);
193            i = end;
194        }
195        // Final fill only if required
196        if (i != n) {
197            fillLongArray(seed, i, n);
198        }
199        ensureNonZero(seed, from, to);
200        return seed;
201    }
202
203    /**
204     * Fill the array between {@code start} inclusive and {@code end} exclusive from the
205     * seed generator. The lock is used to guard access to the generator.
206     *
207     * @param array Array data.
208     * @param start Start (inclusive).
209     * @param end End (exclusive).
210     */
211    private static void fillIntArray(int[] array, int start, int end) {
212        LOCK.lock();
213        try {
214            for (int i = start; i < end; i++) {
215                array[i] = SEED_GENERATOR.nextInt();
216            }
217        } finally {
218            LOCK.unlock();
219        }
220    }
221
222    /**
223     * Fill the array between {@code start} inclusive and {@code end} exclusive from the
224     * seed generator. The lock is used to guard access to the generator.
225     *
226     * @param array Array data.
227     * @param start Start (inclusive).
228     * @param end End (exclusive).
229     */
230    private static void fillLongArray(long[] array, int start, int end) {
231        LOCK.lock();
232        try {
233            for (int i = start; i < end; i++) {
234                array[i] = SEED_GENERATOR.nextLong();
235            }
236        } finally {
237            LOCK.unlock();
238        }
239    }
240
241    /**
242     * Creates an array of {@code byte} numbers for use as a seed using the supplied source of
243     * randomness. A sub-range can be specified that must not contain all zeros.
244     *
245     * @param source Source of randomness.
246     * @param n Size of the array to create.
247     * @param from The start of the not all-zero sub-range (inclusive).
248     * @param to The end of the not all-zero sub-range (exclusive).
249     * @return an array of {@code n} random numbers.
250     */
251    static byte[] createByteArray(UniformRandomProvider source,
252                                  int n,
253                                  int from,
254                                  int to) {
255        final byte[] seed = new byte[n];
256        source.nextBytes(seed);
257        ensureNonZero(seed, from, to, source);
258        return seed;
259    }
260
261    /**
262     * Ensure the seed is not all-zero within the specified sub-range.
263     *
264     * <p>This method will check the sub-range and if all are zero it will fill the range
265     * with a random sequence seeded from the default source of random int values. The
266     * fill ensures position {@code from} has a non-zero value; and the entire sub-range
267     * has a maximum of one zero. The method ensures any length sub-range contains
268     * non-zero bits. The output seed is suitable for generators that cannot be seeded
269     * with all zeros in the specified sub-range.</p>
270     *
271     * @param seed Seed array (modified in place).
272     * @param from The start of the not all-zero sub-range (inclusive).
273     * @param to The end of the not all-zero sub-range (exclusive).
274     * @throws IndexOutOfBoundsException if the sub-range is invalid
275     * @see #createInt()
276     */
277    static void ensureNonZero(int[] seed, int from, int to) {
278        if (from >= to) {
279            return;
280        }
281        // No check on the range so an IndexOutOfBoundsException will occur if invalid
282        for (int i = from; i < to; i++) {
283            if (seed[i] != 0) {
284                return;
285            }
286        }
287        // Fill with non-zero values using a SplitMix-style PRNG.
288        // The range is at least 1.
289        // To ensure the first value is not zero requires the input to the mix function
290        // to be non-zero. This is ensured if the start is even since the increment is odd.
291        int x = createInt() << 1;
292        for (int i = from; i < to; i++) {
293            x += MixFunctions.GOLDEN_RATIO_32;
294            seed[i] = MixFunctions.murmur3(x);
295        }
296    }
297
298    /**
299     * Ensure the seed is not all-zero within the specified sub-range.
300     *
301     * <p>This method will check the sub-range and if all are zero it will fill the range
302     * with a random sequence seeded from the default source of random long values. The
303     * fill ensures position {@code from} has a non-zero value; and the entire sub-range
304     * has a maximum of one zero. The method ensures any length sub-range contains
305     * non-zero bits. The output seed is suitable for generators that cannot be seeded
306     * with all zeros in the specified sub-range.</p>
307     *
308     * @param seed Seed array (modified in place).
309     * @param from The start of the not all-zero sub-range (inclusive).
310     * @param to The end of the not all-zero sub-range (exclusive).
311     * @throws IndexOutOfBoundsException if the sub-range is invalid
312     * @see #createLong()
313     */
314    static void ensureNonZero(long[] seed, int from, int to) {
315        if (from >= to) {
316            return;
317        }
318        // No check on the range so an IndexOutOfBoundsException will occur if invalid
319        for (int i = from; i < to; i++) {
320            if (seed[i] != 0) {
321                return;
322            }
323        }
324        // Fill with non-zero values using a SplitMix-style PRNG.
325        // The range is at least 1.
326        // To ensure the first value is not zero requires the input to the mix function
327        // to be non-zero. This is ensured if the start is even since the increment is odd.
328        long x = createLong() << 1;
329        for (int i = from; i < to; i++) {
330            x += MixFunctions.GOLDEN_RATIO_64;
331            seed[i] = MixFunctions.stafford13(x);
332        }
333    }
334
335    /**
336     * Ensure the seed is not all-zero within the specified sub-range.
337     *
338     * <p>This method will check the sub-range and if all are zero it will fill the range
339     * with a random sequence seeded from the provided source of randomness. If the range
340     * length is above 8 then the first 8 bytes in the range are ensured to not all be
341     * zero. If the range length is below 8 then the first byte in the range is ensured to
342     * be non-zero. The method ensures any length sub-range contains non-zero bits. The
343     * output seed is suitable for generators that cannot be seeded with all zeros in the
344     * specified sub-range.</p>
345     *
346     * @param seed Seed array (modified in place).
347     * @param from The start of the not all-zero sub-range (inclusive).
348     * @param to The end of the not all-zero sub-range (exclusive).
349     * @param source Source of randomness.
350     * @throws IndexOutOfBoundsException if the sub-range is invalid
351     */
352    static void ensureNonZero(byte[] seed, int from, int to, UniformRandomProvider source) {
353        if (from >= to) {
354            return;
355        }
356        // No check on the range so an IndexOutOfBoundsException will occur if invalid
357        for (int i = from; i < to; i++) {
358            if (seed[i] != 0) {
359                return;
360            }
361        }
362        // Defend against a faulty source of randomness (which supplied all zero bytes)
363        // by filling with non-zero values using a SplitMix-style PRNG seeded from the source.
364        // The range is at least 1.
365        // To ensure the first value is not zero requires the input to the mix function
366        // to be non-zero. This is ensured if the start is even since the increment is odd.
367        long x = source.nextLong() << 1;
368
369        // Process in blocks of 8.
370        // Get the length without the final 3 bits set for a multiple of 8.
371        final int len = (to - from) & ~0x7;
372        final int end = from + len;
373        int i = from;
374        while (i < end) {
375            long v = MixFunctions.stafford13(x += MixFunctions.GOLDEN_RATIO_64);
376            for (int j = 0; j < 8; j++) {
377                seed[i++] = (byte) v;
378                v >>>= 8;
379            }
380        }
381
382        if (i < to) {
383            // The final bytes.
384            long v = MixFunctions.stafford13(x + MixFunctions.GOLDEN_RATIO_64);
385            // Note the special case where no blocks have been processed requires these
386            // bytes to be non-zero, i.e. (to - from) < 8. In this case the value 'v' will
387            // be non-zero due to the initialisation of 'x' as even.
388            // Rotate the value so the least significant byte is non-zero. The rotation
389            // in bits is rounded down to the nearest 8-bit block to ensure a byte rotation.
390            if (len == 0) {
391                v = Long.rotateRight(v, Long.numberOfTrailingZeros(v) & ~0x7);
392            }
393            while (i < to) {
394                seed[i++] = (byte) v;
395                v >>>= 8;
396            }
397        }
398    }
399
400    /**
401     * Ensure the value is non-zero.
402     *
403     * <p>This method will replace a zero with a non-zero random number from the random source.</p>
404     *
405     * @param source Source of randomness.
406     * @param value Value.
407     * @return {@code value} if non-zero; else a new random number
408     */
409    static long ensureNonZero(RandomLongSource source,
410                              long value) {
411        long result = value;
412        while (result == 0) {
413            result = source.next();
414        }
415        return result;
416    }
417}