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>128</sup>. Class {@link Xoroshiro128PlusPlus} implements 37 * interfaces {@link RandomGenerator} and {@link LeapableGenerator}, 38 * and therefore supports methods for producing pseudorandomly chosen 39 * numbers of type {@code int}, {@code long}, {@code float}, and {@code double} 40 * as well as creating new {@link Xoroshiro128PlusPlus} objects 41 * by "jumping" or "leaping". 42 * <p> 43 * The class {@link Xoroshiro128PlusPlus} uses the {@code xoroshiro128} algorithm 44 * (parameters 49, 21, 28) with the "++" scrambler that computes 45 * {@code Long.rotateLeft(s0 + s1, 17) + s0}. 46 * (See David Blackman and Sebastiano Vigna, "Scrambled Linear Pseudorandom 47 * Number Generators," ACM Transactions on Mathematical Software, 2021.) 48 * Its state consists of two {@code long} fields {@code x0} and {@code x1}, 49 * which can take on any values provided that they are not both zero. 50 * The period of this generator is 2<sup>128</sup>-1. 51 * <p> 52 * The 64-bit values produced by the {@code nextLong()} method are equidistributed. 53 * To be precise, over the course of the cycle of length 2<sup>128</sup>-1, 54 * each nonzero {@code long} value is generated 2<sup>64</sup> times, 55 * but the value 0 is generated only 2<sup>64</sup>-1 times. 56 * The values produced by the {@code nextInt()}, {@code nextFloat()}, and {@code nextDouble()} 57 * methods are likewise equidistributed. 58 * <p> 59 * Instances {@link Xoroshiro128PlusPlus} are <em>not</em> thread-safe. 60 * They are designed to be used so that each thread as its own instance. 61 * The methods {@link #jump} and {@link #leap} and {@link #jumps} and {@link #leaps} 62 * can be used to construct new instances of {@link Xoroshiro128PlusPlus} that traverse 63 * other parts of the state cycle. 64 * <p> 65 * Instances of {@link Xoroshiro128PlusPlus} are not cryptographically 66 * secure. Consider instead using {@link java.security.SecureRandom} 67 * in security-sensitive applications. Additionally, 68 * default-constructed instances do not use a cryptographically random 69 * seed unless the {@linkplain System#getProperty system property} 70 * {@code java.util.secureRandomSeed} is set to {@code true}. 71 * 72 * @since 17 73 * 74 */ 75 @RandomGeneratorProperties( 76 name = "Xoroshiro128PlusPlus", 77 group = "Xoroshiro", 78 i = 128, j = 1, k = 0, 79 equidistribution = 1 80 ) 81 public final class Xoroshiro128PlusPlus implements LeapableGenerator { 82 83 /* 84 * Implementation Overview. 85 * 86 * This is an implementation of the xoroshiro128++ algorithm version 1.0, 87 * written in 2019 by David Blackman and Sebastiano Vigna (vigna@acm.org). 88 * 89 * The jump operation moves the current generator forward by 2*64 90 * steps; this has the same effect as calling nextLong() 2**64 91 * times, but is much faster. Similarly, the leap operation moves 92 * the current generator forward by 2*96 steps; this has the same 93 * effect as calling nextLong() 2**96 times, but is much faster. 94 * The copy method may be used to make a copy of the current 95 * generator. Thus one may repeatedly and cumulatively copy and 96 * jump to produce a sequence of generators whose states are well 97 * spaced apart along the overall state cycle (indeed, the jumps() 98 * and leaps() methods each produce a stream of such generators). 99 * The generators can then be parceled out to other threads. 100 * 101 * File organization: First the non-public methods that constitute the 102 * main algorithm, then the public methods. Note that many methods are 103 * defined by classes {@link AbstractJumpableGenerator} and {@link AbstractGenerator}. 104 */ 105 106 /* ---------------- static fields ---------------- */ 107 108 /** 109 * Group name. 110 */ 111 private static final String GROUP = "Xoroshiro"; 112 113 /** 114 * The seed generator for default constructors. 115 */ 116 private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed()); 117 118 /* ---------------- instance fields ---------------- */ 119 120 /** 121 * The per-instance state. 122 * At least one of the two fields x0 and x1 must be nonzero. 123 */ 124 private long x0, x1; 125 126 /* ---------------- constructors ---------------- */ 127 128 /** 129 * Basic constructor that initializes all fields from parameters. 130 * It then adjusts the field values if necessary to ensure that 131 * all constraints on the values of fields are met. 132 * 133 * @param x0 first word of the initial state 134 * @param x1 second word of the initial state 135 */ Xoroshiro128PlusPlus(long x0, long x1)136 public Xoroshiro128PlusPlus(long x0, long x1) { 137 this.x0 = x0; 138 this.x1 = x1; 139 // If x0 and x1 are both zero, we must choose nonzero values. 140 if ((x0 | x1) == 0) { 141 this.x0 = RandomSupport.GOLDEN_RATIO_64; 142 this.x1 = RandomSupport.SILVER_RATIO_64; 143 } 144 } 145 146 /** 147 * Creates a new instance of {@link Xoroshiro128PlusPlus} using the 148 * specified {@code long} value as the initial seed. Instances of 149 * {@link Xoroshiro128PlusPlus} created with the same seed in the same 150 * program generate identical sequences of values. 151 * 152 * @param seed the initial seed 153 */ Xoroshiro128PlusPlus(long seed)154 public Xoroshiro128PlusPlus(long seed) { 155 // Using a value with irregularly spaced 1-bits to xor the seed 156 // argument tends to improve "pedestrian" seeds such as 0 or 157 // other small integers. We may as well use SILVER_RATIO_64. 158 // 159 // The x values are then filled in as if by a SplitMix PRNG with 160 // GOLDEN_RATIO_64 as the gamma value and Stafford13 as the mixer. 161 this(RandomSupport.mixStafford13(seed ^= RandomSupport.SILVER_RATIO_64), 162 RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64)); 163 } 164 165 /** 166 * Creates a new instance of {@link Xoroshiro128PlusPlus} that is likely to 167 * generate sequences of values that are statistically independent 168 * of those of any other instances in the current program execution, 169 * but may, and typically does, vary across program invocations. 170 */ Xoroshiro128PlusPlus()171 public Xoroshiro128PlusPlus() { 172 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. 173 this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64)); 174 } 175 176 /** 177 * Creates a new instance of {@link Xoroshiro128PlusPlus} using the specified array of 178 * initial seed bytes. Instances of {@link Xoroshiro128PlusPlus} created with the same 179 * seed array in the same program execution generate identical sequences of values. 180 * 181 * @param seed the initial seed 182 */ Xoroshiro128PlusPlus(byte[] seed)183 public Xoroshiro128PlusPlus(byte[] seed) { 184 // Convert the seed to 2 long values, which are not both zero. 185 long[] data = RandomSupport.convertSeedBytesToLongs(seed, 2, 2); 186 long x0 = data[0], x1 = data[1]; 187 this.x0 = x0; 188 this.x1 = x1; 189 } 190 191 /* ---------------- public methods ---------------- */ 192 copy()193 public Xoroshiro128PlusPlus copy() { 194 return new Xoroshiro128PlusPlus(x0, x1); 195 } 196 197 /* 198 * The following two comments are quoted from http://prng.di.unimi.it/xoroshiro128plusplus.c 199 */ 200 201 /* 202 * To the extent possible under law, the author has dedicated all copyright 203 * and related and neighboring rights to this software to the public domain 204 * worldwide. This software is distributed without any warranty. 205 * <p> 206 * See http://creativecommons.org/publicdomain/zero/1.0/. 207 */ 208 209 /* 210 * This is xoroshiro128++ 1.0, one of our all-purpose, rock-solid, 211 * small-state generators. It is extremely (sub-ns) fast and it passes all 212 * tests we are aware of, but its state space is large enough only for 213 * mild parallelism. 214 * <p> 215 * For generating just floating-point numbers, xoroshiro128+ is even 216 * faster (but it has a very mild bias, see notes in the comments). 217 * <p> 218 * The state must be seeded so that it is not everywhere zero. If you have 219 * a 64-bit seed, we suggest to seed a splitmix64 generator and use its 220 * output to fill s. 221 */ 222 223 @Override nextLong()224 public long nextLong() { 225 final long s0 = x0; 226 long s1 = x1; 227 // Compute the result based on current state information 228 // (this allows the computation to be overlapped with state update). 229 final long result = Long.rotateLeft(s0 + s1, 17) + s0; // "plusplus" scrambler 230 231 s1 ^= s0; 232 x0 = Long.rotateLeft(s0, 49) ^ s1 ^ (s1 << 21); // a, b 233 x1 = Long.rotateLeft(s1, 28); // c 234 235 return result; 236 } 237 238 @Override jumpDistance()239 public double jumpDistance() { 240 return 0x1.0p64; 241 } 242 243 @Override leapDistance()244 public double leapDistance() { 245 return 0x1.0p96; 246 } 247 248 private static final long[] JUMP_TABLE = { 0x2bd7a6a6e99c2ddcL, 0x0992ccaf6a6fca05L }; 249 250 private static final long[] LEAP_TABLE = { 0x360fd5f2cf8d5d99L, 0x9c6e6877736c46e3L }; 251 252 @Override jump()253 public void jump() { 254 jumpAlgorithm(JUMP_TABLE); 255 } 256 257 @Override leap()258 public void leap() { 259 jumpAlgorithm(LEAP_TABLE); 260 } 261 jumpAlgorithm(long[] table)262 private void jumpAlgorithm(long[] table) { 263 long s0 = 0, s1 = 0; 264 for (int i = 0; i < table.length; i++) { 265 for (int b = 0; b < 64; b++) { 266 if ((table[i] & (1L << b)) != 0) { 267 s0 ^= x0; 268 s1 ^= x1; 269 } 270 nextLong(); 271 } 272 } 273 x0 = s0; 274 x1 = s1; 275 } 276 } 277