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>1152</sup>. Class {@link L128X1024MixRandom} 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 L128X1024MixRandom} 43 * objects or streams of such objects. 44 * 45 * <p>The {@link L128X1024MixRandom} 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 L128X1024MixRandom} 49 * has 1152 bits of state plus one 128-bit instance-specific parameter. 50 * 51 * <p>If two instances of {@link L128X1024MixRandom} 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 L128X1024MixRandom} 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(someL128X1024MixRandom.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 L128X1024MixRandom} 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 = "L128X1024MixRandom", 80 group = "LXM", 81 i = 1024, j = 1, k = 128, 82 equidistribution = 1 83 ) 84 public final class L128X1024MixRandom extends AbstractSplittableWithBrineGenerator { 85 86 /* 87 * Implementation Overview. 88 * 89 * The 128-bit parameter `a` is represented as two long fields `ah` and `al`. 90 * The 128-bit state variable `s` is represented as two long fields `sh` and `sl`. 91 * 92 * The split operation uses the current generator to choose 20 93 * new 64-bit long values that are then used to initialize the 94 * parameters `ah` and `al`, the state variables `sh`, `sl`, 95 * and the array `x` for a newly constructed generator. 96 * 97 * With extremely high probability, no two generators so chosen 98 * will have the same `a` parameter, and testing has indicated 99 * that the values generated by two instances of {@link L128X1024MixRandom} 100 * will be (approximately) independent if have different values for `a`. 101 * 102 * The default (no-argument) constructor, in essence, uses 103 * "defaultGen" to generate 20 new 64-bit values for the same 104 * purpose. Multiple generators created in this way will certainly 105 * differ in their `a` parameters. The defaultGen state must be accessed 106 * in a thread-safe manner, so we use an AtomicLong to represent 107 * this state. To bootstrap the defaultGen, we start off using a 108 * seed based on current time unless the 109 * java.util.secureRandomSeed property is set. This serves as a 110 * slimmed-down (and insecure) variant of SecureRandom that also 111 * avoids stalls that may occur when using /dev/random. 112 * 113 * File organization: First static fields, then instance 114 * fields, then constructors, then instance methods. 115 */ 116 117 /* ---------------- static fields ---------------- */ 118 119 /* 120 * The length of the array x. 121 */ 122 123 private static final int N = 16; 124 125 /** 126 * The seed generator for default constructors. 127 */ 128 private static final AtomicLong defaultGen = new AtomicLong(RandomSupport.initialSeed()); 129 130 /* 131 * Low half of multiplier used in the LCG portion of the algorithm; 132 * the overall multiplier is (2**64 + ML). 133 * Chosen based on research by Sebastiano Vigna and Guy Steele (2019). 134 * The spectral scores for dimensions 2 through 8 for the multiplier 0x1d605bbb58c8abbfdLL 135 * are [0.991889, 0.907938, 0.830964, 0.837980, 0.780378, 0.797464, 0.761493]. 136 */ 137 138 private static final long ML = 0xd605bbb58c8abbfdL; 139 140 /* ---------------- instance fields ---------------- */ 141 142 /** 143 * The parameter that is used as an additive constant for the LCG. 144 * Must be odd (therefore al must be odd). 145 */ 146 private final long ah, al; 147 148 /** 149 * The per-instance state: sh and sl for the LCG; the array x for the XBG; 150 * p is the rotating pointer into the array x. 151 * At least one of the 16 elements of the array x must be nonzero. 152 */ 153 private long sh, sl; 154 private final long[] x; 155 private int p = N - 1; 156 157 /* ---------------- constructors ---------------- */ 158 159 /** 160 * Basic constructor that initializes all fields from parameters. 161 * It then adjusts the field values if necessary to ensure that 162 * all constraints on the values of fields are met. 163 * 164 * @param ah high half of the additive parameter for the LCG 165 * @param al low half of the additive parameter for the LCG 166 * @param sh high half of the initial state for the LCG 167 * @param sl low half of the initial state for the LCG 168 * @param x0 first word of the initial state for the XBG 169 * @param x1 second word of the initial state for the XBG 170 * @param x2 third word of the initial state for the XBG 171 * @param x3 fourth word of the initial state for the XBG 172 * @param x4 fifth word of the initial state for the XBG 173 * @param x5 sixth word of the initial state for the XBG 174 * @param x6 seventh word of the initial state for the XBG 175 * @param x7 eight word of the initial state for the XBG 176 * @param x8 ninth word of the initial state for the XBG 177 * @param x9 tenth word of the initial state for the XBG 178 * @param x10 eleventh word of the initial state for the XBG 179 * @param x11 twelfth word of the initial state for the XBG 180 * @param x12 thirteenth word of the initial state for the XBG 181 * @param x13 fourteenth word of the initial state for the XBG 182 * @param x14 fifteenth word of the initial state for the XBG 183 * @param x15 sixteenth word of the initial state for the XBG 184 */ L128X1024MixRandom(long ah, long al, long sh, long sl, 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)185 public L128X1024MixRandom(long ah, long al, long sh, long sl, 186 long x0, long x1, long x2, long x3, 187 long x4, long x5, long x6, long x7, 188 long x8, long x9, long x10, long x11, 189 long x12, long x13, long x14, long x15) { 190 // Force a to be odd. 191 this.ah = ah; 192 this.al = al | 1; 193 this.sh = sh; 194 this.sl = sl; 195 this.x = new long[N]; 196 this.x[0] = x0; 197 this.x[1] = x1; 198 this.x[2] = x2; 199 this.x[3] = x3; 200 this.x[4] = x4; 201 this.x[5] = x5; 202 this.x[6] = x6; 203 this.x[7] = x7; 204 this.x[8] = x8; 205 this.x[9] = x9; 206 this.x[10] = x10; 207 this.x[11] = x11; 208 this.x[12] = x12; 209 this.x[13] = x13; 210 this.x[14] = x14; 211 this.x[15] = x15; 212 // If x0, x1, ..., x15 are all zero (very unlikely), we must choose nonzero values. 213 if ((x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15) == 0) { 214 long v = sh; 215 // At least fifteen of the sixteen values generated here will be nonzero. 216 for (int j = 0; j < N; j++) { 217 this.x[j] = RandomSupport.mixStafford13(v += RandomSupport.GOLDEN_RATIO_64); 218 } 219 } 220 } 221 222 /** 223 * Creates a new instance of {@link L128X1024MixRandom} using the 224 * specified {@code long} value as the initial seed. Instances of 225 * {@link L128X1024MixRandom} created with the same seed in the same 226 * program execution generate identical sequences of values. 227 * 228 * @param seed the initial seed 229 */ L128X1024MixRandom(long seed)230 public L128X1024MixRandom(long seed) { 231 // Using a value with irregularly spaced 1-bits to xor the seed 232 // argument tends to improve "pedestrian" seeds such as 0 or 233 // other small integers. We may as well use SILVER_RATIO_64. 234 // 235 // The seed is hashed by mixMurmur64 to produce the `a` parameter. 236 // The seed is hashed by mixStafford13 to produce the initial `x[0]`, 237 // which will then be used to produce the first generated value. 238 // The other x values are filled in as if by a SplitMix PRNG with 239 // GOLDEN_RATIO_64 as the gamma value and mixStafford13 as the mixer. 240 this(RandomSupport.mixMurmur64(seed ^= RandomSupport.SILVER_RATIO_64), 241 RandomSupport.mixMurmur64(seed += RandomSupport.GOLDEN_RATIO_64), 242 0, 243 1, 244 RandomSupport.mixStafford13(seed), 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 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 250 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 251 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 252 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 253 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 254 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 255 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 256 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 257 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 258 RandomSupport.mixStafford13(seed += RandomSupport.GOLDEN_RATIO_64), 259 RandomSupport.mixStafford13(seed + RandomSupport.GOLDEN_RATIO_64)); 260 } 261 262 /** 263 * Creates a new instance of {@link L128X1024MixRandom} that is likely to 264 * generate sequences of values that are statistically independent 265 * of those of any other instances in the current program execution, 266 * but may, and typically does, vary across program invocations. 267 */ L128X1024MixRandom()268 public L128X1024MixRandom() { 269 // Using GOLDEN_RATIO_64 here gives us a good Weyl sequence of values. 270 this(defaultGen.getAndAdd(RandomSupport.GOLDEN_RATIO_64)); 271 } 272 273 /** 274 * Creates a new instance of {@link L128X1024MixRandom} using the specified array of 275 * initial seed bytes. Instances of {@link L128X1024MixRandom} created with the same 276 * seed array in the same program execution generate identical sequences of values. 277 * 278 * @param seed the initial seed 279 */ L128X1024MixRandom(byte[] seed)280 public L128X1024MixRandom(byte[] seed) { 281 // Convert the seed to 20 long values, of which the last 16 are not all zero. 282 long[] data = RandomSupport.convertSeedBytesToLongs(seed, 20, 16); 283 long ah = data[0], al = data[1], sh = data[2], sl = data[3]; 284 // Force a to be odd. 285 this.ah = ah; 286 this.al = al | 1; 287 this.sh = sh; 288 this.sl = sl; 289 this.x = new long[N]; 290 for (int j = 0; j < N; j++) { 291 this.x[j] = data[4+j]; 292 } 293 } 294 295 /* ---------------- public methods ---------------- */ 296 297 @Override split(SplittableGenerator source, long brine)298 public SplittableGenerator split(SplittableGenerator source, long brine) { 299 // Pick a new instance "at random", but use the brine for (the low half of) `a`. 300 return new L128X1024MixRandom(source.nextLong(), brine << 1, 301 source.nextLong(), source.nextLong(), 302 source.nextLong(), source.nextLong(), 303 source.nextLong(), source.nextLong(), 304 source.nextLong(), source.nextLong(), 305 source.nextLong(), source.nextLong(), 306 source.nextLong(), source.nextLong(), 307 source.nextLong(), source.nextLong(), 308 source.nextLong(), source.nextLong(), 309 source.nextLong(), source.nextLong()); 310 } 311 312 @Override nextLong()313 public long nextLong() { 314 // First part of xoroshiro1024: fetch array data 315 final int q = p; 316 final long s0 = x[p = (p + 1) & (N - 1)]; 317 long s15 = x[q]; 318 319 // Compute the result based on current state information 320 // (this allows the computation to be overlapped with state update). 321 final long result = RandomSupport.mixLea64(sh + s0); 322 323 // Update the LCG subgenerator 324 // The LCG is, in effect, s = ((1LL << 64) + ML) * s + a, if only we had 128-bit arithmetic. 325 final long u = ML * sl; 326 327 // Note that Math.multiplyHigh computes the high half of the product of signed values, 328 // but what we need is the high half of the product of unsigned values; for this we use the 329 // formula "unsignedMultiplyHigh(a, b) = multiplyHigh(a, b) + ((a >> 63) & b) + ((b >> 63) & a)"; 330 // in effect, each operand is added to the result iff the sign bit of the other operand is 1. 331 // (See Henry S. Warren, Jr., _Hacker's Delight_ (Second Edition), Addison-Wesley (2013), 332 // Section 8-3, p. 175; or see the First Edition, Addison-Wesley (2003), Section 8-3, p. 133.) 333 // If Math.unsignedMultiplyHigh(long, long) is ever implemented, the following line can become: 334 // sh = (ML * sh) + Math.unsignedMultiplyHigh(ML, sl) + sl + ah; 335 // and this entire comment can be deleted. 336 sh = (ML * sh) + (Math.multiplyHigh(ML, sl) + ((ML >> 63) & sl) + ((sl >> 63) & ML)) + sl + ah; 337 sl = u + al; 338 if (Long.compareUnsigned(sl, u) < 0) ++sh; // Handle the carry propagation from low half to high half. 339 340 // Second part of xoroshiro1024: update array data 341 s15 ^= s0; 342 x[q] = Long.rotateLeft(s0, 25) ^ s15 ^ (s15 << 27); 343 x[p] = Long.rotateLeft(s15, 36); 344 345 return result; 346 } 347 348 } 349