Freeciv-3.1: /fast/freeciv/nightly/S3_1/utility/rand.c Source File

Freeciv-3.1

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/* A global random state:
48 * Initialized by fc_srand(), updated by fc_rand(),
49 * Can be duplicated/saved/restored via fc_rand_state()
50 * and fc_rand_set_state().
51 */
52 static RANDOM_STATE rand_state;
53
54/*********************************************************************/
81 RANDOM_TYPE fc_rand_debug(RANDOM_TYPE size, const char *called_as,
82 int line, const char *file)
83{
84 RANDOM_TYPE new_rand;
85
86 fc_assert_ret_val(rand_state.is_init, 0);
87
88 if (size > 1) {
89 RANDOM_TYPE divisor, max;
90 int bailout = 0;
91
92 divisor = MAX_UINT32 / size;
93 max = size * divisor - 1;
94 do {
95 new_rand = (rand_state.v[rand_state.j]
96 + rand_state.v[rand_state.k]) & MAX_UINT32;
97
98 rand_state.x = (rand_state.x +1) % 56;
99 rand_state.j = (rand_state.j +1) % 56;
100 rand_state.k = (rand_state.k +1) % 56;
101 rand_state.v[rand_state.x] = new_rand;
102
103 if (++bailout > 10000) {
104 log_error("%s(%lu) = %lu bailout at %s:%d",
105 called_as, (unsigned long) size,
106 (unsigned long) new_rand, file, line);
107 new_rand = 0;
108 break;
109 }
110
111 } while (new_rand > max);
112
113 new_rand /= divisor;
114 } else {
115 new_rand = 0;
116 }
117
118 log_rand("%s(%lu) = %lu at %s:%d",
119 called_as, (unsigned long) size,
120 (unsigned long) new_rand, file, line);
121
122 return new_rand;
123}
124
125/*********************************************************************/
128 void fc_srand(RANDOM_TYPE seed)
129{
130 int i;
131
132 rand_state.v[0] = (seed & MAX_UINT32);
133
134 for (i = 1; i < 56; i++) {
135 rand_state.v[i] = (3 * rand_state.v[i-1] + 257) & MAX_UINT32;
136 }
137
138 rand_state.j = (55-55);
139 rand_state.k = (55-24);
140 rand_state.x = (55-0);
141
142 rand_state.is_init = TRUE;
143
144 /* Heat it up a bit:
145 * Using modulus in fc_rand() this was important to pass
146 * test_random1(). Now using divisor in fc_rand() that particular
147 * test no longer indicates problems, but this seems a good idea
148 * anyway -- eg, other tests could well reveal other initial
149 * problems even using divisor.
150 */
151 for (i = 0; i < 10000; i++) {
152 (void) fc_rand(MAX_UINT32);
153 }
154}
155
156/*********************************************************************/
159 void fc_rand_uninit(void)
160{
161 rand_state.is_init = FALSE;
162}
163
164/*********************************************************************/
167 bool fc_rand_is_init(void)
168{
169 return rand_state.is_init;
170}
171
172/*********************************************************************/
175 RANDOM_STATE fc_rand_state(void)
176{
177 int i;
178
179 log_rand("fc_rand_state J=%d K=%d X=%d",
180 rand_state.j, rand_state.k, rand_state.x);
181 for (i = 0; i < 8; i++) {
182 log_rand("fc_rand_state %d, %08x %08x %08x %08x %08x %08x %08x",
183 i, rand_state.v[7 * i],
184 rand_state.v[7 * i + 1], rand_state.v[7 * i + 2],
185 rand_state.v[7 * i + 3], rand_state.v[7 * i + 4],
186 rand_state.v[7 * i + 5], rand_state.v[7 * i + 6]);
187 }
188
189 return rand_state;
190}
191
192/*********************************************************************/
196 void fc_rand_set_state(RANDOM_STATE state)
197{
198 int i;
199
200 rand_state = state;
201
202 log_rand("fc_rand_set_state J=%d K=%d X=%d",
203 rand_state.j, rand_state.k, rand_state.x);
204 for (i = 0; i < 8; i++) {
205 log_rand("fc_rand_set_state %d, %08x %08x %08x %08x %08x %08x %08x",
206 i, rand_state.v[7 * i],
207 rand_state.v[7 * i + 1], rand_state.v[7 * i + 2],
208 rand_state.v[7 * i + 3], rand_state.v[7 * i + 4],
209 rand_state.v[7 * i + 5], rand_state.v[7 * i + 6]);
210 }
211}
212
213/*********************************************************************/
220 void test_random1(int n)
221{
222 RANDOM_STATE saved_state;
223 int i, old_value = 0, new_value;
224 bool didchange, olddidchange = FALSE;
225 int behaviourchange = 0, behavioursame = 0;
226
227 saved_state = fc_rand_state();
228 /* fc_srand(time(NULL)); */ /* use current state */
229
230 for (i = 0; i < n+2; i++) {
231 new_value = fc_rand(2);
232 if (i > 0) { /* have old */
233 didchange = (new_value != old_value);
234 if (i > 1) { /* have olddidchange */
235 if (didchange != olddidchange) {
236 behaviourchange++;
237 } else {
238 behavioursame++;
239 }
240 }
241 olddidchange = didchange;
242 }
243 old_value = new_value;
244 }
245 log_test("test_random1(%d) same: %d, change: %d",
246 n, behavioursame, behaviourchange);
247
248 /* restore state: */
249 fc_rand_set_state(saved_state);
250}
251
252/*********************************************************************/
259 RANDOM_TYPE fc_randomly_debug(RANDOM_TYPE seed, RANDOM_TYPE size,
260 const char *called_as,
261 int line, const char *file)
262{
263 RANDOM_TYPE result;
264
265#define LARGE_PRIME (10007)
266#define SMALL_PRIME (1009)
267
268 /* Check for overflow and underflow */
269 fc_assert_ret_val(seed < MAX_UINT32 / LARGE_PRIME, 0);
270 fc_assert_ret_val(size < SMALL_PRIME, 0);
271 fc_assert_ret_val(size > 0, 0);
272 result = ((seed * LARGE_PRIME) % SMALL_PRIME) % size;
273
274 log_rand("%s(%lu,%lu) = %lu at %s:%d",
275 called_as, (unsigned long) seed, (unsigned long) size,
276 (unsigned long) result, file, line);
277
278 return result;
279}
n
#define n
Definition astring.c:77
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:167
fc_rand_state
RANDOM_STATE fc_rand_state(void)
Definition rand.c:175
fc_rand_debug
RANDOM_TYPE fc_rand_debug(RANDOM_TYPE size, const char *called_as, int line, const char *file)
Definition rand.c:81
fc_srand
void fc_srand(RANDOM_TYPE seed)
Definition rand.c:128
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:259
log_rand
#define log_rand
Definition rand.c:45
rand_state
static RANDOM_STATE rand_state
Definition rand.c:52
test_random1
void test_random1(int n)
Definition rand.c:220
fc_rand_uninit
void fc_rand_uninit(void)
Definition rand.c:159
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:196
rand.h
RANDOM_TYPE
uint32_t RANDOM_TYPE
Definition rand.h:26
fc_rand
#define fc_rand(_size)
Definition rand.h:34
shared.h
MAX_UINT32
#define MAX_UINT32
Definition shared.h:81
size
size_t size
Definition specvec.h:72
RANDOM_STATE
Definition rand.h:28
RANDOM_STATE::x
int x
Definition rand.h:30
RANDOM_STATE::v
RANDOM_TYPE v[56]
Definition rand.h:29
RANDOM_STATE::k
int k
Definition rand.h:30
RANDOM_STATE::is_init
bool is_init
Definition rand.h:31
RANDOM_STATE::j
int j
Definition rand.h:30
support.h
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47