| 1 |
/* |
| 2 |
* This file is part of Deliantra, the Roguelike Realtime MMORPG. |
| 3 |
* |
| 4 |
* Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team |
| 5 |
* |
| 6 |
* Deliantra is free software: you can redistribute it and/or modify it under |
| 7 |
* the terms of the Affero GNU General Public License as published by the |
| 8 |
* Free Software Foundation, either version 3 of the License, or (at your |
| 9 |
* option) any later version. |
| 10 |
* |
| 11 |
* This program is distributed in the hope that it will be useful, |
| 12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 |
* GNU General Public License for more details. |
| 15 |
* |
| 16 |
* You should have received a copy of the Affero GNU General Public License |
| 17 |
* and the GNU General Public License along with this program. If not, see |
| 18 |
* <http://www.gnu.org/licenses/>. |
| 19 |
* |
| 20 |
* The authors can be reached via e-mail to <support@deliantra.net> |
| 21 |
*/ |
| 22 |
|
| 23 |
#ifndef RNG_H__ |
| 24 |
#define RNG_H__ |
| 25 |
|
| 26 |
#include <compiler.h> |
| 27 |
|
| 28 |
// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213. |
| 29 |
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps |
| 30 |
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps |
| 31 |
struct tausworthe_random_generator |
| 32 |
{ |
| 33 |
uint32_t state [4]; |
| 34 |
|
| 35 |
void seed (uint32_t seed); |
| 36 |
uint32_t next (); |
| 37 |
}; |
| 38 |
|
| 39 |
// Xorshift RNGs, George Marsaglia |
| 40 |
// http://www.jstatsoft.org/v08/i14/paper |
| 41 |
// this one is about 40% faster than the tausworthe one above (i.e. not much), |
| 42 |
// despite the inlining, and has the issue of only creating 2**32-1 numbers. |
| 43 |
// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf |
| 44 |
struct xorshift_random_generator |
| 45 |
{ |
| 46 |
uint32_t x, y; |
| 47 |
|
| 48 |
void seed (uint32_t seed) |
| 49 |
{ |
| 50 |
x = seed | 1; |
| 51 |
y = x * 69069U; |
| 52 |
} |
| 53 |
|
| 54 |
uint32_t next () |
| 55 |
{ |
| 56 |
uint32_t t = x ^ (x << 10); |
| 57 |
x = y; |
| 58 |
y = y ^ (y >> 13) ^ t ^ (t >> 10); |
| 59 |
return y; |
| 60 |
} |
| 61 |
}; |
| 62 |
|
| 63 |
template<typename T, int N, int k> |
| 64 |
struct gfsr_random_generator |
| 65 |
{ |
| 66 |
int i; |
| 67 |
T x[N]; |
| 68 |
|
| 69 |
// rng must have same bitwidth as T |
| 70 |
template<typename RNG> |
| 71 |
void seed_rng (RNG rng) |
| 72 |
{ |
| 73 |
i = N; |
| 74 |
|
| 75 |
do |
| 76 |
x [--i] = rng.next (); |
| 77 |
while (i > sizeof (T) * 8); |
| 78 |
|
| 79 |
T m = 1; |
| 80 |
|
| 81 |
do |
| 82 |
{ |
| 83 |
x [--i] = (rng.next () | m) & ~(m - 1); |
| 84 |
m <<= 1; |
| 85 |
} |
| 86 |
while (i); |
| 87 |
} |
| 88 |
|
| 89 |
// actually should subclass to gfsr32... :) |
| 90 |
void seed (uint32_t seed) |
| 91 |
{ |
| 92 |
xorshift_random_generator rng; |
| 93 |
|
| 94 |
rng.seed (seed); |
| 95 |
this->seed_rng (rng); |
| 96 |
} |
| 97 |
|
| 98 |
T next () |
| 99 |
{ |
| 100 |
int j = i + (k - N); |
| 101 |
|
| 102 |
if (j < 0) |
| 103 |
j += N; |
| 104 |
|
| 105 |
T v = (x [i] ^= x [j]); |
| 106 |
|
| 107 |
i = (i ? i : N) - 1; |
| 108 |
|
| 109 |
return v; |
| 110 |
} |
| 111 |
}; |
| 112 |
|
| 113 |
// these are about 2-3 times faster than tausworthe, non-inlined, |
| 114 |
// and likely of higher quality. |
| 115 |
typedef gfsr_random_generator<uint32_t, 250, 103> r250_random_generator; |
| 116 |
typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator; |
| 117 |
|
| 118 |
// freeciv uses this one, so it's good enough for us :) |
| 119 |
typedef gfsr_random_generator<uint32_t, 55, 24> freeciv_random_generator; |
| 120 |
|
| 121 |
// this one should be high quality, but is slightly slower than tausworthe |
| 122 |
struct r250521_random_generator |
| 123 |
{ |
| 124 |
r250_random_generator r250; |
| 125 |
r521_random_generator r521; |
| 126 |
|
| 127 |
void seed (uint32_t seed); |
| 128 |
uint32_t next (); |
| 129 |
}; |
| 130 |
|
| 131 |
// this is actually an adaptor that provides different types |
| 132 |
// of random numbers. |
| 133 |
template<class generator> |
| 134 |
struct random_number_generator : generator |
| 135 |
{ |
| 136 |
// uniform distribution, [0 .. num - 1] |
| 137 |
uint32_t operator ()(uint32_t num) |
| 138 |
{ |
| 139 |
return !is_constant (num) ? get_range (num) // non-constant |
| 140 |
: num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two |
| 141 |
: this->next () & (num - 1); // constant, power-of-two |
| 142 |
} |
| 143 |
|
| 144 |
// return a number within the closed interval [min .. max], max can be >, < or == min. |
| 145 |
int operator () (int r_min, int r_max) |
| 146 |
{ |
| 147 |
return is_constant (r_min <= r_max) && r_min <= r_max |
| 148 |
? r_min + operator ()(r_max - r_min + 1) |
| 149 |
: get_range (r_min, r_max); |
| 150 |
} |
| 151 |
|
| 152 |
// return a number within the half-open interval [0..1[ |
| 153 |
double operator ()() |
| 154 |
{ |
| 155 |
return this->next () / (double)0x100000000ULL; |
| 156 |
} |
| 157 |
|
| 158 |
uint32_t get_u32 (); |
| 159 |
uint64_t get_u64 (); |
| 160 |
|
| 161 |
protected: |
| 162 |
uint32_t get_range (uint32_t r_max); |
| 163 |
int get_range (int r_min, int r_max); |
| 164 |
}; |
| 165 |
|
| 166 |
// the default rng used in the game |
| 167 |
typedef random_number_generator<freeciv_random_generator> rand_gen; |
| 168 |
|
| 169 |
extern rand_gen rndm, rmg_rndm; |
| 170 |
|
| 171 |
#endif |
| 172 |
|
