GameRandomizer/src/nedragtna/random/MTRandom.java

   1 package nedragtna.random;
   2
   3 /*
   4  * MTRandom : A Java implementation of the MT19937 (Mersenne Twister)
   5  *            pseudo random number generator algorithm based upon the
   6  *            original C code by Makoto Matsumoto and Takuji Nishimura.
   7  * Author   : David Beaumont
   8  * Email    : mersenne-at-www.goui.net
   9  *
  10  * For the original C code, see:
  11  *     http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
  12  *
  13  * This version, Copyright (C) 2005, David Beaumont.
  14  *
  15  * This library is free software; you can redistribute it and/or
  16  * modify it under the terms of the GNU Lesser General Public
  17  * License as published by the Free Software Foundation; either
  18  * version 2.1 of the License, or (at your option) any later version.
  19  *
  20  * This library is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23  * Lesser General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU Lesser General Public
  26  * License along with this library; if not, write to the Free Software
  27  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  28  */
  29
  30 import java.util.Random;
  31
  32 /**
  33  * @version 1.0
  34  * @author David Beaumont, Copyright 2005
  35  *         <p>
  36  *         A Java implementation of the MT19937 (Mersenne Twister) pseudo random
  37  *         number generator algorithm based upon the original C code by Makoto
  38  *         Matsumoto and Takuji Nishimura (see <a
  39  *         href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html">
  40  *         http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html</a> for more
  41  *         information.
  42  *         <p>
  43  *         As a subclass of java.util.Random this class provides a single
  44  *         canonical method next() for generating bits in the pseudo random
  45  *         number sequence. Anyone using this class should invoke the public
  46  *         inherited methods (nextInt(), nextFloat etc.) to obtain values as
  47  *         normal. This class should provide a drop-in replacement for the
  48  *         standard implementation of java.util.Random with the additional
  49  *         advantage of having a far longer period and the ability to use a far
  50  *         larger seed value.
  51  *         <p>
  52  *         This is <b>not</b> a cryptographically strong source of randomness
  53  *         and should <b>not</b> be used for cryptographic systems or in any
  54  *         other situation where true random numbers are required.
  55  *         <p>
  56  *         <!-- Creative Commons License --> <a
  57  *         href="http://creativecommons.org/licenses/LGPL/2.1/"><img
  58  *         alt="CC-GNU LGPL" border="0"
  59  *         src="http://creativecommons.org/images/public/cc-LGPL-a.png" /></a><br />
  60  *         This software is licensed under the <a
  61  *         href="http://creativecommons.org/licenses/LGPL/2.1/">CC-GNU LGPL</a>.
  62  *         <!-- /Creative Commons License -->
  63  *
  64  *         <!-- <rdf:RDF xmlns="http://web.resource.org/cc/"
  65  *         xmlns:dc="http://purl.org/dc/elements/1.1/"
  66  *         xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
  67  *
  68  *         <Work rdf:about=""> <license
  69  *         rdf:resource="http://creativecommons.org/licenses/LGPL/2.1/" />
  70  *         <dc:type rdf:resource="http://purl.org/dc/dcmitype/Software" />
  71  *         </Work>
  72  *
  73  *         <License rdf:about="http://creativecommons.org/licenses/LGPL/2.1/">
  74  *         <permits rdf:resource="http://web.resource.org/cc/Reproduction" />
  75  *         <permits rdf:resource="http://web.resource.org/cc/Distribution" />
  76  *         <requires rdf:resource="http://web.resource.org/cc/Notice" />
  77  *         <permits rdf:resource="http://web.resource.org/cc/DerivativeWorks" />
  78  *         <requires rdf:resource="http://web.resource.org/cc/ShareAlike" />
  79  *         <requires rdf:resource="http://web.resource.org/cc/SourceCode" />
  80  *         </License>
  81  *
  82  *         </rdf:RDF> -->
  83  *
  84  */
  85 public class MTRandom extends Random {
  86
  87                 /**
  88                  * Auto-generated serial version UID. Note that MTRandom does NOT support
  89                  * serialisation of its internal state and it may even be necessary to
  90                  * implement read/write methods to re-seed it properly. This is only here to
  91                  * make Eclipse shut up about it being missing.
  92                  */
  93                 private static final long serialVersionUID = -515082678588212038L;
  94
  95                 // Constants used in the original C implementation
  96                 private final static int UPPER_MASK = 0x80000000;
  97                 private final static int LOWER_MASK = 0x7fffffff;
  98
  99                 private final static int N = 624;
 100                 private final static int M = 397;
 101                 private final static int MAGIC[] = { 0x0, 0x9908b0df };
 102                 private final static int MAGIC_FACTOR1 = 1812433253;
 103                 private final static int MAGIC_FACTOR2 = 1664525;
 104                 private final static int MAGIC_FACTOR3 = 1566083941;
 105                 private final static int MAGIC_MASK1 = 0x9d2c5680;
 106                 private final static int MAGIC_MASK2 = 0xefc60000;
 107                 private final static int MAGIC_SEED = 19650218;
 108                 private final static long DEFAULT_SEED = 5489L;
 109
 110                 // Internal state
 111                 private transient int[] mt;
 112                 private transient int mti;
 113                 private transient boolean compat = false;
 114
 115                 // Temporary buffer used during setSeed(long)
 116                 private transient int[] ibuf;
 117
 118                 /**
 119                  * The default constructor for an instance of MTRandom.
 120                  * Since the no-argument constructor of java.util.Random
 121                  * does not seem to call setSeed anymore (since JDK7),
 122                  * we need to do it manually in this constructor.
 123                  * For legacy purposes, the seed remains initialized by
 124                  * a call to System.currentTimeMillis().
 125                  * @author Jonathan Passerat-Palmbach
 126                  *
 127                  */
 128                 public MTRandom() {
 129                         this.setSeed(System.currentTimeMillis());
 130                 }
 131
 132                 /**
 133                  * This version of the constructor can be used to implement identical
 134                  * behaviour to the original C code version of this algorithm including
 135                  * exactly replicating the case where the seed value had not been set prior
 136                  * to calling genrand_int32.
 137                  * <p>
 138                  * If the compatibility flag is set to true, then the algorithm will be
 139                  * seeded with the same default value as was used in the original C code.
 140                  * Furthermore the setSeed() method, which must take a 64 bit long value,
 141                  * will be limited to using only the lower 32 bits of the seed to facilitate
 142                  * seamless migration of existing C code into Java where identical behaviour
 143                  * is required.
 144                  * <p>
 145                  * Whilst useful for ensuring backwards compatibility, it is advised that
 146                  * this feature not be used unless specifically required, due to the
 147                  * reduction in strength of the seed value.
 148                  *
 149                  * @param compatible
 150                  *            Compatibility flag for replicating original behaviour.
 151                  */
 152                 public MTRandom(boolean compatible) {
 153                                 super(0L);
 154                                 compat = compatible;
 155                                 setSeed(compat ? DEFAULT_SEED : System.currentTimeMillis());
 156                 }
 157
 158                 /**
 159                  * This version of the constructor simply initialises the class with the
 160                  * given 64 bit seed value. For a better random number sequence this seed
 161                  * value should contain as much entropy as possible.
 162                  *
 163                  * This constructor was modified due to be compliant to the JDK7's implementation
 164                  * of java.util.Random as explained in MTRandom()
 165                  * @param seed
 166                  *            The seed value with which to initialise this class.
 167                  * @see MTRandom()
 168                  * @author Jonathan Passerat-Palmbach
 169                  */
 170                 public MTRandom(long seed) {
 171                                 super(seed);
 172                                 this.setSeed(seed);
 173                 }
 174
 175                 /**
 176                  * This version of the constructor initialises the class with the given byte
 177                  * array. All the data will be used to initialise this instance.
 178                  *
 179                  * @param buf
 180                  *            The non-empty byte array of seed information.
 181                  * @throws NullPointerException
 182                  *             if the buffer is null.
 183                  * @throws IllegalArgumentException
 184                  *             if the buffer has zero length.
 185                  */
 186                 public MTRandom(byte[] buf) {
 187                                 super(0L);
 188                                 setSeed(buf);
 189                 }
 190
 191                 /**
 192                  * This version of the constructor initialises the class with the given
 193                  * integer array. All the data will be used to initialise this instance.
 194                  *
 195                  * @param buf
 196                  *            The non-empty integer array of seed information.
 197                  * @throws NullPointerException
 198                  *             if the buffer is null.
 199                  * @throws IllegalArgumentException
 200                  *             if the buffer has zero length.
 201                  */
 202                 public MTRandom(int[] buf) {
 203                                 super(0L);
 204                                 setSeed(buf);
 205                 }
 206
 207                 // Initializes mt[N] with a simple integer seed. This method is
 208                 // required as part of the Mersenne Twister algorithm but need
 209                 // not be made public.
 210                 private final void setSeed(int seed) {
 211
 212                                 // Annoying runtime check for initialisation of internal data
 213                                 // caused by java.util.Random invoking setSeed() during init.
 214                                 // This is unavoidable because no fields in our instance will
 215                                 // have been initialised at this point, not even if the code
 216                                 // were placed at the declaration of the member variable.
 217                                 if (mt == null)
 218                                                 mt = new int[N];
 219
 220                                 // ---- Begin Mersenne Twister Algorithm ----
 221                                 mt[0] = seed;
 222                                 for (mti = 1; mti < N; mti++) {
 223                                                 mt[mti] = (MAGIC_FACTOR1 * (mt[mti - 1] ^ (mt[mti - 1] >>> 30)) + mti);
 224                                 }
 225                                 // ---- End Mersenne Twister Algorithm ----
 226                 }
 227
 228                 /**
 229                  * This method resets the state of this instance using the 64 bits of seed
 230                  * data provided. Note that if the same seed data is passed to two different
 231                  * instances of MTRandom (both of which share the same compatibility state)
 232                  * then the sequence of numbers generated by both instances will be
 233                  * identical.
 234                  * <p>
 235                  * If this instance was initialised in 'compatibility' mode then this method
 236                  * will only use the lower 32 bits of any seed value passed in and will
 237                  * match the behaviour of the original C code exactly with respect to state
 238                  * initialisation.
 239                  *
 240                  * @param seed
 241                  *            The 64 bit value used to initialise the random number
 242                  *            generator state.
 243                  */
 244                 public final synchronized void setSeed(long seed) {
 245                                 if (compat) {
 246                                                 setSeed((int) seed);
 247                                 } else {
 248
 249                                                 // Annoying runtime check for initialisation of internal data
 250                                                 // caused by java.util.Random invoking setSeed() during init.
 251                                                 // This is unavoidable because no fields in our instance will
 252                                                 // have been initialised at this point, not even if the code
 253                                                 // were placed at the declaration of the member variable.
 254                                                 if (ibuf == null)
 255                                                                 ibuf = new int[2];
 256
 257                                                 ibuf[0] = (int) seed;
 258                                                 ibuf[1] = (int) (seed >>> 32);
 259                                                 setSeed(ibuf);
 260                                 }
 261                 }
 262
 263                 /**
 264                  * This method resets the state of this instance using the byte array of
 265                  * seed data provided. Note that calling this method is equivalent to
 266                  * calling "setSeed(pack(buf))" and in particular will result in a new
 267                  * integer array being generated during the call. If you wish to retain this
 268                  * seed data to allow the pseudo random sequence to be restarted then it
 269                  * would be more efficient to use the "pack()" method to convert it into an
 270                  * integer array first and then use that to re-seed the instance. The
 271                  * behaviour of the class will be the same in both cases but it will be more
 272                  * efficient.
 273                  *
 274                  * @param buf
 275                  *            The non-empty byte array of seed information.
 276                  * @throws NullPointerException
 277                  *             if the buffer is null.
 278                  * @throws IllegalArgumentException
 279                  *             if the buffer has zero length.
 280                  */
 281                 public final void setSeed(byte[] buf) {
 282                                 setSeed(pack(buf));
 283                 }
 284
 285                 /**
 286                  * This method resets the state of this instance using the integer array of
 287                  * seed data provided. This is the canonical way of resetting the pseudo
 288                  * random number sequence.
 289                  *
 290                  * @param buf
 291                  *            The non-empty integer array of seed information.
 292                  * @throws NullPointerException
 293                  *             if the buffer is null.
 294                  * @throws IllegalArgumentException
 295                  *             if the buffer has zero length.
 296                  */
 297                 public final synchronized void setSeed(int[] buf) {
 298                                 int length = buf.length;
 299                                 if (length == 0)
 300                                                 throw new IllegalArgumentException("Seed buffer may not be empty");
 301                                 // ---- Begin Mersenne Twister Algorithm ----
 302                                 int i = 1, j = 0, k = (N > length ? N : length);
 303                                 setSeed(MAGIC_SEED);
 304                                 for (; k > 0; k--) {
 305                                                 mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * MAGIC_FACTOR2))
 306                                                                                 + buf[j] + j;
 307                                                 i++;
 308                                                 j++;
 309                                                 if (i >= N) {
 310                                                                 mt[0] = mt[N - 1];
 311                                                                 i = 1;
 312                                                 }
 313                                                 if (j >= length)
 314                                                                 j = 0;
 315                                 }
 316                                 for (k = N - 1; k > 0; k--) {
 317                                                 mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >>> 30)) * MAGIC_FACTOR3))
 318                                                                                 - i;
 319                                                 i++;
 320                                                 if (i >= N) {
 321                                                                 mt[0] = mt[N - 1];
 322                                                                 i = 1;
 323                                                 }
 324                                 }
 325                                 mt[0] = UPPER_MASK; // MSB is 1; assuring non-zero initial array
 326                                 // ---- End Mersenne Twister Algorithm ----
 327                 }
 328
 329                 /**
 330                  * This method forms the basis for generating a pseudo random number
 331                  * sequence from this class. If given a value of 32, this method behaves
 332                  * identically to the genrand_int32 function in the original C code and
 333                  * ensures that using the standard nextInt() function (inherited from
 334                  * Random) we are able to replicate behaviour exactly.
 335                  * <p>
 336                  * Note that where the number of bits requested is not equal to 32 then bits
 337                  * will simply be masked out from the top of the returned integer value.
 338                  * That is to say that:
 339                  *
 340                  * <pre>
 341                  * mt.setSeed(12345);
 342                  * int foo = mt.nextInt(16) + (mt.nextInt(16) &lt;&lt; 16);
 343                  * </pre>
 344                  *
 345                  * will not give the same result as
 346                  *
 347                  * <pre>
 348                  * mt.setSeed(12345);
 349                  * int foo = mt.nextInt(32);
 350                  * </pre>
 351                  *
 352                  * @param bits
 353                  *            The number of significant bits desired in the output.
 354                  * @return The next value in the pseudo random sequence with the specified
 355                  *         number of bits in the lower part of the integer.
 356                  */
 357                 protected final synchronized int next(int bits) {
 358                                 // ---- Begin Mersenne Twister Algorithm ----
 359                                 int y, kk;
 360                                 if (mti >= N) { // generate N words at one time
 361
 362                                                 // In the original C implementation, mti is checked here
 363                                                 // to determine if initialisation has occurred; if not
 364                                                 // it initialises this instance with DEFAULT_SEED (5489).
 365                                                 // This is no longer necessary as initialisation of the
 366                                                 // Java instance must result in initialisation occurring
 367                                                 // Use the constructor MTRandom(true) to enable backwards
 368                                                 // compatible behaviour.
 369
 370                                                 for (kk = 0; kk < N - M; kk++) {
 371                                                                 y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
 372                                                                 mt[kk] = mt[kk + M] ^ (y >>> 1) ^ MAGIC[y & 0x1];
 373                                                 }
 374                                                 for (; kk < N - 1; kk++) {
 375                                                                 y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
 376                                                                 mt[kk] = mt[kk + (M - N)] ^ (y >>> 1) ^ MAGIC[y & 0x1];
 377                                                 }
 378                                                 y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
 379                                                 mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ MAGIC[y & 0x1];
 380
 381                                                 mti = 0;
 382                                 }
 383
 384                                 y = mt[mti++];
 385
 386                                 // Tempering
 387                                 y ^= (y >>> 11);
 388                                 y ^= (y << 7) & MAGIC_MASK1;
 389                                 y ^= (y << 15) & MAGIC_MASK2;
 390                                 y ^= (y >>> 18);
 391                                 // ---- End Mersenne Twister Algorithm ----
 392                                 return (y >>> (32 - bits));
 393                 }
 394
 395                 // This is a fairly obscure little code section to pack a
 396                 // byte[] into an int[] in little endian ordering.
 397
 398                 /**
 399                  * This simply utility method can be used in cases where a byte array of
 400                  * seed data is to be used to repeatedly re-seed the random number sequence.
 401                  * By packing the byte array into an integer array first, using this method,
 402                  * and then invoking setSeed() with that; it removes the need to re-pack the
 403                  * byte array each time setSeed() is called.
 404                  * <p>
 405                  * If the length of the byte array is not a multiple of 4 then it is
 406                  * implicitly padded with zeros as necessary. For example:
 407                  *
 408                  * <pre>
 409                  * byte[] { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06 }
 410                  * </pre>
 411                  *
 412                  * becomes
 413                  *
 414                  * <pre>
 415                  * int[]  { 0x04030201, 0x00000605 }
 416                  * </pre>
 417                  * <p>
 418                  * Note that this method will not complain if the given byte array is empty
 419                  * and will produce an empty integer array, but the setSeed() method will
 420                  * throw an exception if the empty integer array is passed to it.
 421                  *
 422                  * @param buf
 423                  *            The non-null byte array to be packed.
 424                  * @return A non-null integer array of the packed bytes.
 425                  * @throws NullPointerException
 426                  *             if the given byte array is null.
 427                  */
 428                 public static int[] pack(byte[] buf) {
 429                                 int k, blen = buf.length, ilen = ((buf.length + 3) >>> 2);
 430                                 int[] ibuf = new int[ilen];
 431                                 for (int n = 0; n < ilen; n++) {
 432                                                 int m = (n + 1) << 2;
 433                                                 if (m > blen)
 434                                                                 m = blen;
 435                                                 for (k = buf[--m] & 0xff; (m & 0x3) != 0; k = (k << 8) | buf[--m]
 436                                                                                 & 0xff)
 437                                                                 ;
 438                                                 ibuf[n] = k;
 439                                 }
 440                                 return ibuf;
 441                 }
 442 }