Skip to content

Instantly share code, notes, and snippets.

@rdebath
Created September 7, 2014 18:53
Show Gist options
  • Save rdebath/965b15025725de9552b3 to your computer and use it in GitHub Desktop.
Save rdebath/965b15025725de9552b3 to your computer and use it in GitHub Desktop.
/*
* 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");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment