1 /*
2 ** m_random.cpp
3 ** Random number generators
4 **
5 **---------------------------------------------------------------------------
6 ** Copyright 2002-2009 Randy Heit
7 ** All rights reserved.
8 **
9 ** Redistribution and use in source and binary forms, with or without
10 ** modification, are permitted provided that the following conditions
11 ** are met:
12 **
13 ** 1. Redistributions of source code must retain the above copyright
14 ** notice, this list of conditions and the following disclaimer.
15 ** 2. Redistributions in binary form must reproduce the above copyright
16 ** notice, this list of conditions and the following disclaimer in the
17 ** documentation and/or other materials provided with the distribution.
18 ** 3. The name of the author may not be used to endorse or promote products
19 ** derived from this software without specific prior written permission.
20 **
21 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 **---------------------------------------------------------------------------
32 **
33 ** This file employs the techniques for improving demo sync and backward
34 ** compatibility that Lee Killough introduced with BOOM. However, none of
35 ** the actual code he wrote is left. In contrast to BOOM, each RNG source
36 ** in ZDoom is implemented as a separate class instance that provides an
37 ** interface to the high-quality Mersenne Twister. See
38 ** <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html>.
39 **
40 ** As Killough's description from m_random.h is still mostly relevant,
41 ** here it is:
42 ** killough 2/16/98:
43 **
44 ** Make every random number generator local to each control-equivalent block.
45 ** Critical for demo sync. The random number generators are made local to
46 ** reduce the chances of sync problems. In Doom, if a single random number
47 ** generator call was off, it would mess up all random number generators.
48 ** This reduces the chances of it happening by making each RNG local to a
49 ** control flow block.
50 **
51 ** Notes to developers: if you want to reduce your demo sync hassles, follow
52 ** this rule: for each call to P_Random you add, add a new class to the enum
53 ** type below for each block of code which calls P_Random. If two calls to
54 ** P_Random are not in "control-equivalent blocks", i.e. there are any cases
55 ** where one is executed, and the other is not, put them in separate classes.
56 */
57
58 // HEADER FILES ------------------------------------------------------------
59
60 #include <assert.h>
61
62 //#include "doomstat.h"
63 #include "wl_def.h"
64 #include "m_random.h"
65 //#include "farchive.h"
66 //#include "b_bot.h"
67 #include "m_png.h"
68 #include "m_crc32.h"
69 //#include "i_system.h"
70 //#include "c_dispatch.h"
71 #include "files.h"
72 #include "farchive.h"
73 #include "wl_loadsave.h"
74
75 // MACROS ------------------------------------------------------------------
76
77 #define RAND_ID MAKE_ID('r','a','N','d')
78
79 // TYPES -------------------------------------------------------------------
80
81 // EXTERNAL FUNCTION PROTOTYPES --------------------------------------------
82
83 // PUBLIC FUNCTION PROTOTYPES ----------------------------------------------
84
85 // PRIVATE FUNCTION PROTOTYPES ---------------------------------------------
86
87 // EXTERNAL DATA DECLARATIONS ----------------------------------------------
88
89 extern FRandom pr_spawnmobj;
90 extern FRandom pr_chase;
91 /*extern FRandom pr_acs;
92 extern FRandom pr_exrandom;*/
93
94 // PUBLIC DATA DEFINITIONS -------------------------------------------------
95
96 FRandom M_Random;
97
98 // Global seed. This is modified predictably to initialize every RNG.
99 DWORD rngseed;
100
101 // PRIVATE DATA DEFINITIONS ------------------------------------------------
102
103 #include "m_random_oldtable.h"
104
105 FRandom *FRandom::RNGList;
106 static TDeletingArray<FRandom *> NewRNGs;
107
108 // CODE --------------------------------------------------------------------
109
110 //==========================================================================
111 //
112 // FRandom - Nameless constructor
113 //
114 // Constructing an RNG in this way means it won't be stored in savegames.
115 //
116 //==========================================================================
117
FRandom()118 FRandom::FRandom ()
119 : NameCRC (0)
120 {
121 #ifndef NDEBUG
122 Name = NULL;
123 initialized = false;
124 #endif
125 Next = RNGList;
126 RNGList = this;
127 }
128
129 //==========================================================================
130 //
131 // FRandom - Named constructor
132 //
133 // This is the standard way to construct RNGs.
134 //
135 //==========================================================================
136
FRandom(const char * name)137 FRandom::FRandom (const char *name)
138 {
139 NameCRC = CalcCRC32 ((const BYTE *)name, (unsigned int)strlen (name));
140 #ifndef NDEBUG
141 initialized = false;
142 Name = name;
143 // A CRC of 0 is reserved for nameless RNGs that don't get stored
144 // in savegames. The chance is very low that you would get a CRC of 0,
145 // but it's still possible.
146 assert (NameCRC != 0);
147 #endif
148
149 // Insert the RNG in the list, sorted by CRC
150 FRandom **prev = &RNGList, *probe = RNGList;
151
152 while (probe != NULL && probe->NameCRC < NameCRC)
153 {
154 prev = &probe->Next;
155 probe = probe->Next;
156 }
157
158 #ifndef NDEBUG
159 if (probe != NULL)
160 {
161 // Because RNGs are identified by their CRCs in save games,
162 // no two RNGs can have names that hash to the same CRC.
163 // Obviously, this means every RNG must have a unique name.
164 assert (probe->NameCRC != NameCRC);
165 }
166 #endif
167
168 Next = probe;
169 *prev = this;
170 }
171
172 //==========================================================================
173 //
174 // FRandom - Destructor
175 //
176 //==========================================================================
177
~FRandom()178 FRandom::~FRandom ()
179 {
180 FRandom *rng, **prev;
181
182 FRandom *last = NULL;
183
184 prev = &RNGList;
185 rng = RNGList;
186
187 while (rng != NULL && rng != this)
188 {
189 last = rng;
190 rng = rng->Next;
191 }
192
193 if (rng != NULL)
194 {
195 *prev = rng->Next;
196 }
197 }
198
199 //==========================================================================
200 //
201 // FRandom :: RandomOld
202 //
203 //==========================================================================
204
RandomOld(bool useOld)205 int FRandom::RandomOld(bool useOld)
206 {
207 return useOld ? old_rndtable[oldidx++] : (++oldidx, GenRand32()&0xFF);
208 }
209
210 //==========================================================================
211 //
212 // FRandom :: StaticClearRandom
213 //
214 // Initialize every RNGs. RNGs are seeded based on the global seed and their
215 // name, so each different RNG can have a different starting value despite
216 // being derived from a common global seed.
217 //
218 //==========================================================================
219
StaticClearRandom()220 void FRandom::StaticClearRandom ()
221 {
222 // go through each RNG and set each starting seed differently
223 for (FRandom *rng = FRandom::RNGList; rng != NULL; rng = rng->Next)
224 {
225 rng->Init(rngseed);
226 }
227 }
228
229 //==========================================================================
230 //
231 // FRandom :: Init
232 //
233 // Initialize a single RNG with a given seed.
234 //
235 //==========================================================================
236
Init(DWORD seed)237 void FRandom::Init(DWORD seed)
238 {
239 // [RH] Use the RNG's name's CRC to modify the original seed.
240 // This way, new RNGs can be added later, and it doesn't matter
241 // which order they get initialized in.
242 DWORD seeds[2] = { NameCRC, seed };
243 InitByArray(seeds, 2);
244
245 oldidx = sfmt.u[0]&0xFF;
246 }
247
248 //==========================================================================
249 //
250 // FRandom :: StaticSumSeeds
251 //
252 // This function produces a DWORD that can be used to check the consistancy
253 // of network games between different machines. Only a select few RNGs are
254 // used for the sum, because not all RNGs are important to network sync.
255 //
256 //==========================================================================
257
StaticSumSeeds()258 DWORD FRandom::StaticSumSeeds ()
259 {
260 return pr_spawnmobj.sfmt.u[0] + pr_spawnmobj.idx +
261 pr_chase.sfmt.u[0] + pr_chase.idx;
262 }
263
264 //==========================================================================
265 //
266 // FRandom :: StaticWriteRNGState
267 //
268 // Stores the state of every RNG into a savegame.
269 //
270 //==========================================================================
271
StaticWriteRNGState(FILE * file)272 void FRandom::StaticWriteRNGState (FILE *file)
273 {
274 FRandom *rng;
275 FPNGChunkArchive arc (file, RAND_ID);
276
277 arc << rngseed;
278
279 for (rng = FRandom::RNGList; rng != NULL; rng = rng->Next)
280 {
281 // Only write those RNGs that have names
282 if (rng->NameCRC != 0)
283 {
284 arc << rng->NameCRC << rng->idx << rng->oldidx;
285 for (int i = 0; i < SFMT::N32; ++i)
286 {
287 arc << rng->sfmt.u[i];
288 }
289 }
290 }
291 }
292
293 //==========================================================================
294 //
295 // FRandom :: StaticReadRNGState
296 //
297 // Restores the state of every RNG from a savegame. RNGs that were added
298 // since the savegame was created are cleared to their initial value.
299 //
300 //==========================================================================
301
StaticReadRNGState(PNGHandle * png)302 void FRandom::StaticReadRNGState (PNGHandle *png)
303 {
304 FRandom *rng;
305
306 size_t len = M_FindPNGChunk (png, RAND_ID);
307
308 if (len != 0)
309 {
310 const size_t sizeof_rng = sizeof(rng->NameCRC) + sizeof(rng->idx) + sizeof(rng->sfmt.u);
311 const int rngcount = (int)((len-4) / sizeof_rng);
312 int i;
313 DWORD crc;
314
315 FPNGChunkArchive arc (png->File->GetFile(), RAND_ID, len);
316
317 arc << rngseed;
318 FRandom::StaticClearRandom ();
319
320 for (i = rngcount; i; --i)
321 {
322 arc << crc;
323 for (rng = FRandom::RNGList; rng != NULL; rng = rng->Next)
324 {
325 if (rng->NameCRC == crc)
326 {
327 arc << rng->idx;
328 if(GameSave::SaveVersion >= 1379630950u)
329 arc << rng->oldidx;
330 for (int i = 0; i < SFMT::N32; ++i)
331 {
332 arc << rng->sfmt.u[i];
333 }
334 break;
335 }
336 }
337 if (rng == NULL)
338 { // The RNG was removed. Skip it.
339 int idx;
340 DWORD sfmt;
341 arc << idx;
342 if(GameSave::SaveVersion >= 1379630950u)
343 arc << rng->oldidx;
344 for (int i = 0; i < SFMT::N32; ++i)
345 {
346 arc << sfmt;
347 }
348 }
349 }
350 png->File->ResetFilePtr();
351 }
352 }
353
354 //==========================================================================
355 //
356 // FRandom :: StaticFindRNG
357 //
358 // This function attempts to find an RNG with the given name.
359 // If it can't it will create a new one. Duplicate CRCs will
360 // be ignored and if it happens map to the same RNG.
361 // This is for use by DECORATE.
362 //
363 //==========================================================================
364
StaticFindRNG(const char * name)365 FRandom *FRandom::StaticFindRNG (const char *name)
366 {
367 DWORD NameCRC = CalcCRC32 ((const BYTE *)name, (unsigned int)strlen (name));
368
369 // Use the default RNG if this one happens to have a CRC of 0.
370 //if (NameCRC == 0) return &pr_exrandom;
371
372 // Find the RNG in the list, sorted by CRC
373 FRandom **prev = &RNGList, *probe = RNGList;
374
375 while (probe != NULL && probe->NameCRC < NameCRC)
376 {
377 prev = &probe->Next;
378 probe = probe->Next;
379 }
380 // Found one so return it.
381 if (probe == NULL || probe->NameCRC != NameCRC)
382 {
383 // A matching RNG doesn't exist yet so create it.
384 probe = new FRandom(name);
385
386 // Store the new RNG for destruction when ZDoom quits.
387 NewRNGs.Push(probe);
388 }
389 return probe;
390 }
391
392 //==========================================================================
393 //
394 // FRandom :: StaticPrintSeeds
395 //
396 // Prints a snapshot of the current RNG states. This is probably wrong.
397 //
398 //==========================================================================
399
400 #if 0
401 #ifndef NDEBUG
402 void FRandom::StaticPrintSeeds ()
403 {
404 FRandom *rng = RNGList;
405
406 while (rng != NULL)
407 {
408 int idx = rng->idx < SFMT::N32 ? rng->idx : 0;
409 Printf ("%s: %08x .. %d\n", rng->Name, rng->sfmt.u[idx], idx);
410 rng = rng->Next;
411 }
412 }
413
414 CCMD (showrngs)
415 {
416 FRandom::StaticPrintSeeds ();
417 }
418 #endif
419 #endif
420
421