001 /*
002 Copyright (c) 1996-2012, Damon Hart-Davis
003 All rights reserved.
004
005 Redistribution and use in source and binary forms, with or without
006 modification, are permitted provided that the following conditions are
007 met:
008
009 * Redistributions of source code must retain the above copyright
010 notice, this list of conditions and the following disclaimer.
011
012 * Redistributions in binary form must reproduce the above copyright
013 notice, this list of conditions and the following disclaimer in the
014 documentation and/or other materials provided with the
015 distribution.
016
017 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
019 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
020 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
021 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
022 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
023 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
024 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
025 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
026 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
027 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028 */
029 package org.hd.d.pg2k.svrCore;
030
031 import java.util.Random;
032 import java.util.concurrent.atomic.AtomicInteger;
033
034 /**Provides random number sources to be shared across the system.
035 * The sources provided are static variables all extending
036 * java.util.Random.
037 * <p>
038 * Reseeding is either not allowed (throws an exception),
039 * or in the spirit of SecureRandom guarantees not to
040 * reduce randomness, so these generators can be safely shared.
041 * <p>
042 * The sources are partially seeded from time of day or some
043 * equivalent.
044 * <p>
045 * Using these shared sources helps:
046 * <ul>
047 * <li>Avoid rework and redundant resources.
048 * <li>Avoid the cost of multiple initialisations.
049 * <li>Break up correlations that might otherwise be present.
050 * <li>Possibly add extra unpredictability given the multiple
051 * interleaved uses of each source.
052 * </ul>
053 *
054 * @author Damon Hart-Davis
055 */
056 public final class Rnd
057 {
058 /**Don't allow creation of instances. */
059 private Rnd() { }
060
061 /**Our good-but-slow random number source.
062 * We use a cryptographically-secure random number generator,
063 * but because sequence-guessing may be possible this should
064 * <em>not</em> be used as a source of numbers for highly
065 * secure purposes.
066 * <p>
067 * We will take whatever default generator is available.
068 * <p>
069 * We allow the generator to seed itself on first use,
070 * hopefully with some genuine entropy.
071 * <p>
072 * We make this generator available to all comers,
073 * but they should probably not reseed it, just get random
074 * values from it. (However, a SecureRandom generator is not
075 * completely reset by being reseeded, ie ``is guaranteed not
076 * to have its randomness reduced'' by being reseeded, so even
077 * reseeding probably does not matter too much.)
078 * <p>
079 * Note that this generator can be relatively slow, taking
080 * circa 30s--60s to initialise on an SS5/Cycle5-155MHz
081 * (oolong.exnet.com, 1999/12/28, no /dev/random).
082 */
083 public static final java.security.SecureRandom goodRnd =
084 new java.security.SecureRandom();
085
086 /**A fast random number generator (compared to goodRnd).
087 * Less good than goodRnd, and possibly with unhelpful
088 * correlations, but OK and seeded with at least the time.
089 * <p>
090 * We allow attempts to reseed this generator,
091 * but the reseed value is combined with bits from goodRnd
092 * which should make this safe to share
093 * and prevents this sequence ever getting 'less' random.
094 * <p>
095 * This generator is initially seeded from the time
096 * to ensure that we get off to a unique-ish start.
097 * On subsequent reseeds will use goodRnd to ensure unpredictability.
098 * This should allow for a fast start-up and overall decent behaviour.
099 * <p>
100 * We force reseeding from goodRnd often enough
101 * (more than 1 once every sqrt(n) samples,
102 * where n is the sequence length of the generator)
103 * to avoid "drawing from an urn without replacement" behaviour.
104 * For java.util.Random the sequence length is ~2^48,
105 * so we reseed from goodRnd at most every 2^24 calls to the
106 * internal next() generator routine.
107 * We do this infrequently enough to keep the amortised cost-per-call
108 * low, however.
109 */
110 public static final Random fastRnd = (new Random(System.currentTimeMillis() ^
111 Long.rotateRight(System.nanoTime(), 13) ^
112 (new Object()).hashCode()) {
113
114 /**Ensure that reseeding cannot "reduce randomness".
115 * Setting a particular seed <em>does not</em> reset the generator
116 * to a predictable value, but instead starts the sequence
117 * in a new place using a value from goodRnd()
118 * and the value supplied; this should be different every time
119 * even if the same seed is used repeatedly,
120 * ie the seed value supplied is relatively unimportant.
121 */
122 @Override
123 public final void setSeed(final long seed)
124 { super.setSeed(seed ^ goodRnd.nextLong()); }
125
126 /**Count-down to next reseed of this generator using goodRnd.
127 * We reseed when this value goes negative.
128 * (Starting it at zero would force a reseed on first use.)
129 * <p>
130 * We start this at a random-ish somewhat low count
131 * to allow our initial seeding with time to give the system
132 * a fast start-up, but then use more heavy-weight reseeding
133 * from goodRnd as usual subsequently.
134 * <p>
135 * We use an AtomicInteger so that we can count down safely
136 * without taking a lock which would reduce potential concurrency.
137 */
138 private final AtomicInteger untilReseed =
139 new AtomicInteger(1151 + (int)((System.nanoTime()>>>1) % 9551));
140
141 /**Generates random bits, and periodically reseeds from goodRnd to avoid long predictable runs.
142 * The time until the next reseed is also randomly chosen
143 * during each reseed, reducing predictability further.
144 * <p>
145 * But use goodRnd if you really do need good numbers.
146 */
147 @Override
148 protected final int next(final int bits)
149 {
150 // If we've drawn enough values from this sequence
151 // then reseed it from a cryptographically-good source
152 // to eliminate indefinitely-predictable sequences.
153 final int u;
154 if((u = untilReseed.decrementAndGet()) < 0)
155 {
156 // Draw a long from our good generator if not horrible starved for energy.
157 // Use 16 of the bits for our count-down value,
158 // and the rest implicitly for our 48-bit seed.
159 final long r = GenUtils.mustConservePowerExtreme() ? System.currentTimeMillis() : goodRnd.nextLong();
160 // Reset count-down to next reseed with lower bound
161 // (providing no one else got in there first).
162 untilReseed.compareAndSet(u, 0xfff + (int) (r >>> 48));
163
164 // Now reseed with the new (secure) value,
165 // and some of the old state XORed over the
166 // "count-down-to-reseed" value bits we earlier extracted
167 // just for good measure!
168 super.setSeed(r ^ Long.rotateLeft(super.next(32), 37));
169
170 //System.out.println("***RESEEDED fastRnd()"); // Ideally will not happen until system up and running and stable...
171 //Thread.dumpStack();
172 }
173
174 return(super.next(bits));
175 }
176
177 /**Unique Serialisation class ID generated by http://random.hd.org/. */
178 private static final long serialVersionUID = 3538275569093778199L;
179 });
180 }