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 jdk.internal.util.random.RandomSupport; 31 import jdk.internal.util.random.RandomSupport.AbstractSplittableWithBrineGenerator; 32 import jdk.internal.util.random.RandomSupport.RandomGeneratorProperties; 33 34 /** 35 * A "splittable" pseudorandom number generator (PRNG) whose period 36 * is roughly 2<sup>1088</sup>. Class {@link L64X1024MixRandom} implements 37 * interfaces {@link RandomGenerator} and {@link SplittableGenerator}, 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 split-off {@link L64X1024MixRandom} 43 * objects or streams of such objects. 44 * 45 * <p>The {@link L64X1024MixRandom} algorithm is a specific member of 46 * the LXM family of algorithms for pseudorandom number generators; 47 * for more information, see the documentation for package 48 * {@link jdk.random}. Each instance of {@link L64X1024MixRandom} 49 * has 1088 bits of state plus one 64-bit instance-specific parameter. 50 * 51 * <p>If two instances of {@link L64X1024MixRandom} are created with 52 * the same seed within the same program execution, and the same 53 * sequence of method calls is made for each, they will generate and 54 * return identical sequences of values. 55 * 56 * <p>As with {@link java.util.SplittableRandom}, instances of 57 * {@link L64X1024MixRandom} are <em>not</em> thread-safe. They are 58 * designed to be split, not shared, across threads (see the {@link #split} 59 * method). For example, a {@link java.util.concurrent.ForkJoinTask} 60 * fork/join-style computation using random numbers might include a 61 * construction of the form 62 * {@code new Subtask(someL64X1024MixRandom.split()).fork()}. 63 * 64 * <p>This class provides additional methods for generating random 65 * streams, that employ the above techniques when used in 66 * {@code stream.parallel()} mode. 67 * 68 * <p>Instances of {@link L64X1024MixRandom} are not cryptographically 69 * secure. Consider instead using {@link java.security.SecureRandom} 70 * in security-sensitive applications. Additionally, 71 * default-constructed instances do not use a cryptographically random 72 * seed unless the {@linkplain System#getProperty system property} 73 * {@code java.util.secureRandomSeed} is set to {@code true}. 74 * 75 * @since 17 76 * 77 */ 78 @RandomGeneratorProperties( 79 name = "L64X1024MixRandom", 80 group = "LXM", 81 i = 1024, j = 1, k = 64, 82 equidistribution = 16 83 ) 84 public final class L64X1024MixRandom extends AbstractSplittableWithBrineGenerator { 85 86 /* 87 * Implementation Overview. 88 * 89 * The split() operation uses the current generator to choose 18 new 64-bit 90 * long values that are then used to initialize the parameter `a`, the 91 * state variable `s`, and the array `x` for a newly constructed generator. 92 * 93 * With extremely high probability, no two generators so chosen 94 * will have the same `a` parameter, and testing has indicated 95 * that the values generated by two instances of {@link L64X1024MixRandom} 96 * will be (approximately) independent if have different values for `a`. 97 * 98 * The default (no-argument) constructor, in essence, uses 99 * "defaultGen" to generate 18 new 64-bit values for the same 100 * purpose. Multiple generators created in this way will certainly 101 * differ in their `a` parameters. The defaultGen state must be accessed 102 * in a thread-safe manner, so we use an AtomicLong to represent 103 * this state. To bootstrap the defaultGen, we start off using a 104 * seed based on current time unless the 105 * java.util.secureRandomSeed property is set. This serves as a 106 * slimmed-down (and insecure) variant of SecureRandom that also 107 * avoids stalls that may occur when using /dev/random. 108 * 109 * File organization: First static fields, then instance 110 * fields, then constructors, then instance methods. 111 */ 112 113 /* ---------------- static fields ---------------- */ 114 115 /* 116 * The length of the array x. 117 */ 118 119 private static final int N = 16; 120 121 /** 122 * The seed generator for default constructors. 123 */ 124 private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed()); 125 126 /* 127 * Multiplier used in the LCG portion of the algorithm. 128 * Chosen based on research by Sebastiano Vigna and Guy Steele (2019). 129 * The spectral scores for dimensions 2 through 8 for the multiplier 0xd1342543de82ef95 130 * are [0.958602, 0.937479, 0.870757, 0.822326, 0.820405, 0.813065, 0.760215]. 131 */ 132 133 private static final long M = 0xd1342543de82ef95L; 134 135 /* ---------------- instance fields ---------------- */ 136 137 /** 138 * The parameter that is used as an additive constant for the LCG. 139 * Must be odd. 140 */ 141 private final long a; 142 143 /** 144 * The per-instance state: s for the LCG; the array x for the XBG; 145 * p is the rotating pointer into the array x. 146 * At least one of the 16 elements of the array x must be nonzero. 147 */ 148 private long s; 149 private final long[] x; 150 private int p = N - 1; 151 152 /* ---------------- constructors ---------------- */ 153 154 /** 155 * Basic constructor that initializes all fields from parameters. 156 * It then adjusts the field values if necessary to ensure that 157 * all constraints on the values of fields are met. 158 * 159 * @param a additive parameter for the LCG 160 * @param s initial state for the LCG 161 * @param x0 first word of the initial state for the XBG 162 * @param x1 second word of the initial state for the XBG 163 * @param x2 third word of the initial state for the XBG 164 * @param x3 fourth word of the initial state for the XBG 165 * @param x4 fifth word of the initial state for the XBG 166 * @param x5 sixth word of the initial state for the XBG 167 * @param x6 seventh word of the initial state for the XBG 168 * @param x7 eight word of the initial state for the XBG 169 * @param x8 ninth word of the initial state for the XBG 170 * @param x9 tenth word of the initial state for the XBG 171 * @param x10 eleventh word of the initial state for the XBG 172 * @param x11 twelfth word of the initial state for the XBG 173 * @param x12 thirteenth word of the initial state for the XBG 174 * @param x13 fourteenth word of the initial state for the XBG 175 * @param x14 fifteenth word of the initial state for the XBG 176 * @param x15 sixteenth word of the initial state for the XBG 177 */ L64X1024MixRandom(long a, long s, long x0, long x1, long x2, long x3, long x4, long x5, long x6, long x7, long x8, long x9, long x10, long x11, long x12, long x13, long x14, long x15)178 public L64X1024MixRandom(long a, long s, 179 long x0, long x1, long x2, long x3, 180 long x4, long x5, long x6, long x7, 181 long x8, long x9, long x10, long x11, 182 long x12, long x13, long x14, long x15) { 183 // Force a to be odd. 184 this.a = a | 1; 185 this.s = s; 186 this.x = new long[N]; 187 this.x[0] = x0; 188 this.x[1] = x1; 189 this.x[2] = x2; 190 this.x[3] = x3; 191 this.x[4] = x4; 192 this.x[5] = x5; 193 this.x[6] = x6; 194 this.x[7] = x7; 195 this.x[8] = x8; 196 this.x[9] = x9; 197 this.x[10] = x10; 198 this.x[11] = x11; 199 this.x[12] = x12; 200 this.x[13] = x13; 201 this.x[14] = x14; 202 this.x[15] = x15; 203 // If x0, x1, ..., x15 are all zero (very unlikely), we must choose nonzero values. 204 if ((x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15) == 0) { 205 long v = s; 206 // At least fifteen of the sixteen values generated here will be nonzero. 207 for (int j = 0; j < N; j++) { 208 this.x[j] = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64); 209 } 210 } 211 } 212 213 /** 214 * Creates a new instance of {@link L64X1024MixRandom} using the 215 * specified {@code long} value as the initial seed. Instances of 216 * {@link L64X1024MixRandom} created with the same seed in the same 217 * program execution generate identical sequences of values. 218 * 219 * @param seed the initial seed 220 */ L64X1024MixRandom(long seed)221 public L64X1024MixRandom(long seed) { 222 // Using a value with irregularly spaced 1-bits to xor the seed 223 // argument tends to improve "pedestrian" seeds such as 0 or 224 // other small integers. We may as well use SILVER_RATIO_64. 225 // 226 // The seed is hashed by mixMurmur64 to produce the `a` parameter. 227 // The seed is hashed by mixStafford13 to produce the initial `x[0]`, 228 // which will then be used to produce the first generated value. 229 // The other x values are filled in as if by a SplitMix PRNG with 230 // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer. 231 this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64), 232 1, 233 RandomSupport.mixStafford13(seed), 234 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 235 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 236 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 237 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 238 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 239 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 240 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 241 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 242 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 243 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 244 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 245 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 246 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 247 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 248 RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64)); 249 } 250 251 /** 252 * Creates a new instance of {@link L64X1024MixRandom} that is likely to 253 * generate sequences of values that are statistically independent 254 * of those of any other instances in the current program execution, 255 * but may, and typically does, vary across program invocations. 256 */ L64X1024MixRandom()257 public L64X1024MixRandom() { 258 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. 259 this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64)); 260 } 261 262 /** 263 * Creates a new instance of {@link L64X1024MixRandom} using the specified array of 264 * initial seed bytes. Instances of {@link L64X1024MixRandom} created with the same 265 * seed array in the same program execution generate identical sequences of values. 266 * 267 * @param seed the initial seed 268 */ L64X1024MixRandom(byte[] seed)269 public L64X1024MixRandom(byte[] seed) { 270 // Convert the seed to 18 long values, of which the last 16 are not all zero. 271 long[] data = RandomSupport.convertSeedBytesToLongs(seed, 18, 16); 272 long a = data[0], s = data[1]; 273 // Force a to be odd. 274 this.a = a | 1; 275 this.s = s; 276 this.x = new long[N]; 277 for (int j = 0; j < N; j++) { 278 this.x[j] = data[2+j]; 279 } 280 } 281 282 /* ---------------- public methods ---------------- */ 283 284 @Override split(SplittableGenerator source, long brine)285 public SplittableGenerator split(SplittableGenerator source, long brine) { 286 // Pick a new instance "at random", but use the brine for `a`. 287 return new L64X1024MixRandom(brine << 1, source.nextLong(), 288 source.nextLong(), source.nextLong(), 289 source.nextLong(), source.nextLong(), 290 source.nextLong(), source.nextLong(), 291 source.nextLong(), source.nextLong(), 292 source.nextLong(), source.nextLong(), 293 source.nextLong(), source.nextLong(), 294 source.nextLong(), source.nextLong(), 295 source.nextLong(), source.nextLong()); 296 } 297 298 @Override nextLong()299 public long nextLong() { 300 // First part of xoroshiro1024: fetch array data 301 final int q = p; 302 final long s0 = x[p = (p + 1) & (N - 1)]; 303 long s15 = x[q]; 304 305 // Compute the result based on current state information 306 // (this allows the computation to be overlapped with state update). 307 308 final long result = RandomSupport.mixLea64(s + s0); 309 310 // Update the LCG subgenerator 311 s = M * s + a; // LCG 312 313 // Second part of xoroshiro1024: update array data 314 s15 ^= s0; 315 x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27); 316 x[p] = Long.rotateLeft(s15, 36); 317 318 return result; 319 } 320 321 } 322