001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018package org.apache.commons.rng.core; 019 020import java.util.Arrays; 021import org.apache.commons.rng.RestorableUniformRandomProvider; 022import org.apache.commons.rng.RandomProviderState; 023 024/** 025 * Base class with default implementation for common methods. 026 */ 027public abstract class BaseProvider 028 implements RestorableUniformRandomProvider { 029 /** 030 * The fractional part of the golden ratio, phi, scaled to 64-bits and rounded to odd. 031 * <pre> 032 * phi = (sqrt(5) - 1) / 2) * 2^64 033 * </pre> 034 * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio">Golden ratio</a> 035 */ 036 private static final long GOLDEN_RATIO_64 = 0x9e3779b97f4a7c15L; 037 /** The fractional part of the golden ratio, phi, scaled to 32-bits and rounded to odd. */ 038 private static final int GOLDEN_RATIO_32 = 0x9e3779b9; 039 040 /** Create an instance. */ 041 public BaseProvider() {} 042 043 /** {@inheritDoc} */ 044 @Override 045 public RandomProviderState saveState() { 046 return new RandomProviderDefaultState(getStateInternal()); 047 } 048 049 /** {@inheritDoc} */ 050 @Override 051 public void restoreState(RandomProviderState state) { 052 if (state instanceof RandomProviderDefaultState) { 053 setStateInternal(((RandomProviderDefaultState) state).getState()); 054 } else { 055 throw new IllegalArgumentException("Foreign instance"); 056 } 057 } 058 059 /** {@inheritDoc} */ 060 @Override 061 public String toString() { 062 return getClass().getName(); 063 } 064 065 /** 066 * Combine parent and subclass states. 067 * This method must be called by all subclasses in order to ensure 068 * that state can be restored in case some of it is stored higher 069 * up in the class hierarchy. 070 * 071 * I.e. the body of the overridden {@link #getStateInternal()}, 072 * will end with a statement like the following: 073 * <pre> 074 * <code> 075 * return composeStateInternal(state, 076 * super.getStateInternal()); 077 * </code> 078 * </pre> 079 * where {@code state} is the state needed and defined by the class 080 * where the method is overridden. 081 * 082 * @param state State of the calling class. 083 * @param parentState State of the calling class' parent. 084 * @return the combined state. 085 * Bytes that belong to the local state will be stored at the 086 * beginning of the resulting array. 087 */ 088 protected byte[] composeStateInternal(byte[] state, 089 byte[] parentState) { 090 final int len = parentState.length + state.length; 091 final byte[] c = new byte[len]; 092 System.arraycopy(state, 0, c, 0, state.length); 093 System.arraycopy(parentState, 0, c, state.length, parentState.length); 094 return c; 095 } 096 097 /** 098 * Splits the given {@code state} into a part to be consumed by the caller 099 * 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}