joust.c

/*
 * To compile:
 *  gcc -O3 -std=c99 -Wall -Wextra -Wshadow -fopenmp joust.c -o joust
 *
 *
 *  TODO
 *	Allow for (...)*0 comments.
 *	Allow (...{...}...}%3 format as alias for (...)*3...(...)*3
 *	Table like the proper joust versions.
 *	Full dump of match results
 *	Table like slow python version
 *
 *	Non-expansion mode for bots that do (((...)*10000)*10000)*10000)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#ifndef STACKSIZE
#define STACKSIZE 2048
#endif
#ifndef MAXINSTR
#define MAXINSTR 10000
#endif

char * loadbf(char * filename);
signed char * convertbf(char * bfstring);
void runbf(signed char * bytecode);
void runmatch(signed char * bytecode1, signed char * bytecode2, int tapelen, char *name1, char *name2);

enum instruction {
    I_FIN,
    I_LEFT, I_RIGHT, I_UP, I_DOWN, I_PRT, I_INP,
    I_BEQ, I_BNE, I_JEQ, I_JNE
};

int enable_input = 0;
int max_runtime = MAXINSTR;

int
main(int argc, char ** argv)
{
    signed char ** code;
    char ** cleanbf;
    char * pgm = argv[0];

    for(;;) {
	if (argc < 2 || argv[1][0] != '-' || argv[1][1] == '\0') {
	    break;

	} else if (strncmp(argv[1], "-M", 2) == 0) {
	    max_runtime = strtoul(argv[1]+2, 0, 10);
	    if (max_runtime <= 0) max_runtime = MAXINSTR;
	    argc--; argv++;

	} else if (strcmp(argv[1], "-h") == 0) {

	    fprintf(stderr, "%s: [options] [File]\n", pgm);
	    fprintf(stderr, "%s\n",
	    "\t"    "-h      This message"
	    );

	} else if (argv[1][0] == '-') {
	    fprintf(stderr, "Unknown option '%s'.\n", argv[1]);
	    exit(1);
	} else break;
    }

    /* A single file is a BF test */
    if (argc <= 2) {
	enable_input = 1;
	char * bf1 = loadbf(argv[1]);
	signed char * code1 = convertbf(bf1);
	runbf(code1);
	exit(0);
    }

    code = malloc(argc*sizeof*code);
    cleanbf = malloc(argc*sizeof*cleanbf);

    for (int i=1; i<argc; i++) {
	cleanbf[i] = loadbf(argv[i]);
	code[i] = convertbf(cleanbf[i]);
    }

    printf("!Max count is %d cycles\n", max_runtime);

#pragma omp parallel for schedule(dynamic)
    for (int i=1; i<argc-1; i++) {
	for (int j=i+1; j<argc; j++) {
	    for(int tl=10; tl<=30; tl++)
		runmatch(code[i], code[j], tl, argv[i], argv[j]);
	}
    }

    return 0;
}

char *
loadbf(char * filename)
{
    FILE * ifd;
    int ch = 0;
    int n=0, p=0;
    int stkptr = 0, repstate = 3, repcnt = 2, repstart = 0, repend = 0;
    int stack[STACKSIZE];
    char * pgm = 0;

    if (filename) {
	ifd = fopen(filename, "r");
	if (ifd == 0) { perror(filename); exit(1); }
    } else
	ifd = stdin;

    while( (ch != EOF && (ch=getc(ifd)) != EOF) || repstate != 0 ) {
	if (ch == 0 && !filename) ch = EOF;

	if ((repstate == 1 || repstate == 2) && ch == ' ') continue;
	if (repstate == 1 && (ch == '*' || ch == '%')) {
	    repstate = 2;
	    continue;
	}
	if ((repstate == 2 || repstate == 3) && (ch >= '0' && ch <= '9')) {
	    repcnt = repcnt * 10 + ch - '0';
	    repstate = 3;
	    continue;
	}

	if (repstate == 3 && repcnt > 1) {
	    if (p+(long long)repcnt*(repend-repstart) > 1000000000) {
		fprintf(stderr, "%s: Expansion failure, final BF is excessive.\n", filename);
		exit(1);
	    }
	    if (p+repcnt*(repend-repstart) >= n) {
		n *=2;
		if (n<p+repcnt*(repend-repstart)) n = p+repcnt*(repend-repstart) + 32;
		pgm = realloc(pgm, (n+2)*sizeof*pgm);
		if(!pgm) {perror(filename); exit(1);}
	    }
	    if (repcnt>max_runtime && !enable_input) repcnt = max_runtime;
	    repcnt--;
	    while(repcnt > 0) {
		memcpy(pgm+p, pgm+repstart, (repend-repstart)*sizeof*pgm);
		p += repend-repstart;
		repcnt--;
	    }
	}
	repstart = repend = repstate = repcnt = 0;

	if (ch == '(') {
	    stack[stkptr] = p;
	    stkptr++;
	    if(stkptr >= STACKSIZE) {
		fprintf(stderr, "Bracket stack overflow\n");
		exit(1);
	    }
	    continue;
	}
	if (stkptr > 0 && ch == ')') {
	    stkptr--;
	    repstart = stack[stkptr];
	    repend = p;
	    repstate = 1;
	    continue;
	}

	if (! ( ch=='>' || ch=='<' || ch=='+' || ch=='-' ||
		ch=='[' || ch==']' || ch=='.' || (enable_input && ch==',' )))
	    continue;

	if (p>= n) {
	    if(n==0) n=32;
	    pgm = realloc(pgm, (n*2+2)*sizeof*pgm);
	    if(!pgm) {perror(filename); exit(1);}
	    n*=2;
	}
	pgm[p++] = ch;
    }
    if(filename) fclose(ifd);
    pgm[p] = 0;

    /* Loaded and unpacked the BF, now check for illegal '[]' characters */
    for(stkptr=ch=p=0; pgm[p]; p++)
    {
	if (pgm[p] == '[' ) {
	    stack[stkptr] = p;
	    stkptr++;
	    if(stkptr >= STACKSIZE) {
		fprintf(stderr, "Loop stack overflow\n");
		exit(1);
	    }
	}
	if (pgm[p] == ']' ) {
	    if (stkptr == 0) {
		pgm[p] = ' ';
		ch = 1;
	    } else
		stkptr--;
	}
    }

    while(stkptr>0) { ch = 1; stkptr--; pgm[stack[stkptr]] = ' '; }

    if(ch) {
	/* There were some bad loops, get rid of them */
	int d = 0;
	for(p=0; pgm[p]; p++) if (pgm[p] != ' ') pgm[d++] = pgm[p];
	pgm[d] = 0;
    }

    if (!enable_input)
	printf("! %s expanded to %d\n", filename, strlen(pgm));

    return pgm;
}

/*  This is a rather limited conversion to byte code; I'm not even doing any
 *  run length encoding because I need to sync two programs instruction by
 *  instruction.
 */
signed char *
convertbf(char * bfstring)
{
    int bycnt=0, bp=0;
    char * s;
    signed char * bytecode;
    int stkptr = 0;
    int stack[STACKSIZE];

    for(s=bfstring; *s; s++) {
	if (*s == '[' || *s == ']')
	    bycnt += 5;	/* Worst case. */
	else
	    bycnt ++;
    }
    bytecode = malloc(bycnt+1);
    if (!bytecode) {perror(0); exit(1);}

    for(s=bfstring; *s; s++) {
	switch(*s) {
	    case '<': bytecode[bp++] = I_LEFT; break;
	    case '>': bytecode[bp++] = I_RIGHT; break;
	    case '+': bytecode[bp++] = I_UP; break;
	    case '-': bytecode[bp++] = I_DOWN; break;
	    case '.': bytecode[bp++] = I_PRT; break;
	    case ',': bytecode[bp++] = I_INP; break;
	    case '[':
		stack[stkptr] = bp;
		stkptr++;
		if(stkptr >= STACKSIZE) {
		    fprintf(stderr, "Loop stack overflow\n");
		    exit(1);
		}
		bp += 5;
		break;
	    case ']':
		stkptr--;
		if (bp - stack[stkptr] < 127 ) {
		    memmove(bytecode+stack[stkptr], bytecode+stack[stkptr]+3, bp - stack[stkptr]-3);
		    bp -= 3;
		    bytecode[bp++] = I_BNE;
		    bp++;
		    bytecode[bp-1] = (stack[stkptr]+2)-bp;
		    bytecode[stack[stkptr]] = I_BEQ;
		    bytecode[stack[stkptr]+1] = bp-(stack[stkptr]+2);
		} else {
		    bytecode[bp++] = I_JNE;
		    bp += 4;

		    bytecode[stack[stkptr]] = I_JEQ;
		    bytecode[stack[stkptr]+1] = ((bp    ) & 0xFF);
		    bytecode[stack[stkptr]+2] = ((bp>>8 ) & 0xFF);
		    bytecode[stack[stkptr]+3] = ((bp>>16) & 0xFF);
		    bytecode[stack[stkptr]+4] = ((bp>>24) & 0xFF);

		    bytecode[bp-4] = (((stack[stkptr]+5)    ) & 0xFF);
		    bytecode[bp-3] = (((stack[stkptr]+5)>>8 ) & 0xFF);
		    bytecode[bp-2] = (((stack[stkptr]+5)>>16) & 0xFF);
		    bytecode[bp-1] = (((stack[stkptr]+5)>>24) & 0xFF);
		}
		break;
	}
    }
    bytecode[bp++] = I_FIN;

    return bytecode;
}

/* Okay this is a plain interpreter for a single BF program.
 * Good for testing.
 */
void
runbf(signed char * bytecode)
{
    char mem[USHRT_MAX];
    short m = 0;
    int p;
    for(p=0; bytecode[p] != I_FIN; p++) {
	switch(bytecode[p]) {
	case I_LEFT: m--; break;
	case I_RIGHT: m++; break;
	case I_UP: mem[m]++; break;
	case I_DOWN: mem[m]--; break;
	case I_INP: {int ch=getchar(); if(ch!=EOF) mem[m] = ch;} break;
	case I_PRT: putchar(mem[m]); break;

	case I_BNE: if(mem[m]) p+=bytecode[p+1]; p++; break;
	case I_BEQ: if(!mem[m]) p+=bytecode[p+1]; p++; break;
	case I_JNE:
	    if (mem[m]) {
		p = ((unsigned char)bytecode[p+1]) +
		    ((unsigned char)bytecode[p+2]<<8) +
		    ((unsigned char)bytecode[p+3]<<16) +
		    ((unsigned char)bytecode[p+4]<<24) -1;
	    } else
		p+=4;
	    break;
	case I_JEQ:
	    if (!mem[m]) {
		p = ((unsigned char)bytecode[p+1]) +
		    ((unsigned char)bytecode[p+2]<<8) +
		    ((unsigned char)bytecode[p+3]<<16) +
		    ((unsigned char)bytecode[p+4]<<24) -1;
	    } else
		p+=4;
	    break;
	}
    }
}

void
runmatch(signed char * bytecode1, signed char * bytecode2, int tapelen, char *name1, char *name2)
{
    char mem[128] = {0};
    int m1 = 0, m2 = tapelen-1;
    int p1=0, p2=0;
    int m1z = 0, m2z = 0;
    int icnt;

    mem[m1] = mem[m2] = -128;

    for(icnt = 0; icnt < max_runtime && (bytecode1[p1] != I_FIN || bytecode2[p2] != I_FIN) ; ) {
	int m2tst = mem[m2];

	icnt++;
	switch(bytecode1[p1]) {
	case I_LEFT: m1--; p1++; break;
	case I_RIGHT: m1++; p1++; break;
	case I_UP: mem[m1]++; p1++; break;
	case I_DOWN: mem[m1]--; p1++; break;
	case I_PRT: p1++; break;

	case I_BNE: if(mem[m1]) p1+=bytecode1[p1+1]; p1+=2; break;
	case I_BEQ: if(!mem[m1]) p1+=bytecode1[p1+1]; p1+=2; break;
	case I_JNE:
	    if (mem[m1]) {
		p1 = ((unsigned char)bytecode1[p1+1]) +
		    ((unsigned char)bytecode1[p1+2]<<8) +
		    ((unsigned char)bytecode1[p1+3]<<16) +
		    ((unsigned char)bytecode1[p1+4]<<24);
	    } else
		p1+=5;
	    break;
	case I_JEQ:
	    if (!mem[m1]) {
		p1 = ((unsigned char)bytecode1[p1+1]) +
		    ((unsigned char)bytecode1[p1+2]<<8) +
		    ((unsigned char)bytecode1[p1+3]<<16) +
		    ((unsigned char)bytecode1[p1+4]<<24);
	    } else
		p1+=5;
	    break;
	}

	switch(bytecode2[p2]) {
	case I_LEFT: m2++; p2++; break;
	case I_RIGHT: m2--; p2++; break;
	case I_UP: mem[m2]++; p2++; break;
	case I_DOWN: mem[m2]--; p2++; break;
	case I_PRT: p2++; break;

	case I_BNE: if(m2tst) p2+=bytecode2[p2+1]; p2+=2; break;
	case I_BEQ: if(!m2tst) p2+=bytecode2[p2+1]; p2+=2; break;
	case I_JNE:
	    if (m2tst) {
		p2 = ((unsigned char)bytecode2[p2+1]) +
		    ((unsigned char)bytecode2[p2+2]<<8) +
		    ((unsigned char)bytecode2[p2+3]<<16) +
		    ((unsigned char)bytecode2[p2+4]<<24);
	    } else
		p2+=5;
	    break;
	case I_JEQ:
	    if (!m2tst) {
		p2 = ((unsigned char)bytecode2[p2+1]) +
		    ((unsigned char)bytecode2[p2+2]<<8) +
		    ((unsigned char)bytecode2[p2+3]<<16) +
		    ((unsigned char)bytecode2[p2+4]<<24);
	    } else
		p2+=5;
	    break;
	}

	if (mem[0] == 0) m1z++; else m1z = 0;
	if (mem[tapelen-1] == 0) m2z++; else m2z = 0;

	if (m1<0 || m1>=tapelen) break;
	if (m2<0 || m2>=tapelen) break;
	if (m1z == 2 || m2z == 2) break;
    }

    #pragma omp critical(savescore)
    {
	int m1lost = 0, m2lost = 0;

	if (m1z==2) m1lost = 1;
	if (m2z==2) m2lost = 1;
	if (m1<0 || m1>=tapelen) m1lost = 1;
	if (m2<0 || m2>=tapelen) m2lost = 1;
	if (icnt == max_runtime)
	    printf("%s vs %s, tape %d, timeout, ", name1, name2, tapelen);
	else
	    printf("%s vs %s, tape %d, cycles %d, ", name1, name2, tapelen, icnt);

	if (m1lost && m2lost) {
	    printf("Both lost, so it's a draw\n");
	} else
	if (m1lost || (!m2lost && abs(mem[0]) < abs(mem[tapelen-1]))) {
	    printf("Winner: %s\n", name2);
	} else
	if (m2lost || (!m1lost && abs(mem[0]) > abs(mem[tapelen-1]))) {
	    printf("Winner: %s\n", name1);
	} else
	    printf("The match was a draw\n");
    }
}