exhaust.c

/* exhaust.c: crippled pmars-like redcode simulator
 * $Id: exhaust.c,v 1.5 2003/07/13 09:22:32 martinus Exp $
 */

/* This file is part of `exhaust', a memory array redcode simulator.
 * Copyright (C) 2002 M Joonas Pihlaja
 *
 * This file falls under the GNU Public License, version 2.  See the
 * file COPYING for details.  */

#define VERSION 1
#define REVISION 9

/* Note pmars incompatibility: Minimum warrior separation (minsep) is
   handled wrong by pmars (prior to 0.8.6) when minsep < MAXLENGTH.
   This affects running warriors in small cores since the other
   warriors might be loaded outside of core (it might even crash).
*/
#include <stdio.h>
#ifdef SYSV
#include <strings.h>
#else
#include <string.h>
#endif
#include <ctype.h>
#include <stdlib.h>
#include <time.h>

#include "asm.h"     /* assembler proto */
#include "exhaust.h" /* types */
#include "insn.h"
#include "sim.h" /* simulator proto */
#include "types.h"

#define MAX_WARRIORS 10

static unsigned int NWarriors = 0;
static warrior_t Warriors[MAX_WARRIORS];

static char *WarriorNames[MAX_WARRIORS];
/* File names of warriors. */

static field_t Positions[MAX_WARRIORS];
static field_t StartPositions[MAX_WARRIORS];
/* Starting position of each warrior. */

static unsigned int Deaths[MAX_WARRIORS];

static uint32_t Results[MAX_WARRIORS][MAX_WARRIORS + 1];
/* Results[war_id][j] is the number of
   rounds in which warrior war_id
   survives until the end with exactly
   j-1 other warriors.  For j=0, then
   it is the number of rounds where
   the warrior died. */

static pspace_t *PSpaces[MAX_WARRIORS];
/* p-spaces of warriors. */

/* Globals to communicate options from readargs() to main() */
int OPT_cycles = 80000;           /* cycles until tie */
unsigned int OPT_rounds = 1;      /* number of rounds to fight */
unsigned int OPT_coresize = 8000; /* default core size */
unsigned int OPT_minsep = 0;      /* minimum distance between warriors */
int OPT_processes = 8000;         /* default max. procs./warrior */
int OPT_F = 0;                    /* initial position of warrior 2 */
int OPT_k = 0;                    /* nothing (`koth' format flag) */
int OPT_b = 0;                    /* nothing (we are always `brief') */
int OPT_m = 0;                    /* multi-warrior output format. */

char *prog_name;
char errmsg[256];

/*---------------------------------------------------------------
 * Utilities
 */

#define min(x, y) ((x) < (y) ? (x) : (y))

/* xbasename(): custom basename(1); returns the filename from a path
 */
static char *xbasename(char *s) {
  char *b;
  b = strrchr(s, '/');
  return b ? 1 + b : s;
}

void panic(char *msg) {
  fprintf(stderr, "%s: ", prog_name);
  fprintf(stderr, "%s", msg);
  exit(1);
}

/* pmars/rng.c random number generator
 */
int32_t rng(int32_t seed) {
  register int32_t temp = seed;
  temp = 16807 * (temp % 127773) - 2836 * (temp / 127773);
  if (temp < 0) temp += 2147483647;
  return temp;
}

void usage() {
  printf("%s v%d.%d\n", prog_name, VERSION, REVISION);
  printf("usage: %s [opts] warriors...\n", prog_name);
  printf(
      "opts: -r <rounds>, -c <cycles>, -F <pos>, -s <coresize>,\n"
      "      -p <maxprocs>, -d <minsep>, -bk\n");
  exit(1);
}

/*---------------------------------------------------------------
 * Warrior initialisations.
 */

void import_warriors() {
  unsigned int i;

  for (i = 0; i < NWarriors; i++) {
    asm_fname(WarriorNames[i], &Warriors[i], OPT_coresize);
  }
}

void check_sanity() {
  uint32_t space_used;
  unsigned int i;

  /* Make sure each warrior has some code. */
  for (i = 0; i < NWarriors; i++) {
    if (Warriors[i].len == 0) {
      sprintf(errmsg, "warrior %d has no code\n", i);
      panic(errmsg);
    }
  }

  /* Make sure there is some minimum sepation. */
  if (OPT_minsep == 0) {
    OPT_minsep = min(OPT_coresize / NWarriors, MAXLENGTH);
  }

  /* Make sure minsep dominates the lengths of all warriors. */
  for (i = 0; i < NWarriors; i++) {
    if (OPT_minsep < Warriors[i].len) {
      panic("minimum separation must be >= longest warrior\n");
    }
  }

  /* Make sure there is space for all warriors to be loaded. */
  space_used = NWarriors * OPT_minsep;
  if (space_used > OPT_coresize) {
    panic("warriors too large to fit into core\n");
  }
}

/*---------------------------------------------------------------
 * Warrior positioning algorithms
 *
 * These are pMARS compatible.  Warrior 0 is always positioned at 0.
 * posit() and npos() are transcribed from pmars/pos.c.  */

#define RETRIES1                                                       \
  20 /* how many times to try generating one \ \ \ \             \ \ \ \
      * position */
#define RETRIES2 4 /* how many times to start backtracking */
int posit(int32_t *seed) {
  unsigned int pos = 1, i;
  unsigned int retries1 = RETRIES1, retries2 = RETRIES2;
  int diff;

  do {
    /* generate */
    *seed = rng(*seed);
    Positions[pos] = (*seed % (OPT_coresize - 2 * OPT_minsep + 1)) + OPT_minsep;

    /* test for overlap */
    for (i = 1; i < pos; ++i) {
      /* calculate positive difference */
      diff = (int)Positions[pos] - Positions[i];
      if (diff < 0) diff = -diff;
      if ((unsigned int)diff < OPT_minsep) break; /* overlap! */
    }

    if (i == pos) /* no overlap, generate next number */
      ++pos;
    else {                     /* overlap */
      if (!retries2) return 1; /* exceeded attempts, fail */
      if (!retries1) {         /* backtrack: generate new sequence starting */
        pos = i;               /* at arbitrary position (last conflict) */
        --retries2;
        retries1 = RETRIES1;
      } else /* generate new current number (pos not
              * incremented) */
        --retries1;
    }
  } while (pos < NWarriors);
  return 0;
}

void npos(int32_t *seed) {
  unsigned int i, j;
  unsigned int temp;
  unsigned int room = OPT_coresize - OPT_minsep * NWarriors + 1;

  /* Choose NWarriors-1 positions from the available room. */
  for (i = 1; i < NWarriors; i++) {
    *seed = rng(*seed);
    temp = *seed % room;
    for (j = i - 1; j > 0; j--) {
      if (temp > Positions[j]) break;
      Positions[j + 1] = Positions[j];
    }
    Positions[j + 1] = temp;
  }

  /* Separate the positions by OPT_minsep cells. */
  temp = OPT_minsep;
  for (i = 1; i < NWarriors; i++) {
    Positions[i] += temp;
    temp += OPT_minsep;
  }

  /* Random permutation of positions. */
  for (i = 1; i < NWarriors; i++) {
    *seed = rng(*seed);
    j = *seed % (NWarriors - i) + i;
    temp = Positions[j];
    Positions[j] = Positions[i];
    Positions[i] = temp;
  }
}

int32_t compute_positions(int32_t seed) {
  uint32_t avail = OPT_coresize + 1 - NWarriors * OPT_minsep;

  Positions[0] = 0;

  /* Case single warrior. */
  if (NWarriors == 1) return seed;

  /* Case one on one. */
  if (NWarriors == 2) {
    Positions[1] = OPT_minsep + seed % avail;
    seed = rng(seed);
    return seed;
  }

  if (NWarriors > 2) {
    if (posit(&seed)) {
      npos(&seed);
    }
  }
  return seed;
}

/*---------------------------------------------------------------
 * Misc.
 */

void save_pspaces() {
  pspace_t **ps;
  ps = sim_get_pspaces();
  memcpy(PSpaces, ps, sizeof(pspace_t *) * NWarriors);
}

void amalgamate_pspaces() {
  unsigned int i, j;

  /* Share p-space according to PINs. */
  for (i = 0; i < NWarriors; i++) {
    if (Warriors[i].have_pin) {
      for (j = 0; j < i; j++) {
        if (Warriors[j].have_pin && Warriors[j].pin == Warriors[i].pin) {
          pspace_share(PSpaces[i], PSpaces[j]);
        }
      }
    }
  }
}

void load_warriors() {
  unsigned int i;
  for (i = 0; i < NWarriors; i++) {
    sim_load_warrior(Positions[i], &Warriors[i].code[0], Warriors[i].len);
  }
}

void set_starting_order(unsigned int round) {
  unsigned int i;
  pspace_t **ps;

  /* Copy load positions into starting positions array
     with a cyclic shift of rounds places. */
  for (i = 0; i < NWarriors; i++) {
    unsigned int j = (i + round) % NWarriors;
    StartPositions[i] = (Positions[j] + Warriors[j].start) % OPT_coresize;
  }

  /* Copy p-spaces into simulator p-space array with a
     cyclic shift of rounds places. */
  ps = sim_get_pspaces();
  for (i = 0; i < NWarriors; i++) {
    ps[i] = PSpaces[(i + round) % NWarriors];
  }
}

void clear_results() {
  unsigned int i, j;
  for (i = 0; i < NWarriors; i++) {
    for (j = 0; j <= NWarriors; j++) {
      Results[i][j] = 0;
    }
  }
}

void accumulate_results() {
  unsigned int i;

  /* Fetch the results of the last round from p-space location 0
     that has been updated by the simulator. */
  for (i = 0; i < NWarriors; i++) {
    unsigned int result;
    result = pspace_get(PSpaces[i], 0);
    Results[i][result]++;
  }
}

void output_results() {
  unsigned int i;
  unsigned int j;

  if (NWarriors == 2 && !OPT_m) {
    printf("%d %d\n", Results[0][1], Results[0][2]);
    printf("%d %d\n", Results[1][1], Results[1][2]);
  } else {
    for (i = 0; i < NWarriors; i++) {
      for (j = 1; j <= NWarriors; j++) {
        printf("%d ", Results[i][j]);
      }
      printf("%d\n", Results[i][0]);
    }
  }
}

/*---------------------------------------------------------------
 * Command line arguments.
 */

/*
 * parse options
 */
void readargs(int argc, char **argv) {
  int n;
  char c;
  int cix;
  int tmp;

  n = 1;
  while (n < argc) {
    cix = 0;
    c = argv[n][cix++];
    if (c == '-' && argv[n][1]) {
      do {
        c = argv[n][cix++];
        if (c) switch (c) {
            case 'k':
              OPT_k = 1;
              break;
            case 'b':
              OPT_b = 1;
              break;
            case 'm':
              OPT_m = 1;
              break;

            case 'F':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -F\n");
              c = 0;
              OPT_F = atoi(argv[++n]);
              break;

            case 's':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -s\n");
              c = 0;
              OPT_coresize = atoi(argv[++n]);
              if (OPT_coresize <= 0) panic("core size must be > 0\n");
              break;

            case 'd':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -d\n");
              c = 0;
              OPT_minsep = atoi(argv[++n]);
              if ((int)OPT_minsep <= 0)
                panic("minimum warrior separation must be > 0\n");
              break;

            case 'p':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -p\n");
              c = 0;
              OPT_processes = atoi(argv[++n]);
              if (OPT_processes <= 0) panic("max processes must be > 0\n");
              break;

            case 'r':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -r\n");
              c = 0;
              tmp = atoi(argv[++n]);
              if (tmp < 0) panic("can't do a negative number of rounds!\n");
              OPT_rounds = tmp;
              break;
            case 'c':
              if (n == argc - 1 || !isdigit(argv[n + 1][0]))
                panic("bad argument for option -c\n");
              c = 0;
              OPT_cycles = atoi(argv[++n]);
              if (OPT_cycles <= 0) panic("cycles must be > 0\n");
              break;
            default:
              sprintf(errmsg, "unknown option '%c'\n", c);
              panic(errmsg);
          }
      } while (c);

    } else /* it's a file name */ {
      if (NWarriors == MAX_WARRIORS) {
        panic("too many warriors\n");
      }
      WarriorNames[NWarriors++] = argv[n];
    }
    n++;
  }

  if (NWarriors == 0) usage();
}

/*-------------------------------------------------------------------------
 * Main
 */

int main(int argc, char **argv) {
  unsigned int n; /* round counter */
  int32_t seed;   /* rnd seed. */

  prog_name = xbasename(argv[0]);
  readargs(argc, argv);

  import_warriors();
  check_sanity();
  clear_results();

  seed = OPT_F ? OPT_F - OPT_minsep : rng(time(0) * 0x1d872b41);

  /*
   * Allocate simulator buffers and initialise p-spaces.
   */
  if (!sim_alloc_bufs(NWarriors, OPT_coresize, OPT_processes, OPT_cycles))
    panic("can't allocate memory.\n");

  save_pspaces();
  amalgamate_pspaces(); /* Share P-spaces with equal PINs */

  /*
   * Fight OPT_rounds rounds.
   */
  for (n = 0; n < OPT_rounds; n++) {
    int nalive;
    sim_clear_core();

    seed = compute_positions(seed);
    load_warriors();
    set_starting_order(n);

    nalive = sim_mw(NWarriors, &StartPositions[0], &Deaths[0]);
    if (nalive < 0) panic("simulator panic!\n");

    accumulate_results();
  }
  sim_free_bufs();
  /*print_counts();*/

  output_results();
  return 0;
}