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