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 /** {@inheritDoc} */ 041 @Override 042 public RandomProviderState saveState() { 043 return new RandomProviderDefaultState(getStateInternal()); 044 } 045 046 /** {@inheritDoc} */ 047 @Override 048 public void restoreState(RandomProviderState state) { 049 if (state instanceof RandomProviderDefaultState) { 050 setStateInternal(((RandomProviderDefaultState) state).getState()); 051 } else { 052 throw new IllegalArgumentException("Foreign instance"); 053 } 054 } 055 056 /** {@inheritDoc} */ 057 @Override 058 public String toString() { 059 return getClass().getName(); 060 } 061 062 /** 063 * Combine parent and subclass states. 064 * This method must be called by all subclasses in order to ensure 065 * that state can be restored in case some of it is stored higher 066 * up in the class hierarchy. 067 * 068 * I.e. the body of the overridden {@link #getStateInternal()}, 069 * will end with a statement like the following: 070 * <pre> 071 * <code> 072 * return composeStateInternal(state, 073 * super.getStateInternal()); 074 * </code> 075 * </pre> 076 * where {@code state} is the state needed and defined by the class 077 * where the method is overridden. 078 * 079 * @param state State of the calling class. 080 * @param parentState State of the calling class' parent. 081 * @return the combined state. 082 * Bytes that belong to the local state will be stored at the 083 * beginning of the resulting array. 084 */ 085 protected byte[] composeStateInternal(byte[] state, 086 byte[] parentState) { 087 final int len = parentState.length + state.length; 088 final byte[] c = new byte[len]; 089 System.arraycopy(state, 0, c, 0, state.length); 090 System.arraycopy(parentState, 0, c, state.length, parentState.length); 091 return c; 092 } 093 094 /** 095 * Splits the given {@code state} into a part to be consumed by the caller 096 * in order to restore its local state, while the reminder is passed to 097 * the parent class. 098 * 099 * 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}