server/include/rng.h

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2010 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
 * <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

#ifndef RNG_H__
#define RNG_H__

#include <compiler.h>

// 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_random_generator
{
  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_random_generator
{
  uint32_t x, y;

  void seed (uint32_t seed)
  {
    x = seed | 1;
    y = x * 69069U;
  }

  uint32_t next ()
  {
    uint32_t t = x ^ (x << 10);
    x = y;
    y = y ^ (y >> 13) ^ t ^ (t >> 10);
    return y;
  }
};

template<typename T, int N, int k>
struct gfsr_random_generator
{
  int i;
  T x[N];

  // rng must have same bitwidth as T
  template<typename RNG>
  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 (uint32_t seed)
  {
    xorshift_random_generator 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_random_generator<uint32_t, 250, 103> r250_random_generator;
typedef gfsr_random_generator<uint32_t, 521, 168> r521_random_generator;

// freeciv uses this one, so it's good enough for us :)
typedef gfsr_random_generator<uint32_t,  55,  24> freeciv_random_generator;

// this one should be high quality, but is slightly slower than tausworthe
struct r250521_random_generator
{
  r250_random_generator r250;
  r521_random_generator r521;

  void seed (uint32_t seed);
  uint32_t next ();
};

// this is actually an adaptor that provides different types
// of random numbers.
template<class generator>
struct random_number_generator : generator
{
  // 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);
  }

  // return a number within the half-open interval [0..1[
  double operator ()()
  {
    return this->next () / (double)0x100000000ULL;
  }

  uint32_t get_u32 ();
  uint64_t get_u64 ();

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<freeciv_random_generator> rand_gen;

extern rand_gen rndm, rmg_rndm;

#endif

Revision:	1.1
Committed:	Fri Jul 2 02:00:47 2010 UTC (13 years, 10 months ago) by root
Content type:	text/plain
Branch:	MAIN
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.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