001/*  Written in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org)
002
003To the extent possible under law, the author has dedicated all copyright
004and related and neighboring rights to this software to the public domain
005worldwide. This software is distributed without any warranty.
006
007See <http://creativecommons.org/publicdomain/zero/1.0/>. */
008package squidpony.squidmath;
009
010import squidpony.StringKit;
011
012import java.io.Serializable;
013
014/**
015 * A Linear Feedback Shift Register that may be used like a StatefulRandomness but is not truly random. This has a
016 * period of (2 to the 64) minus 1, and is based on Wikipedia's code for a Galois LFSR but uses data from
017 * http://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf .
018 * It is important to note that an LFSR will produce each number from 1 until its maximum exactly once before repeating,
019 * so this may be useful as a way of generating test data in an unpredictable order.
020 * @author Tommy Ettinger
021 */
022public class LFSR implements StatefulRandomness, Serializable {
023
024        private static final long DOUBLE_MASK = (1L << 53) - 1;
025    private static final double NORM_53 = 1. / (1L << 53);
026    private static final long FLOAT_MASK = (1L << 24) - 1;
027    private static final double NORM_24 = 1. / (1L << 24);
028
029        private static final long serialVersionUID = -2373549048478690398L;
030
031    public long state;
032
033    /**
034     * Creates a new generator seeded using Math.random.
035     */
036    public LFSR() {
037        this((long) (Math.random() * Long.MAX_VALUE));
038    }
039
040    public LFSR(final long seed) {
041        setState(seed);
042    }
043
044    public LFSR(final CharSequence seed)
045    {
046        this(CrossHash.hash64(seed));
047    }
048
049
050    @Override
051    public final int next(int bits) {
052        return (int)nextLong() >>> (32 - bits);
053    }
054
055    @Override
056    public final long nextLong() {
057        return state = (state >>> 1 ^ (-(state & 1L) & 0xD800000000000000L));
058    }
059
060    /**
061     * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the
062     * copy, both will generate the same sequence of random numbers from the point copy() was called. This just needs to
063     * copy the state so it isn't shared, usually, and produce a new value with the same exact state.
064     *
065     * @return a copy of this RandomnessSource
066     */
067    @Override
068    public LFSR copy() {
069        return new LFSR(state);
070    }
071
072
073    /**
074     * Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
075     * @return any int, all 32 bits are random
076     */
077    public int nextInt() {
078        return (int)nextLong();
079    }
080
081    /**
082     * Exclusive on the outer bound; the inner bound is 0. The bound may be negative, which will produce a non-positive
083     * result.
084     * @param bound the outer exclusive bound; may be positive or negative
085     * @return a random long between 0 (inclusive) and bound (exclusive)
086     */
087    public int nextInt( final int bound ) {
088        return (int)((bound * (nextLong() & 0x7FFFFFFFL)) >> 31);
089    }
090    /**
091     * Inclusive lower, exclusive upper.
092     * @param inner the inner bound, inclusive, can be positive or negative
093     * @param outer the outer bound, exclusive, should be positive, should usually be greater than inner
094     * @return a random int that may be equal to inner and will otherwise be between inner and outer
095     */
096    public int nextInt(final int inner, final int outer) {
097        return inner + nextInt(outer - inner);
098    }
099
100    /**
101     * Exclusive on the outer bound; the inner bound is 0. The bound may be negative, which will produce a non-positive
102     * result.
103     * @param bound the outer exclusive bound; may be positive or negative
104     * @return a random long between 0 (inclusive) and bound (exclusive)
105     */
106    public long nextLong(long bound) {
107        long rand = nextLong();
108        final long randLow = rand & 0xFFFFFFFFL;
109        final long boundLow = bound & 0xFFFFFFFFL;
110        rand >>>= 32;
111        bound >>= 32;
112        final long t = rand * boundLow + (randLow * boundLow >>> 32);
113        return rand * bound + (t >> 32) + (randLow * bound + (t & 0xFFFFFFFFL) >> 32);
114    }
115
116    /**
117     * Inclusive inner, exclusive outer; both inner and outer can be positive or negative.
118     * @param inner the inner bound, inclusive, can be positive or negative
119     * @param outer the outer bound, exclusive, can be positive or negative and may be greater than or less than inner
120     * @return a random long that may be equal to inner and will otherwise be between inner and outer
121     */
122    public long nextLong(final long inner, final long outer) {
123        return inner + nextLong(outer - inner);
124    }
125
126    public double nextDouble() {
127        return (nextLong() & DOUBLE_MASK) * NORM_53;
128    }
129
130    public float nextFloat() {
131        return (float) ((nextLong() & FLOAT_MASK) * NORM_24);
132    }
133
134    public boolean nextBoolean() {
135        return nextLong() < 0L;
136    }
137
138    public void nextBytes(final byte[] bytes) {
139        int i = bytes.length, n;
140        while (i != 0) {
141            n = Math.min(i, 8);
142            for (long bits = nextLong(); n-- != 0; bits >>>= 8) {
143                bytes[--i] = (byte) bits;
144            }
145        }
146    }
147
148    /**
149     * Get the current internal state of the StatefulRandomness as a long.
150     *
151     * @return the current internal state of this object.
152     */
153    @Override
154    public long getState() {
155        return state;
156    }
157
158    /**
159     * Sets the seed of this generator using one long, running that through LightRNG's algorithm twice to get the state.
160     * @param seed the number to use as the seed
161     */
162    public void setState(final long seed) {
163        if(seed == 0)
164            state = -1L;
165        else
166            state = seed;
167    }
168
169    @Override
170    public String toString() {
171        return "LFSR with state 0x" + StringKit.hex(state) + 'L';
172    }
173
174    @Override
175    public boolean equals(Object o) {
176        if (this == o) return true;
177        if (o == null || getClass() != o.getClass()) return false;
178
179        LFSR lfsr = (LFSR) o;
180
181        return (state == lfsr.state);
182    }
183
184    @Override
185    public int hashCode() {
186        return (int) (state ^ (state >>> 32));
187    }
188
189    /**
190     * Gets the next number that an LFSR would produce using {@link #nextLong()} if its state was {@code state}.
191     * Does not allow state to be 0. Strongly consider using the result of this and assigning it to state if you expect
192     * to call this again, such as with {@code (state = LFSR.determine(state))}, which will ensure the long-term
193     * properties of an LFSR hold up (such as having a period of ((2 to the 64) minus 1), or the guarantee that every
194     * number from 1 to ((2 to the 64) minus 1), inclusive on both, will be generated once per period).
195     * @param state any long other than 0
196     * @return the next long that a 64-bit LFSR would produce with the given state
197     */
198    public static long determine(final long state)
199    {
200        return state >>> 1 ^ (-(state & 1L) & 0xD800000000000000L);
201    }
202
203    /**
204     * Gets the next number from 1 to 255 that a different kind of LFSR would produce if its state was {@code state}.
205     * Does not allow state to be 0. If given all byte values except 0 as arguments, will produce all ints 1-255.
206     * Strongly consider using the result of this and assigning it to state if you expect to call this again, such as
207     * with {@code (state = LFSR.determineByte(state))}, which will ensure the long-term properties of an LFSR hold up
208     * (such as having a period of 255, or the guarantee that every number from 1 to 255, inclusive on both, will be
209     * generated once per period).
210     * @param state any byte other than 0
211     * @return the next int between 1 and 255 that an 8-bit LFSR would produce with the given state
212     */
213    public static int determineByte(final byte state)
214    {
215        return state >>> 1 ^ (-(state & 1) & 0xB8);
216    }
217
218    /**
219     * Gets the next number that a different kind of 32-bit LFSR would produce if its state was {@code state}.
220     * Does not allow state to be 0. If given all int values except 0 as arguments, will produce all ints except 0.
221     * Strongly consider using the result of this and assigning it to state if you expect to call this again, such as
222     * with {@code (state = LFSR.determineInt(state))}, which will ensure the long-term properties of an LFSR hold up
223     * (such as having a period of ((2 to the 32) minus 1), or the guarantee that every number from 1 to ((2 to the 32)
224     * minus 1), inclusive on both, will be generated once per period).
225     * @param state any long other than 0
226     * @return the next int that a 32-bit LFSR would produce with the given state
227     */
228    public static int determineInt(final int state)
229    {
230        return state >>> 1 ^ (-(state & 1) & 0xA3000000);
231    }
232
233    /**
234     * Gets the next positive long that a different kind of 63-bit LFSR would produce if its state was {@code state}.
235     * Does not allow state to be 0 or negative. If given all positive long values (not including 0) as arguments, will
236     * produce all longs greater than 0. Strongly consider using the result of this and assigning it to state if you
237     * expect to call this again, such as with {@code (state = LFSR.determinePositiveLong(state))}, which will ensure
238     * the long-term properties of an LFSR hold up (such as having a period of ((2 to the 63) minus 1), or the guarantee
239     * that every number from 1 to ((2 to the 63) minus 1), inclusive on both, will be generated once per period).
240     * @param state any positive long, not including 0
241     * @return the next int that a 63-bit LFSR would produce with the given state
242     */
243    public static long determinePositiveLong(final long state)
244    {
245        return state >>> 1 ^ (-(state & 1L) & 0x6000000000000000L);
246    }
247
248    /**
249     * Gets the next positive int that a different kind of 31-bit LFSR would produce if its state was {@code state}.
250     * Does not allow state to be 0 or negative. If given all positive int values (not including 0) as arguments, will
251     * produce all ints greater than 0. Strongly consider using the result of this and assigning it to state if you
252     * expect to call this again, such as with {@code (state = LFSR.determinePositiveInt(state))}, which will ensure the
253     * long-term properties of an LFSR hold up (such as having a period of ((2 to the 31) minus 1), or the guarantee
254     * that every number from 1 to ((2 to the 31) minus 1), inclusive on both, will be generated once per period).
255     * <br>
256     * A potential benefit of using this particular LFSR type is that the period is a prime number, 2147483647; this can
257     * sometimes be relevant if you simultaneously get pseudo-random numbers from sources of randomness with different
258     * periods that are "relatively co-prime" (that is, they share no common factors other than 1). This case lengthens
259     * the total period of the combined generators significantly, generally multiplying the periods together to get the
260     * combined period, as opposed to other cases that may simply add them together.
261     * @param state any positive int, not including 0
262     * @return the next int that a 31-bit LFSR would produce with the given state
263     */
264    public static int determinePositiveInt(final int state)
265    {
266        return state >>> 1 ^ (-(state & 1) & 0x48000000);
267    }
268
269    /**
270     * Gets the next int that a different kind of LFSR would produce if its state was {@code state}.
271     * Does not allow state to be {@link Integer#MIN_VALUE}, nor will this produce a result of {@link Integer#MIN_VALUE}
272     * (as long as {@link Integer#MIN_VALUE} was not the input). If given all int values except
273     * {@link Integer#MIN_VALUE} as arguments, will produce all ints in the range {@code [-2147483647,2147483647]},
274     * including 0 but not -2147483648 (the minimum int). Strongly consider using the result of this and assigning it to
275     * state if you expect to call this again, such as with {@code (state = LFSR.determineIntSymmetrical(state))}, which
276     * will ensure the long-term properties of an LFSR hold up (such as having a period of ((2 to the 32) minus 1), or
277     * the guarantee that every int except {@link Integer#MIN_VALUE} will be generated once per period).
278     * <br>
279     * This is called Symmetrical because it produces the same amount of positive and negative numbers, instead of the
280     * normal generation of more negative ones (due to how ints are represented, the min value is always further from 0
281     * than the max value for any signed integer type).
282     * @param state any int other than -2147483648 (0x80000000), which is {@link Integer#MIN_VALUE}; can produce 0
283     * @return the next int other than -2147483648 that an LFSR would produce with the given state
284     */
285    public static int determineIntSymmetrical(final int state)
286    {
287        return ((state ^ 0x80000000) >>> 1 ^ (-(state & 1) & 0xA3000000));
288    }
289
290    /**
291     * Gets the next number that an LFSR would produce using {@link #nextInt(int)} if its state was {@code state} and
292     * {@code bound} was passed to nextInt(). Does not allow state to be 0, but bound can be negative, which causes this
293     * not to produce positive numbers. This method is very predictable and its use is not encouraged; prefer using
294     * {@link #determineBounded(int, int)}.
295     * @param state any long other than 0
296     * @param bound the exclusive bound on the result as an int; does better if the bound is not too high (below 10000?)
297     * @return the next value that {@link LFSR#determine(long)} would produce with the given state, but limited to bound; can return 0
298     */
299    public static int determineBounded(final long state, final int bound)
300    {
301        return (int)((bound * (state >>> 1 & 0xFFFFFFFFL)) >> 32);
302    }
303    /**
304     * Gets an int using {@link #determineInt(int)} and bounds it to fit between 0 (inclusive) and bound (exclusive).
305     * Does not allow state to be 0, but bound can be negative, which causes this not to produce positive numbers.
306     * @param state any int other than 0
307     * @param bound the exclusive bound on the result as an int; does better if the bound is not too high (below 10000?)
308     * @return the next int that {@link LFSR#determineInt(int)} would produce with the given state, but limited to bound; can return 0
309     */
310    public static int determineBounded(final int state, final int bound)
311    {
312        return (int)((bound * ((state >>> 1 ^ (-(state & 1) & 0xA3000000)) & 0xFFFFFFFFL)) >> 32);
313    }
314}