/* exhaust.c: crippled pmars-like redcode simulator
 * $Id: exhaust.c,v 1.3 2003/09/04 15:44:24 varfar 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
#define PATCHLEVEL 2

/* 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 <stdlib.h>
#include <time.h>
#include <ctype.h>

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

#include "compress.h"
#define FALSE (0==1)
#define TRUE (1==1)

static unsigned int NWarriors = 0;
static warrior_t *Warriors = NULL;	/* [NWarriors] */

static char **WarriorNames = NULL;	/* [NWarriors] */
/* File names of warriors. */

static field_t *Positions = NULL;	/* [NWarriors] */
static field_t *StartPositions = NULL;	/* [NWarriors] */
/* Starting position of each warrior.
 * The StartPositions[] array is a copy
 * of Positions[], rotated by the number of
 * the round, to emulate pMARS.
 */

static unsigned int *Deaths = NULL;	/* [NWarriors] */

static unsigned **ScoresMatrix = NULL;	/* [NWarriors][NWarriors] for each matching */

static pspace_t **PSpaces = NULL;	/* [NWarriors] */
/* 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, '/');
    if (!b) {
        b = strrchr (s, '\\');
    }
    return b ? 1 + b : s;
}

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


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

/* Like realloc(3), but works with NULL pointers. */
void *
xrealloc (void *p, size_t newsize) {
    if (p == NULL) {
        return malloc (newsize);
    }
    return realloc (p, newsize);
}

void
usage () {
    printf ("%s v%d.%d", prog_name, VERSION, REVISION);
    if (PATCHLEVEL > 0) {
        printf (".%d", PATCHLEVEL);
    }
    printf ("\n");
    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
free_related_memory () {
    if (Warriors) {
        free (Warriors);
        Warriors = NULL;
    }
    if (Positions) {
        free (Positions);
        Positions = NULL;
    }
    if (StartPositions) {
        free (StartPositions);
        StartPositions = NULL;
    }
    if (Deaths) {
        free (Deaths);
        Deaths = NULL;
    }
    // free ScoreMatrix..
    if (PSpaces) {
        free (PSpaces);
        PSpaces = NULL;
    }
    if (WarriorNames) {
        free (WarriorNames);
        WarriorNames = NULL;
    }
}

void
alloc_related_memory () {
    //unsigned int i;

    Warriors = (warrior_t *) malloc (sizeof (warrior_t) * NWarriors);
    Positions = (field_t *) malloc (sizeof (field_t) * NWarriors);
    StartPositions = (field_t *) malloc (sizeof (field_t) * NWarriors);
    Deaths = (unsigned int *) malloc (sizeof (unsigned int *) * NWarriors);

    // ScoreMatrix..

    /* Warrior P-spaces */
    PSpaces = (pspace_t **) malloc (sizeof (pspace_t *) * NWarriors);

}


void
import_warriors () {
    unsigned int i;

    for (i = 0; i < NWarriors; i++) {
		  fprintf(stderr,"loading %s..\n",WarriorNames[i]);
        asm_fname (WarriorNames[i], &Warriors[i], OPT_coresize);
    }
	 fprintf(stderr,"%i warriors loaded\n",NWarriors);
}

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

    /* Make sure each warrior has some code. */
    for (i = 0; i < NWarriors; i++) {
        if (Warriors[i].len == 0 || Warriors[i].len > MAXLENGTH) {
            sprintf (errmsg, "warrior %d has a bad amount of code code (%i instructions)\n", i,Warriors[i].len);
            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) {
            sprintf (errmsg, "warrior %s is too long (%i > %i)\n",
                     WarriorNames[i], Warriors[i].len, OPT_minsep);
            panic (errmsg);
        }
    }

    /* Make sure there is space for all warriors to be loaded. */
    space_used = 2 * OPT_minsep;	// two interesting warriors
    if (space_used > OPT_coresize) {
        panic ("warriors or minimum separation 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 (s32_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 (s32_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;
    }
}

s32_t
compute_positions (s32_t seed) {
    u32_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]);
                }
            }
        }
    }
}

s32_t
load_warriors (unsigned i, unsigned j, s32_t * seed) {
    unsigned pos = OPT_minsep + (*seed % (OPT_coresize - OPT_minsep - OPT_minsep));
    if(j > NWarriors)
        exit(1);
    *seed = rng (*seed);
    sim_load_warrior (0, &Warriors[i].code[0], Warriors[i].len);
    sim_load_warrior (pos, &Warriors[j].code[0], Warriors[j].len);
    if(OPT_coresize <= (pos+Warriors[j].len))
        exit(1);
    return pos + Warriors[j].start;
}

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
output_results (unsigned long long exec_count, time_t run_time) {
    unsigned int i, j, op, mod;
    unsigned long long count;
    char //buf[128],
    // html
    *html_preamble = "<html>\n<body>\n<h1>%s</h1>\n",
    *html_table_preamble = "<h2>%s</h2><table border=\"1\">\n",
    *html_start_row = "<tr>",
    *html_name = "<th>%s</th>",
    *html_text = "<td>%s</td>",
    *html_value = "<td>%i</td>",
	 *html_valueu32 = "<td>%u</td>",
    *html_valueu64 = "<td>%llu</td>",
    *html_end_row = "</tr>\n",
    *html_table_postamble = "</table>\n",
    *html_postamble = "</body>\n</html>\n",
    // tab-seperated-value
    *tsv_preamble = "",
    *tsv_table_preamble = "",
    *tsv_start_row = "",
    *tsv_name = "%s\t",
    *tsv_text = tsv_name,
    *tsv_value = "%i\t",
	 *tsv_valueu32 = "%u\t",
    *tsv_valueu64 = "%llu\t",
    *tsv_end_row = "\n", *tsv_table_postamble = "", *tsv_postamble = "",
    // --- actually used ones ---
    *preamble = html_preamble,
    *table_preamble = html_table_preamble,
    *start_row = html_start_row,
    *name = html_name,
    *text = html_text,
    *value = html_value,
	 *valueu32 = html_valueu32,
    *valueu64 = html_valueu64,
    *end_row = html_end_row,
    *table_postamble = html_table_postamble, *postamble = html_postamble;
		
    printf (preamble, "RESULTS");

    printf (table_preamble, "Scores Matrix");
    printf (start_row);
    printf (name, "");
    for (i = 0; i < NWarriors; i++) {
        printf (name, xbasename (WarriorNames[i]));
    }
    printf (end_row);

    for (i = 0; i < NWarriors; i++) {
        printf (start_row);
        printf (name, xbasename (WarriorNames[i]));
        for (j = 0; j < NWarriors; j++) {
            printf (valueu32, ScoresMatrix[i][j]);
        }
        printf (end_row);
    }

    printf (table_postamble);

    printf (table_preamble, "Opcode Execution Frequency");
    for (op = 0; op < OPCODE_LAST; op++) {
        for (mod = 0; mod < MODIFIER_LAST; mod++) {
            count = get_opcode_count (_OP (op, mod));
            if (count > 0) {
                printf (start_row);
                printf (name, MNEMONIC_OPCODE[op]);
                printf (name, MNEMONIC_MODIFIER[mod]);
                printf (valueu64, count);
                printf (end_row);
            }
        }
    }
    printf (table_postamble);

    printf (table_preamble, "Misc Info");
    printf (start_row);
    printf (name, "instructions");
    printf (valueu64, exec_count);
    printf(end_row);
    printf (start_row);
    printf (name, "checksum");
    printf (valueu32,get_exec_trail_checksum());
    printf (end_row);
    printf (start_row);
    printf (name, "rounds");
    printf (valueu64, (NWarriors * (NWarriors / 2) * OPT_rounds));
    printf(end_row);
    printf (start_row);
    printf (name, "time (secs)");
    printf (valueu32, run_time);
    printf(end_row);
    printf (start_row);
    printf (name, "rounds/sec");

    if (run_time > 0) {
        printf (valueu64, (NWarriors * (NWarriors / 2) * OPT_rounds) / run_time);
    } else {
        printf (text, "all of them!");
    }
    printf (end_row);

    printf (start_row);
    printf (name, "logical bytes");
    printf (valueu64,get_logical_bytes());
    printf(end_row);
    printf (start_row);
    printf (name, "physical bytes");
    printf (valueu64,get_physical_bytes());
    printf(end_row);
    printf (table_postamble);

    printf (postamble);
}

FILE *open_exec_trail(unsigned i,int append) {
    char exectrailbuf[128];
    FILE *ret = 0;
    sprintf (exectrailbuf, "%s.ex", xbasename (WarriorNames[i]));
    ret = fopen (exectrailbuf, append? "ab": "wb");
    if (!ret)
        panic (exectrailbuf);
    return ret;
}


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

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

    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 ((int) 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 */ {
            ++NWarriors;
            WarriorNames = xrealloc (WarriorNames, NWarriors * sizeof (char *));
            WarriorNames[NWarriors - 1] = argv[n];
        }
        n++;
    }

    if (NWarriors == 0)
        usage ();
    else {
        ScoresMatrix = (unsigned **) malloc (NWarriors * sizeof (unsigned *));
        if (!ScoresMatrix)
            panic ("x5");
        for (i = 0; i < NWarriors; i++) {
            exec_trail = open_exec_trail(i,FALSE);
            if (1 != fwrite (&i, sizeof (i), 1, exec_trail))
                panic ("x16");
            fclose(exec_trail); // keep file handle count low!
            ScoresMatrix[i] = calloc (NWarriors, sizeof (unsigned));
            if (!ScoresMatrix[i])
                panic ("x6");
        }
    }
}



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

int
main (int argc, char **argv) {
    unsigned int i, j, len, ilen, jlen, k, m,	// matching values
    n;				/* round counter */
    s32_t seed;			/* rnd seed. */
    unsigned ok = (0==0);
    unsigned char exec_trail_op;
    unsigned long long exec_count = 0;
    FILE *fi, *fj;
    time_t start_time, end_time, run_time;

    comp_buf_t desti, destj;

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

    import_warriors ();
    check_sanity ();

    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.
     */

    if (OPT_rounds > 0 && NWarriors > 1)

        time (&start_time);

    for (i = 0; i < NWarriors; i++) {
        fi = open_exec_trail(i,TRUE);
        desti.f = fi; 
        for (j = i; j < NWarriors; j++) {
            if (i != j) {
                fj = open_exec_trail(j,TRUE);
					 destj.f = fj;
					 for (n = 0; n < OPT_rounds; n++) {

                    sim_clear_core ();

                    switch (sim
                            (2, Warriors[i].start, load_warriors (i, j, &seed),
                             OPT_cycles, NULL)) {
                    case 0:	// i won
                        ScoresMatrix[i][j] += 3;
                        break;
                    case 1:	// j won
                        ScoresMatrix[j][i] += 3;
                        break;
                    case 2:	// tie
                        ScoresMatrix[i][j]++;
                        ScoresMatrix[j][i]++;
                        break;
                    default:
                        panic ("simulator panic!\n");
                    }
                    // assign exec trail
                    len = get_exec_trail_length ();
                    jlen = len >> 1;
                    ilen = jlen + (len & 1);
                    if (ilen + jlen != len)
                        panic ("x16");
                    if (ilen > OPT_cycles)
                        panic ("x13");
                    if (1 != fwrite (&j, sizeof (j), 1, fi))
                        panic ("x14");
                    if (1 != fwrite (&i, sizeof (i), 1, fj))
                        panic ("x15");
                    if (1 != fwrite (&ilen, sizeof (ilen), 1, fi))
                        panic ("x9");
                    if (1 != fwrite (&jlen, sizeof (jlen), 1, fj))
                        panic ("x10");
                    m = 0;
						  desti.len = 0;
						  destj.len = 0;
                    for (k = 0; k < len; k++) {
                        exec_trail_op = get_exec_trail (k);
								if(exec_trail_op >= _OP(OPCODE_LAST,MODIFIER_LAST))
									panic ("x17");
                        switch (m++ & 1) {	// toggle between the warriors in the round
                        case 0:
									write_compressed(&desti,exec_trail_op);
                           break;
                        case 1:
									write_compressed(&destj,exec_trail_op);
                           break;
                        }
                        exec_count++;
                    }
						  flush_compressed(&desti);
						  flush_compressed(&destj);
                }
                //printf("%u\r",exec_count); fflush(stdout);
                fclose(fj);
            }
        }
        fclose(fi);
    }

    time (&end_time);

    run_time = end_time - start_time;

    sim_free_bufs ();
    output_results (exec_count, run_time);
    free_related_memory ();
    return 0;
}