1 /*
2  * PROPRIETARY INFORMATION.  This software is proprietary to POWDER
3  * Development, and is not to be reproduced, transmitted, or disclosed
4  * in any way without written permission.
5  *
6  * Produced by:	Jeff Lait
7  *
8  *      	POWDER Development
9  *
10  * NAME:        rand.cpp ( POWDER Library, C++ )
11  *
12  * COMMENTS:
13  *	A collection of utility functions to get random numbers.
14  */
15 
16 #include "mygba.h"
17 
18 #include "assert.h"
19 #include "rand.h"
20 #include "dpdf_table.h"
21 
22 // Bring in the Mersenne Twister
23 #include "mt19937ar.c"
24 
25 #include <ctype.h>
26 
27 class RAND_STATE
28 {
29 public:
30     // Read from current RNG into this
31     void	 read();
32     // Write from this into RNG.
33     void	 write();
34 
35     RAND_STATE	*myOlderState;
36     unsigned long	myMT[N];
37     unsigned int	myMTI;
38 };
39 
40 void
read()41 RAND_STATE::read()
42 {
43     memcpy(myMT, mt, sizeof(unsigned long) * N);
44     myMTI = mti;
45 }
46 
47 void
write()48 RAND_STATE::write()
49 {
50     memcpy(mt, myMT, sizeof(unsigned long) * N);
51     mti = myMTI;
52 }
53 
54 RAND_STATE *glbOldRandState = 0;
55 
56 void
rand_pushstate()57 rand_pushstate()
58 {
59     RAND_STATE		*state;
60 
61     state = new RAND_STATE();
62     state->myOlderState = glbOldRandState;
63     state->read();
64     glbOldRandState = state;
65 }
66 
67 void
rand_popstate()68 rand_popstate()
69 {
70     UT_ASSERT(glbOldRandState != 0);
71     if (!glbOldRandState)
72 	return;
73 
74     RAND_STATE	*state;
75     state = glbOldRandState;
76     state->write();
77     glbOldRandState = state->myOlderState;
78     delete state;
79 }
80 
81 void
rand_init()82 rand_init()
83 {
84     if (!mt)
85     {
86 	mt = new unsigned long[N];
87     }
88 }
89 
90 const u8 glb_percenttable[1024] =
91 {
92     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
93     1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3,
94     3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
95     4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
96     6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7,
97     7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9,
98     9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
99     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,
100     12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14,
101     14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15,
102     15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17,
103     17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18,
104     18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20,
105     20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21,
106     21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23,
107     23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25,
108     25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26,
109     26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28,
110     28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29,
111     29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31,
112     31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32,
113     32, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 34, 34, 34, 34,
114     34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35,
115     36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37,
116     37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 39,
117     39, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40,
118     40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42,
119     42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, 43, 43,
120     43, 43, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 45, 45, 45, 45,
121     45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 46, 46, 46,
122     46, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48, 48, 48, 48,
123     48, 48, 48, 48, 48, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 50,
124     50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51,
125     51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53,
126     53, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 54, 54,
127     54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56,
128     56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57,
129     57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59,
130     59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60,
131     61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62,
132     62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64,
133     64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65,
134     65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67,
135     67, 67, 67, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68, 68, 68,
136     68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70,
137     70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 71, 71,
138     71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73,
139     73, 73, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 75,
140     75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 76,
141     76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 78, 78,
142     78, 78, 78, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79, 79,
143     79, 79, 79, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81,
144     81, 81, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 82, 82, 82, 82,
145     82, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84,
146     84, 84, 84, 84, 84, 84, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85,
147     86, 86, 86, 86, 86, 86, 86, 86, 86, 86, 87, 87, 87, 87, 87, 87,
148     87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 88, 88, 88, 88, 88, 89,
149     89, 89, 89, 89, 89, 89, 89, 89, 89, 90, 90, 90, 90, 90, 90, 90,
150     90, 90, 90, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 91, 92, 92,
151     92, 92, 92, 92, 92, 92, 92, 92, 93, 93, 93, 93, 93, 93, 93, 93,
152     93, 93, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 95, 95, 95, 95,
153     95, 95, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96, 96, 96, 96,
154     96, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98,
155     98, 98, 98, 98, 98, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99
156 };
157 
158 #if 0
159 void
160 rand_print()
161 {
162     // Build our percenttable.
163     int		i;
164     for (i = 0; i < 1023; i++)
165     {
166 	float		val;
167 	val = ((float)i) / 1024;
168 	val *= 100;
169 	// Round down intentionally.
170 	glb_percenttable[i] = (u8) val;
171     }
172 
173     for (i = 0; i < 1023; i++)
174     {
175 	printf("%d,", glb_percenttable[i]);
176 	if (i && !(i & 15))
177 	    printf("\n\t");
178 	else
179 	    printf(" ");
180     }
181 }
182 #endif
183 
184 int
genrandom()185 genrandom()
186 {
187     return (int) genrand_int31();
188 }
189 
190 long
rand_getseed()191 rand_getseed()
192 {
193     long		seed;
194 
195     // We lose one bit here as we only use 31 bits out of 32.
196     // (Actually, we lose a heck of a lot more because we reduce
197     // the internal state from 624*32 bits to 31 bits.)
198     seed = genrandom();
199 
200     rand_setseed(seed);
201     return seed;
202 }
203 
204 void
rand_setseed(long seed)205 rand_setseed(long seed)
206 {
207     init_genrand(seed);
208 }
209 
210 double
rand_double()211 rand_double()
212 {
213     return genrand_res53();
214 }
215 
216 int
rand_range(int min,int max)217 rand_range(int min, int max)
218 {
219     int		v;
220 
221     if (min > max)
222 	return rand_range(max, min);
223 
224     v = rand_choice(max - min + 1);
225     return v + min;
226 }
227 
228 int
rand_choice(int num)229 rand_choice(int num)
230 {
231     int		v;
232 
233     // Choice of 0 or 1 is always 0.
234     if (num < 2) return 0;
235 
236     // Handle simple cases...
237     switch (num)
238     {
239 	case 2:
240 	    return (genrandom() & 1);
241 
242 	case 3:
243 	{
244 	    unsigned int		fullrandom;
245 
246 	    fullrandom = genrandom();
247 	    // Guaranteed to terminate because we are unsigned.
248 	    // Slightly biases to 0.
249 	    while ((fullrandom & 3) == 3)
250 	    {
251 		fullrandom >>= 2;
252 	    }
253 	    return fullrandom & 3;
254 	}
255 
256 	case 4:
257 	    return (genrandom() & 3);
258 
259 	case 8:
260 	    // We have an affinity for 8 sided dice...
261 	    return (genrandom() & 7);
262 
263 	case 100:
264 	{
265 	    // This is used by the percentile code is is more common
266 	    // than one might think
267 	    int				index;
268 
269 	    index = genrandom() & 1023;
270 	    return glb_percenttable[index];
271 	}
272     }
273 
274     v = abs(genrandom());
275     v %= num;
276 
277     return v;
278 }
279 
280 const char *
rand_string(const char ** stringlist)281 rand_string(const char **stringlist)
282 {
283     int		n;
284 
285     // Find length of the string list.
286     for (n = 0; stringlist[n]; n++);
287 
288     return stringlist[rand_choice(n)];
289 }
290 
291 int
rand_roll(int num,int reroll)292 rand_roll(int num, int reroll)
293 {
294     int		max = 0, val;
295 
296     // -1, 0, and 1 all evaluate to themselves always.
297     if (num >= -1 && num <= 1)
298 	return num;
299 
300     if (num < 0)
301     {
302 	// Negative numbers just invoke this and reverse the results.
303 	// Note we can't just negate the result, as we want higher rerolls
304 	// to move it closer to -1, not closer to num!
305 	val = rand_roll(-num, reroll);
306 	val -= num + 1;
307 	return val;
308     }
309 
310     if (reroll < 0)
311     {
312 	// Negative rerolls means we want to reroll but pick the
313 	// smallest result.  This is the same as inverting our normal
314 	// roll distribution, so thus...
315 	val = rand_roll(num, -reroll);
316 	val = num + 1 - val;
317 	return val;
318     }
319 
320     // I wasn't even drunk when I made reroll of 0 mean roll
321     // once, and thus necissating this change.
322     reroll++;
323     while (reroll--)
324     {
325 	val = rand_choice(num) + 1;
326 	if (val > max)
327 	    max = val;
328     }
329 
330     return max;
331 }
332 
333 int
rand_rollMean(int sides,int reroll,int scale)334 rand_rollMean(int sides, int reroll, int scale)
335 {
336     if (sides == 0)
337 	return 0;
338 
339     if (sides < 0)
340     {
341 	return -rand_rollMean(-sides, reroll, scale);
342     }
343 
344     int		mean;
345 
346     // Simple case...
347     if (!reroll)
348     {
349 	mean = (sides + 1) * scale;
350 	mean = (mean + 1) / 2;
351 
352 	return mean;
353     }
354     // Now, more complicated cases...
355     if (reroll < 0)
356     {
357 	// Invert distribution
358 	// Negative rerolls means we want to reroll but pick the
359 	// smallest result.  This is the same as inverting our normal
360 	// roll distribution, so thus...
361 	mean = rand_rollMean(sides, -reroll, scale);
362 	mean = (sides + 1)*scale - mean;
363 	return mean;
364     }
365     // Given M variates Ri[1..N], what is
366     // mean(max(Ri))
367     // Very tempted to do bruteforce here.
368     // We do brute force offline with the builddpdf program and
369     // just do a table lookup here.  The GBA doesn't like floats
370     // very much :>
371     if (sides < 2)
372     {
373 	// A one sided die is obvious
374 	// At least, obvious if you remember important things like
375 	// including the scale factor!
376 	return scale;
377     }
378 
379     // Make sure we are in the table, otherwise just clamp.
380     if (sides > DPDF_MAXSIDES)
381     {
382 	UT_ASSERT(!"Too many sides!");
383 	sides = DPDF_MAXSIDES;
384     }
385     if (reroll > DPDF_MAXROLLS)
386     {
387 	UT_ASSERT(!"Too many rolls!");
388 	reroll = DPDF_MAXROLLS;
389     }
390     // To apply the user defined scale, we multiply by the users
391     // scale and then divide by our scale.
392     mean = glb_dpdftable[reroll][sides-2];
393     mean *= scale;
394     mean += DPDF_SCALE / 2;
395     mean /= DPDF_SCALE;
396 
397     return mean;
398 }
399 
400 int
rand_dice(int numdie,int sides,int bonus)401 rand_dice(int numdie, int sides, int bonus)
402 {
403     int		i, total = bonus;
404 
405     for (i = 0; i < numdie; i++)
406     {
407 	total += rand_choice(sides) + 1;
408     }
409     return total;
410 }
411 
412 bool
rand_chance(int percentage)413 rand_chance(int percentage)
414 {
415     int		percent;
416 
417     // We want to avoid any random number hijinks if we are invoking
418     // with zero or 100.  This can occur due to rand_chance(glbdef.value)
419     // where value is usually one or the other.
420     if (percentage == 0)
421 	return false;
422     if (percentage == 100)
423 	return true;
424 
425     percent = rand_choice(100);
426     // We want strict less than so percentage 0 will never pass,
427     // and percentage 99 will fail only one in 100.
428     return percent < percentage;
429 }
430 
431 int
rand_sign()432 rand_sign()
433 {
434     return rand_choice(2) * 2 - 1;
435 }
436 
437 void
rand_direction(int & dx,int & dy)438 rand_direction(int &dx, int &dy)
439 {
440     if (rand_choice(2))
441     {
442 	dx = rand_sign();
443 	dy = 0;
444     }
445     else
446     {
447 	dx = 0;
448 	dy = rand_sign();
449     }
450 }
451 
452 void
rand_eightwaydirection(int & dx,int & dy)453 rand_eightwaydirection(int &dx, int &dy)
454 {
455     dx = rand_sign();
456     dy = rand_sign();
457 
458     if (rand_choice(2))
459     {
460 	// Go orthogonal...
461 	if (rand_choice(2))
462 	    dx = 0;
463 	else
464 	    dy = 0;
465     }
466 }
467 
468 int
rand_dice(const DICE & dice,int multiplier)469 rand_dice(const DICE &dice, int multiplier)
470 {
471     return rand_dice(dice.myNumdie * multiplier, dice.mySides,
472 		     dice.myBonus * multiplier);
473 }
474 
475 int
rand_diceMean(const DICE & dice,int multiplier)476 rand_diceMean(const DICE &dice, int multiplier)
477 {
478     int		i, total = dice.myBonus*256*multiplier;
479 
480     for (i = 0; i < dice.myNumdie * multiplier; i++)
481     {
482 	total += rand_rollMean(dice.mySides, 0, 256);
483     }
484     // Round off and normalize
485     total += 128;
486     total >>= 8;
487     return total;
488 }
489 
490 void
rand_shuffle(u8 * set,int n)491 rand_shuffle(u8 *set, int n)
492 {
493     int		i, j;
494     u8		tmp;
495 
496     for (i = n-1; i > 0; i--)
497     {
498 	// Want to swap with anything earlier, including self!
499 	j = rand_choice(i+1);
500 
501 	tmp = set[i];
502 	set[i] = set[j];
503 	set[j] = tmp;
504     }
505 }
506 
507 void
rand_shuffle(int * set,int n)508 rand_shuffle(int *set, int n)
509 {
510     int		i, j;
511     int		tmp;
512 
513     for (i = n-1; i > 0; i--)
514     {
515 	// Want to swap with anything earlier, including self!
516 	j = rand_choice(i+1);
517 
518 	tmp = set[i];
519 	set[i] = set[j];
520 	set[j] = tmp;
521     }
522 }
523 
524 void
getDirection(int dir,int & dx,int & dy)525 getDirection(int dir, int &dx, int &dy)
526 {
527     dir &= 3;
528     const static int		dxtable[4] = { 0, 1, 0, -1 };
529     const static int		dytable[4] = { 1, 0, -1, 0 };
530     dx = dxtable[dir];
531     dy = dytable[dir];
532 }
533 
534 void
rand_angletodir(int angle,int & dx,int & dy)535 rand_angletodir(int angle, int &dx, int &dy)
536 {
537     angle &= 7;
538 
539     const static int		dxtable[8] = { 1, 1, 0,-1,-1,-1, 0, 1 };
540     const static int		dytable[8] = { 0, 1, 1, 1, 0,-1,-1,-1 };
541 
542     dx = dxtable[angle];
543     dy = dytable[angle];
544 }
545 
546 int
rand_dirtoangle(int dx,int dy)547 rand_dirtoangle(int dx, int dy)
548 {
549     int		x, y, a;
550 
551     for (a = 0; a < 8; a++)
552     {
553 	rand_angletodir(a, x, y);
554 	if (x == dx && y == dy)
555 	    return a;
556     }
557 
558     // This is 0,0, so we just return any angle!
559     return rand_range(0, 7);
560 }
561 
562 
563 unsigned int
rand_wanginthash(unsigned int key)564 rand_wanginthash(unsigned int key)
565 {
566     key += ~(key << 16);
567     key ^=  (key >> 5);
568     key +=  (key << 3);
569     key ^=  (key >> 13);
570     key += ~(key << 9);
571     key ^=  (key >> 17);
572     return key;
573 }
574 
575 unsigned int
rand_hashstring(const char * s)576 rand_hashstring(const char *s)
577 {
578     unsigned int	hash = 0;
579     if (!s)
580 	return hash;
581     while (*s)
582     {
583 	hash *= 37;		// Stolen from Perl.
584 	hash += *s;
585 	s++;
586     }
587 
588     return rand_wanginthash(hash);
589 }
590 
591 
592 // Written in a beautiful provincial park in a nice cool June day.
593 // If this were traditional manuscript, it would smell of woodsmoke,
594 // but the curse of digital is the destruction of all sidebands
595 // of history.  Which I guess makes comments like this all the
596 // more important.
597 void
rand_name(char * text,int len)598 rand_name(char *text, int len)
599 {
600     // Very simple markov generator.
601     // We repeat letters to make them more likely.
602     const char *vowels = "aaaeeeiiiooouuyy'";
603     const char *frictive = "rsfhvnmz";
604     const char *plosive = "tpdgkbc";
605     const char *weird = "qwjx";
606     // State transitions..
607     // v -> f, p, w, v'
608     // v' -> f, p, w
609     // f -> p', v
610     // p -> v, f'
611     // w, p', f' -> v
612 
613     int		syllables = 0;
614     char	state;
615     int		pos = 0;
616     bool	prime = false;
617 
618     // Initial state choice
619     if (rand_chance(30))
620 	state = 'v';
621     else if (rand_chance(40))
622 	state = 'f';
623     else if (rand_chance(70))
624 	state = 'p';
625     else
626 	state = 'w';
627 
628     while (pos < len-1)
629     {
630 	// Apply current state
631 	switch (state)
632 	{
633 	    case 'v':
634 		text[pos++] = vowels[rand_choice(strlen(vowels))];
635 		if (!prime)
636 		    syllables++;
637 		break;
638 	    case 'f':
639 		text[pos++] = frictive[rand_choice(strlen(frictive))];
640 		break;
641 	    case 'p':
642 		text[pos++] = plosive[rand_choice(strlen(plosive))];
643 		break;
644 	    case 'w':
645 		text[pos++] = weird[rand_choice(strlen(weird))];
646 		break;
647 	}
648 
649 	// Chance to stop..
650 	if (syllables && pos >= 3)
651 	{
652 	    if (rand_chance(20+pos*4))
653 		break;
654 	}
655 
656 	// Transition...
657 	switch (state)
658 	{
659 	    case 'v':
660 		if (!prime && rand_chance(10))
661 		{
662 		    state = 'v';
663 		    prime = true;
664 		    break;
665 		}
666 		else if (rand_chance(40))
667 		    state = 'f';
668 		else if (rand_chance(70))
669 		    state = 'p';
670 		else
671 		    state = 'w';
672 		prime = false;
673 		break;
674 	    case 'f':
675 		if (!prime && rand_chance(50))
676 		{
677 		    prime = true;
678 		    state = 'p';
679 		    break;
680 		}
681 		state = 'v';
682 		prime = false;
683 		break;
684 	    case 'p':
685 		if (!prime && rand_chance(10))
686 		{
687 		    prime = true;
688 		    state = 'f';
689 		    break;
690 		}
691 		state = 'v';
692 		prime = false;
693 		break;
694 	    case 'w':
695 		state = 'v';
696 		prime = false;
697 		break;
698 	}
699     }
700     text[0] = toupper(text[0]);
701     text[pos++] = '\0';
702 }
703