/*
* This file is part of Deliantra, the Roguelike Realtime MMORPG.
*
* Copyright (©) 2010,2011 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
*
* Deliantra is free software: you can redistribute it and/or modify it under
* the terms of the Affero GNU General Public License as published by the
* Free Software Foundation, either version 3 of the License, or (at your
* option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the Affero GNU General Public License
* and the GNU General Public License along with this program. If not, see
* .
*
* The authors can be reached via e-mail to
*/
#ifndef RNG_H__
#define RNG_H__
#include
typedef uint32_t seed_t; // overkill
// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
struct tausworthe_rng
{
uint32_t state [4];
void seed (uint32_t seed);
uint32_t next ();
};
// Xorshift RNGs, George Marsaglia
// http://www.jstatsoft.org/v08/i14/paper
// this one is about 40% faster than the tausworthe one above (i.e. not much),
// despite the inlining, and has the issue of only creating 2**32-1 numbers.
// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
struct xorshift_rng
{
uint32_t x, y;
void seed (uint32_t seed)
{
x = seed ? seed : 0xdeadbeef;
y = x * 69069U;
}
uint32_t next ()
{
uint32_t t = x ^ (x << 10);
x = y;
y = y ^ (y >> 13) ^ t ^ (t >> 10);
return y;
}
};
template
struct lc_rng
{
uint32_t x;
void seed (uint32_t seed)
{
x = seed;
}
uint32_t next ()
{
x = x * A + B;
return x;
}
};
typedef lc_rng<3039177861U, 0U> borosh_niederreiter_rng;
typedef lc_rng<2147001325U, 715136305U> bcpl_rng;
typedef lc_rng< 1664525U, 1U> lavaux_janssens_rng;
template
struct gfsr_rng
{
int i;
T x[N];
// rng must have same bitwidth as T
template
void seed_rng (RNG rng)
{
i = N;
do
x [--i] = rng.next ();
while (i > sizeof (T) * 8);
T m = 1;
do
{
x [--i] = (rng.next () | m) & ~(m - 1);
m <<= 1;
}
while (i);
}
// actually should subclass to gfsr32... :)
void seed (seed_t seed)
{
xorshift_rng rng;
rng.seed (seed);
this->seed_rng (rng);
}
T next ()
{
int j = i + (k - N);
if (j < 0)
j += N;
T v = (x [i] ^= x [j]);
i = (i ? i : N) - 1;
return v;
}
};
// these are about 2-3 times faster than tausworthe, non-inlined,
// and likely of higher quality.
typedef gfsr_rng r250_rng;
typedef gfsr_rng r521_rng;
// freeciv uses this one, so it's good enough for us :)
// (also known as mitchell moore generator
typedef gfsr_rng freeciv_rng;
// this one should be high quality, but is slightly slower than tausworthe
struct r250521_rng
{
r250_rng r250;
r521_rng r521;
void seed (uint32_t seed);
uint32_t next ();
};
/////////////////////////////////////////////////////////////////////////////
// this is actually an adaptor that provides different
// distributions of random numbers.
template
struct random_number_generator : generator
{
random_number_generator ()
{
}
random_number_generator (seed_t seed)
{
this->seed (seed);
}
// uniform distribution, [0 .. num - 1]
uint32_t operator ()(uint32_t num)
{
return !is_constant (num) ? get_range (num) // non-constant
: num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
: this->next () & (num - 1); // constant, power-of-two
}
// return a number within the closed interval [min .. max], max can be >, < or == min.
int operator () (int r_min, int r_max)
{
return is_constant (r_min <= r_max) && r_min <= r_max
? r_min + operator ()(r_max - r_min + 1)
: get_range (r_min, r_max);
}
uint32_t get_u32 ();
uint64_t get_u64 ();
float get_float ();
double get_double ();
// return a number within the half-open interval [0..1[
double operator () ()
{
return get_double ();
}
uint32_t poisson (double mean);
protected:
uint32_t get_range (uint32_t r_max);
int get_range (int r_min, int r_max);
};
// the default rng used in the game
typedef random_number_generator rand_gen;
// used when we often seed
typedef random_number_generator seedable_rand_gen;
extern rand_gen rndm, rmg_rndm;
#endif