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}