server/include/rng.h

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 *
 * Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
 * Copyright (©) 2010,2011,2012,2013,2014,2015,2016 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 "ecb.h"

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<uint32_t A, uint32_t B>
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;
typedef lc_rng<   1664525U, 1013904223U> numerical_recipes_rng;

template<typename T, int N, int k>
struct gfsr_rng
{
  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 (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<uint32_t, 250, 103> r250_rng;
typedef gfsr_rng<uint32_t, 521, 168> r521_rng;

// freeciv uses this one, so it's good enough for us :)
// (also known as mitchell moore generator)
typedef gfsr_rng<uint32_t,  55,  24> 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<class generator>
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 !ecb_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 ecb_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<freeciv_rng> rand_gen;

// used when we often seed
typedef random_number_generator<tausworthe_rng> seedable_rand_gen;

extern rand_gen rndm, rmg_rndm;

#endif

Revision:	1.16
Committed:	Wed Dec 5 21:18:37 2018 UTC (5 years, 5 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.15:	+1 -1 lines
Log Message:	nuke compiler.h
#	User	Rev	Content
1	root	1.1	/*
2			* This file is part of Deliantra, the Roguelike Realtime MMORPG.
3	root	1.12	*
4	root	1.15	* Copyright (©) 2017,2018 Marc Alexander Lehmann / the Deliantra team
5	root	1.13	* Copyright (©) 2010,2011,2012,2013,2014,2015,2016 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
6	root	1.12	*
7	root	1.1	* Deliantra is free software: you can redistribute it and/or modify it under
8			* the terms of the Affero GNU General Public License as published by the
9			* Free Software Foundation, either version 3 of the License, or (at your
10			* option) any later version.
11	root	1.12	*
12	root	1.1	* This program is distributed in the hope that it will be useful,
13			* but WITHOUT ANY WARRANTY; without even the implied warranty of
14			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15			* GNU General Public License for more details.
16	root	1.12	*
17	root	1.1	* You should have received a copy of the Affero GNU General Public License
18			* and the GNU General Public License along with this program. If not, see
19			* <http://www.gnu.org/licenses/>.
20	root	1.12	*
21	root	1.1	* The authors can be reached via e-mail to <support@deliantra.net>
22			*/
23
24			#ifndef RNG_H__
25			#define RNG_H__
26
27	root	1.16	#include "ecb.h"
28	root	1.1
29	root	1.7	typedef uint32_t seed_t; // overkill
30
31	root	1.1	// P. L'Ecuyer, “Maximally Equidistributed Combined Tausworthe Generators”, Mathematics of Computation, 65, 213 (1996), 203–213.
32			// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
33			// http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
34	root	1.3	struct tausworthe_rng
35	root	1.1	{
36			uint32_t state [4];
37
38			void seed (uint32_t seed);
39			uint32_t next ();
40			};
41
42			// Xorshift RNGs, George Marsaglia
43			// http://www.jstatsoft.org/v08/i14/paper
44			// this one is about 40% faster than the tausworthe one above (i.e. not much),
45			// despite the inlining, and has the issue of only creating 2**32-1 numbers.
46			// see also http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
47	root	1.3	struct xorshift_rng
48	root	1.1	{
49			uint32_t x, y;
50
51			void seed (uint32_t seed)
52			{
53	root	1.4	x = seed ? seed : 0xdeadbeef;
54	root	1.1	y = x * 69069U;
55			}
56
57			uint32_t next ()
58			{
59			uint32_t t = x ^ (x << 10);
60			x = y;
61			y = y ^ (y >> 13) ^ t ^ (t >> 10);
62			return y;
63			}
64			};
65
66	root	1.3	template<uint32_t A, uint32_t B>
67			struct lc_rng
68			{
69			uint32_t x;
70
71			void seed (uint32_t seed)
72			{
73			x = seed;
74			}
75
76			uint32_t next ()
77			{
78			x = x * A + B;
79			return x;
80			}
81			};
82
83	root	1.10	typedef lc_rng<3039177861U, 0U> borosh_niederreiter_rng;
84			typedef lc_rng<2147001325U, 715136305U> bcpl_rng;
85			typedef lc_rng< 1664525U, 1U> lavaux_janssens_rng;
86			typedef lc_rng< 1664525U, 1013904223U> numerical_recipes_rng;
87	root	1.3
88	root	1.1	template<typename T, int N, int k>
89	root	1.3	struct gfsr_rng
90	root	1.1	{
91			int i;
92			T x[N];
93
94			// rng must have same bitwidth as T
95			template<typename RNG>
96			void seed_rng (RNG rng)
97			{
98			i = N;
99
100			do
101			x [--i] = rng.next ();
102			while (i > sizeof (T) * 8);
103
104			T m = 1;
105
106			do
107			{
108			x [--i] = (rng.next () \| m) & ~(m - 1);
109			m <<= 1;
110			}
111			while (i);
112			}
113
114			// actually should subclass to gfsr32... :)
115	root	1.7	void seed (seed_t seed)
116	root	1.1	{
117	root	1.3	xorshift_rng rng;
118	root	1.1
119			rng.seed (seed);
120			this->seed_rng (rng);
121			}
122
123			T next ()
124			{
125			int j = i + (k - N);
126
127			if (j < 0)
128			j += N;
129
130			T v = (x [i] ^= x [j]);
131
132			i = (i ? i : N) - 1;
133
134			return v;
135			}
136			};
137
138			// these are about 2-3 times faster than tausworthe, non-inlined,
139			// and likely of higher quality.
140	root	1.3	typedef gfsr_rng<uint32_t, 250, 103> r250_rng;
141			typedef gfsr_rng<uint32_t, 521, 168> r521_rng;
142	root	1.1
143			// freeciv uses this one, so it's good enough for us :)
144	root	1.11	// (also known as mitchell moore generator)
145	root	1.3	typedef gfsr_rng<uint32_t, 55, 24> freeciv_rng;
146	root	1.1
147			// this one should be high quality, but is slightly slower than tausworthe
148	root	1.3	struct r250521_rng
149	root	1.1	{
150	root	1.3	r250_rng r250;
151			r521_rng r521;
152	root	1.1
153			void seed (uint32_t seed);
154			uint32_t next ();
155			};
156
157	root	1.8	/////////////////////////////////////////////////////////////////////////////
158
159	root	1.5	// this is actually an adaptor that provides different
160			// distributions of random numbers.
161	root	1.1	template<class generator>
162			struct random_number_generator : generator
163			{
164	root	1.2	random_number_generator ()
165			{
166			}
167
168	root	1.7	random_number_generator (seed_t seed)
169	root	1.2	{
170			this->seed (seed);
171			}
172
173	root	1.1	// uniform distribution, [0 .. num - 1]
174			uint32_t operator ()(uint32_t num)
175			{
176	root	1.14	return !ecb_is_constant (num) ? get_range (num) // non-constant
177			: num & (num - 1) ? (this->next () * (uint64_t)num) >> 32U // constant, non-power-of-two
178			: this->next () & (num - 1); // constant, power-of-two
179	root	1.1	}
180
181			// return a number within the closed interval [min .. max], max can be >, < or == min.
182			int operator () (int r_min, int r_max)
183			{
184	root	1.14	return ecb_is_constant (r_min <= r_max) && r_min <= r_max
185	root	1.1	? r_min + operator ()(r_max - r_min + 1)
186			: get_range (r_min, r_max);
187			}
188
189	root	1.3	uint32_t get_u32 ();
190			uint64_t get_u64 ();
191			float get_float ();
192			double get_double ();
193
194	root	1.1	// return a number within the half-open interval [0..1[
195	root	1.3	double operator () ()
196	root	1.1	{
197	root	1.3	return get_double ();
198	root	1.1	}
199
200	root	1.3	uint32_t poisson (double mean);
201	root	1.1
202			protected:
203			uint32_t get_range (uint32_t r_max);
204			int get_range (int r_min, int r_max);
205			};
206
207			// the default rng used in the game
208	root	1.3	typedef random_number_generator<freeciv_rng> rand_gen;
209	root	1.1
210	root	1.2	// used when we often seed
211	root	1.3	typedef random_number_generator<tausworthe_rng> seedable_rand_gen;
212	root	1.2
213	root	1.1	extern rand_gen rndm, rmg_rndm;
214
215			#endif
216