1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.rng.core.source32;
18
19 import java.util.SplittableRandom;
20 import java.util.concurrent.ThreadLocalRandom;
21 import java.util.function.Function;
22 import java.util.function.IntSupplier;
23 import java.util.function.Supplier;
24 import java.util.function.UnaryOperator;
25 import java.util.stream.IntStream;
26 import java.util.stream.Stream;
27 import org.apache.commons.rng.LongJumpableUniformRandomProvider;
28 import org.apache.commons.rng.RestorableUniformRandomProvider;
29 import org.apache.commons.rng.core.RandomAssert;
30 import org.junit.jupiter.api.Assertions;
31 import org.junit.jupiter.api.RepeatedTest;
32 import org.junit.jupiter.api.Test;
33 import org.junit.jupiter.api.TestInstance;
34 import org.junit.jupiter.api.TestInstance.Lifecycle;
35 import org.junit.jupiter.params.ParameterizedTest;
36 import org.junit.jupiter.params.provider.Arguments;
37 import org.junit.jupiter.params.provider.MethodSource;
38
39 /**
40 * Base test for LXM generators. These generators all use the same basic steps:
41 * <pre>
42 * s = state of LCG
43 * t = state of XBG
44 *
45 * generate():
46 * z <- mix(combine(w upper bits of s, w upper bits of t))
47 * s <- LCG state update
48 * t <- XBG state update
49 * </pre>
50 *
51 * <p>This base class provides a composite generator of an LCG and XBG
52 * both using w = 32-bits. Tests for a RNG implementation must define
53 * a factory for constructing a reference composite LXM generator. Implementations
54 * for the 32-bit LCG used in the LXM family are provided.
55 * Implementations for the XBG are provided based on version in the Commons RNG core library.
56 *
57 * <p>It is assumed the XBG generator may be a {@link LongJumpableUniformRandomProvider}.
58 * The composite generator requires the sub-generators to provide a jump and long jump
59 * equivalent operation. This is performed by advancing/rewinding the LCG and XBG the same number
60 * of cycles. In practice this is performed using:
61 * <ul>
62 * <li>A large jump of the XBG that wraps the state of the LCG.
63 * <li>Leaving the XBG state unchanged and advancing the LCG. This effectively
64 * rewinds the state of the LXM by the period of the XBG multiplied by the number of
65 * cycles advanced by the LCG.
66 * </ul>
67 *
68 * <p>The paper by Steele and Vigna suggest advancing the LCG to take advantage of
69 * the fast update step of the LCG. If the LCG and XBG sub-generators support
70 * jump/longJump then the composite can then be used to test arbitrary
71 * combinations of calls to: generate the next long value; and jump operations.
72 * This is not possible using the reference implementations of the LXM family in
73 * JDK 17 which do not implement jumping (instead providing a split operation to
74 * create new RNGs).
75 *
76 * <p>The test assumes the following conditions:
77 * <ul>
78 * <li>The seed length equals the state size of the LCG and XBG generators.
79 * <li>The LXM generator seed is the seed for the LCG appended with the seed for the XBG.
80 * <li>The LCG seed in order is [additive parameter, initial state]. The additive parameter
81 * must be odd for a maximum period LCG and the test asserts the final bit of the add parameter
82 * from the seed is effectively ignored as it is forced to be odd in the constructor.
83 * <li>If the XBG seed is all zeros, the LXM generator is partially functional. It will output
84 * non-zero values but the sequence may be statistically weak and the period is that of the LCG.
85 * This cannot be practically tested but non-zero output is verified for an all zero seed.
86 * </ul>
87 *
88 * <p>Note: The seed order prioritises the additive parameter first. This parameter can be used to
89 * create independent streams of generators. It allows constructing a generator from a single long
90 * value, where the rest of the state is filled with a procedure generating non-zero values,
91 * which will be independent from a second generator constructed with a different single additive
92 * parameter. The difference must be in the high 31-bits of the seed value. A suitable filling
93 * procedure from an initial seed value is provided in the Commons RNG Simple module.
94 *
95 * <p>The class uses a per-class lifecycle. This allows abstract methods to be overridden
96 * in implementing classes to control test behaviour.
97 */
98 @TestInstance(Lifecycle.PER_CLASS)
99 abstract class AbstractLXMTest {
100 /**
101 * A function to mix two int values.
102 * Implements the combine and mix functions of the LXM generator.
103 */
104 interface Mix {
105 /**
106 * Mix the values.
107 *
108 * @param a Value a
109 * @param b Value b
110 * @return the result
111 */
112 int apply(int a, int b);
113 }
114
115 /**
116 * A jumpable sub-generator. This can be a linear congruential generator (LCG)
117 * or xor-based generator (XBG) when used in the LXM family.
118 *
119 * <p>For simplicity the steps of obtaining the upper bits of the state
120 * and updating the state are combined to a single operation.
121 */
122 interface SubGen {
123 /**
124 * Return the upper 32-bits of the current state and update the state.
125 *
126 * @return the upper 32-bits of the old state
127 */
128 int stateAndUpdate();
129
130 /**
131 * Create a copy and then advance the state in a single jump; the copy is returned.
132 *
133 * @return the copy
134 */
135 SubGen copyAndJump();
136
137 /**
138 * Create a copy and then advance the state in a single int jump; the copy is returned.
139 *
140 * @return the copy
141 */
142 SubGen copyAndLongJump();
143 }
144
145 /**
146 * Mix the sum using the lea32 function.
147 *
148 * @param a Value a
149 * @param b Value b
150 * @return the result
151 */
152 static int mixLea32(int a, int b) {
153 return LXMSupport.lea32(a + b);
154 }
155
156 /**
157 * A 32-bit linear congruential generator.
158 */
159 static class LCG32 implements SubGen {
160 /** Multiplier. */
161 private static final int M = LXMSupport.M32;
162 /** Additive parameter (must be odd). */
163 private final int a;
164 /** State. */
165 private int s;
166 /** Power of 2 for the jump. */
167 private final int jumpPower;
168 /** Power of 2 for the long jump. */
169 private final int longJumpPower;
170
171 /**
172 * Create an instance with a jump of 1 cycle and int jump of 2^32 cycles.
173 *
174 * @param a Additive parameter (set to odd)
175 * @param s State
176 */
177 LCG32(int a, int s) {
178 this(a, s, 0, 16);
179 }
180
181 /**
182 * @param a Additive parameter (set to odd)
183 * @param s State
184 * @param jumpPower Jump size as a power of 2
185 * @param longJumpPower Long jump size as a power of 2
186 */
187 LCG32(int a, int s, int jumpPower, int longJumpPower) {
188 this.a = a | 1;
189 this.s = s;
190 this.jumpPower = jumpPower;
191 this.longJumpPower = longJumpPower;
192 }
193
194 @Override
195 public int stateAndUpdate() {
196 final int s0 = s;
197 s = M * s + a;
198 return s0;
199 }
200
201 @Override
202 public SubGen copyAndJump() {
203 final SubGen copy = new LCG32(a, s, jumpPower, longJumpPower);
204 s = LXMSupportTest.lcgAdvancePow2(s, M, a, jumpPower);
205 return copy;
206 }
207
208 @Override
209 public SubGen copyAndLongJump() {
210 final SubGen copy = new LCG32(a, s, jumpPower, longJumpPower);
211 s = LXMSupportTest.lcgAdvancePow2(s, M, a, longJumpPower);
212 return copy;
213 }
214 }
215
216 /**
217 * A xor-based generator using XoRoShiRo64.
218 *
219 * <p>The generator does not support jumps and simply returns a copy.
220 */
221 static class XBGXoRoShiRo64 extends AbstractXoRoShiRo64 implements SubGen {
222 /**
223 * Create an instance (note that jumping is not supported).
224 *
225 * @param seed seed
226 */
227 XBGXoRoShiRo64(int[] seed) {
228 super(seed);
229 }
230
231 /**
232 * @param seed0 seed element 0
233 * @param seed1 seed element 1
234 */
235 XBGXoRoShiRo64(int seed0, int seed1) {
236 super(seed0, seed1);
237 }
238
239 /**
240 * Copy constructor.
241 *
242 * @param source the source to copy
243 */
244 XBGXoRoShiRo64(XBGXoRoShiRo64 source) {
245 // There is no super-class copy constructor so just construct
246 // from the RNG state.
247 // Warning:
248 // This will not copy the cached state from source.
249 // This only matters if tests use nextBoolean.
250 this(source.state0, source.state1);
251 }
252
253 @Override
254 public int stateAndUpdate() {
255 final int s0 = state0;
256 next();
257 return s0;
258 }
259
260 @Override
261 public SubGen copyAndJump() {
262 // No jump function
263 return new XBGXoRoShiRo64(this);
264 }
265
266 @Override
267 public SubGen copyAndLongJump() {
268 // No jump function
269 return new XBGXoRoShiRo64(this);
270 }
271
272 @Override
273 protected int nextOutput() {
274 // Not used
275 return 0;
276 }
277 }
278
279 /**
280 * A composite LXM generator. Implements:
281 * <pre>
282 * s = state of LCG
283 * t = state of XBG
284 *
285 * generate():
286 * z <- mix(combine(w upper bits of s, w upper bits of t))
287 * s <- LCG state update
288 * t <- XBG state update
289 * </pre>
290 * <p>w is assumed to be 32-bits.
291 */
292 static class LXMGenerator extends IntProvider implements LongJumpableUniformRandomProvider {
293 /** Mix implementation. */
294 private final Mix mix;
295 /** LCG implementation. */
296 private final SubGen lcg;
297 /** XBG implementation. */
298 private final SubGen xbg;
299
300 /**
301 * Create a new instance.
302 * The jump and long jump of the LCG are assumed to appropriately match those of the XBG.
303 * This can be achieved by an XBG jump that wraps the period of the LCG; or advancing
304 * the LCG and leaving the XBG state unchanged, effectively rewinding the LXM generator.
305 *
306 * @param mix Mix implementation
307 * @param lcg LCG implementation
308 * @param xbg XBG implementation
309 */
310 LXMGenerator(Mix mix, SubGen lcg, SubGen xbg) {
311 this.lcg = lcg;
312 this.xbg = xbg;
313 this.mix = mix;
314 }
315
316 @Override
317 public int next() {
318 return mix.apply(lcg.stateAndUpdate(), xbg.stateAndUpdate());
319 }
320
321 @Override
322 public LXMGenerator jump() {
323 return new LXMGenerator(mix, lcg.copyAndJump(), xbg.copyAndJump());
324 }
325
326 @Override
327 public LXMGenerator longJump() {
328 return new LXMGenerator(mix, lcg.copyAndLongJump(), xbg.copyAndLongJump());
329 }
330 }
331
332 /**
333 * A factory for creating LXMGenerator objects.
334 */
335 interface LXMGeneratorFactory {
336 /**
337 * Return the size of the LCG long seed array.
338 *
339 * @return the LCG seed size
340 */
341 int lcgSeedSize();
342
343 /**
344 * Return the size of the XBG long seed array.
345 *
346 * @return the XBG seed size
347 */
348 int xbgSeedSize();
349
350 /**
351 * Return the size of the long seed array.
352 * The default implementation adds the size of the LCG and XBG seed.
353 *
354 * @return the seed size
355 */
356 default int seedSize() {
357 return lcgSeedSize() + xbgSeedSize();
358 }
359
360 /**
361 * Creates a new LXMGenerator.
362 *
363 * <p>Tests using the LXMGenerator assume the seed is a composite containing the
364 * LCG seed and then the XBG seed.
365 *
366 * @param seed the seed
367 * @return the generator
368 */
369 LXMGenerator create(int[] seed);
370
371 /**
372 * Gets the mix implementation. This is used to test initial output of the generator.
373 * The default implementation is {@link AbstractLXMTest#mixLea32(int, int)}.
374 *
375 * @return the mix
376 */
377 default Mix getMix() {
378 return AbstractLXMTest::mixLea32;
379 }
380 }
381
382 /**
383 * Test the LCG implementations. These tests should execute only once, and not
384 * for each instance of the abstract outer class (i.e. the test is not {@code @Nested}).
385 *
386 * <p>Note: The LCG implementation is not present in the main RNG core package and
387 * this test ensures an LCG update of:
388 * <pre>
389 * s = m * s + a
390 *
391 * s = state
392 * m = multiplier
393 * a = addition
394 * </pre>
395 *
396 * <p>A test is made to ensure the LCG can perform jump and long jump operations using
397 * small jumps that can be verified by an equal number of single state updates.
398 */
399 static class LCGTest {
400 /** A count {@code k} where a jump of {@code 2^k} will wrap the LCG state. */
401 private static final int NO_JUMP = -1;
402 /** A count {@code k=2} for a jump of {@code 2^k}, or 4 cycles. */
403 private static final int JUMP = 2;
404 /** A count {@code k=4} for a long jump of {@code 2^k}, or 16 cycles. */
405 private static final int LONG_JUMP = 4;
406
407 @RepeatedTest(value = 10)
408 void testLCG32DefaultJump() {
409 final SplittableRandom rng = new SplittableRandom();
410 final int state = rng.nextInt();
411 final int add = rng.nextInt();
412 final SubGen lcg1 = new LCG32(add, state);
413 final SubGen lcg2 = new LCG32(add, state, 0, 16);
414 for (int j = 0; j < 10; j++) {
415 Assertions.assertEquals(lcg1.stateAndUpdate(), lcg2.stateAndUpdate(),
416 () -> String.format("seed %d,%d", state, add));
417 }
418 lcg1.copyAndJump();
419 lcg2.copyAndJump();
420 for (int j = 0; j < 10; j++) {
421 Assertions.assertEquals(lcg1.stateAndUpdate(), lcg2.stateAndUpdate(),
422 () -> String.format("seed %d,%d", state, add));
423 }
424 lcg1.copyAndLongJump();
425 lcg2.copyAndLongJump();
426 for (int j = 0; j < 10; j++) {
427 Assertions.assertEquals(lcg1.stateAndUpdate(), lcg2.stateAndUpdate(),
428 () -> String.format("seed %d,%d", state, add));
429 }
430 }
431
432 @RepeatedTest(value = 10)
433 void testLCG32() {
434 final SplittableRandom rng = new SplittableRandom();
435 final int state = rng.nextInt();
436 final int add = rng.nextInt();
437 int s = state;
438 final int a = add | 1;
439 final SubGen lcg = new LCG32(add, state, NO_JUMP, NO_JUMP);
440 for (int j = 0; j < 10; j++) {
441 Assertions.assertEquals(s, lcg.stateAndUpdate(),
442 () -> String.format("seed %d,%d", state, add));
443 s = LXMSupport.M32 * s + a;
444 }
445 }
446
447 @RepeatedTest(value = 10)
448 void testLCG32Jump() {
449 final SplittableRandom rng = new SplittableRandom();
450 final int state = rng.nextInt();
451 final int add = rng.nextInt();
452 final Supplier<String> msg = () -> String.format("seed %d,%d", state, add);
453 int s = state;
454 final int a = add | 1;
455 final SubGen lcg = new LCG32(add, state, JUMP, LONG_JUMP);
456
457 final SubGen copy1 = lcg.copyAndJump();
458 for (int j = 1 << JUMP; j-- != 0;) {
459 Assertions.assertEquals(s, copy1.stateAndUpdate(), msg);
460 s = LXMSupport.M32 * s + a;
461 }
462 Assertions.assertEquals(s, lcg.stateAndUpdate(), msg);
463 s = LXMSupport.M32 * s + a;
464
465 final SubGen copy2 = lcg.copyAndLongJump();
466 for (int j = 1 << LONG_JUMP; j-- != 0;) {
467 Assertions.assertEquals(s, copy2.stateAndUpdate(), msg);
468 s = LXMSupport.M32 * s + a;
469 }
470 Assertions.assertEquals(s, lcg.stateAndUpdate(), msg);
471 }
472 }
473
474 /**
475 * Test the XBG implementations. These tests should execute only once, and not
476 * for each instance of the abstract outer class (i.e. the test is not {@code @Nested}).
477 *
478 * <p>Note: The XBG implementation are extensions of RNGs already verified against
479 * reference implementations. These tests ensure that the upper bits of the state is
480 * identical after {@code n} cycles then a jump; or a jump then {@code n} cycles.
481 * This is the functionality required for a jumpable XBG generator.
482 */
483 static class XBGTest {
484
485 @RepeatedTest(value = 5)
486 void testXBGXoRoShiRo64NoJump() {
487 final SplittableRandom r = new SplittableRandom();
488 assertNoJump(new XBGXoRoShiRo64(r.nextInt(), r.nextInt()));
489 }
490
491 void assertNoJump(SubGen g) {
492 final SubGen g1 = g.copyAndJump();
493 Assertions.assertNotSame(g, g1);
494 for (int i = 0; i < 10; i++) {
495 Assertions.assertEquals(g.stateAndUpdate(), g1.stateAndUpdate());
496 }
497 final SubGen g2 = g.copyAndLongJump();
498 Assertions.assertNotSame(g, g2);
499 for (int i = 0; i < 10; i++) {
500 Assertions.assertEquals(g.stateAndUpdate(), g2.stateAndUpdate());
501 }
502 }
503
504 // Note: These test are duplicates of the XBGTest in the source64 package
505 // which does have jumpable XBG sub-generators. The tests work even when
506 // the jump is not implemented and is a simple copy operation.
507
508 @RepeatedTest(value = 5)
509 void testXBGXoRoShiRo64Jump() {
510 assertJumpAndCycle(ThreadLocalRandom.current().nextLong(), 2, XBGXoRoShiRo64::new, SubGen::copyAndJump);
511 }
512
513 @RepeatedTest(value = 5)
514 void testXBGXoRoShiRo64LongJump() {
515 assertJumpAndCycle(ThreadLocalRandom.current().nextLong(), 2, XBGXoRoShiRo64::new, SubGen::copyAndLongJump);
516 }
517
518 /**
519 * Assert alternating jump and cycle of the XBG.
520 *
521 * <p>This test verifies one generator can jump and advance {@code n} steps
522 * while the other generator advances {@code n} steps then jumps. The two should
523 * be in the same state. The copy left behind by the first jump should match the
524 * state of the other generator as it cycles.
525 *
526 * @param testSeed A seed for the test
527 * @param seedSize The seed size
528 * @param factory Factory to create the XBG
529 * @param jump XBG jump function
530 */
531 private static void assertJumpAndCycle(long testSeed, int seedSize,
532 Function<int[], SubGen> factory, UnaryOperator<SubGen> jump) {
533 final SplittableRandom r = new SplittableRandom(testSeed);
534 final int[] seed = r.ints(seedSize).toArray();
535 final int[] steps = createSteps(r, seedSize);
536 final int cycles = 2 * seedSize;
537
538 final SubGen rng1 = factory.apply(seed);
539 final SubGen rng2 = factory.apply(seed);
540
541 // Try jumping and stepping with a number of steps up to the seed size
542 for (int i = 0; i < steps.length; i++) {
543 final int step = steps[i];
544 final int index = i;
545 // Jump 1
546 final SubGen copy = jump.apply(rng1);
547 // Advance 2; it should match the copy
548 for (int j = 0; j < step; j++) {
549 Assertions.assertEquals(rng2.stateAndUpdate(), copy.stateAndUpdate(),
550 () -> String.format("[%d] Incorrect trailing copy, seed=%d", index, testSeed));
551 // Advance in parallel
552 rng1.stateAndUpdate();
553 }
554 // Catch up 2; it should match 1
555 jump.apply(rng2);
556 for (int j = 0; j < cycles; j++) {
557 Assertions.assertEquals(rng1.stateAndUpdate(), rng2.stateAndUpdate(),
558 () -> String.format("[%d] Incorrect after catch up jump, seed=%d", index, testSeed));
559 }
560 }
561 }
562 }
563
564 /////////////////////////////////////
565 // Tests for the LXM implementation
566 /////////////////////////////////////
567
568 /**
569 * Gets the factory to create a composite LXM generator.
570 * The generator is used to provide reference output for the generator under test.
571 *
572 * @return the factory
573 */
574 abstract LXMGeneratorFactory getFactory();
575
576 /**
577 * Creates a new instance of the RNG under test.
578 *
579 * @param seed the seed
580 * @return the RNG
581 */
582 abstract LongJumpableUniformRandomProvider create(int[] seed);
583
584 /**
585 * Gets a stream of reference data. Each Argument consist of the int array seed and
586 * the int array of the expected output from the LXM generator.
587 * <pre>
588 * int[] seed;
589 * int[] expected;
590 * return Stream.of(Arguments.of(seed, expected));
591 * </pre>
592 *
593 * @return the reference data
594 */
595 abstract Stream<Arguments> getReferenceData();
596
597 /**
598 * Test the reference data with the LXM generator.
599 * The reference data should be created with a reference implementation of the
600 * LXM algorithm, for example the implementations in JDK 17.
601 */
602 @ParameterizedTest
603 @MethodSource(value = "getReferenceData")
604 final void testReferenceData(int[] seed, int[] expected) {
605 RandomAssert.assertEquals(expected, create(seed));
606 }
607
608 /**
609 * Test the reference data with the composite LXM generator. This ensures the composite
610 * correctly implements the LXM algorithm.
611 */
612 @ParameterizedTest
613 @MethodSource(value = "getReferenceData")
614 final void testReferenceDataWithComposite(int[] seed, int[] expected) {
615 RandomAssert.assertEquals(expected, getFactory().create(seed));
616 }
617
618 /**
619 * Test initial output is the mix of the most significant bits of the LCG and XBG state.
620 * This test ensures the LXM algorithm applies the mix function to the current state
621 * before state update. Thus the initial output should be a direct mix of the seed state.
622 */
623 @RepeatedTest(value = 5)
624 final void testInitialOutput() {
625 final int[] seed = createRandomSeed();
626 // Upper 32 bits of LCG state
627 final int s = seed[getFactory().lcgSeedSize() / 2];
628 // Upper 32 bits of XBG state
629 final int t = seed[getFactory().lcgSeedSize()];
630 Assertions.assertEquals(getFactory().getMix().apply(s, t), create(seed).nextInt());
631 }
632
633 @Test
634 final void testConstructorWithZeroSeedIsPartiallyFunctional() {
635 // Note: It is impractical to demonstrate the RNG is partially functional:
636 // output quality may be statistically poor and the period is that of the LCG.
637 // The test demonstrates the RNG is not totally non-functional with a zero seed
638 // which is not the case for a standard XBG.
639 final int seedSize = getFactory().seedSize();
640 RandomAssert.assertNextLongNonZeroOutput(create(new int[seedSize]), 0, seedSize);
641 }
642
643 @ParameterizedTest
644 @MethodSource(value = "getReferenceData")
645 final void testConstructorWithoutFullLengthSeed(int[] seed) {
646 // Hit the case when the input seed is self-seeded when not full length
647 final int seedSize = getFactory().seedSize();
648 RandomAssert.assertNextIntNonZeroOutput(create(new int[] {seed[0]}),
649 seedSize, seedSize);
650 }
651
652 @RepeatedTest(value = 5)
653 final void testConstructorIgnoresFinalAddParameterSeedBit() {
654 final int[] seed1 = createRandomSeed();
655 final int[] seed2 = seed1.clone();
656 final int seedSize = getFactory().seedSize();
657 // seed1 unset final add parameter bit; seed2 set final bit
658 final int index = getFactory().lcgSeedSize() / 2 - 1;
659 seed1[index] &= -1 << 1;
660 seed2[index] |= 1;
661 Assertions.assertEquals(1, seed1[index] ^ seed2[index]);
662 final LongJumpableUniformRandomProvider rng1 = create(seed1);
663 final LongJumpableUniformRandomProvider rng2 = create(seed2);
664 RandomAssert.assertNextLongEquals(seedSize * 2, rng1, rng2);
665 }
666
667 @ParameterizedTest
668 @MethodSource(value = "getReferenceData")
669 final void testJump(int[] seed, int[] expected) {
670 final int[] expectedAfter = createExpectedSequence(seed, expected.length, false);
671 RandomAssert.assertJumpEquals(expected, expectedAfter, create(seed));
672 }
673
674 @ParameterizedTest
675 @MethodSource(value = "getReferenceData")
676 final void testLongJump(int[] seed, int[] expected) {
677 final int[] expectedAfter = createExpectedSequence(seed, expected.length, true);
678 RandomAssert.assertLongJumpEquals(expected, expectedAfter, create(seed));
679 }
680
681 @RepeatedTest(value = 5)
682 final void testJumpAndOutput() {
683 assertJumpAndOutput(false, ThreadLocalRandom.current().nextLong());
684 }
685
686 @RepeatedTest(value = 5)
687 final void testLongJumpAndOutput() {
688 assertJumpAndOutput(true, ThreadLocalRandom.current().nextLong());
689 }
690
691 /**
692 * Assert alternating jump and output from the LXM generator and the
693 * reference composite LXM generator.
694 *
695 * <p>The composite generator uses an LCG that is tested to match
696 * output after a jump (see {@link LCGTest} or a series of cycles.
697 * The XBG generator is <em>assumed</em> to function similarly.
698 * The {@link XBGTest} verifies that the generator is in the same
699 * state when using {@code n} steps then a jump; or a jump then
700 * {@code n} steps.
701 *
702 * <p>This test verifies one LXM generator can jump and advance
703 * {@code n} steps while the other generator advances {@code n}
704 * steps then jumps. The two should be in the same state. The copy
705 * left behind by the first jump should match the output of the other
706 * generator as it cycles.
707 *
708 * @param longJump If true use the long jump; otherwise the jump
709 * @param testSeed A seed for the test
710 */
711 private void assertJumpAndOutput(boolean longJump, long testSeed) {
712 final SplittableRandom r = new SplittableRandom(testSeed);
713 final int[] seed = createRandomSeed(r::nextInt);
714 final int[] steps = createSteps(r);
715 final int cycles = getFactory().seedSize();
716
717 LongJumpableUniformRandomProvider rng1 = create(seed);
718 LongJumpableUniformRandomProvider rng2 = getFactory().create(seed);
719
720 final UnaryOperator<LongJumpableUniformRandomProvider> jump = longJump ?
721 x -> (LongJumpableUniformRandomProvider) x.longJump() :
722 x -> (LongJumpableUniformRandomProvider) x.jump();
723
724 // Alternate jumping and stepping then stepping and jumping.
725 for (int i = 0; i < steps.length; i++) {
726 final int step = steps[i];
727 final int index = i;
728 // Jump 1
729 LongJumpableUniformRandomProvider copy = jump.apply(rng1);
730 // Advance 2; it should match the copy
731 for (int j = 0; j < step; j++) {
732 Assertions.assertEquals(rng2.nextInt(), copy.nextInt(),
733 () -> String.format("[%d] Incorrect trailing copy, seed=%d", index, testSeed));
734 // Advance 1 in parallel
735 rng1.nextInt();
736 }
737 // Catch up 2; it should match 1
738 jump.apply(rng2);
739 for (int j = 0; j < cycles; j++) {
740 Assertions.assertEquals(rng1.nextInt(), rng2.nextInt(),
741 () -> String.format("[%d] Incorrect after catch up jump, seed=%d", index, testSeed));
742 }
743
744 // Swap
745 copy = rng1;
746 rng1 = rng2;
747 rng2 = copy;
748 }
749 }
750
751 @RepeatedTest(value = 5)
752 final void testSaveRestoreAfterJump() {
753 assertSaveRestoreAfterJump(false, ThreadLocalRandom.current().nextLong());
754 }
755
756 @RepeatedTest(value = 5)
757 final void testSaveRestoreAfterLongJump() {
758 assertSaveRestoreAfterJump(true, ThreadLocalRandom.current().nextLong());
759 }
760
761 /**
762 * Assert that the precomputation of the jump coefficients functions
763 * with saved/restore.
764 *
765 * @param longJump If true use the long jump; otherwise the jump
766 * @param testSeed A seed for the test
767 */
768 private void assertSaveRestoreAfterJump(boolean longJump, long testSeed) {
769 final SplittableRandom r = new SplittableRandom(testSeed);
770 final int cycles = getFactory().seedSize();
771
772 final UnaryOperator<LongJumpableUniformRandomProvider> jump = longJump ?
773 x -> (LongJumpableUniformRandomProvider) x.longJump() :
774 x -> (LongJumpableUniformRandomProvider) x.jump();
775
776 // Create 2 generators and jump them
777 final LongJumpableUniformRandomProvider rng1 = create(createRandomSeed(r::nextInt));
778 final LongJumpableUniformRandomProvider rng2 = create(createRandomSeed(r::nextInt));
779 jump.apply(rng1);
780 jump.apply(rng2);
781
782 // Restore the state from one to the other
783 RestorableUniformRandomProvider g1 = (RestorableUniformRandomProvider) rng1;
784 RestorableUniformRandomProvider g2 = (RestorableUniformRandomProvider) rng2;
785 g2.restoreState(g1.saveState());
786
787 // They should have the same output
788 RandomAssert.assertNextLongEquals(cycles, rng1, rng2);
789
790 // They should have the same output after a jump too
791 jump.apply(rng1);
792 jump.apply(rng2);
793
794 RandomAssert.assertNextLongEquals(cycles, rng1, rng2);
795 }
796
797 /**
798 * Create the expected sequence after a jump by advancing the XBG and LCG
799 * sub-generators. This is done by creating and jumping the composite LXM
800 * generator.
801 *
802 * @param seed the seed
803 * @param length the length of the expected sequence
804 * @param longJump If true use the long jump; otherwise the jump
805 * @return the expected sequence
806 */
807 private int[] createExpectedSequence(int[] seed, int length, boolean longJump) {
808 final LXMGenerator rng = getFactory().create(seed);
809 if (longJump) {
810 rng.longJump();
811 } else {
812 rng.jump();
813 }
814 return IntStream.generate(rng::nextInt).limit(length).toArray();
815 }
816
817 /**
818 * Creates a random seed of the correct length. Used when the seed can be anything.
819 *
820 * @return the seed
821 */
822 private int[] createRandomSeed() {
823 return createRandomSeed(new SplittableRandom()::nextInt);
824 }
825
826 /**
827 * Creates a random seed of the correct length using the provided generator.
828 * Used when the seed can be anything.
829 *
830 * @param gen the generator
831 * @return the seed
832 */
833 private int[] createRandomSeed(IntSupplier gen) {
834 return IntStream.generate(gen).limit(getFactory().seedSize()).toArray();
835 }
836
837 /**
838 * Creates a random permutation of steps in [1, seed size].
839 * The seed size is obtained from the LXM generator factory.
840 *
841 * @param rng Source of randomness
842 * @return the steps
843 */
844 private int[] createSteps(SplittableRandom rng) {
845 return createSteps(rng, getFactory().seedSize());
846 }
847
848 /**
849 * Creates a random permutation of steps in [1, seed size].
850 *
851 * @param rng Source of randomness
852 * @param seedSize Seed size
853 * @return the steps
854 */
855 private static int[] createSteps(SplittableRandom rng, int seedSize) {
856 final int[] steps = IntStream.rangeClosed(1, seedSize).toArray();
857 // Fisher-Yates shuffle
858 for (int i = steps.length; i > 1; i--) {
859 final int j = rng.nextInt(i);
860 final int tmp = steps[i - 1];
861 steps[i - 1] = steps[j];
862 steps[j] = tmp;
863 }
864 return steps;
865 }
866 }