--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/interps/bfjoust/egojoust.c	Sun Dec 09 19:30:08 2012 +0000
@@ -0,0 +1,438 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#include "buffer.h"
+
+#define MINTAPELEN 10
+#define MAXTAPELEN 30
+#define POLARITIES 4
+#define RUNCOUNT   (((MAXTAPELEN-MINTAPELEN) + 1) * POLARITIES)
+
+/* parse a BFJoust program */
+int parseFile(struct Buffer_char *progp)
+{
+    int i, end, inner, iend, llen, ilen, rlen, times, rep, loc;
+    struct Buffer_char prog = *progp;
+    struct Buffer_char temp;
+
+    /* go through looking for things to expand */
+    for (i = 0; i < prog.bufused; i++) {
+        if (prog.buf[i] == '(') {
+            /* look for the match */
+            int depth = 1;
+            inner = iend = -1;
+            for (end = i + 1; end < prog.bufused && depth; end++) {
+                if (prog.buf[end] == '(') {
+                    depth++;
+                } else if (prog.buf[end] == ')') {
+                    depth--;
+                } else if (depth == 1 && prog.buf[end] == '{') {
+                    inner = end;
+                } else if (depth == 1 && prog.buf[end] == '}') {
+                    iend = end;
+                }
+            }
+
+            /* make sure it's sensible */
+            end--;
+            if (end + 2 >= prog.bufused) return 0;
+
+            /* expand it only if it includes [ or ], or is a '%' loop (which make interpretation basically impossible if unexpanded) */
+            llen = end - i;
+            if (strcspn(prog.buf + i, "[]") >= llen && prog.buf[end+1] == '*') {
+                continue;
+            }
+
+            /* check what comes next */
+            times = atoi(prog.buf + end + 2);
+            if (times < 0 || times > 10000) times = 10000;
+            if (prog.buf[end+1] == '*') {
+                llen = end - i - 1;
+
+                /* the simple case, just repeat n times */
+                INIT_BUFFER(temp);
+                temp.bufused = times * llen;
+                while (temp.bufsz < temp.bufused) {
+                    EXPAND_BUFFER(temp);
+                }
+                for (rep = 0; rep < times; rep++) {
+                    memcpy(temp.buf + rep * llen, prog.buf + i + 1, llen);
+                }
+
+            } else if (prog.buf[end+1] == '%') {
+                /* make sure there's a {} */
+                if (inner == -1 || iend == -1) return 0;
+
+                llen = inner - i - 1;
+                ilen = iend - inner - 1;
+                rlen = end - iend - 1;
+                if (llen < 0 || ilen < 0 || rlen < 0) return 0;
+
+                /* set up the buffer */
+                INIT_BUFFER(temp);
+                temp.bufused = times * llen + ilen + times * rlen;
+                while (temp.bufsz < temp.bufused) {
+                    EXPAND_BUFFER(temp);
+                }
+                
+                /* now the left */
+                loc = 0;
+                for (rep = 0; rep < times; rep++) {
+                    memcpy(temp.buf + loc + rep * llen, prog.buf + i + 1, llen);
+                }
+                loc = times * llen;
+
+                /* the inner */
+                memcpy(temp.buf + loc, prog.buf + inner + 1, ilen);
+                loc += ilen;
+
+                /* and the right */
+                for (rep = 0; rep < times; rep++) {
+                    memcpy(temp.buf + loc + rep * rlen, prog.buf + iend + 1, rlen);
+                }
+
+            } else {
+                return 0;
+
+            }
+
+            /* now copy it back into prog */
+            while (prog.bufsz < prog.bufused + temp.bufused + 1) {
+                EXPAND_BUFFER(prog);
+            }
+            memmove(prog.buf + i + temp.bufused, prog.buf + end + 1, prog.bufused - end - 1);
+            memcpy(prog.buf + i, temp.buf, temp.bufused);
+            prog.bufused = prog.bufused - end + i - 1 + temp.bufused;
+            WRITE_BUFFER(prog, "", 1); prog.bufused--;
+
+            FREE_BUFFER(temp);
+
+            i--;
+        }
+    }
+
+    memcpy(progp, &prog, sizeof(prog));
+    return 1;
+}
+
+/* returns true if this is a BF comment */
+int isComment(char c)
+{
+    return (c != '<' && c != '>' && c != '-' && c != '+' && c != '[' && c != ']' && c != '(' && c != ')' && c != '.');
+}
+
+/* run an execution step */
+void runStep(struct Buffer_char prog, int *loops, int *pip,
+             char *tape, char *otape, int tapelen, int *tip,
+             int tapedir, int polarity,
+             struct Buffer_int *pstack, struct Buffer_int *pmax)
+{
+    int pi = *pip;
+    int ti = *tip;
+    int reps = 0;
+
+    /* find a non-comment character */
+rerun:
+    if (++reps > 16) return;
+    if (pi < 0) return;
+    for (; pi < prog.bufused && isComment(prog.buf[pi]); pi++);
+    *pip = pi;
+    if (pi >= prog.bufused) return;
+
+    /* run it */
+    switch (prog.buf[pi]) {
+        case '<':
+            ti -= tapedir;
+            break;
+
+        case '>':
+            ti += tapedir;
+            break;
+
+        case '-':
+            otape[ti] -= polarity;
+            break;
+
+        case '+':
+            otape[ti] += polarity;
+            break;
+
+        case '[':
+            if (tape[ti] == 0) {
+                /* first check the cache */
+                if (loops[pi] != -1) {
+                    pi = loops[pi];
+                } else {
+                    int depth = 1;
+                    int opi = pi;
+                    for (pi++; pi < prog.bufused && depth; pi++) {
+                        switch (prog.buf[pi]) {
+                            case '[':
+                                depth++;
+                                break;
+
+                            case ']':
+                                depth--;
+                                break;
+                        }
+                    }
+                    pi--;
+
+                    loops[opi] = pi;
+                    loops[pi] = opi;
+                }
+            }
+            break;
+
+        case ']':
+            if (tape[ti] != 0) {
+                /* check the cache */
+                if (loops[pi] != -1) {
+                    pi = loops[pi];
+                } else {
+                    int depth = 1;
+                    for (pi--; pi >= 0 && depth; pi--) {
+                        switch (prog.buf[pi]) {
+                            case ']':
+                                depth++;
+                                break;
+
+                            case '[':
+                                depth--;
+                                break;
+                        }
+                    }
+                    pi++;
+                }
+            }
+            break;
+
+        case '(':
+            /* make sure this is cached */
+            if (loops[pi] == -1) {
+                int depth = 1;
+                int ipi;
+                for (ipi = pi + 1; ipi < prog.bufused && depth; ipi++) {
+                    switch (prog.buf[ipi]) {
+                        case '(':
+                            depth++;
+                            break;
+
+                        case ')':
+                            depth--;
+                            break;
+                    }
+                }
+                ipi--;
+
+                loops[pi] = ipi;
+                loops[ipi] = pi;
+            }
+
+            /* push the counter */
+            {
+                int count = atoi(prog.buf + loops[pi] + 2);
+                if (BUFFER_SPACE(*pstack) < 1) {
+                    EXPAND_BUFFER(*pstack);
+                    EXPAND_BUFFER(*pmax);
+                }
+                pstack->buf[pstack->bufused++] = 0;
+                pmax->buf[pmax->bufused++] = count;
+            }
+
+            /* then continue immediately */
+            pi++;
+            goto rerun;
+
+        case ')':
+            /* increment the counter */
+            if (pstack->bufused > 0) {
+                pstack->buf[pstack->bufused-1]++;
+            }
+
+            /* either reloop or don't */
+            if (pstack->buf[pstack->bufused-1] < pmax->buf[pstack->bufused-1]) {
+                pi = loops[pi];
+            } else {
+                pstack->bufused = pmax->bufused = pstack->bufused - 1;
+            }
+            pi++;
+            goto rerun;
+
+        case '.':
+            /* nop */
+            break;
+    }
+    pi++;
+
+    *pip = pi;
+    *tip = ti;
+}
+
+/* simple hashing function, same as is used in sdbm */
+size_t simpleHash(size_t slen, unsigned char *str)
+{
+    size_t hash = 0;
+
+    for (; slen > 0; slen--)
+        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
+
+    return hash;
+}
+
+int main(int argc, char **argv)
+{
+    struct Buffer_char lprog, rprog;
+    struct Buffer_int lloops, rloops;
+    struct Buffer_int lpstack, rpstack, lpmax, rpmax;
+    FILE *lfh, *rfh;
+    int lparse, rparse;
+    char *tape, *otape;
+    int lt, rt, tapelen;
+    int polarity, lpol, rpol;
+    int lpi, rpi;
+    int lwins, rwins;
+    int lloss, rloss;
+    int step;
+
+    if (argc < 3) {
+        fprintf(stderr, "Use: egojoust <left program> <right program>\n");
+        return 0;
+    }
+
+    /* read in the files */
+    INIT_BUFFER(lprog);
+    SF(lfh, fopen, NULL, (argv[1], "r"));
+    READ_FILE_BUFFER(lprog, lfh);
+    WRITE_BUFFER(lprog, "", 1); lprog.bufused--;
+
+    INIT_BUFFER(rprog);
+    SF(rfh, fopen, NULL, (argv[2], "r"));
+    READ_FILE_BUFFER(rprog, rfh);
+    WRITE_BUFFER(rprog, "", 1); rprog.bufused--;
+
+    /* parse them */
+    lparse = parseFile(&lprog);
+    rparse = parseFile(&rprog);
+    if (!lparse) {
+        if (!rparse) {
+            printf("Both warriors failed to parse. Tie!\n");
+            return 0;
+        } else {
+            printf("Left warrior failed to parse, right warrior wins!\n");
+            return RUNCOUNT;
+        }
+    } else if (!rparse) {
+        printf("Right warrior failed to parse, left warrior wins!\n");
+        return -RUNCOUNT;
+    }
+
+    /* allocate the tape */
+    SF(tape, malloc, NULL, (30));
+    SF(otape, malloc, NULL, (30));
+
+    /* prepare the caches */
+    INIT_BUFFER(lloops);
+    INIT_BUFFER(rloops);
+    while (lloops.bufsz < lprog.bufused) EXPAND_BUFFER(lloops);
+    memset(lloops.buf, -1, lprog.bufused * sizeof(int));
+    while (rloops.bufsz < rprog.bufused) EXPAND_BUFFER(rloops);
+    memset(rloops.buf, -1, rprog.bufused * sizeof(int));
+
+    INIT_BUFFER(lpstack);
+    INIT_BUFFER(rpstack);
+    INIT_BUFFER(lpmax);
+    INIT_BUFFER(rpmax);
+
+    /* run for each polarity, for each length from 10 to 30 */
+    lwins = 0;
+    rwins = 0;
+
+    printf("%s vs %s:\n", argv[1], argv[2]);
+
+    for (polarity = 0; polarity < POLARITIES; polarity++) {
+        /* set up the polarity */
+        if (polarity & 0x2) {
+            lpol = -1;
+        } else {
+            lpol = 1;
+        }
+
+        if (polarity & 0x1) {
+            rpol = -1;
+        } else {
+            rpol = 1;
+        }
+
+    for (tapelen = MINTAPELEN; tapelen <= MAXTAPELEN; tapelen++) {
+        /* make the tape */
+        memset(tape, 0, tapelen);
+        tape[0] = tape[tapelen-1] = (char) (unsigned char) 128;
+        lt = 0;
+        rt = tapelen - 1;
+        memcpy(otape, tape, tapelen);
+
+        /* then run */
+        lpi = rpi = lloss = rloss = 0;
+        for (step = 0; step < 100000 && lloss < 2 && rloss < 2; step++) {
+            /* run the left */
+            runStep(lprog, lloops.buf, &lpi, tape, otape, tapelen, &lt, 1, lpol, &lpstack, &lpmax);
+
+            /* and the right */
+            runStep(rprog, rloops.buf, &rpi, tape, otape, tapelen, &rt, -1, rpol, &rpstack, &rpmax);
+
+            /* commit the tape */
+            memcpy(tape, otape, tapelen);
+
+            /* check for loss conditions */
+            if (tape[0] == 0) {
+                lloss++;
+            } else {
+                lloss = 0;
+            }
+            if (lt < 0 || lt >= tapelen) {
+                fprintf(stderr, "Left ran off the tape (%d/%d)!\n", lt, tapelen);
+                lloss = 3;
+            }
+            if (tape[tapelen-1] == 0) {
+                rloss++;
+            } else {
+                rloss = 0;
+            }
+            if (rt < 0 || rt >= tapelen) {
+                fprintf(stderr, "Right ran off the tape (%d/%d)!\n", rt, tapelen);
+                rloss = 3;
+            }
+        }
+
+        /* now find the victor */
+        if (lloss > rloss) {
+            /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[2]);*/
+            printf(">");
+            rwins++;
+        } else if (rloss > lloss) {
+            /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[1]);*/
+            printf("<");
+            lwins++;
+        } else {
+            /*printf("%d/%d: Tie!\n", polarity, tapelen);*/
+            printf("X");
+        }
+    }
+
+    printf(" ");
+    }
+
+    printf("\n");
+
+    if (lwins > rwins) {
+        printf("%s wins\n\n", argv[1]);
+    } else if (rwins > lwins) {
+        printf("%s wins\n\n", argv[2]);
+    } else {
+        printf("Tie\n\n");
+    }
+    return rwins - lwins;
+}