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 package java.util;

    26 

    27 import java.math.BigInteger;

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

    29 

    30 /**

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

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

    33  * generate subtasks.  Class {@code Xoroshiro128StarStar} implements

    34  * interfaces {@link java.util.Rng} and {@link java.util.LeapableRng},

    35  * and therefore supports methods for producing pseudorandomly chosen

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

    37  * as well as creating new {@code Xoroshiro128StarStar} objects

    38  * by "jumping" or "leaping".

    39  *

    40  * <p>Series of generated values pass the TestU01 BigCrush and PractRand test suites

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

    42  *

    43  * <p>The class {@code Xoroshiro128StarStar} uses the {@code xoroshiro128} algorithm,

    44  * version 1.0 (parameters 24, 16, 37), with the "**" scrambler (a mixing function).

    45  * Its state consists of two {@code long} fields {@code x0} and {@code x1},

    46  * which can take on any values provided that they are not both zero.

    47  * The period of this generator is 2<sup>128</sup>-1.

    48  *

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

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

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

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

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

    54  * methods are likewise equidistributed.

    55  *

    56  * <p>In fact, the 64-bit values produced by the {@code nextLong()} method are 2-equidistributed.

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

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

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

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

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

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

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

    64  * methods are likewise 2-equidistributed, but note that that the subsequence (0, 0)

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

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

    67  *

    68  * <p>Instances {@code Xoroshiro128StarStar} are <em>not</em> thread-safe.

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

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

    71  * can be used to construct new instances of {@code Xoroshiro128StarStar} that traverse

    72  * other parts of the state cycle.

    73  *

    74  * <p>Instances of {@code Xoroshiro128StarStar} are not cryptographically

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

    76  * in security-sensitive applications. Additionally,

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

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

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

    80  *

    81  * @author  Guy Steele

    82  * @author  Doug Lea

    83  * @since   1.8

    84  */

    85 public final class Xoroshiro128StarStar implements LeapableRng {

    86 

    87     /*

    88      * Implementation Overview.

    89      *

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

    91      * in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org),

    92      * and updated with improved parameters in 2018.

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

    94      *

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

    96      *    xorshift Generators, Scrambled. ACM Transactions on Mathematical

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

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

    99      *

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

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

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

   103      *

   104      * The jump operation moves the current generator forward by 2*64

   105      * steps; this has the same effect as calling nextLong() 2**64

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

   107      * the current generator forward by 2*96 steps; this has the same

   108      * effect as calling nextLong() 2**96 times, but is much faster.

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

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

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

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

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

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

   115      *

   116      * File organization: First the non-public methods that constitute the

   117      * main algorithm, then the public methods.  Note that many methods are

   118      * defined by classes {@code AbstractJumpableRng} and {@code AbstractRng}.

   119      */

   120 

   121     /* ---------------- static fields ---------------- */

   122 

   123     /**

   124      * The seed generator for default constructors.

   125      */

   126     private static final AtomicLong defaultGen = new AtomicLong(RngSupport.initialSeed());

   127 

   128     /*

   129      * The period of this generator, which is 2**128 - 1.

   130      */

   131     private static final BigInteger thePeriod =

   132 	BigInteger.ONE.shiftLeft(128).subtract(BigInteger.ONE);

   133 

   134     /* ---------------- instance fields ---------------- */

   135 

   136     /**

   137      * The per-instance state.

   138      * At least one of the two fields x0 and x1 must be nonzero.

   139      */

   140     private long x0, x1;

   141 

   142     /* ---------------- constructors ---------------- */

   143 

   144     /**

   145      * Basic constructor that initializes all fields from parameters.

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

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

   148       *

   149      * @param x0 first word of the initial state

   150      * @param x1 second word of the initial state

   151     */

   152     public Xoroshiro128StarStar(long x0, long x1) {

   153 	this.x0 = x0;

   154         this.x1 = x1;

   155 	// If x0 and x1 are both zero, we must choose nonzero values.

   156         if ((x0 | x1) == 0) {

   157 	    // At least one of the two values generated here will be nonzero.

   158 	    this.x0 = RngSupport.mixStafford13(x0 += RngSupport.GOLDEN_RATIO_64);

   159 	    this.x1 = (x0 += RngSupport.GOLDEN_RATIO_64);

   160 	}

   161     }

   162 

   163     /**

   164      * Creates a new instance of {@code Xoroshiro128StarStar} using the

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

   166      * {@code Xoroshiro128StarStar} created with the same seed in the same

   167      * program generate identical sequences of values.

   168      *

   169      * @param seed the initial seed

   170      */

   171     public Xoroshiro128StarStar(long seed) {

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

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

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

   175 	//

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

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

   178         this(RngSupport.mixStafford13(seed ^= RngSupport.SILVER_RATIO_64),

   179 	     RngSupport.mixStafford13(seed + RngSupport.GOLDEN_RATIO_64));

   180     }

   181 

   182     /**

   183      * Creates a new instance of {@code Xoroshiro128StarStar} that is likely to

   184      * generate sequences of values that are statistically independent

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

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

   187      */

   188     public Xoroshiro128StarStar() {

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

   190         this(defaultGen.getAndAdd(RngSupport.GOLDEN_RATIO_64));

   191     }

   192 

   193     /**

   194      * Creates a new instance of {@code Xoroshiro128StarStar} using the specified array of

   195      * initial seed bytes. Instances of {@code Xoroshiro128StarStar} created with the same

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

   197      *

   198      * @param seed the initial seed

   199      */

   200     public Xoroshiro128StarStar(byte[] seed) {

   201 	// Convert the seed to 2 long values, which are not both zero.

   202 	long[] data = RngSupport.convertSeedBytesToLongs(seed, 2, 2);

   203 	long x0 = data[0], x1 = data[1];

   204         this.x0 = x0;

   205         this.x1 = x1;

   206     }

   207     

   208     /* ---------------- public methods ---------------- */

   209 

   210     public Xoroshiro128StarStar copy() { return new Xoroshiro128StarStar(x0, x1); }

   211 

   212 /*  

   213 

   214 To the extent possible under law, the author has dedicated all copyright

   215 and related and neighboring rights to this software to the public domain

   216 worldwide. This software is distributed without any warranty.

   217 

   218 See <http://creativecommons.org/publicdomain/zero/1.0/>. */

   219 

   220 /* This is the successor to xorshift128+. It is the fastest full-period

   221    generator passing BigCrush without systematic failures, but due to the

   222    relatively short period it is acceptable only for applications with a

   223    mild amount of parallelism; otherwise, use a xorshift1024* generator.

   224 

   225    Beside passing BigCrush, this generator passes the PractRand test suite

   226    up to (and included) 16TB, with the exception of binary rank tests,

   227    which fail due to the lowest bit being an LFSR; all other bits pass all

   228    tests. We suggest to use a sign test to extract a random Boolean value.

   229    

   230    Note that the generator uses a simulated rotate operation, which most C

   231    compilers will turn into a single instruction. In Java, you can use

   232    Long.rotateLeft(). In languages that do not make low-level rotation

   233    instructions accessible xorshift128+ could be faster.

   234 

   235    The state must be seeded so that it is not everywhere zero. If you have

   236    a 64-bit seed, we suggest to seed a splitmix64 generator and use its

   237    output to fill s. */

   238 

   239 

   240     /**

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

   242      *

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

   244      */

   245     public long nextLong() {

   246 	final long s0 = x0;

   247 	long s1 = x1;

   248 	final long z = s0;

   249 

   250 	s1 ^= s0;

   251 	x0 = Long.rotateLeft(s0, 24) ^ s1 ^ (s1 << 16); // a, b

   252 	x1 = Long.rotateLeft(s1, 37); // c

   253 	

   254 	return Long.rotateLeft(z * 5, 7) * 9;  // "starstar" mixing function

   255     }

   256 

   257     public BigInteger period() { return thePeriod; }

   258 

   259     public double defaultJumpDistance() { return 0x1.0p64; }

   260 

   261     public double defaultLeapDistance() { return 0x1.0p96; }

   262 

   263     private static final long[] JUMP_TABLE = { 0xdf900294d8f554a5L, 0x170865df4b3201fcL };

   264     

   265     private static final long[] LEAP_TABLE = { 0xd2a98b26625eee7bL, 0xdddf9b1090aa7ac1L };

   266    

   267 /* This is the jump function for the generator. It is equivalent

   268    to 2**64 calls to nextLong(); it can be used to generate 2**64

   269    non-overlapping subsequences for parallel computations. */

   270 

   271     public void jump() { jumpAlgorithm(JUMP_TABLE); }

   272     

   273 /* This is the long-jump function for the generator. It is equivalent to

   274    2**96 calls to next(); it can be used to generate 2**32 starting points,

   275    from each of which jump() will generate 2**32 non-overlapping

   276    subsequences for parallel distributed computations. */

   277 

   278     public void leap() { jumpAlgorithm(LEAP_TABLE); }

   279 

   280     private void jumpAlgorithm(long[] table) {

   281 	long s0 = 0, s1 = 0;

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

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

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

   285 		    s0 ^= x0;

   286 		    s1 ^= x1;

   287 		}

   288 		nextLong();

   289 	    }

   290 	    x0 = s0;

   291 	    x1 = s1;

   292 	}

   293     }

   294 }