1 /* exhaust.c: crippled pmars-like redcode simulator
2 * $Id: exhaust.c,v 1.15 2002/12/28 05:49:45 rowan Exp $
3 */
4
5 /* This file is part of `exhaust', a memory array redcode simulator.
6 * Copyright (C) 2002 M Joonas Pihlaja
7 *
8 * This file falls under the GNU Public License, version 2. See the
9 * file COPYING for details. */
10
11 #define VERSION 1
12 #define REVISION 9
13 #define PATCHLEVEL 2
14
15 /* Note pmars incompatibility: Minimum warrior separation (minsep) is
16 handled wrong by pmars (prior to 0.8.6) when minsep < MAXLENGTH.
17 This affects running warriors in small cores since the other
18 warriors might be loaded outside of core (it might even crash).
19 */
20 #include <stdio.h>
21 #ifdef SYSV
22 #include <strings.h>
23 #else
24 #include <string.h>
25 #endif
26 #include <stdlib.h>
27 #include <time.h>
28 #include <ctype.h>
29
30 #include "exhaust.h" /* types */
31 #include "asm.h" /* assembler proto */
32 #include "sim.h" /* simulator proto */
33
34 static unsigned int NWarriors = 0;
35 static warrior_t *Warriors = NULL; /* [NWarriors] */
36
37 static char * *WarriorNames = NULL; /* [NWarriors] */
38 /* File names of warriors. */
39
40 static field_t *Positions = NULL; /* [NWarriors] */
41 static field_t *StartPositions = NULL; /* [NWarriors] */
42 /* Starting position of each warrior.
43 * The StartPositions[] array is a copy
44 * of Positions[], rotated by the number of
45 * the round, to emulate pMARS.
46 */
47
48 static unsigned int *Deaths = NULL; /* [NWarriors] */
49
50 static u32_t **Results = NULL; /* [NWarriors][NWarriors+1] */
51 /* Results[war_id][j] is the number of
52 rounds in which warrior war_id
53 survives until the end with exactly
54 j-1 other warriors. For j=0, then
55 it is the number of rounds where
56 the warrior died. */
57
58 static pspace_t ** PSpaces = NULL; /* [NWarriors] */
59 /* p-spaces of warriors. */
60
61
62 /* Globals to communicate options from readargs() to main() */
63 int OPT_cycles = 80000; /* cycles until tie */
64 unsigned int OPT_rounds = 1; /* number of rounds to fight */
65 unsigned int OPT_coresize = 8000; /* default core size */
66 unsigned int OPT_minsep = 0; /* minimum distance between warriors */
67 int OPT_processes = 8000; /* default max. procs./warrior */
68 int OPT_F = 0; /* initial position of warrior 2 */
69 int OPT_k = 0; /* nothing (`koth' format flag) */
70 int OPT_b = 0; /* nothing (we are always `brief') */
71 int OPT_m = 0; /* multi-warrior output format. */
72
73 char *prog_name;
74 char errmsg[256];
75
76 /*---------------------------------------------------------------
77 * Utilities
78 */
79
80 #define min(x,y) ((x)<(y) ? (x) : (y))
81
82 /* xbasename(): custom basename(1); returns the filename from a path
83 */
84 static
85 char *
xbasename(char * s)86 xbasename(char *s)
87 {
88 char *b;
89 b = strrchr(s,'/');
90 if (!b) {
91 b = strrchr(s,'\\');
92 }
93 return b ? 1+b : s;
94 }
95
96 void
panic(const char * msg)97 panic( const char *msg )
98 {
99 fprintf(stderr, "%s: ", prog_name );
100 fprintf(stderr, "%s", msg );
101 exit(1);
102 }
103
104
105 /* pmars/rng.c random number generator
106 */
107 s32_t
rng(s32_t seed)108 rng(s32_t seed)
109 {
110 register s32_t temp = seed;
111 temp = 16807 * (temp % 127773) - 2836 * (temp / 127773);
112 if (temp < 0)
113 temp += 2147483647;
114 return temp;
115 }
116
117 /* Like realloc(3), but works with NULL pointers. */
118 void *
xrealloc(void * p,size_t newsize)119 xrealloc(void *p, size_t newsize)
120 {
121 if (p==NULL) {
122 return malloc(newsize);
123 }
124 return realloc(p, newsize);
125 }
126
127 void
usage()128 usage()
129 {
130 printf("%s v%d.%d", prog_name, VERSION, REVISION);
131 if (PATCHLEVEL>0){
132 printf(".%d", PATCHLEVEL);
133 }
134 printf("\n");
135 printf("usage: %s [opts] warriors...\n", prog_name );
136 printf("opts: -r <rounds>, -c <cycles>, -F <pos>, -s <coresize>,\n"
137 " -p <maxprocs>, -d <minsep>, -bk\n");
138 exit(1);
139 }
140
141 /*---------------------------------------------------------------
142 * Warrior initialisations.
143 */
144
145 void
free_related_memory()146 free_related_memory()
147 {
148 if (Warriors) { free(Warriors); Warriors = NULL; }
149 if (Positions) { free(Positions); Positions = NULL; }
150 if (StartPositions) { free(StartPositions); StartPositions = NULL; }
151 if (Deaths) { free(Deaths); Deaths = NULL; }
152 if (Results) {
153 if (Results[0]) { free(Results[0]); Results[0] = NULL; }
154 free(Results); Results = NULL;
155 }
156 if (PSpaces) { free(PSpaces); PSpaces = NULL; }
157 if (WarriorNames) { free(WarriorNames); WarriorNames = NULL; }
158 }
159
160 void
alloc_related_memory()161 alloc_related_memory()
162 {
163 unsigned int i;
164
165 Warriors = (warrior_t*)malloc(sizeof(warrior_t)*NWarriors);
166 Positions = (field_t*)malloc(sizeof(field_t)*NWarriors);
167 StartPositions = (field_t*)malloc(sizeof(field_t)*NWarriors);
168 Deaths = (unsigned int*)malloc(sizeof(unsigned int*)*NWarriors);
169
170 /* The results matrix */
171 Results = (u32_t**)malloc(sizeof(u32_t*)*NWarriors);
172 Results[0] = (u32_t*)malloc(sizeof(u32_t)*NWarriors*(NWarriors+1));
173 for (i=1; i<NWarriors; i++) {
174 Results[i] = Results[i-1] + NWarriors+1;
175 }
176
177 /* Warrior P-spaces */
178 PSpaces = (pspace_t **)malloc(sizeof(pspace_t*) * NWarriors);
179
180 if (!(Warriors && Positions && StartPositions && Deaths &&
181 Results && Results[0] && PSpaces))
182 {
183 free_related_memory();
184 panic("Can't allocate memory.");
185 }
186 }
187
188
189 void
import_warriors()190 import_warriors()
191 {
192 unsigned int i;
193
194 for (i=0; i<NWarriors; i++) {
195 asm_fname( WarriorNames[i], &Warriors[i], OPT_coresize );
196 }
197 }
198
199 void
check_sanity()200 check_sanity()
201 {
202 u32_t space_used;
203 unsigned int i;
204
205 /* Make sure each warrior has some code. */
206 for (i=0; i<NWarriors; i++) {
207 if (Warriors[i].len == 0) {
208 sprintf(errmsg,"warrior %d has no code\n", i);
209 panic(errmsg);
210 }
211 }
212
213 /* Make sure there is some minimum sepation. */
214 if ( OPT_minsep == 0 ) {
215 OPT_minsep = min( OPT_coresize/NWarriors, MAXLENGTH );
216 }
217
218 /* Make sure minsep dominates the lengths of all warriors. */
219 for (i=0; i<NWarriors; i++) {
220 if ( OPT_minsep < Warriors[i].len ) {
221 panic("minimum separation must be >= longest warrior\n");
222 }
223 }
224
225 /* Make sure there is space for all warriors to be loaded. */
226 space_used = NWarriors*OPT_minsep;
227 if ( space_used > OPT_coresize ) {
228 panic("warriors or minimum separation too large to fit into core\n");
229 }
230 }
231
232
233 /*---------------------------------------------------------------
234 * Warrior positioning algorithms
235 *
236 * These are pMARS compatible. Warrior 0 is always positioned at 0.
237 * posit() and npos() are transcribed from pmars/pos.c. */
238
239 #define RETRIES1 20 /* how many times to try generating one
240 * position */
241 #define RETRIES2 4 /* how many times to start backtracking */
242 int
posit(s32_t * seed)243 posit(s32_t *seed)
244 {
245 unsigned int pos = 1, i;
246 unsigned int retries1 = RETRIES1, retries2 = RETRIES2;
247 int diff;
248
249 do {
250 /* generate */
251 *seed = rng(*seed);
252 Positions[pos] =
253 (*seed % (OPT_coresize - 2*OPT_minsep+1))+OPT_minsep;
254
255 /* test for overlap */
256 for (i = 1; i < pos; ++i) {
257 /* calculate positive difference */
258 diff = (int) Positions[pos] - Positions[i];
259 if (diff < 0)
260 diff = -diff;
261 if ((unsigned int)diff < OPT_minsep)
262 break; /* overlap! */
263 }
264
265 if (i == pos) /* no overlap, generate next number */
266 ++pos;
267 else { /* overlap */
268 if (!retries2)
269 return 1; /* exceeded attempts, fail */
270 if (!retries1) { /* backtrack: generate new sequence starting */
271 pos = i; /* at arbitrary position (last conflict) */
272 --retries2;
273 retries1 = RETRIES1;
274 } else /* generate new current number (pos not
275 * incremented) */
276 --retries1;
277 }
278 } while (pos < NWarriors);
279 return 0;
280 }
281
282 void
npos(s32_t * seed)283 npos(s32_t *seed)
284 {
285 unsigned int i, j;
286 unsigned int temp;
287 unsigned int room = OPT_coresize - OPT_minsep*NWarriors+1;
288
289 /* Choose NWarriors-1 positions from the available room. */
290 for (i = 1; i < NWarriors; i++) {
291 *seed = rng(*seed);
292 temp = *seed % room;
293 for (j = i - 1; j > 0; j--) {
294 if (temp > Positions[j])
295 break;
296 Positions[j+1] = Positions[j];
297 }
298 Positions[j+1] = temp;
299 }
300
301 /* Separate the positions by OPT_minsep cells. */
302 temp = OPT_minsep;
303 for (i = 1; i < NWarriors; i++) {
304 Positions[i] += temp;
305 temp += OPT_minsep;
306 }
307
308 /* Random permutation of positions. */
309 for (i = 1; i < NWarriors; i++) {
310 *seed = rng(*seed);
311 j = *seed % (NWarriors - i) + i;
312 temp = Positions[j];
313 Positions[j] = Positions[i];
314 Positions[i] = temp;
315 }
316 }
317
318 s32_t
compute_positions(s32_t seed)319 compute_positions(s32_t seed)
320 {
321 u32_t avail = OPT_coresize+1 - NWarriors*OPT_minsep;
322
323 Positions[0] = 0;
324
325 /* Case single warrior. */
326 if (NWarriors == 1) return seed;
327
328 /* Case one on one. */
329 if (NWarriors == 2) {
330 Positions[1] = OPT_minsep + seed % avail;
331 seed = rng(seed);
332 return seed;
333 }
334
335 if (NWarriors>2) {
336 if (posit(&seed)) {
337 npos(&seed);
338 }
339 }
340 return seed;
341 }
342
343
344 /*---------------------------------------------------------------
345 * Misc.
346 */
347
348 void
save_pspaces()349 save_pspaces()
350 {
351 pspace_t **ps;
352 ps = sim_get_pspaces();
353 memcpy( PSpaces, ps, sizeof(pspace_t *)*NWarriors );
354 }
355
356 void
amalgamate_pspaces()357 amalgamate_pspaces()
358 {
359 unsigned int i, j;
360
361 /* Share p-space according to PINs. */
362 for (i=0; i<NWarriors; i++) {
363 if ( Warriors[i].have_pin ) {
364 for (j=0; j<i; j++) {
365 if ( Warriors[j].have_pin &&
366 Warriors[j].pin == Warriors[i].pin )
367 {
368 pspace_share( PSpaces[i], PSpaces[j] );
369 }
370 }
371 }
372 }
373 }
374
375 void
load_warriors()376 load_warriors()
377 {
378 unsigned int i;
379 for (i=0; i<NWarriors; i++) {
380 sim_load_warrior(Positions[i], &Warriors[i].code[0], Warriors[i].len);
381 }
382 }
383
384 void
set_starting_order(unsigned int round)385 set_starting_order(unsigned int round)
386 {
387 unsigned int i;
388 pspace_t **ps;
389
390 /* Copy load positions into starting positions array
391 with a cyclic shift of rounds places. */
392 for (i=0; i<NWarriors; i++) {
393 unsigned int j = (i+round) % NWarriors;
394 StartPositions[i] =
395 ( Positions[j] + Warriors[j].start ) % OPT_coresize;
396 }
397
398 /* Copy p-spaces into simulator p-space array with a
399 cyclic shift of rounds places. */
400 ps = sim_get_pspaces();
401 for (i=0; i<NWarriors; i++) {
402 ps[i] = PSpaces[(i + round) % NWarriors];
403 }
404 }
405
406 void
clear_results()407 clear_results()
408 {
409 unsigned int i, j;
410 for (i=0; i<NWarriors; i++) {
411 for (j=0; j<=NWarriors; j++) {
412 Results[i][j] = 0;
413 }
414 }
415 }
416
417 void
accumulate_results()418 accumulate_results()
419 {
420 unsigned int i;
421
422 /* Fetch the results of the last round from p-space location 0
423 that has been updated by the simulator. */
424 for (i=0; i<NWarriors; i++) {
425 unsigned int result;
426 result = pspace_get(PSpaces[i], 0);
427 Results[i][result]++;
428 }
429 }
430
431
432 void
output_results()433 output_results()
434 {
435 unsigned int i;
436 unsigned int j;
437
438 if (NWarriors == 2 && !OPT_m) {
439 printf("%ld %ld\n", Results[0][1], Results[0][2]);
440 printf("%ld %ld\n", Results[1][1], Results[1][2]);
441 } else {
442 for (i=0; i<NWarriors; i++) {
443 for (j=1; j<=NWarriors; j++) {
444 printf("%ld ", Results[i][j]);
445 }
446 printf("%ld\n", Results[i][0]);
447 }
448 }
449 }
450
451
452 /*---------------------------------------------------------------
453 * Command line arguments.
454 */
455
456 /*
457 * parse options
458 */
459 void
readargs(int argc,char ** argv)460 readargs( int argc, char **argv )
461 {
462 int n;
463 char c;
464 int cix;
465 int tmp;
466
467 n = 1;
468 while ( n < argc ) {
469 cix = 0;
470 c = argv[n][cix++];
471 if ( c == '-' && argv[n][1] ) {
472 do {
473 c = argv[n][cix++];
474 if (c)
475 switch (c) {
476
477 case 'k': OPT_k = 1; break;
478 case 'b': OPT_b = 1; break;
479 case 'm': OPT_m = 1; break;
480
481 case 'F':
482 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
483 panic( "bad argument for option -F\n");
484 c = 0;
485 OPT_F = atoi( argv[++n] );
486 break;
487
488 case 's':
489 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
490 panic( "bad argument for option -s\n");
491 c = 0;
492 OPT_coresize = atoi( argv[++n] );
493 if ( (int)OPT_coresize <= 0 )
494 panic( "core size must be > 0\n");
495 break;
496
497 case 'd':
498 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
499 panic( "bad argument for option -d\n");
500 c = 0;
501 OPT_minsep = atoi( argv[++n] );
502 if ( (int)OPT_minsep <= 0 )
503 panic( "minimum warrior separation must be > 0\n" );
504 break;
505
506 case 'p':
507 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
508 panic( "bad argument for option -p\n");
509 c = 0;
510 OPT_processes = atoi( argv[++n] );
511 if ( OPT_processes <= 0 )
512 panic( "max processes must be > 0\n" );
513 break;
514
515 case 'r':
516 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
517 panic( "bad argument for option -r\n");
518 c = 0;
519 tmp = atoi( argv[++n] );
520 if ( tmp < 0 )
521 panic( "can't do a negative number of rounds!\n" );
522 OPT_rounds = tmp;
523 break;
524 case 'c':
525 if ( n == argc-1 || !isdigit(argv[n+1][0]) )
526 panic( "bad argument for option -c\n");
527 c = 0;
528 OPT_cycles = atoi( argv[++n] );
529 if ( OPT_cycles <= 0 )
530 panic( "cycles must be > 0\n" );
531 break;
532 default:
533 sprintf(errmsg,"unknown option '%c'\n", c);
534 panic(errmsg);
535 }
536 } while (c);
537
538 } else /* it's a file name */ {
539 ++NWarriors;
540 WarriorNames = xrealloc(WarriorNames, NWarriors*sizeof(char*));
541 WarriorNames[NWarriors-1] = argv[n];
542 }
543 n++;
544 }
545
546 if ( NWarriors == 0 )
547 usage();
548 }
549
550
551
552 /*-------------------------------------------------------------------------
553 * Main
554 */
555
556
557 int
main(int argc,char ** argv)558 main( int argc, char **argv )
559 {
560 unsigned int n; /* round counter */
561 s32_t seed; /* rnd seed. */
562
563 prog_name = xbasename(argv[0]);
564 readargs(argc, argv);
565 alloc_related_memory();
566
567 import_warriors();
568 check_sanity();
569 clear_results();
570
571 seed = OPT_F ? OPT_F-OPT_minsep : rng(time(0)*0x1d872b41);
572
573 /*
574 * Allocate simulator buffers and initialise p-spaces.
575 */
576 if (! sim_alloc_bufs( NWarriors, OPT_coresize, OPT_processes, OPT_cycles))
577 panic("can't allocate memory.\n");
578
579 save_pspaces();
580 amalgamate_pspaces(); /* Share P-spaces with equal PINs */
581
582 /*
583 * Fight OPT_rounds rounds.
584 */
585 for ( n = 0; n < OPT_rounds; n++ ) {
586 int nalive;
587 sim_clear_core();
588
589 seed = compute_positions(seed);
590 load_warriors();
591 set_starting_order(n);
592
593 nalive = sim_mw( NWarriors, &StartPositions[0], &Deaths[0] );
594 if (nalive<0)
595 panic("simulator panic!\n");
596
597 accumulate_results();
598 }
599
600 sim_free_bufs();
601 output_results();
602 free_related_memory();
603 return 0;
604 }
605