#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;
}