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            seed[i] = MixFunctions.murmur3(x += MixFunctions.GOLDEN_RATIO_32);
294        }
295    }
296
297    /**
298     * Ensure the seed is not all-zero within the specified sub-range.
299     *
300     * <p>This method will check the sub-range and if all are zero it will fill the range
301     * with a random sequence seeded from the default source of random long values. The
302     * fill ensures position {@code from} has a non-zero value; and the entire sub-range
303     * has a maximum of one zero. The method ensures any length sub-range contains
304     * non-zero bits. The output seed is suitable for generators that cannot be seeded
305     * with all zeros in the specified sub-range.</p>
306     *
307     * @param seed Seed array (modified in place).
308     * @param from The start of the not all-zero sub-range (inclusive).
309     * @param to The end of the not all-zero sub-range (exclusive).
310     * @throws IndexOutOfBoundsException if the sub-range is invalid
311     * @see #createLong()
312     */
313    static void ensureNonZero(long[] seed, int from, int to) {
314        if (from >= to) {
315            return;
316        }
317        // No check on the range so an IndexOutOfBoundsException will occur if invalid
318        for (int i = from; i < to; i++) {
319            if (seed[i] != 0) {
320                return;
321            }
322        }
323        // Fill with non-zero values using a SplitMix-style PRNG.
324        // The range is at least 1.
325        // To ensure the first value is not zero requires the input to the mix function
326        // to be non-zero. This is ensured if the start is even since the increment is odd.
327        long x = createLong() << 1;
328        for (int i = from; i < to; i++) {
329            seed[i] = MixFunctions.stafford13(x += MixFunctions.GOLDEN_RATIO_64);
330        }
331    }
332
333    /**
334     * Ensure the seed is not all-zero within the specified sub-range.
335     *
336     * <p>This method will check the sub-range and if all are zero it will fill the range
337     * with a random sequence seeded from the provided source of randomness. If the range
338     * length is above 8 then the first 8 bytes in the range are ensured to not all be
339     * zero. If the range length is below 8 then the first byte in the range is ensured to
340     * be non-zero. The method ensures any length sub-range contains non-zero bits. The
341     * output seed is suitable for generators that cannot be seeded with all zeros in the
342     * specified sub-range.</p>
343     *
344     * @param seed Seed array (modified in place).
345     * @param from The start of the not all-zero sub-range (inclusive).
346     * @param to The end of the not all-zero sub-range (exclusive).
347     * @param source Source of randomness.
348     * @throws IndexOutOfBoundsException if the sub-range is invalid
349     */
350    static void ensureNonZero(byte[] seed, int from, int to, UniformRandomProvider source) {
351        if (from >= to) {
352            return;
353        }
354        // No check on the range so an IndexOutOfBoundsException will occur if invalid
355        for (int i = from; i < to; i++) {
356            if (seed[i] != 0) {
357                return;
358            }
359        }
360        // Defend against a faulty source of randomness (which supplied all zero bytes)
361        // by filling with non-zero values using a SplitMix-style PRNG seeded from the source.
362        // The range is at least 1.
363        // To ensure the first value is not zero requires the input to the mix function
364        // to be non-zero. This is ensured if the start is even since the increment is odd.
365        long x = source.nextLong() << 1;
366
367        // Process in blocks of 8.
368        // Get the length without the final 3 bits set for a multiple of 8.
369        final int len = (to - from) & ~0x7;
370        final int end = from + len;
371        int i = from;
372        while (i < end) {
373            long v = MixFunctions.stafford13(x += MixFunctions.GOLDEN_RATIO_64);
374            for (int j = 0; j < 8; j++) {
375                seed[i++] = (byte) v;
376                v >>>= 8;
377            }
378        }
379
380        if (i < to) {
381            // The final bytes.
382            long v = MixFunctions.stafford13(x + MixFunctions.GOLDEN_RATIO_64);
383            // Note the special case where no blocks have been processed requires these
384            // bytes to be non-zero, i.e. (to - from) < 8. In this case the value 'v' will
385            // be non-zero due to the initialisation of 'x' as even.
386            // Rotate the value so the least significant byte is non-zero. The rotation
387            // in bits is rounded down to the nearest 8-bit block to ensure a byte rotation.
388            if (len == 0) {
389                v = Long.rotateRight(v, Long.numberOfTrailingZeros(v) & ~0x7);
390            }
391            while (i < to) {
392                seed[i++] = (byte) v;
393                v >>>= 8;
394            }
395        }
396    }
397
398    /**
399     * Ensure the value is non-zero.
400     *
401     * <p>This method will replace a zero with a non-zero random number from the random source.</p>
402     *
403     * @param source Source of randomness.
404     * @param value Value.
405     * @return {@code value} if non-zero; else a new random number
406     */
407    static long ensureNonZero(RandomLongSource source,
408                              long value) {
409        long result = value;
410        while (result == 0) {
411            result = source.next();
412        }
413        return result;
414    }
415}