Meander/Implementation

This is an implementation of Meander in C by User:Rdebath.

The code is a simple text file either on the command line (eg dropped onto the exe) or from the standard input. The final state is output on the standard output. Options "-x" and "-t" give more information about the run.

Characters other than the command characters are not put on the tape, but do take up space (leaving the cells at zero), newlines and tabs do the reasonable thing. UTF-8 continuation bytes and control characters are completely ignored.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CKS 80

struct tapechunk {
    char tape[CKS];
    struct tapechunk *next, *prev;
    int  chunk_id;
} *t = 0;

int full_trace = 0;
int use_hexdump = 0;

void dump_tape(void);
void hex_dump_tape(void);
void run_code(int dp);

int
main(int argc, char ** argv)
{
    int ch, pos, dp;
    struct tapechunk * tp;
    FILE * ifd;
    for(;;) {
        if (argc>1 && strcmp(argv[1], "-t") == 0) {
            full_trace = 1; argc--; argv++;
        } else if (argc>1 && strcmp(argv[1], "-x") == 0) {
            use_hexdump = 1; argc--; argv++;
        } else if (argc>1 && strcmp(argv[1], "-h") == 0) {
            fprintf(stderr, "meander [options] [file]\n");
            fprintf(stderr, "-t  Full trace.\n");
            fprintf(stderr, "-x  Dump tape using hexadecimal.\n");
            exit(0);
        } else if (argc>1 && argv[1][0] == '-') {
            fprintf(stderr, "Unknown option %s\n", argv[1]);
            exit(1);
        } else break;
    }
    if (argc<=1)
        ifd = stdin;
    else if((ifd = fopen(argv[1],"r")) == 0) {
        perror(argv[1]); exit(1);
    }

    tp = t = calloc(1, sizeof*t);
    dp = pos = 0;

    while((ch = fgetc(ifd)) != EOF) {
        int v = 0;
        if (strchr("!-+?", ch)) {
            v = ch;
        } else if (ch == '\n') {
            pos += CKS; pos -= pos % CKS + 1;
        } else if (ch == '\t') {
            pos += 8; pos -= pos % 8 + 1;
        } else if (ch < ' ' || (ch&0xC0) == 0x80) {
            continue;
        }
        tp->tape[pos % CKS] = v;
        pos++;
        if(v) dp = pos;
        if (pos % CKS == 0) {
            tp->next = calloc(1, sizeof*tp);
            if (tp->next == 0) { perror("Tape allocation"); exit(1); }
            tp->next->chunk_id = tp->chunk_id + 1;
            tp->next->prev = tp;
            tp = tp->next;
        }
    }

    if (ifd != stdin) fclose(ifd);

    if (full_trace) {
        printf("Before Run ...\n");
        if (use_hexdump) hex_dump_tape(); else dump_tape();
    }
    run_code(dp);

    if (full_trace)
        printf("After Run ...\n");
    if (use_hexdump) hex_dump_tape(); else dump_tape();

    return 0;
}

void
dump_tape(void)
{
    struct tapechunk * tp = t;
    while(tp) {
        int i, j;
        for(i=j=0; i<CKS; i++) {
            if (tp->tape[i] == 0) continue;
            while(j<i) {
                putchar(' ');
                j++;
            }
            if (tp->tape[i] >= ' ' && tp->tape[i] <= '~') {
                putchar(tp->tape[i]);
            } else
                putchar('.');
            j++;
        }
        if(tp->next || j)
            putchar('\n');
        tp=tp->next;
    }
}

void
hex_output(FILE * ofd, int ch)
{
static char linebuf[80];
static char buf[20];
static int pos = 0, addr = 0;

    if( ch == EOF ) {
        if(pos)
            fprintf(ofd, "%06x:  %.66s\n", addr, linebuf);
        pos = 0;
        addr = 0;
    } else {
        if(!pos)
            memset(linebuf, ' ', sizeof(linebuf));
        sprintf(buf, "%02x", ch&0xFF);
        memcpy(linebuf+pos*3+(pos>7), buf, 2);

        if( ch > ' ' && ch <= '~' )
                linebuf[50+pos] = ch;
        else    linebuf[50+pos] = '.';
        pos = ((pos+1) & 0xF);
        if( pos == 0 ) {
            fprintf(ofd, "%06x:  %.66s\n", addr, linebuf);
            addr += 16;
        }
    }
}

void
hex_dump_tape(void)
{
    struct tapechunk * tp = t;
    while(tp) {
        int i;
        for(i=0; i<CKS; i++)
            hex_output(stdout, tp->tape[i]);
        tp=tp->next;
    }
}

void run_code(int dp)
{
static int ip_step[8] = {1, 81, 80, 79, -1, -81, -80, -79 };
static int dp_step[4] = {1, 80, -1, -80 };

    struct tapechunk *pc=t, *dc=t;
    int ip = 0;
    int ip_dir = 0;
    int dp_dir = 0;

    while (dp >= CKS) { dp -= CKS; dc = dc->next; }

    while(pc) {
        if (full_trace) {
            static int stepno = 0;
            printf("Step %d, ip = %d[%d] (%d,%d), dp = %d[%d] (%d,%d), inst(%d), data(%d)\n",
                ++stepno,
                pc->chunk_id*CKS+ip, ip_dir,
                pc->chunk_id,ip,
                dc->chunk_id*CKS+dp, dp_dir,
                dc->chunk_id,dp,
                pc->tape[ip],
                dc->tape[dp]);
        }
        switch(pc->tape[ip]) {
        case '!': ip_dir = ((ip_dir + 1) & 7); break;
        case '-': dp_dir = ((dp_dir + 1) & 3); break;
        case '+':
            dc->tape[dp] ++;
            dp = dp + dp_step[dp_dir];
            while (dp < 0) {
                if (dc->prev == 0) {
                    dc->prev = calloc(1, sizeof*dc);
                    if (dc->prev == 0) { perror("Tape allocation"); exit(1); }
                    dc->prev->chunk_id = dc->chunk_id - 1;
                    dc->prev->next = dc;
                }
                dp += CKS;
                dc = dc->prev;
            }
            while (dp >= CKS) {
                if (dc->next == 0) {
                    dc->next = calloc(1, sizeof*dc);
                    if (dc->next == 0) { perror("Tape allocation"); exit(1); }
                    dc->next->chunk_id = dc->chunk_id + 1;
                    dc->next->prev = dc;
                }
                dp -= CKS;
                dc=dc->next;
            }
            break;
        case '?':
            if (dc->tape[dp])
                ip_dir = ((ip_dir + 6) & 7);
            else
                ip_dir = ((ip_dir + 2) & 7);
            break;
        }
        ip = ip + ip_step[ip_dir];
        while (ip < 0 && pc) { ip += CKS; pc=pc->prev; }
        while (ip >= CKS && pc) { ip -= CKS; pc=pc->next; }

    }
}