Freeciv-3.2: /fast/freeciv/nightly/S3_2/utility/rand.c Source File

Freeciv-3.2

Loading...
Searching...
No Matches
rand.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13
14/*************************************************************************
15 The following random number generator can be found in _The Art of
16 Computer Programming Vol 2._ (2nd ed) by Donald E. Knuth. (C) 1998.
17 The algorithm is described in section 3.2.2 as Mitchell and Moore's
18 variant of a standard additive number generator. Note that the
19 the constants 55 and 24 are not random. Please become familiar with
20 this algorithm before you mess with it.
21
22 Since the additive number generator requires a table of numbers from
23 which to generate its random sequences, we must invent a way to
24 populate that table from a single seed value. I have chosen to do
25 this with a different PRNG, known as the "linear congruential method"
26 (also found in Knuth, Vol2). I must admit that my choices of constants
27 (3, 257, and MAX_UINT32) are probably not optimal, but they seem to
28 work well enough for our purposes.
29
30 Original author for this code: Cedric Tefft <cedric@earthling.net>
31 Modified to use rand_state struct by David Pfitzner <dwp@mso.anu.edu.au>
32*************************************************************************/
33
34#ifdef HAVE_CONFIG_H
35#include <fc_config.h>
36#endif
37
38/* utility */
39#include "log.h"
40#include "shared.h"
41#include "support.h" /* TRUE, FALSE */
42
43#include "rand.h"
44
45#define log_rand log_debug
46
47
48#define STD_RAND_VALUE_LOG(_c, _s, _nr, _f, _l) \
49 log_rand("%s(%lu) = %lu at %s:%d", _c, \
50 (unsigned long) _s, (unsigned long) _nr, \
51 _f, _l);
52
53
54#ifdef LOG_RAND_VALUES
55static bool randlog_enabled = TRUE;
56
57/*********************************************************************/
63void enable_randlog(bool enable)
64{
65 randlog_enabled = enable;
66}
67
68#define RAND_VALUE_LOG(_c, _s, _nr, _f, _l) \
69 if (randlog_enabled) { \
70 log_normal("%lu -> %lu %s:%d", \
71 (unsigned long) _s, (unsigned long) _nr, \
72 fc_basename(_f), _l); \
73 } else { \
74 STD_RAND_VALUE_LOG(_c, _s, _nr, _f, _l); \
75 }
76#else
77#define RAND_VALUE_LOG STD_RAND_VALUE_LOG
78#endif
79
80/* A global random state:
81 * Initialized by fc_srand(), updated by fc_rand(),
82 * Can be duplicated/saved/restored via fc_rand_state()
83 * and fc_rand_set_state().
84 */
85 static RANDOM_STATE rand_state;
86
87/*********************************************************************/
114 RANDOM_TYPE fc_rand_debug(RANDOM_TYPE size, const char *called_as,
115 int line, const char *file)
116{
117 RANDOM_TYPE new_rand;
118
119 fc_assert_ret_val(rand_state.is_init, 0);
120
121 if (size > 1) {
122 RANDOM_TYPE divisor, max;
123 int bailout = 0;
124
125 divisor = MAX_UINT32 / size;
126 max = size * divisor - 1;
127
128 do {
129 new_rand = (rand_state.v[rand_state.j]
130 + rand_state.v[rand_state.k]) & MAX_UINT32;
131
132 rand_state.x = (rand_state.x +1) % 56;
133 rand_state.j = (rand_state.j +1) % 56;
134 rand_state.k = (rand_state.k +1) % 56;
135 rand_state.v[rand_state.x] = new_rand;
136
137 if (++bailout > 10000) {
138 log_error("%s(%lu) = %lu bailout at %s:%d",
139 called_as, (unsigned long) size,
140 (unsigned long) new_rand, file, line);
141 new_rand = 0;
142 break;
143 }
144
145 } while (new_rand > max);
146
147 new_rand /= divisor;
148 } else {
149 new_rand = 0;
150 }
151
152 RAND_VALUE_LOG(called_as, (unsigned long) size,
153 (unsigned long) new_rand, file, line);
154
155 return new_rand;
156}
157
158/*********************************************************************/
161 void fc_srand(RANDOM_TYPE seed)
162{
163 int i;
164
165 rand_state.v[0] = (seed & MAX_UINT32);
166
167 for (i = 1; i < 56; i++) {
168 rand_state.v[i] = (3 * rand_state.v[i-1] + 257) & MAX_UINT32;
169 }
170
171 rand_state.j = (55 - 55);
172 rand_state.k = (55 - 24);
173 rand_state.x = (55 - 0);
174
175 rand_state.is_init = TRUE;
176
177 /* Heat it up a bit:
178 * Using modulus in fc_rand() this was important to pass
179 * test_random1(). Now using divisor in fc_rand() that particular
180 * test no longer indicates problems, but this seems a good idea
181 * anyway -- eg, other tests could well reveal other initial
182 * problems even using divisor.
183 */
184 for (i = 0; i < 10000; i++) {
185 (void) fc_rand(MAX_UINT32);
186 }
187}
188
189/*********************************************************************/
192 void fc_rand_uninit(void)
193{
194 rand_state.is_init = FALSE;
195}
196
197/*********************************************************************/
200 bool fc_rand_is_init(void)
201{
202 return rand_state.is_init;
203}
204
205/*********************************************************************/
208 RANDOM_STATE fc_rand_state(void)
209{
210 int i;
211
212 log_rand("fc_rand_state J=%d K=%d X=%d",
213 rand_state.j, rand_state.k, rand_state.x);
214 for (i = 0; i < 8; i++) {
215 log_rand("fc_rand_state %d, %08x %08x %08x %08x %08x %08x %08x",
216 i, rand_state.v[7 * i],
217 rand_state.v[7 * i + 1], rand_state.v[7 * i + 2],
218 rand_state.v[7 * i + 3], rand_state.v[7 * i + 4],
219 rand_state.v[7 * i + 5], rand_state.v[7 * i + 6]);
220 }
221
222 return rand_state;
223}
224
225/*********************************************************************/
229 void fc_rand_set_state(RANDOM_STATE state)
230{
231 int i;
232
233 rand_state = state;
234
235 log_rand("fc_rand_set_state J=%d K=%d X=%d",
236 rand_state.j, rand_state.k, rand_state.x);
237 for (i = 0; i < 8; i++) {
238 log_rand("fc_rand_set_state %d, %08x %08x %08x %08x %08x %08x %08x",
239 i, rand_state.v[7 * i],
240 rand_state.v[7 * i + 1], rand_state.v[7 * i + 2],
241 rand_state.v[7 * i + 3], rand_state.v[7 * i + 4],
242 rand_state.v[7 * i + 5], rand_state.v[7 * i + 6]);
243 }
244}
245
246/*********************************************************************/
253 void test_random1(int n)
254{
255 RANDOM_STATE saved_state;
256 int i, old_value = 0, new_value;
257 bool didchange, olddidchange = FALSE;
258 int behaviourchange = 0, behavioursame = 0;
259
260 saved_state = fc_rand_state();
261 /* fc_srand(time(NULL)); */ /* Use current state */
262
263 for (i = 0; i < n + 2; i++) {
264 new_value = fc_rand(2);
265 if (i > 0) { /* Have old */
266 didchange = (new_value != old_value);
267 if (i > 1) { /* Have olddidchange */
268 if (didchange != olddidchange) {
269 behaviourchange++;
270 } else {
271 behavioursame++;
272 }
273 }
274 olddidchange = didchange;
275 }
276 old_value = new_value;
277 }
278 log_test("test_random1(%d) same: %d, change: %d",
279 n, behavioursame, behaviourchange);
280
281 /* Restore state: */
282 fc_rand_set_state(saved_state);
283}
284
285/*********************************************************************/
292 RANDOM_TYPE fc_randomly_debug(RANDOM_TYPE seed, RANDOM_TYPE size,
293 const char *called_as,
294 int line, const char *file)
295{
296 RANDOM_TYPE result;
297
298#define LARGE_PRIME (10007)
299#define SMALL_PRIME (1009)
300
301 /* Check for overflow and underflow */
302 fc_assert_ret_val(seed < MAX_UINT32 / LARGE_PRIME, 0);
303 fc_assert_ret_val(size < SMALL_PRIME, 0);
304 fc_assert_ret_val(size > 0, 0);
305 result = ((seed * LARGE_PRIME) % SMALL_PRIME) % size;
306
307 log_rand("%s(%lu,%lu) = %lu at %s:%d",
308 called_as, (unsigned long) seed, (unsigned long) size,
309 (unsigned long) result, file, line);
310
311 return result;
312}
n
#define n
Definition astring.c:77
incite_cost
char * incite_cost
Definition comments.c:74
enable
#define enable(id)
Definition widget.h:223
log.h
log_test
#define log_test
Definition log.h:136
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
log_error
#define log_error(message,...)
Definition log.h:103
fc_rand_is_init
bool fc_rand_is_init(void)
Definition rand.c:200
fc_rand_state
RANDOM_STATE fc_rand_state(void)
Definition rand.c:208
fc_rand_debug
RANDOM_TYPE fc_rand_debug(RANDOM_TYPE size, const char *called_as, int line, const char *file)
Definition rand.c:114
fc_srand
void fc_srand(RANDOM_TYPE seed)
Definition rand.c:161
fc_randomly_debug
RANDOM_TYPE fc_randomly_debug(RANDOM_TYPE seed, RANDOM_TYPE size, const char *called_as, int line, const char *file)
Definition rand.c:292
log_rand
#define log_rand
Definition rand.c:45
rand_state
static RANDOM_STATE rand_state
Definition rand.c:85
RAND_VALUE_LOG
#define RAND_VALUE_LOG
Definition rand.c:77
test_random1
void test_random1(int n)
Definition rand.c:253
fc_rand_uninit
void fc_rand_uninit(void)
Definition rand.c:192
LARGE_PRIME
#define LARGE_PRIME
SMALL_PRIME
#define SMALL_PRIME
fc_rand_set_state
void fc_rand_set_state(RANDOM_STATE state)
Definition rand.c:229
rand.h
RANDOM_TYPE
uint32_t RANDOM_TYPE
Definition rand.h:26
fc_rand
#define fc_rand(_size)
Definition rand.h:56
shared.h
MAX_UINT32
#define MAX_UINT32
Definition shared.h:81
size
size_t size
Definition specvec.h:72
RANDOM_STATE
Definition rand.h:50
RANDOM_STATE::x
int x
Definition rand.h:52
RANDOM_STATE::v
RANDOM_TYPE v[56]
Definition rand.h:51
RANDOM_STATE::k
int k
Definition rand.h:52
RANDOM_STATE::is_init
bool is_init
Definition rand.h:53
RANDOM_STATE::j
int j
Definition rand.h:52
support.h
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47