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 * <p>Note: It is not recommended to use this method from a constructor 178 * as it can be overridden by subclasses possibly leading to unexpected behaviour. 179 * Future versions may remove this method, or change it to static. 180 * 181 * @param state State. Must be allocated. 182 * @param seed Seed. Cannot be null. 183 */ 184 protected void fillState(int[] state, 185 int[] seed) { 186 final int stateSize = state.length; 187 final int seedSize = seed.length; 188 System.arraycopy(seed, 0, state, 0, Math.min(seedSize, stateSize)); 189 190 if (seedSize < stateSize) { 191 for (int i = seedSize; i < stateSize; i++) { 192 state[i] = (int) scrambleWell(state[i - seedSize], i); 193 } 194 } 195 } 196 197 /** 198 * Simple filling procedure. 199 * It will 200 * <ol> 201 * <li> 202 * fill the beginning of {@code state} by copying 203 * {@code min(seed.length, state.length)} elements from 204 * {@code seed}, 205 * </li> 206 * <li> 207 * set all remaining elements of {@code state} with non-zero 208 * values (even if {@code seed.length < state.length}). 209 * </li> 210 * </ol> 211 * 212 * <p>Note: It is not recommended to use this method from a constructor 213 * as it can be overridden by subclasses possibly leading to unexpected behaviour. 214 * Future versions may remove this method, or change it to static. 215 * 216 * @param state State. Must be allocated. 217 * @param seed Seed. Cannot be null. 218 */ 219 protected void fillState(long[] state, 220 long[] seed) { 221 final int stateSize = state.length; 222 final int seedSize = seed.length; 223 System.arraycopy(seed, 0, state, 0, Math.min(seedSize, stateSize)); 224 225 if (seedSize < stateSize) { 226 for (int i = seedSize; i < stateSize; i++) { 227 state[i] = scrambleWell(state[i - seedSize], i); 228 } 229 } 230 } 231 232 /** 233 * Checks that the {@code state} has the {@code expected} size. 234 * 235 * @param state State. 236 * @param expected Expected length of {@code state} array. 237 * @throws IllegalStateException if {@code state.length < expected}. 238 * @deprecated Method is used internally and should be made private in 239 * some future release. 240 */ 241 @Deprecated 242 protected void checkStateSize(byte[] state, 243 int expected) { 244 if (state.length < expected) { 245 throw new IllegalStateException("State size must be larger than " + 246 expected + " but was " + state.length); 247 } 248 } 249 250 /** 251 * Checks whether {@code index} is in the range {@code [min, max]}. 252 * 253 * @param min Lower bound. 254 * @param max Upper bound. 255 * @param index Value that must lie within the {@code [min, max]} interval. 256 * @throws IndexOutOfBoundsException if {@code index} is not within the 257 * {@code [min, max]} interval. 258 */ 259 protected void checkIndex(int min, 260 int max, 261 int index) { 262 if (index < min || 263 index > max) { 264 throw new IndexOutOfBoundsException(index + " is out of interval [" + 265 min + ", " + 266 max + "]"); 267 } 268 } 269 270 /** 271 * Transformation used to scramble the initial state of 272 * a generator. 273 * 274 * @param n Seed element. 275 * @param mult Multiplier. 276 * @param shift Shift. 277 * @param add Offset. 278 * @return the transformed seed element. 279 */ 280 private static long scramble(long n, 281 long mult, 282 int shift, 283 int add) { 284 // Code inspired from "AbstractWell" class. 285 return mult * (n ^ (n >> shift)) + add; 286 } 287 288 /** 289 * Transformation used to scramble the initial state of 290 * a generator. 291 * 292 * @param n Seed element. 293 * @param add Offset. 294 * @return the transformed seed element. 295 * @see #scramble(long,long,int,int) 296 */ 297 private static long scrambleWell(long n, 298 int add) { 299 // Code inspired from "AbstractWell" class. 300 return scramble(n, 1812433253L, 30, add); 301 } 302 303 /** 304 * Extend the seed to the specified minimum length. If the seed is equal or greater than the 305 * minimum length, return the same seed unchanged. Otherwise: 306 * <ol> 307 * <li>Create a new array of the specified length</li> 308 * <li>Copy all elements of the seed into the array</li> 309 * <li>Fill the remaining values. The additional values will have at most one occurrence 310 * of zero. If the original seed is all zero, the first extended value will be non-zero. 311 * </li> 312 * </ol> 313 * 314 * <p>This method can be used in constructors that must pass their seed to the super class 315 * to avoid a duplication of seed expansion to the minimum length required by the super class 316 * and the class: 317 * <pre> 318 * public RNG extends AnotherRNG { 319 * public RNG(long[] seed) { 320 * super(seed = extendSeed(seed, SEED_SIZE)); 321 * // Use seed for additional state ... 322 * } 323 * } 324 * </pre> 325 * 326 * <p>Note using the state filling procedure provided in {@link #fillState(long[], long[])} 327 * is not possible as it is an instance method. Calling a seed extension routine must use a 328 * static method. 329 * 330 * <p>This method functions as if the seed has been extended using a 331 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} 332 * generator seeded with {@code seed[0]}, or zero if the input seed length is zero. 333 * <pre> 334 * if (seed.length < length) { 335 * final long[] s = Arrays.copyOf(seed, length); 336 * final SplitMix64 rng = new SplitMix64(s[0]); 337 * for (int i = seed.length; i < length; i++) { 338 * s[i] = rng.nextLong(); 339 * } 340 * return s; 341 * }</pre> 342 * 343 * @param seed Input seed 344 * @param length The minimum length 345 * @return the seed 346 * @since 1.5 347 */ 348 protected static long[] extendSeed(long[] seed, int length) { 349 if (seed.length < length) { 350 final long[] s = Arrays.copyOf(seed, length); 351 // Fill the rest as if using a SplitMix64 RNG 352 long x = s[0]; 353 for (int i = seed.length; i < length; i++) { 354 x += GOLDEN_RATIO_64; 355 s[i] = stafford13(x); 356 } 357 return s; 358 } 359 return seed; 360 } 361 362 /** 363 * Extend the seed to the specified minimum length. If the seed is equal or greater than the 364 * minimum length, return the same seed unchanged. Otherwise: 365 * <ol> 366 * <li>Create a new array of the specified length</li> 367 * <li>Copy all elements of the seed into the array</li> 368 * <li>Fill the remaining values. The additional values will have at most one occurrence 369 * of zero. If the original seed is all zero, the first extended value will be non-zero. 370 * </li> 371 * </ol> 372 * 373 * <p>This method can be used in constructors that must pass their seed to the super class 374 * to avoid a duplication of seed expansion to the minimum length required by the super class 375 * and the class: 376 * <pre> 377 * public RNG extends AnotherRNG { 378 * public RNG(int[] seed) { 379 * super(seed = extendSeed(seed, SEED_SIZE)); 380 * // Use seed for additional state ... 381 * } 382 * } 383 * </pre> 384 * 385 * <p>Note using the state filling procedure provided in {@link #fillState(int[], int[])} 386 * is not possible as it is an instance method. Calling a seed extension routine must use a 387 * static method. 388 * 389 * <p>This method functions as if the seed has been extended using a 390 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64}-style 32-bit 391 * generator seeded with {@code seed[0]}, or zero if the input seed length is zero. The 392 * generator uses the 32-bit mixing function from MurmurHash3. 393 * 394 * @param seed Input seed 395 * @param length The minimum length 396 * @return the seed 397 * @since 1.5 398 */ 399 protected static int[] extendSeed(int[] seed, int length) { 400 if (seed.length < length) { 401 final int[] s = Arrays.copyOf(seed, length); 402 // Fill the rest as if using a SplitMix64-style RNG for 32-bit output 403 int x = s[0]; 404 for (int i = seed.length; i < length; i++) { 405 x += GOLDEN_RATIO_32; 406 s[i] = murmur3(x); 407 } 408 return s; 409 } 410 return seed; 411 } 412 413 /** 414 * Perform variant 13 of David Stafford's 64-bit mix function. 415 * This is the mix function used in the 416 * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} RNG. 417 * 418 * <p>This is ranked first of the top 14 Stafford mixers. 419 * 420 * <p>This function can be used to mix the bits of a {@code long} value to 421 * obtain a better distribution and avoid collisions between similar values. 422 * 423 * @param x the input value 424 * @return the output value 425 * @see <a href="https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html">Better 426 * Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a> 427 */ 428 private static long stafford13(long x) { 429 x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L; 430 x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL; 431 return x ^ (x >>> 31); 432 } 433 434 /** 435 * Perform the finalising 32-bit mix function of Austin Appleby's MurmurHash3. 436 * 437 * <p>This function can be used to mix the bits of a {@code int} value to 438 * obtain a better distribution and avoid collisions between similar values. 439 * 440 * @param x the input value 441 * @return the output value 442 * @see <a href="https://github.com/aappleby/smhasher">SMHasher</a> 443 */ 444 private static int murmur3(int x) { 445 x = (x ^ (x >>> 16)) * 0x85ebca6b; 446 x = (x ^ (x >>> 13)) * 0xc2b2ae35; 447 return x ^ (x >>> 16); 448 } 449}