src/mersenne.cpp
author truelight
Wed, 20 Jun 2007 12:09:47 +0000
changeset 6979 c4abd9b85a7a
parent 6247 7d81e3a5d803
permissions -rw-r--r--
(svn r10235) -Fix: the 32bpp-anim blitter repainted pixel color 0, which is transparency and therefor should never be repainted (spotted by Rubidium)
2186
db48cf29b983 (svn r2701) Insert Id tags into all source files
tron
parents: 2075
diff changeset
     1
/* $Id$ */
db48cf29b983 (svn r2701) Insert Id tags into all source files
tron
parents: 2075
diff changeset
     2
6201
bee01dc45e39 (svn r8987) -Cleanup: doxygen changes. Again. Mostly (still) @files missing tags and (more than just) a few comments style.
belugas
parents: 5584
diff changeset
     3
/** @file mersenne.cpp */
bee01dc45e39 (svn r8987) -Cleanup: doxygen changes. Again. Mostly (still) @files missing tags and (more than just) a few comments style.
belugas
parents: 5584
diff changeset
     4
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
     5
#include "stdafx.h"
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
     6
#include "openttd.h"
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
     7
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
     8
#ifdef MERSENNE_TWISTER
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
     9
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    10
// Source code for Mersenne Twister.
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    11
// A Random number generator with much higher quality random numbers.
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    12
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    13
#define N              (624)                 // length of _mt_state vector
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    14
#define M              (397)                 // a period parameter
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    15
#define K              (0x9908B0DFU)         // a magic constant
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    16
#define hiBit(u)       ((u) & 0x80000000U)   // mask all but highest   bit of u
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    17
#define loBit(u)       ((u) & 0x00000001U)   // mask all but lowest    bit of u
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    18
#define loBits(u)      ((u) & 0x7FFFFFFFU)   // mask     the highest   bit of u
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    19
#define mixBits(u, v)  (hiBit(u)|loBits(v))  // move hi bit of u to hi bit of v
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    20
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    21
static uint32   _mt_state[N+1];     // _mt_state vector + 1 extra to not violate ANSI C
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    22
static uint32   *_mt_next;          // _mt_next random value is computed from here
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    23
static int      _mt_left = -1;      // can *_mt_next++ this many times before reloading
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    24
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    25
void SeedMT(uint32 seed)
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    26
{
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    27
    register uint32 x = (seed | 1U) & 0xFFFFFFFFU, *s = _mt_state;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    28
    register int    j;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    29
2952
58522ed8f0f1 (svn r3511) More whitespace ([FS#46] by Rubidium)
tron
parents: 2548
diff changeset
    30
    for (_mt_left=0, *s++=x, j=N; --j;
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    31
        *s++ = (x*=69069U) & 0xFFFFFFFFU);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    32
 }
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    33
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    34
6247
7d81e3a5d803 (svn r9050) -Codechange: Foo(void) -> Foo()
rubidium
parents: 6201
diff changeset
    35
static uint32 ReloadMT()
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    36
 {
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    37
    register uint32 *p0=_mt_state, *p2=_mt_state+2, *pM=_mt_state+M, s0, s1;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    38
    register int    j;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    39
2952
58522ed8f0f1 (svn r3511) More whitespace ([FS#46] by Rubidium)
tron
parents: 2548
diff changeset
    40
    if (_mt_left < -1)
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    41
        SeedMT(4357U);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    42
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    43
    _mt_left=N-1, _mt_next=_mt_state+1;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    44
2952
58522ed8f0f1 (svn r3511) More whitespace ([FS#46] by Rubidium)
tron
parents: 2548
diff changeset
    45
    for (s0=_mt_state[0], s1=_mt_state[1], j=N-M+1; --j; s0=s1, s1=*p2++)
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    46
        *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    47
2952
58522ed8f0f1 (svn r3511) More whitespace ([FS#46] by Rubidium)
tron
parents: 2548
diff changeset
    48
    for (pM=_mt_state, j=M; --j; s0=s1, s1=*p2++)
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    49
        *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    50
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    51
    s1=_mt_state[0], *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    52
    s1 ^= (s1 >> 11);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    53
    s1 ^= (s1 <<  7) & 0x9D2C5680U;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    54
    s1 ^= (s1 << 15) & 0xEFC60000U;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    55
    return(s1 ^ (s1 >> 18));
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    56
 }
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    57
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    58
6247
7d81e3a5d803 (svn r9050) -Codechange: Foo(void) -> Foo()
rubidium
parents: 6201
diff changeset
    59
uint32 RandomMT()
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    60
{
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    61
	uint32 y;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    62
2952
58522ed8f0f1 (svn r3511) More whitespace ([FS#46] by Rubidium)
tron
parents: 2548
diff changeset
    63
	if (--_mt_left < 0)
2075
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    64
		return ReloadMT();
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    65
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    66
	y  = *_mt_next++;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    67
	y ^= (y >> 11);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    68
	y ^= (y <<  7) & 0x9D2C5680U;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    69
	y ^= (y << 15) & 0xEFC60000U;
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    70
	return y ^ (y >> 18);
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    71
}
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    72
#else
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    73
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    74
void SeedMT(uint32 seed) {}
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    75
21d2986569d1 (svn r2585) - Fix [Makefile]: some small cleanups, remove warnings, and add mersenne to makefile (Luca)
Darkvater
parents: 2073
diff changeset
    76
#endif /* MERSENNE_TWISTER */