1 /* 2 * Copyright (c) 2021, 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 jdk.random; 27 28 import java.util.concurrent.atomic.AtomicLong; 29 import java.util.random.RandomGenerator; 30 import java.util.random.RandomGenerator.LeapableGenerator; 31 import jdk.internal.util.random.RandomSupport; 32 import jdk.internal.util.random.RandomSupport.RandomGeneratorProperties; 33 34 /** 35 * A "jumpable and leapable" pseudorandom number generator (PRNG) whose period 36 * is roughly 2<sup>256</sup>. Class {@link Xoshiro256PlusPlus} implements 37 * interfaces {@link RandomGenerator} and {@link LeapableGenerator}, 38 * and therefore supports methods for producing pseudorandomly chosen 39 * values of type {@code int}, {@code long}, {@code float}, {@code double}, 40 * and {@code boolean} (and for producing streams of pseudorandomly chosen 41 * numbers of type {@code int}, {@code long}, and {@code double}), 42 * as well as methods for creating new {@link Xoshiro256PlusPlus} objects 43 * by moving forward either a large distance (2<sup>128</sup>) or a very large 44 * distance (2<sup>192</sup>) around the state cycle. 45 * <p> 46 * Series of generated values pass the TestU01 BigCrush and PractRand test suites 47 * that measure independence and uniformity properties of random number generators. 48 * (Most recently validated with 49 * <a href="http://simul.iro.umontreal.ca/testu01/tu01.html">version 1.2.3 of TestU01</a> 50 * and <a href="http://pracrand.sourceforge.net">version 0.90 of PractRand</a>. 51 * Note that TestU01 BigCrush was used to test not only values produced by the {@code nextLong()} 52 * method but also the result of bit-reversing each value produced by {@code nextLong()}.) 53 * These tests validate only the methods for certain 54 * types and ranges, but similar properties are expected to hold, at 55 * least approximately, for others as well. 56 * <p> 57 * The class {@link Xoshiro256PlusPlus} uses the {@code xoshiro256} algorithm, 58 * version 1.0 (parameters 17, 45), with the "++" scrambler that computes 59 * {@code Long.rotateLeft(s0 + s3, 23) + s0}. 60 * (See David Blackman and Sebastiano Vigna, "Scrambled Linear Pseudorandom 61 * Number Generators," ACM Transactions on Mathematical Software, 2021.) 62 * Its state consists of four {@code long} fields {@code x0}, {@code x1}, {@code x2}, 63 * and {@code x3}, which can take on any values provided that they are not all zero. 64 * The period of this generator is 2<sup>256</sup>-1. 65 * <p> 66 * The 64-bit values produced by the {@code nextLong()} method are equidistributed. 67 * To be precise, over the course of the cycle of length 2<sup>256</sup>-1, 68 * each nonzero {@code long} value is generated 2<sup>192</sup> times, 69 * but the value 0 is generated only 2<sup>192</sup>-1 times. 70 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} 71 * methods are likewise equidistributed. 72 * Moreover, the 64-bit values produced by the {@code nextLong()} method are 3-equidistributed. 73 * <p> 74 * Instances {@link Xoshiro256PlusPlus} are <em>not</em> thread-safe. 75 * They are designed to be used so that each thread as its own instance. 76 * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps} 77 * can be used to construct new instances of {@link Xoshiro256PlusPlus} that traverse 78 * other parts of the state cycle. 79 * <p> 80 * Instances of {@link Xoshiro256PlusPlus} are not cryptographically 81 * secure. Consider instead using {@link java.security.SecureRandom} 82 * in security-sensitive applications. Additionally, 83 * default-constructed instances do not use a cryptographically random 84 * seed unless the {@linkplain System#getProperty system property} 85 * {@code java.util.secureRandomSeed} is set to {@code true}. 86 * 87 * @since 17 88 * 89 */ 90 @RandomGeneratorProperties( 91 name = "Xoshiro256PlusPlus", 92 group = "Xoshiro", 93 i = 256, j = 1, k = 0, 94 equidistribution = 3 95 ) 96 public final class Xoshiro256PlusPlus implements LeapableGenerator { 97 98 /* 99 * Implementation Overview. 100 * 101 * This is an implementation of the xoshiro256++ algorithm version 1.0, 102 * written in 2019 by David Blackman and Sebastiano Vigna (vigna@acm.org). 103 * 104 * The jump operation moves the current generator forward by 2*128 105 * steps; this has the same effect as calling nextLong() 2**128 106 * times, but is much faster. Similarly, the leap operation moves 107 * the current generator forward by 2*192 steps; this has the same 108 * effect as calling nextLong() 2**192 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 static fields, then instance 117 * fields, then constructors, then instance methods. 118 */ 119 120 /* ---------------- static fields ---------------- */ 121 122 /** 123 * The seed generator for default constructors. 124 */ 125 private static final AtomicLong DEFAULT_GEN = new AtomicLong(RandomSupport.initialSeed()); 126 127 /* ---------------- instance fields ---------------- */ 128 129 /** 130 * The per-instance state. 131 * At least one of the four fields x0, x1, x2, and x3 must be nonzero. 132 */ 133 private long x0, x1, x2, x3; 134 135 /* ---------------- constructors ---------------- */ 136 137 /** 138 * Basic constructor that initializes all fields from parameters. 139 * It then adjusts the field values if necessary to ensure that 140 * all constraints on the values of fields are met. 141 * 142 * @param x0 first word of the initial state 143 * @param x1 second word of the initial state 144 * @param x2 third word of the initial state 145 * @param x3 fourth word of the initial state 146 */ Xoshiro256PlusPlus(long x0, long x1, long x2, long x3)147 public Xoshiro256PlusPlus(long x0, long x1, long x2, long x3) { 148 this.x0 = x0; 149 this.x1 = x1; 150 this.x2 = x2; 151 this.x3 = x3; 152 // If x0, x1, x2, and x3 are all zero, we must choose nonzero values. 153 if ((x0 | x1 | x2 | x3) == 0) { 154 // At least three of the four values generated here will be nonzero. 155 this.x0 = RandomSupport.mixStafford13(x0 += RandomSupport.GOLDEN_RATIO_64); 156 this.x1 = (x0 += RandomSupport.GOLDEN_RATIO_64); 157 this.x2 = (x0 += RandomSupport.GOLDEN_RATIO_64); 158 this.x3 = (x0 += RandomSupport.GOLDEN_RATIO_64); 159 } 160 } 161 162 /** 163 * Creates a new instance of {@link Xoshiro256PlusPlus} using the 164 * specified {@code long} value as the initial seed. Instances of 165 * {@link Xoshiro256PlusPlus} created with the same seed in the same 166 * program generate identical sequences of values. 167 * 168 * @param seed the initial seed 169 */ Xoshiro256PlusPlus(long seed)170 public Xoshiro256PlusPlus(long seed) { 171 // Using a value with irregularly spaced 1-bits to xor the seed 172 // argument tends to improve "pedestrian" seeds such as 0 or 173 // other small integers. We may as well use SILVER_RATIO_64. 174 // 175 // The x values are then filled in as if by a SplitMix PRNG with 176 // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer. 177 this(RandomSupport.mixStafford13(seed ^= RandomSupport.SILVER_RATIO_64), 178 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 179 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 180 RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64)); 181 } 182 183 /** 184 * Creates a new instance of {@link Xoshiro256PlusPlus} that is likely to 185 * generate sequences of values that are statistically independent 186 * of those of any other instances in the current program execution, 187 * but may, and typically does, vary across program invocations. 188 */ Xoshiro256PlusPlus()189 public Xoshiro256PlusPlus() { 190 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. 191 this(DEFAULT_GEN.getAndAdd(RandomSupport.GOLDEN_RATIO_64)); 192 } 193 194 /** 195 * Creates a new instance of {@link Xoshiro256PlusPlus} using the specified array of 196 * initial seed bytes. Instances of {@link Xoshiro256PlusPlus} created with the same 197 * seed array in the same program execution generate identical sequences of values. 198 * 199 * @param seed the initial seed 200 */ Xoshiro256PlusPlus(byte[] seed)201 public Xoshiro256PlusPlus(byte[] seed) { 202 // Convert the seed to 4 long values, which are not all zero. 203 long[] data = RandomSupport.convertSeedBytesToLongs(seed, 4, 4); 204 long x0 = data[0], x1 = data[1], x2 = data[2], x3 = data[3]; 205 this.x0 = x0; 206 this.x1 = x1; 207 this.x2 = x2; 208 this.x3 = x3; 209 } 210 211 /* ---------------- public methods ---------------- */ 212 copy()213 public Xoshiro256PlusPlus copy() { 214 return new Xoshiro256PlusPlus(x0, x1, x2, x3); 215 } 216 217 /* 218 * The following two comments are quoted from http://prng.di.unimi.it/xoshiro256plusplus.c 219 */ 220 221 /* 222 * To the extent possible under law, the author has dedicated all copyright 223 * and related and neighboring rights to this software to the public domain 224 * worldwide. This software is distributed without any warranty. 225 * <p> 226 * See http://creativecommons.org/publicdomain/zero/1.0/. 227 */ 228 229 /* 230 * This is xoshiro256++ 1.0, one of our all-purpose, rock-solid generators. 231 * It has excellent (sub-ns) speed, a state (256 bits) that is large 232 * enough for any parallel application, and it passes all tests we are 233 * aware of. 234 * 235 * For generating just floating-point numbers, xoshiro256+ is even faster. 236 * 237 * The state must be seeded so that it is not everywhere zero. If you have 238 * a 64-bit seed, we suggest to seed a splitmix64 generator and use its 239 * output to fill s. 240 */ 241 242 @Override nextLong()243 public long nextLong() { 244 // Compute the result based on current state information 245 // (this allows the computation to be overlapped with state update). 246 final long result = Long.rotateLeft(x0 + x3, 23) + x0; // "plusplus" scrambler 247 248 long q0 = x0, q1 = x1, q2 = x2, q3 = x3; 249 { // xoshiro256 1.0 250 long t = q1 << 17; 251 q2 ^= q0; 252 q3 ^= q1; 253 q1 ^= q2; 254 q0 ^= q3; 255 q2 ^= t; 256 q3 = Long.rotateLeft(q3, 45); 257 } 258 x0 = q0; x1 = q1; x2 = q2; x3 = q3; 259 return result; 260 } 261 262 @Override jumpDistance()263 public double jumpDistance() { 264 return 0x1.0p128; 265 } 266 267 @Override leapDistance()268 public double leapDistance() { 269 return 0x1.0p192; 270 } 271 272 private static final long[] JUMP_TABLE = { 273 0x180ec6d33cfd0abaL, 0xd5a61266f0c9392cL, 0xa9582618e03fc9aaL, 0x39abdc4529b1661cL }; 274 275 private static final long[] LEAP_TABLE = { 276 0x76e15d3efefdcbbfL, 0xc5004e441c522fb3L, 0x77710069854ee241L, 0x39109bb02acbe635L }; 277 278 @Override jump()279 public void jump() { 280 jumpAlgorithm(JUMP_TABLE); 281 } 282 283 @Override leap()284 public void leap() { 285 jumpAlgorithm(LEAP_TABLE); 286 } 287 jumpAlgorithm(long[] table)288 private void jumpAlgorithm(long[] table) { 289 long s0 = 0, s1 = 0, s2 = 0, s3 = 0; 290 for (int i = 0; i < table.length; i++) { 291 for (int b = 0; b < 64; b++) { 292 if ((table[i] & (1L << b)) != 0) { 293 s0 ^= x0; 294 s1 ^= x1; 295 s2 ^= x2; 296 s3 ^= x3; 297 } 298 nextLong(); 299 } 300 } 301 x0 = s0; 302 x1 = s1; 303 x2 = s2; 304 x3 = s3; 305 } 306 307 } 308