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
18 package org.apache.commons.rng.core;
19
20 import java.util.Arrays;
21 import org.apache.commons.rng.RestorableUniformRandomProvider;
22 import org.apache.commons.rng.RandomProviderState;
23
24 /**
25 * Base class with default implementation for common methods.
26 */
27 public abstract class BaseProvider
28 implements RestorableUniformRandomProvider {
29 /**
30 * The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd.
31 * <pre>
32 * phi = (sqrt(5) - 1) / 2) * 2^64
33 * </pre>
34 * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio">Golden ratio</a>
35 */
36 private static final long GOLDEN_RATIO_64 = 0x9e3779b97f4a7c15L;
37 /** The fractional part of the golden ratio, phi, scaled to 32-bits and rounded to odd. */
38 private static final int GOLDEN_RATIO_32 = 0x9e3779b9;
39
40 /** Create an instance. */
41 public BaseProvider() {}
42
43 /** {@inheritDoc} */
44 @Override
45 public RandomProviderState saveState() {
46 return new RandomProviderDefaultState(getStateInternal());
47 }
48
49 /** {@inheritDoc} */
50 @Override
51 public void restoreState(RandomProviderState state) {
52 if (state instanceof RandomProviderDefaultState) {
53 setStateInternal(((RandomProviderDefaultState) state).getState());
54 } else {
55 throw new IllegalArgumentException("Foreign instance");
56 }
57 }
58
59 /** {@inheritDoc} */
60 @Override
61 public String toString() {
62 return getClass().getName();
63 }
64
65 /**
66 * Combine parent and subclass states.
67 * This method must be called by all subclasses in order to ensure
68 * that state can be restored in case some of it is stored higher
69 * up in the class hierarchy.
70 *
71 * I.e. the body of the overridden {@link #getStateInternal()},
72 * will end with a statement like the following:
73 * <pre>
74 * <code>
75 * return composeStateInternal(state,
76 * super.getStateInternal());
77 * </code>
78 * </pre>
79 * where {@code state} is the state needed and defined by the class
80 * where the method is overridden.
81 *
82 * @param state State of the calling class.
83 * @param parentState State of the calling class' parent.
84 * @return the combined state.
85 * Bytes that belong to the local state will be stored at the
86 * beginning of the resulting array.
87 */
88 protected byte[] composeStateInternal(byte[] state,
89 byte[] parentState) {
90 final int len = parentState.length + state.length;
91 final byte[] c = new byte[len];
92 System.arraycopy(state, 0, c, 0, state.length);
93 System.arraycopy(parentState, 0, c, state.length, parentState.length);
94 return c;
95 }
96
97 /**
98 * Splits the given {@code state} into a part to be consumed by the caller
99 * in order to restore its local state, while the reminder is passed to
100 * the parent class.
101 *
102 * I.e. the body of the overridden {@link #setStateInternal(byte[])},
103 * will contain statements like the following:
104 * <pre>
105 * <code>
106 * final byte[][] s = splitState(state, localStateLength);
107 * // Use "s[0]" to recover the local state.
108 * super.setStateInternal(s[1]);
109 * </code>
110 * </pre>
111 * where {@code state} is the combined state of the calling class and of
112 * all its parents.
113 *
114 * @param state State.
115 * The local state must be stored at the beginning of the array.
116 * @param localStateLength Number of elements that will be consumed by the
117 * locally defined state.
118 * @return the local state (in slot 0) and the parent state (in slot 1).
119 * @throws IllegalStateException if {@code state.length < localStateLength}.
120 */
121 protected byte[][] splitStateInternal(byte[] state,
122 int localStateLength) {
123 checkStateSize(state, localStateLength);
124
125 final byte[] local = new byte[localStateLength];
126 System.arraycopy(state, 0, local, 0, localStateLength);
127 final int parentLength = state.length - localStateLength;
128 final byte[] parent = new byte[parentLength];
129 System.arraycopy(state, localStateLength, parent, 0, parentLength);
130
131 return new byte[][] {local, parent};
132 }
133
134 /**
135 * Creates a snapshot of the RNG state.
136 *
137 * @return the internal state.
138 */
139 protected byte[] getStateInternal() {
140 // This class has no state (and is the top-level class that
141 // declares this method).
142 return new byte[0];
143 }
144
145 /**
146 * Resets the RNG to the given {@code state}.
147 *
148 * @param state State (previously obtained by a call to
149 * {@link #getStateInternal()}).
150 * @throws IllegalStateException if the size of the given array is
151 * not consistent with the state defined by this class.
152 *
153 * @see #checkStateSize(byte[],int)
154 */
155 protected void setStateInternal(byte[] state) {
156 if (state.length != 0) {
157 // This class has no state.
158 throw new IllegalStateException("State not fully recovered by subclasses");
159 }
160 }
161
162 /**
163 * Simple filling procedure.
164 * It will
165 * <ol>
166 * <li>
167 * fill the beginning of {@code state} by copying
168 * {@code min(seed.length, state.length)} elements from
169 * {@code seed},
170 * </li>
171 * <li>
172 * set all remaining elements of {@code state} with non-zero
173 * values (even if {@code seed.length < state.length}).
174 * </li>
175 * </ol>
176 *
177 * @param state State. Must be allocated.
178 * @param seed Seed. Cannot be null.
179 */
180 protected void fillState(int[] state,
181 int[] seed) {
182 final int stateSize = state.length;
183 final int seedSize = seed.length;
184 System.arraycopy(seed, 0, state, 0, Math.min(seedSize, stateSize));
185
186 if (seedSize < stateSize) {
187 for (int i = seedSize; i < stateSize; i++) {
188 state[i] = (int) (scrambleWell(state[i - seed.length], i) & 0xffffffffL);
189 }
190 }
191 }
192
193 /**
194 * Simple filling procedure.
195 * It will
196 * <ol>
197 * <li>
198 * fill the beginning of {@code state} by copying
199 * {@code min(seed.length, state.length)} elements from
200 * {@code seed},
201 * </li>
202 * <li>
203 * set all remaining elements of {@code state} with non-zero
204 * values (even if {@code seed.length < state.length}).
205 * </li>
206 * </ol>
207 *
208 * @param state State. Must be allocated.
209 * @param seed Seed. Cannot be null.
210 */
211 protected void fillState(long[] state,
212 long[] seed) {
213 final int stateSize = state.length;
214 final int seedSize = seed.length;
215 System.arraycopy(seed, 0, state, 0, Math.min(seedSize, stateSize));
216
217 if (seedSize < stateSize) {
218 for (int i = seedSize; i < stateSize; i++) {
219 state[i] = scrambleWell(state[i - seed.length], i);
220 }
221 }
222 }
223
224 /**
225 * Checks that the {@code state} has the {@code expected} size.
226 *
227 * @param state State.
228 * @param expected Expected length of {@code state} array.
229 * @throws IllegalStateException if {@code state.length < expected}.
230 * @deprecated Method is used internally and should be made private in
231 * some future release.
232 */
233 @Deprecated
234 protected void checkStateSize(byte[] state,
235 int expected) {
236 if (state.length < expected) {
237 throw new IllegalStateException("State size must be larger than " +
238 expected + " but was " + state.length);
239 }
240 }
241
242 /**
243 * Checks whether {@code index} is in the range {@code [min, max]}.
244 *
245 * @param min Lower bound.
246 * @param max Upper bound.
247 * @param index Value that must lie within the {@code [min, max]} interval.
248 * @throws IndexOutOfBoundsException if {@code index} is not within the
249 * {@code [min, max]} interval.
250 */
251 protected void checkIndex(int min,
252 int max,
253 int index) {
254 if (index < min ||
255 index > max) {
256 throw new IndexOutOfBoundsException(index + " is out of interval [" +
257 min + ", " +
258 max + "]");
259 }
260 }
261
262 /**
263 * Transformation used to scramble the initial state of
264 * a generator.
265 *
266 * @param n Seed element.
267 * @param mult Multiplier.
268 * @param shift Shift.
269 * @param add Offset.
270 * @return the transformed seed element.
271 */
272 private static long scramble(long n,
273 long mult,
274 int shift,
275 int add) {
276 // Code inspired from "AbstractWell" class.
277 return mult * (n ^ (n >> shift)) + add;
278 }
279
280 /**
281 * Transformation used to scramble the initial state of
282 * a generator.
283 *
284 * @param n Seed element.
285 * @param add Offset.
286 * @return the transformed seed element.
287 * @see #scramble(long,long,int,int)
288 */
289 private static long scrambleWell(long n,
290 int add) {
291 // Code inspired from "AbstractWell" class.
292 return scramble(n, 1812433253L, 30, add);
293 }
294
295 /**
296 * Extend the seed to the specified minimum length. If the seed is equal or greater than the
297 * minimum length, return the same seed unchanged. Otherwise:
298 * <ol>
299 * <li>Create a new array of the specified length
300 * <li>Copy all elements of the seed into the array
301 * <li>Fill the remaining values. The additional values will have at most one occurrence
302 * of zero. If the original seed is all zero, the first extended value will be non-zero.
303 * </li>
304 * </ol>
305 *
306 * <p>This method can be used in constructors that must pass their seed to the super class
307 * to avoid a duplication of seed expansion to the minimum length required by the super class
308 * and the class:
309 * <pre>
310 * public RNG extends AnotherRNG {
311 * public RNG(long[] seed) {
312 * super(seed = extendSeed(seed, SEED_SIZE));
313 * // Use seed for additional state ...
314 * }
315 * }
316 * </pre>
317 *
318 * <p>Note using the state filling procedure provided in {@link #fillState(long[], long[])}
319 * is not possible as it is an instance method. Calling a seed extension routine must use a
320 * static method.
321 *
322 * <p>This method functions as if the seed has been extended using a
323 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64}
324 * generator seeded with {@code seed[0]}, or zero if the input seed length is zero.
325 * <pre>
326 * if (seed.length < length) {
327 * final long[] s = Arrays.copyOf(seed, length);
328 * final SplitMix64 rng = new SplitMix64(s[0]);
329 * for (int i = seed.length; i < length; i++) {
330 * s[i] = rng.nextLong();
331 * }
332 * return s;
333 * }</pre>
334 *
335 * @param seed Input seed
336 * @param length The minimum length
337 * @return the seed
338 * @since 1.5
339 */
340 protected static long[] extendSeed(long[] seed, int length) {
341 if (seed.length < length) {
342 final long[] s = Arrays.copyOf(seed, length);
343 // Fill the rest as if using a SplitMix64 RNG
344 long x = s[0];
345 for (int i = seed.length; i < length; i++) {
346 x += GOLDEN_RATIO_64;
347 s[i] = stafford13(x);
348 }
349 return s;
350 }
351 return seed;
352 }
353
354 /**
355 * Extend the seed to the specified minimum length. If the seed is equal or greater than the
356 * minimum length, return the same seed unchanged. Otherwise:
357 * <ol>
358 * <li>Create a new array of the specified length
359 * <li>Copy all elements of the seed into the array
360 * <li>Fill the remaining values. The additional values will have at most one occurrence
361 * of zero. If the original seed is all zero, the first extended value will be non-zero.
362 * </li>
363 * </ol>
364 *
365 * <p>This method can be used in constructors that must pass their seed to the super class
366 * to avoid a duplication of seed expansion to the minimum length required by the super class
367 * and the class:
368 * <pre>
369 * public RNG extends AnotherRNG {
370 * public RNG(int[] seed) {
371 * super(seed = extendSeed(seed, SEED_SIZE));
372 * // Use seed for additional state ...
373 * }
374 * }
375 * </pre>
376 *
377 * <p>Note using the state filling procedure provided in {@link #fillState(int[], int[])}
378 * is not possible as it is an instance method. Calling a seed extension routine must use a
379 * static method.
380 *
381 * <p>This method functions as if the seed has been extended using a
382 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64}-style 32-bit
383 * generator seeded with {@code seed[0]}, or zero if the input seed length is zero. The
384 * generator uses the 32-bit mixing function from MurmurHash3.
385 *
386 * @param seed Input seed
387 * @param length The minimum length
388 * @return the seed
389 * @since 1.5
390 */
391 protected static int[] extendSeed(int[] seed, int length) {
392 if (seed.length < length) {
393 final int[] s = Arrays.copyOf(seed, length);
394 // Fill the rest as if using a SplitMix64-style RNG for 32-bit output
395 int x = s[0];
396 for (int i = seed.length; i < length; i++) {
397 x += GOLDEN_RATIO_32;
398 s[i] = murmur3(x);
399 }
400 return s;
401 }
402 return seed;
403 }
404
405 /**
406 * Perform variant 13 of David Stafford's 64-bit mix function.
407 * This is the mix function used in the
408 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} RNG.
409 *
410 * <p>This is ranked first of the top 14 Stafford mixers.
411 *
412 * <p>This function can be used to mix the bits of a {@code long} value to
413 * obtain a better distribution and avoid collisions between similar values.
414 *
415 * @param x the input value
416 * @return the output value
417 * @see <a href="https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html">Better
418 * Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a>
419 */
420 private static long stafford13(long x) {
421 x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L;
422 x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL;
423 return x ^ (x >>> 31);
424 }
425
426 /**
427 * Perform the finalising 32-bit mix function of Austin Appleby's MurmurHash3.
428 *
429 * <p>This function can be used to mix the bits of a {@code int} value to
430 * obtain a better distribution and avoid collisions between similar values.
431 *
432 * @param x the input value
433 * @return the output value
434 * @see <a href="https://github.com/aappleby/smhasher">SMHasher</a>
435 */
436 private static int murmur3(int x) {
437 x = (x ^ (x >>> 16)) * 0x85ebca6b;
438 x = (x ^ (x >>> 13)) * 0xc2b2ae35;
439 return x ^ (x >>> 16);
440 }
441 }