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}