001/*
002Written in 2015 by Sebastiano Vigna (vigna@acm.org)
003
004To the extent possible under law, the author has dedicated all copyright
005and related and neighboring rights to this software to the public domain
006worldwide. This software is distributed without any warranty.
007
008See <http://creativecommons.org/publicdomain/zero/1.0/>. */
009package squidpony.squidmath;
010
011import squidpony.StringKit;
012
013/**
014 * A port of Sebastiano Vigna's XorShift 128+ generator. Should be very fast and produce high-quality output.
015 * Original version at http://xorshift.di.unimi.it/xorshift128plus.c
016 * Written in 2015 by Sebastiano Vigna (vigna@acm.org)
017 * @author Sebastiano Vigna
018 * @author Tommy Ettinger
019 */
020public class XorRNG implements RandomnessSource {
021
022        private static final long DOUBLE_MASK = (1L << 53) - 1;
023    private static final double NORM_53 = 1. / (1L << 53);
024    private static final long FLOAT_MASK = (1L << 24) - 1;
025    private static final double NORM_24 = 1. / (1L << 24);
026
027        private static final long serialVersionUID = 1263134736171610359L;
028
029    private long state0, state1;
030
031    /**
032     * Creates a new generator seeded using Math.random.
033     */
034    public XorRNG() {
035        this((long) (Math.random() * Long.MAX_VALUE));
036    }
037
038    public XorRNG(final long seed) {
039        setSeed(seed);
040    }
041
042    @Override
043    public int next(int bits) {
044        return (int) (nextLong() & (1L << bits) - 1);
045    }
046
047    @Override
048    public long nextLong() {
049        long s1 = state0;
050        final long s0 = state1;
051        state0 = s0;
052        s1 ^= s1 << 23; // a
053        return ( state1 = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) ) ) + s0; // b, c
054    }
055
056    public int nextInt() {
057        return (int) nextLong();
058    }
059
060    public int nextInt(final int n) {
061        if (n <= 0) {
062            throw new IllegalArgumentException();
063        }
064        return (int) ((nextLong() >>> 1) % n);
065    }
066
067    public long nextLong(final long n) {
068        if (n <= 0) {
069            throw new IllegalArgumentException();
070        }
071        for (;;) {
072            final long bits = nextLong() >>> 1;
073            final long value = bits % n;
074            if (bits - value + (n - 1) >= 0) {
075                return value;
076            }
077        }
078    }
079
080    public double nextDouble() {
081        return (nextLong() & DOUBLE_MASK) * NORM_53;
082    }
083
084    public float nextFloat() {
085        return (float) ((nextLong() & FLOAT_MASK) * NORM_24);
086    }
087
088    public boolean nextBoolean() {
089        return (nextLong() & 1) != 0L;
090    }
091
092    public void nextBytes(final byte[] bytes) {
093        int i = bytes.length, n = 0;
094        while (i != 0) {
095            n = Math.min(i, 8);
096            for (long bits = nextLong(); n-- != 0; bits >>= 8) {
097                bytes[--i] = (byte) bits;
098            }
099        }
100    }
101
102    private long avalanche ( long k )
103    {
104        k ^= k >> 33;
105        k *= 0xff51afd7ed558ccdL;
106        k ^= k >> 33;
107        k *= 0xc4ceb9fe1a85ec53L;
108        k ^= k >> 33;
109
110        return k;
111    }
112
113    /**
114     * Sets the seed of this generator. Passing this 0 will just set it to -1
115     * instead.
116     *
117     * @param seed the number to use as the seed
118     */
119    public void setSeed(final long seed) {
120        state0 = avalanche(seed == 0 ? -1 : seed);
121        state1 = avalanche(state0);
122        state0 = avalanche(state1);
123    }
124
125    @Override
126    public String toString() {
127        return "XorRNG with state hash 0x" + StringKit.hexHash(state0, state1) + 'L';
128    }
129
130    /**
131     * Produces a copy of this RandomnessSource that, if next() and/or nextLong() are called on this object and the
132     * copy, both will generate the same sequence of random numbers from the point copy() was called. This just need to
133     * copy the state so it isn't shared, usually, and produce a new value with the same exact state.
134     *
135     * @return a copy of this RandomnessSource
136     */
137    @Override
138    public RandomnessSource copy() {
139        XorRNG next = new XorRNG(state0);
140        next.state0 = state0;
141        next.state1 = state1;
142        return next;
143    }
144}