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