1 /* pMARS -- a portable Memory Array Redcode Simulator
2 * Copyright (C) 1993-1996 Albert Ma, Na'ndor Sieben, Stefan Strack and Mintardjo Wangsawidjaja
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18
19 /*
20 * pos.c: RNG and positioning functions
21 * $Id: pos.c,v 1.1.1.1 2000/08/20 13:29:42 iltzu Exp $
22 */
23 #include "global.h"
24 #include "sim.h"
25
26 #ifdef NEW_STYLE
27 int posit(void);
28 void npos(void);
29 S32_T rng(S32_T seed);
30 #endif
31
32 /* minimal standard random number generator; integer version 2
33 * Communications of the ACM, 31:10 (1988)
34 * returns 1 <= seed <= 2^31-2, cycle: 2^32, tested and approved */
35 S32_T
rng(seed)36 rng(seed)
37 S32_T seed;
38 {
39 register S32_T temp = seed;
40 temp = 16807 * (temp % 127773) - 2836 * (temp / 127773);
41 if (temp < 0)
42 temp += 2147483647;
43 return temp;
44 }
45
46 #define RETRIES1 20 /* how many times to try generating one
47 * position */
48 #define RETRIES2 4 /* how many times to start backtracking */
49 int
posit()50 posit()
51 {
52 int pos = 1, i, retries1 = RETRIES1, retries2 = RETRIES2;
53 int diff;
54
55 do {
56 /* generate */
57 warrior[pos].position =
58 ((seed = rng(seed)) % (coreSize - 2 * separation + 1)) + separation;
59 /* test for overlap */
60 for (i = 1; i < pos; ++i) {
61 /* calculate positive difference */
62 diff = (int) warrior[pos].position - warrior[i].position;
63 if (diff < 0)
64 diff = -diff;
65 if (diff < separation)
66 break; /* overlap! */
67 }
68 if (i == pos) /* no overlap, generate next number */
69 ++pos;
70 else { /* overlap */
71 if (!retries2)
72 return 1; /* exceeded attempts, fail */
73 if (!retries1) { /* backtrack: generate new sequence starting
74 * at an */
75 pos = i; /* arbitrary position (last conflict) */
76 --retries2;
77 retries1 = RETRIES1;
78 } else /* generate new current number (pos not
79 * incremented) */
80 --retries1;
81 }
82 } while (pos < warriors);
83 return 0;
84 }
85
86 void
npos()87 npos()
88 {
89 int i, j;
90 unsigned int temp;
91 unsigned int room = coreSize - separation * warriors + 1;
92 for (i = 1; i < warriors; i++) {
93 temp = (seed = rng(seed)) % room;
94 for (j = i - 1; j > 0; j--) {
95 if (temp > warrior[j].position)
96 break;
97 warrior[j + 1].position = warrior[j].position;
98 }
99 warrior[j + 1].position = temp;
100 }
101 temp = separation;
102 for (i = 1; i < warriors; i++) {
103 warrior[i].position += temp;
104 temp += separation;
105 }
106 for (i = 1; i < warriors; i++) {
107 j = (seed = rng(seed)) % (warriors - i) + i;
108 temp = warrior[j].position;
109 warrior[j].position = warrior[i].position;
110 warrior[i].position = temp;
111 }
112 }
113