1 /*

     2  * Copyright (c) 2013, 2019, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package java.util.random;

    27 

    28 import java.math.BigInteger;

    29 import java.util.concurrent.atomic.AtomicLong;

    30 import java.util.random.RandomGenerator.LeapableGenerator;

    31 

    32 /**

    33  * A generator of uniform pseudorandom values applicable for use in

    34  * (among other contexts) isolated parallel computations that may

    35  * generate subtasks.  Class {@link Xoshiro256StarStar} implements

    36  * interfaces {@link RandomGenerator} and {@link LeapableGenerator},

    37  * and therefore supports methods for producing pseudorandomly chosen

    38  * numbers of type {@code int}, {@code long}, {@code float}, and {@code double}

    39  * as well as creating new {@link Xoshiro256StarStar} objects

    40  * by "jumping" or "leaping".

    41  * <p>

    42  * Series of generated values pass the TestU01 BigCrush and PractRand test suites

    43  * that measure independence and uniformity properties of random number generators.

    44  * (Most recently validated with

    45  * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a>

    46  * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>.

    47  * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()}

    48  * method but also the result of bit-reversing each value produced by {@code nextLong()}.)

    49  * These tests validate only the methods for certain

    50  * types and ranges, but similar properties are expected to hold, at

    51  * least approximately, for others as well.

    52  * <p>

    53  * The class {@link Xoshiro256StarStar} uses the {@code xoshiro256} algorithm,

    54  * version 1.0 (parameters 17, 45), with the "**" scrambler (a mixing function).

    55  * Its state consists of four {@code long} fields {@code x0}, {@code x1}, {@code x2},

    56  * and {@code x3}, which can take on any values provided that they are not all zero.

    57  * The period of this generator is 2<sup>256</sup>-1.

    58  * <p>

    59  * The 64-bit values produced by the {@code nextLong()} method are equidistributed.

    60  * To be precise, over the course of the cycle of length 2<sup>256</sup>-1,

    61  * each nonzero {@code long} value is generated 2<sup>192</sup> times,

    62  * but the value 0 is generated only 2<sup>192</sup>-1 times.

    63  * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}

    64  * methods are likewise equidistributed.

    65  * <p>

    66  * In fact, the 64-bit values produced by the {@code nextLong()} method are 4-equidistributed.

    67  * To be precise: consider the (overlapping) length-4 subsequences of the cycle of 64-bit

    68  * values produced by {@code nextLong()} (assuming no other methods are called that would

    69  * affect the state).  There are 2<sup>256</sup>-1 such subsequences, and each subsequence,

    70  * which consists of 4 64-bit values, can have one of 2<sup>256</sup> values.  Of those

    71  * 2<sup>256</sup> subsequence values, each one is generated exactly once over the course

    72  * of the entire cycle, except that the subsequence (0, 0, 0, 0) never appears.

    73  * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()}

    74  * methods are likewise 4-equidistributed, but note that that the subsequence (0, 0, 0, 0)

    75  * can also appear (but occurring somewhat less frequently than all other subsequences),

    76  * because the values produced by those methods have fewer than 64 randomly chosen bits.

    77  * <p>

    78  * Instances {@link Xoshiro256StarStar} are <em>not</em> thread-safe.

    79  * They are designed to be used so that each thread as its own instance.

    80  * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps}

    81  * can be used to construct new instances of {@link Xoshiro256StarStar} that traverse

    82  * other parts of the state cycle.

    83  * <p>

    84  * Instances of {@link Xoshiro256StarStar} are not cryptographically

    85  * secure.  Consider instead using {@link java.security.SecureRandom}

    86  * in security-sensitive applications. Additionally,

    87  * default-constructed instances do not use a cryptographically random

    88  * seed unless the {@linkplain System#getProperty system property}

    89  * {@code java.util.secureRandomSeed} is set to {@code true}.

    90  *

    91  * @since 14

    92  */

    93 public final class Xoshiro256StarStar implements LeapableGenerator {

    94 

    95     /*

    96      * Implementation Overview.

    97      *

    98      * This is an implementation of the xoroshiro128** algorithm written

    99      * in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org).

   100      * See http://xoshiro.di.unimi.it and these two papers:

   101      *

   102      *    Sebastiano Vigna. 2016. An Experimental Exploration of Marsaglia's

   103      *    xorshift Generators, Scrambled. ACM Transactions on Mathematical

   104      *    Software 42, 4, Article 30 (June 2016), 23 pages.

   105      *    https://doi.org/10.1145/2845077

   106      *

   107      *    David Blackman and Sebastiano Vigna.  2018.  Scrambled Linear

   108      *    Pseudorandom Number Generators.  Computing Research Repository (CoRR).

   109      *    http://arxiv.org/abs/1805.01407

   110      *

   111      * The jump operation moves the current generator forward by 2*128

   112      * steps; this has the same effect as calling nextLong() 2**128

   113      * times, but is much faster.  Similarly, the leap operation moves

   114      * the current generator forward by 2*192 steps; this has the same

   115      * effect as calling nextLong() 2**192 times, but is much faster.

   116      * The copy method may be used to make a copy of the current

   117      * generator.  Thus one may repeatedly and cumulatively copy and

   118      * jump to produce a sequence of generators whose states are well

   119      * spaced apart along the overall state cycle (indeed, the jumps()

   120      * and leaps() methods each produce a stream of such generators).

   121      * The generators can then be parceled out to other threads.

   122      *

   123      * File organization: First static fields, then instance

   124      * fields, then constructors, then instance methods.

   125      */

   126 

   127     /* ---------------- static fields ---------------- */

   128 

   129     /**

   130      * The seed generator for default constructors.

   131      */

   132     private static final AtomicLong DEFAULT_GEN = new AtomicLong(RandomSupport.initialSeed());

   133 

   134     /*

   135      * The period of this generator, which is 2**256 - 1.

   136      */

   137     private static final BigInteger PERIOD =

   138         BigInteger.ONE.shiftLeft(256).subtract(BigInteger.ONE);

   139 

   140     /* ---------------- instance fields ---------------- */

   141 

   142     /**

   143      * The per-instance state.

   144      * At least one of the four fields x0, x1, x2, and x3 must be nonzero.

   145      */

   146     private long x0, x1, x2, x3;

   147 

   148     /* ---------------- constructors ---------------- */

   149 

   150     /**

   151      * Basic constructor that initializes all fields from parameters.

   152      * It then adjusts the field values if necessary to ensure that

   153      * all constraints on the values of fields are met.

   154      *

   155      * @param x0 first word of the initial state

   156      * @param x1 second word of the initial state

   157      * @param x2 third word of the initial state

   158      * @param x3 fourth word of the initial state

   159      */

   160     public Xoshiro256StarStar(long x0, long x1, long x2, long x3) {

   161         this.x0 = x0;

   162         this.x1 = x1;

   163         this.x2 = x2;

   164         this.x3 = x3;

   165         // If x0, x1, x2, and x3 are all zero, we must choose nonzero values.

   166         if ((x0 | x1 | x2 | x3) == 0) {

   167             // At least three of the four values generated here will be nonzero.

   168             this.x0 = RandomSupport.mixStafford13(x0 += RandomSupport.GOLDEN_RATIO_64);

   169             this.x1 = (x0 += RandomSupport.GOLDEN_RATIO_64);

   170             this.x2 = (x0 += RandomSupport.GOLDEN_RATIO_64);

   171             this.x3 = (x0 += RandomSupport.GOLDEN_RATIO_64);

   172         }

   173     }

   174 

   175     /**

   176      * Creates a new instance of {@link Xoshiro256StarStar} using the

   177      * specified {@code long} value as the initial seed. Instances of

   178      * {@link Xoshiro256StarStar} created with the same seed in the same

   179      * program generate identical sequences of values.

   180      *

   181      * @param seed the initial seed

   182      */

   183     public Xoshiro256StarStar(long seed) {

   184         // Using a value with irregularly spaced 1-bits to xor the seed

   185         // argument tends to improve "pedestrian" seeds such as 0 or

   186         // other small integers.  We may as well use SILVER_RATIO_64.

   187         //

   188         // The x values are then filled in as if by a SplitMix PRNG with

   189         // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer.

   190         this(RandomSupport.mixStafford13(seed ^= RandomSupport.SILVER_RATIO_64),

   191              RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),

   192              RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64),

   193              RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64));

   194     }

   195 

   196     /**

   197      * Creates a new instance of {@link Xoshiro256StarStar} that is likely to

   198      * generate sequences of values that are statistically independent

   199      * of those of any other instances in the current program execution,

   200      * but may, and typically does, vary across program invocations.

   201      */

   202     public Xoshiro256StarStar() {

   203         // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values.

   204         this(DEFAULT_GEN.getAndAdd(RandomSupport.GOLDEN_RATIO_64));

   205     }

   206 

   207     /**

   208      * Creates a new instance of {@link Xoshiro256StarStar} using the specified array of

   209      * initial seed bytes. Instances of {@link Xoshiro256StarStar} created with the same

   210      * seed array in the same program execution generate identical sequences of values.

   211      *

   212      * @param seed the initial seed

   213      */

   214     public Xoshiro256StarStar(byte[] seed) {

   215         // Convert the seed to 4 long values, which are not all zero.

   216         long[] data = RandomSupport.convertSeedBytesToLongs(seed, 4, 4);

   217         long x0 = data[0], x1 = data[1], x2 = data[2], x3 = data[3];

   218         this.x0 = x0;

   219         this.x1 = x1;

   220         this.x2 = x2;

   221         this.x3 = x3;

   222     }

   223 

   224     /* ---------------- public methods ---------------- */

   225 

   226     public Xoshiro256StarStar copy() {

   227         return new Xoshiro256StarStar(x0, x1, x2, x3);

   228     }

   229 

   230     /**

   231      * Returns a pseudorandom {@code long} value.

   232      *

   233      * @return a pseudorandom {@code long} value

   234      */

   235    public long nextLong() {

   236        // Compute the result based on current state information

   237        // (this allows the computation to be overlapped with state update).

   238        final long result = Long.rotateLeft(x0 * 5, 7) * 9;  // "starstar" mixing function

   239        

   240        long q0 = x0, q1 = x1, q2 = x2, q3 = x3;

   241        {   // xoshiro256 1.0

   242            long t = q1 << 17;

   243            q2 ^= q0;

   244            q3 ^= q1;

   245            q1 ^= q2;

   246            q0 ^= q3;

   247            q2 ^= t;

   248            q3 = Long.rotateLeft(q3, 45);

   249        }

   250         x0 = q0; x1 = q1; x2 = q2; x3 = q3;

   251         return result;

   252     }

   253 

   254     public BigInteger period() {

   255         return PERIOD;

   256     }

   257 

   258     public double defaultJumpDistance() {

   259         return 0x1.0p64;

   260     }

   261 

   262     public double defaultLeapDistance() {

   263         return 0x1.0p96;

   264     }

   265 

   266     private static final long[] JUMP_TABLE = {

   267         0x180ec6d33cfd0abaL, 0xd5a61266f0c9392cL, 0xa9582618e03fc9aaL, 0x39abdc4529b1661cL };

   268 

   269     private static final long[] LEAP_TABLE = {

   270         0x76e15d3efefdcbbfL, 0xc5004e441c522fb3L, 0x77710069854ee241L, 0x39109bb02acbe635L };

   271 

   272     /**

   273      * This is the jump function for the generator. It is equivalent to 2**128 calls to next(); it

   274      * can be used to generate 2**128 non-overlapping subsequences for parallel computations.

   275      */

   276     public void jump() {

   277         jumpAlgorithm(JUMP_TABLE);

   278     }

   279 

   280     /**

   281      * This is the long-jump function for the generator. It is equivalent to 2**192 calls to next();

   282      * it can be used to generate 2**64 starting points, from each of which jump() will generate

   283      * 2**64 non-overlapping subsequences for parallel distributed computations.

   284      */

   285     public void leap() {

   286         jumpAlgorithm(LEAP_TABLE);

   287     }

   288 

   289     private void jumpAlgorithm(long[] table) {

   290         long s0 = 0, s1 = 0, s2 = 0, s3 = 0;

   291         for (int i = 0; i < table.length; i++) {

   292             for (int b = 0; b < 64; b++) {

   293                 if ((table[i] & (1L << b)) != 0) {

   294                     s0 ^= x0;

   295                     s1 ^= x1;

   296                     s2 ^= x2;

   297                     s3 ^= x3;

   298                 }

   299                 nextLong();

   300             }

   301             x0 = s0;

   302             x1 = s1;

   303             x2 = s2;

   304             x3 = s3;

   305         }

   306     }

   307 

   308 }