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