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
012/**
013 * A port of Blackman and Vigna's xoroshiro 128+ generator; should be very fast and produce high-quality output.
014 * Testing shows it is within 5% the speed of LightRNG, sometimes faster and sometimes slower, and has a larger period.
015 * It's called XoRo because it involves Xor as well as Rotate operations on the 128-bit pseudo-random state.
016 * Original version at http://xoroshiro.di.unimi.it/xoroshiro128plus.c
017 * Written in 2016 by David Blackman and Sebastiano Vigna (vigna@acm.org)
018 * @author Sebastiano Vigna
019 * @author David Blackman
020 * @author Tommy Ettinger
021 */
022public class XoRoRNG implements RandomnessSource {
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 = 1018744536171610261L;
030
031    private long state0, state1;
032
033    /**
034     * Creates a new generator seeded using Math.random.
035     */
036    public XoRoRNG() {
037        this((long) (Math.random() * Long.MAX_VALUE));
038    }
039
040    public XoRoRNG(final long seed) {
041        setSeed(seed);
042    }
043
044    @Override
045    public int next(int bits) {
046        return (int) (nextLong() & (1L << bits) - 1);
047    }
048
049    @Override
050    public long nextLong() {
051        final long s0 = state0;
052        long s1 = state1;
053        final long result = s0 + s1;
054
055        s1 ^= s0;
056        state0 = Long.rotateLeft(s0, 55) ^ s1 ^ (s1 << 14); // a, b
057        state1 = Long.rotateLeft(s1, 36); // c
058
059        return result;
060    }
061
062    /**
063     * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the
064     * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to
065     * copy the state so it isn't shared, usually, and produce a new value with the same exact state.
066     *
067     * @return a copy of this RandomnessSource
068     */
069    @Override
070    public RandomnessSource copy() {
071        XoRoRNG next = new XoRoRNG(state0);
072        next.state0 = state0;
073        next.state1 = state1;
074        return next;
075    }
076
077
078    /**
079     * Can return any int, positive or negative, of any size permissible in a 32-bit signed integer.
080     * @return any int, all 32 bits are random
081     */
082    public int nextInt() {
083        return (int)nextLong();
084    }
085
086    /**
087     * Exclusive on the upper bound.  The lower bound is 0.
088     * @param bound the upper bound; should be positive
089     * @return a random int less than n and at least equal to 0
090     */
091    public int nextInt( final int bound ) {
092        if ( bound <= 0 ) return 0;
093        int threshold = (0x7fffffff - bound + 1) % bound;
094        for (;;) {
095            int bits = (int)(nextLong() & 0x7fffffff);
096            if (bits >= threshold)
097                return bits % bound;
098        }
099    }
100    /**
101     * Inclusive lower, exclusive upper.
102     * @param lower the lower bound, inclusive, can be positive or negative
103     * @param upper the upper bound, exclusive, should be positive, must be greater than lower
104     * @return a random int at least equal to lower and less than upper
105     */
106    public int nextInt( final int lower, final int upper ) {
107        if ( upper - lower <= 0 ) throw new IllegalArgumentException("Upper bound must be greater than lower bound");
108        return lower + nextInt(upper - lower);
109    }
110
111    /**
112     * Exclusive on the upper bound. The lower bound is 0.
113     * @param bound the upper bound; should be positive
114     * @return a random long less than n
115     */
116    public long nextLong( final long bound ) {
117        if ( bound <= 0 ) return 0;
118        long threshold = (0x7fffffffffffffffL - bound + 1) % bound;
119        for (;;) {
120            long bits = nextLong() & 0x7fffffffffffffffL;
121            if (bits >= threshold)
122                return bits % bound;
123        }
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() & 1) != 0L;
136    }
137
138    public void nextBytes(final byte[] bytes) {
139        int i = bytes.length, n = 0;
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     * Sets the seed of this generator. Passing this 0 will just set it to -1
150     * instead.
151     *
152     * @param seed the number to use as the seed
153     */
154    public void setSeed(final long seed) {
155
156        long state = seed + 0x9E3779B97F4A7C15L,
157                z = state;
158        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
159        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
160        state0 = z ^ (z >>> 31);
161        state = seed + 0x9E3779B97F4A7C15L;
162        z = state;
163        z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L;
164        z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL;
165        state1 = z ^ (z >>> 31);
166    }
167
168    @Override
169    public String toString() {
170        return "XoRoRNG with state hash 0x" + StringKit.hexHash(state0, state1) + 'L';
171    }
172}