brainfuck/bf.c

/*
 * bf.c
 * https://gitlab.com/bztsrc/brainfuck
 *
 * Copyright (C) 2021 bzt (bztsrc@gitlab)
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 * @brief Brainfuck interpreter and compiler
 *
 */

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

/* bytecode */
#define IMM 0x80
/* tokens that can occur in scripts */
#define INC 0x00    /* > ptr++; */
#define DEC 0x10    /* < ptr--; */
#define ADD 0x20    /* + (*ptr)++; */
#define SUB 0x30    /* - (*ptr)--; */
#define JZ  0x40    /* [ while(*ptr) { */
#define JNZ 0x50    /* ] } */
#define PUT 0x60    /* . putchar(*ptr); */
#define GET 0x70    /* , *ptr = getchar(); */
/* tokens generated by the optimizer */
#define ZRO 0xF0    /* [-] */
#define FFZ 0xF1    /* [>] */
#define FLZ 0xF2    /* [<] */
#define MVD 0xF3    /* [-<+>] */
#define MVU 0xF4    /* [->+<] */

#define MAXNEST 256

/***************************
 * Main Brainfuck function *
 ***************************/
int main(int argc, char **argv)
{
    void *end;
    char **arg = argv, *inp = NULL, *out = NULL, *src = NULL, *tmp = NULL, *c, *il, cell = 'b';
    unsigned char *tokens = NULL, *datab = NULL, *db, bytecode[4], *b;
    unsigned short *dataw = NULL, *dw;
    unsigned int *params = NULL, *datad = NULL, *dd;
    int i, profiling = 0, mode = 0, memory = 32768, opt = 3, tsize = 0, size, nl, nest, jmp[MAXNEST];
    long int tim = 0, tim2 = 0;
    struct timeval tv;
    FILE *f;

    /* parse arguments */
    if(argc < 2) {
usage:  printf("BrainFuck by bzt Copyright (C) 2021 MIT license\n\n"
            "%s [-p] [-O[01234]] [-m<size>] [-w|-d] <bf source> [-b|-c|-s|-o] [out]\n\n"
            "  -p   turn on profiling\n"
            "  -O   optimization level\n"
            "  -m   set program memory size\n"
            "  -w   use word cells (16 bit)\n"
            "  -d   use dword cells (32 bit)\n"
            "  -b   output bytecode\n"
            "  -c   output C source\n"
            "  -s   output x86_64 assembly\n"
            "  -o   output ELF binary\n"
            "\n", argv[0]);
        exit(0);
    }
    while(arg && *arg) {
        arg++;
        if(!arg || !*arg) break;
        if(arg[0][0] == '-')
            switch(arg[0][1]) {
                case 'p': profiling++; break;
                case 'b': mode = 1; break;
                case 'c': mode = 2; break;
                case 's': mode = 3; break;
                case 'o': mode = 4; break;
                case 'O': opt = atoi(arg[0] + 2); break;
                case 'm': memory = atoi(arg[0] + 2); break;
                case 'w': cell = 'w'; break;
                case 'd': cell = 'l'; break;
                default: fprintf(stderr, "bf: unknown flag '%c'\n", arg[0][1]); exit(1); break;
            }
        else if(!inp) inp = arg[0];
        else out = arg[0];
    }
    if(!inp) {
        fprintf(stderr, "bf: no input file specified.\n");
        goto usage;
    }
    if(memory < 256) memory = 256;
    if(memory > 0xFFFFFF) memory = 0xFFFFFF;

    /* read input */
    f = fopen(inp, "r");
    if(f) {
        fseek(f, 0, SEEK_END);
        size = (int)ftell(f);
        if(size < 1) { fclose(f); goto err; }
        fseek(f, 0, SEEK_SET);
        src = (char*)malloc(size+1);
        if(!src) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", size+1); exit(2); }
        fread(src, size, 1, f);
        fclose(f);
        src[size] = 0;
    } else {
err:    fprintf(stderr, "bf: unable to read '%s'\n", inp);
        exit(1);
    }
    if(profiling) {
        gettimeofday(&tv, NULL);
        tim = (long int)(tv.tv_sec * 1000000L + tv.tv_usec);
    }

    /* tokenize (or read back bytecode) */
    if(src[0] == 'B' && src[1] == 'C') {
        tsize = size;
    } else {
        /* quickly count the number of valid instructions */
        for(tsize = 0, c = src; c < src + size; c++)
            switch(*c) {
                case '<': case '>': case '+': case '-': case '[': case ']': case '.': case ',': tsize++; break;
            }
    }
    if(tsize > 0xFFFFF) { fprintf(stderr, "bf: %s: too many instructions\n", inp); exit(1); }
    tokens = (unsigned char*)malloc(tsize);
    if(!tokens) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", tsize); exit(2); }
    params = (unsigned int*)malloc(tsize * sizeof(unsigned int));
    if(!params) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", tsize * (int)sizeof(unsigned int)); exit(2); }
    memset(params, 0, tsize * sizeof(unsigned int));
    if(src[0] == 'B' && src[1] == 'C') {
        /* bytecode */
        for(b = (unsigned char*)src + 2, i = 0; b < (unsigned char*)src + size && i < tsize; i++, b++) {
            tokens[i] = *b & 0x70;
            if((*b & 0xF0) == 0xF0) {
                tokens[i] = *b & 0xF7;
                if(tokens[i] != ZRO) {
                    if(*b & 0x08) {
                        params[i] = (unsigned int)((*(b + 1) << 16) | (*(b + 2) << 8) | *(b + 3));
                        b += 3;
                    } else {
                        params[i] = (unsigned int)((*(b + 1) << 8) | *(b + 2));
                        b += 2;
                    }
                }
            } else {
                    if(*b & IMM) {
                        params[i] = (unsigned int)(((*b & 0x0F) << 16) | (*(b + 1) << 8) | *(b + 2));
                        b += 2;
                    } else {
                        params[i] = (unsigned int)(*b & 0x0F);
                    }
            }
        }
    } else {
        /* plain text */
        for(c = il = src, i = nest = 0, nl = 1; c < src + size && i < tsize; ) {
            switch(*c) {
                case '<':
                    do { params[i]++; c++; } while(opt && *c == '<');
                    tokens[i++] = DEC;
                    break;
                case '>':
                    do { params[i]++; c++; } while(opt && *c == '>');
                    tokens[i++] = INC;
                    break;
                case '+':
                    do { params[i]++; c++; } while(opt && *c == '+');
                    tokens[i++] = ADD;
                    break;
                case '-':
                    do { params[i]++; c++; } while(opt && *c == '-');
                    tokens[i++] = SUB;
                    break;
                case '[':
                    if(nest + 1 >= MAXNEST) {
                        fprintf(stderr, "%s:%d:%d: maximum nesting level reached\n", inp, nl, (int)(c - il + 1));
                        exit(1);
                    }
                    jmp[nest++] = i;
                    tokens[i++] = JZ;
                    c++;
                    break;
                case ']':
                    if(nest < 1) {
                        fprintf(stderr, "%s:%d:%d: ] without opening [\n", inp, nl, (int)(c - il + 1));
                        exit(1);
                    }
                    nest--;
                    /* optimize bytecode */
                    if(opt > 1 && i && tokens[i - 1] == JZ) {
                        i--;
                    } else
                    if(opt > 1 && i > 1 && tokens[i - 1] == SUB && tokens[i - 2] == JZ && params[i - 1] == 1) {
                        i--;
                        tokens[i - 1] = ZRO;
                        params[i - 1] = params[i] = 0;
                    } else
                    if(opt > 2 && i > 1 && tokens[i - 1] == INC && tokens[i - 2] == JZ) {
                        i--;
                        tokens[i - 1] = FFZ;
                        params[i - 1] = params[i];
                        params[i] = params[i + 1] = 0;
                    } else
                    if(opt > 2 && i > 1 && tokens[i - 1] == DEC && tokens[i - 2] == JZ) {
                        i--;
                        tokens[i - 1] = FLZ;
                        params[i - 1] = params[i];
                        params[i] = params[i + 1] = 0;
                    } else
                    if(opt > 2 && i > 4 && tokens[i - 1] == INC && tokens[i - 2] == ADD && tokens[i - 3] == DEC &&
                        tokens[i - 4] == SUB && tokens[i - 5] == JZ && params[i - 1] == params[i - 3] &&
                        params[i - 2] == 1 && params[i - 4] == 1) {
                        i -= 4;
                        tokens[i - 1] = MVD;
                        params[i - 1] = params[i + 1];
                        params[i] = params[i + 1] = params[i + 2] = params[i + 3] = 0;
                    } else
                    if(opt > 2 && i > 4 && tokens[i - 1] == DEC && tokens[i - 2] == ADD && tokens[i - 3] == INC &&
                        tokens[i - 4] == SUB && tokens[i - 5] == JZ && params[i - 1] == params[i - 3] &&
                        params[i - 2] == 1 && params[i - 4] == 1) {
                        i -= 4;
                        tokens[i - 1] = MVU;
                        params[i - 1] = params[i + 1];
                        params[i] = params[i + 1] = params[i + 2] = params[i + 3] = 0;
                    } else {
                        params[i] = jmp[nest];
                        params[jmp[nest]] = i;
                        tokens[i++] = JNZ;
                    }
                    c++;
                    break;
                case '.':
                    tokens[i++] = PUT; c++;
                    break;
                case ',':
                    tokens[i++] = GET; c++;
                    break;
                case '\n':
                    nl++; c++; il = c;
                    break;
                default: c++; break;
            }
        }
        if(nest > 0) {
            fprintf(stderr, "%s:%d:%d: unclosed [\n", inp, nl, (int)(c - il + 1));
            exit(1);
        }
    }
    free(src);
    tsize = i;
    if(tsize < 1) goto err;

    if(profiling) {
        gettimeofday(&tv, NULL);
        tim2 = (long int)(tv.tv_sec * 1000000L + tv.tv_usec);
        tim = tim2 - tim;
        fprintf(stderr, "Optimizer:    %3ld.%06ld sec\n", tim / 1000000L, tim % 1000000L);
    }

    /* do the stuff */
    if(out) {
        f = fopen(out, "w");
        if(!f) {
            fprintf(stderr, "bf: unable to write '%s'\n", out);
            exit(1);
        }
    } else {
        if(mode == 1 || mode == 4) {
            fprintf(stderr, "bf: no output specified.\n");
            exit(1);
        }
        f = stdout;
    }

    switch(mode) {
    case 0:
        /* interpret bytecode */
        switch(cell) {
            /* byte cells (8 bit) */
            case 'b':
                datab = (unsigned char*)malloc(memory);
                if(!datab) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", memory); exit(2); }
                memset(datab, 0, memory);
                for(i = 0, db = datab, end = datab + memory; i < tsize; i++) {
                    switch(tokens[i]) {
                        case INC:
                            db += params[i];
                            if((void*)db >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case DEC:
                            db -= params[i];
                            if(db < datab) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case ADD: (*db) += (unsigned char)params[i]; break;
                        case SUB: (*db) -= (unsigned char)params[i]; break;
                        case JZ: if(!*db) i = params[i]; break;
                        case JNZ: if(*db) i = params[i]; break;
                        case PUT: putchar(*db); break;
                        case GET:
                            *db = getchar();
                            if(*db == 27) i = tsize;
                            break;
                        case ZRO: *db = 0; break;
                        case FFZ:
                            while(*db) {
                                db += params[i];
                                if((void*)db >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case FLZ:
                            while(*db) {
                                db -= params[i];
                                if(db < datab) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case MVD:
                            if(*db) {
                                if((db - params[i]) < datab) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(db - params[i]) += *db; *db = 0;
                            }
                            break;
                        case MVU:
                            if(*db) {
                                if((void*)(db + params[i]) >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(db + params[i]) += *db; *db = 0;
                            }
                            break;
                    }
                }
                free(datab);
                break;
            /* word cells (16 bit) */
            case 'w':
                dataw = (unsigned short*)malloc(memory * sizeof(unsigned short));
                if(!dataw) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", memory * (int)sizeof(unsigned short)); exit(2); }
                memset(dataw, 0, memory * sizeof(unsigned short));
                for(i = 0, dw = dataw, end = dataw + memory; i < tsize; i++) {
                    switch(tokens[i]) {
                        case INC:
                            dw += params[i];
                            if((void*)dw >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case DEC:
                            dw -= params[i];
                            if(dw < dataw) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case ADD: (*dw) += (unsigned short)params[i]; break;
                        case SUB: (*dw) -= (unsigned short)params[i]; break;
                        case JZ:  if(!*dw) i = params[i]; break;
                        case JNZ: if(*dw) i = params[i]; break;
                        case PUT: putchar((unsigned char)*dw); break;
                        case GET:
                            *dw = (unsigned short)getchar();
                            if(*dw == 27) i = tsize;
                            break;
                        case ZRO: *dw = 0; break;
                        case FFZ:
                            while(*dw) {
                                dw += params[i];
                                if((void*)dw >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case FLZ:
                            while(*dw) {
                                dw -= params[i];
                                if(dw < dataw) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case MVD:
                            if(*dw) {
                                if((dw - params[i]) < dataw) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(dw - params[i]) += *dw; *dw = 0;
                            }
                            break;
                        case MVU:
                            if(*dw) {
                                if((void*)(dw + params[i]) >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(dw + params[i]) += *dw; *dw = 0;
                            }
                            break;
                    }
                }
                free(dataw);
                break;
            /* dword cells (32 bit) */
            case 'l':
                datad = (unsigned int*)malloc(memory * sizeof(unsigned int));
                if(!datad) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", memory * (int)sizeof(unsigned int)); exit(2); }
                memset(datad, 0, memory * sizeof(unsigned int));
                for(i = 0, dd = datad, end = datad + memory; i < tsize; i++) {
                    switch(tokens[i]) {
                        case INC:
                            dd += params[i];
                            if((void*)dd >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case DEC:
                            dd -= params[i];
                            if(dd < datad) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            break;
                        case ADD: (*dd) += params[i]; break;
                        case SUB: (*dd) -= params[i]; break;
                        case JZ:  if(!*dd) i = params[i]; break;
                        case JNZ: if(*dd) i = params[i]; break;
                        case PUT: putchar((unsigned char)*dd); break;
                        case GET:
                            *dd = (unsigned int)getchar();
                            if(*dd == 27) i = tsize;
                            break;
                        case ZRO: *dd = 0; break;
                        case FFZ:
                            while(*dd) {
                                dd += params[i];
                                if((void*)dd >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case FLZ:
                            while(*dd) {
                                dd -= params[i];
                                if(dd < datad) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                            }
                            break;
                        case MVD:
                            if(*dd) {
                                if((dd - params[i]) < datad) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(dd - params[i]) += *dd; *dd = 0;
                            }
                            break;
                        case MVU:
                            if(*dd) {
                                if((void*)(dd + params[i]) >= end) { fprintf(stderr, "bf: out of bound addressing\n"); exit(2); }
                                *(dd + params[i]) += *dd; *dd = 0;
                            }
                            break;
                    }
                }
                free(datad);
                break;
        }
        break;
    case 1:
        /* output bytecode */
        fwrite("BC", 2, 1, f);
        for(i = 0; i < tsize; i++) {
            bytecode[0] = tokens[i];
            switch(tokens[i]) {
                /* tokens generated by the optimizer */
                case ZRO:
                    fwrite(bytecode, 1, 1, f);
                    break;
                case FFZ: case FLZ: case MVD: case MVU:
                    if(params[i] > 0xFFFF) {
                        bytecode[0] |= 0x08;
                        bytecode[1] = (params[i] >> 16) & 0xFF;
                        bytecode[2] = (params[i] >> 8) & 0xFF;
                        bytecode[3] = params[i] & 0xFF;
                        fwrite(bytecode, 4, 1, f);
                    } else {
                        bytecode[1] = (params[i] >> 8) & 0xFF;
                        bytecode[2] = params[i] & 0xFF;
                        fwrite(bytecode, 3, 1, f);
                    }
                    break;
                /* normal tokens in the script */
                default:
                    if(params[i] < 16) {
                        bytecode[0] |= params[i];
                        fwrite(bytecode, 1, 1, f);
                    } else {
                        bytecode[0] |= IMM | ((params[i] >> 16) & 0x0F);
                        bytecode[1] = (params[i] >> 8) & 0xFF;
                        bytecode[2] = params[i] & 0xFF;
                        fwrite(bytecode, 3, 1, f);
                    }
                    break;
            }
        }
        break;
    case 2:
        /* output C */
        fprintf(f, "/* BrainFuck compiled ANSI C */\n\n"
            "#include <stdio.h>\n");
        if(profiling)
            fprintf(f, "#include <string.h>\n#include <sys/time.h>\n");

        fprintf(f, "\nint main(int argc, char **argv)\n{\n"
            "    unsigned %s data[%d], *ptr = data;\n", cell == 'l' ? "int" : (cell == 'w' ? "short" : "char"), memory);
        if(profiling)
            fprintf(f, "    long int tim = 0;\n    struct timeval tv;\n\n"
                    "    gettimeofday(&tv, NULL);\n    tim = (long int)(tv.tv_sec * 1000000L + tv.tv_usec);\n");
        fprintf(f, "\n");
        for(i = nest = 0; i < tsize; i++) {
            if(tokens[i] == JNZ) nest--;
            for(nl = 0; nl < nest + 1; nl++)
                fprintf(f, "    ");
            switch(tokens[i]) {
                case INC:
                    if(params[i] == 1) fprintf(f, "ptr++;");
                    else fprintf(f, "ptr += %d;", params[i]);
                    if(opt < 4)
                        fprintf(f, " if(ptr >= data + %d) goto end;", memory);
                    fprintf(f, "\n");
                    break;
                case DEC:
                    if(params[i] == 1) fprintf(f, "ptr--;");
                    else fprintf(f, "ptr -= %d;", params[i]);
                    if(opt < 4)
                        fprintf(f, " if(ptr < data) goto end;");
                    fprintf(f, "\n");
                    break;
                case ADD:
                    if(params[i] == 1) fprintf(f, "(*ptr)++;\n");
                    else fprintf(f, "(*ptr) += %d;\n", params[i]);
                    break;
                case SUB:
                    if(params[i] == 1) fprintf(f, "(*ptr)--;\n");
                    else fprintf(f, "(*ptr) -= %d;\n", params[i]);
                    break;
                case JZ:
                    fprintf(f, "while(*ptr) {\n");
                    nest++;
                    break;
                case JNZ:
                    fprintf(f, "}\n");
                    break;
                case PUT:
                    fprintf(f, "putchar((unsigned char)*ptr);\n");
                    break;
                case GET:
                    fprintf(f, "*ptr = (unsigned %s)getchar(); if(*ptr == 27) goto end;\n",
                        cell == 'l' ? "int" : (cell == 'w' ? "short" : "char"));
                    break;
                case ZRO:
                    fprintf(f, "*ptr = 0;\n");
                    break;
                case FFZ:
                    fprintf(f, "while(*ptr) { ptr += %d; ", params[i]);
                    if(opt < 4)
                        fprintf(f, "if(ptr >= data + %d) { goto end; } ", memory);
                    fprintf(f, "}\n");
                    break;
                case FLZ:
                    fprintf(f, "while(*ptr) { ptr -= %d; ", params[i]);
                    if(opt < 4)
                        fprintf(f, "if(ptr < data) { goto end; } ");
                    fprintf(f, "}\n");
                    break;
                case MVD:
                    fprintf(f, "if(*ptr) { ");
                    if(opt < 4)
                        fprintf(f, "if(ptr - %d < data) { goto end; } ", params[i]);
                    fprintf(f, "*(ptr - %d) += *ptr; *ptr = 0; }\n", params[i]);
                    break;
                case MVU:
                    fprintf(f, "if(*ptr) { ");
                    if(opt < 4)
                        fprintf(f, "if(ptr + %d >= data + %d) { goto end; } ", params[i], memory);
                    fprintf(f, "*(ptr + %d) += *ptr; *ptr = 0; }\n", params[i]);
                    break;
            }
        }
        fprintf(f, "\nend:");
        if(profiling)
            fprintf(f, "gettimeofday(&tv, NULL);\n"
                "    tim = (long int)(tv.tv_sec * 1000000L + tv.tv_usec) - tim;\n"
                "    fprintf(stderr, \"Execution:    %%3ld.%%06ld sec\\n\", tim / 1000000L, tim %% 1000000L);\n    ");
        fprintf(f, "return 0;\n}\n");
        break;
    case 3:
    case 4:
        if(mode == 4) {
            if(f != stdout) fclose(f);
            tmp = (char*)malloc(16 + strlen(out));
            if(!tmp) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", 4 + (int)strlen(out)); exit(2); }
            sprintf(tmp, "%s.s", out);
            f = fopen(tmp, "w");
            if(!f) {
                fprintf(stderr, "bf: unable to create temporary file '%s'\n", tmp);
                exit(2);
            }
        }
        /* output assembly */
        fprintf(f, "/* BrainFuck compiled native instructions */\n\n"
            ".globl %s\n.type %s, @function\n\n", mode == 4 ? "_start" : "main", mode == 4 ? "_start" : "main");
        if(profiling)
            fprintf(f, ".section .rodata\nstr:    .string \"Execution:    %%3ld.%%06ld sec\\n\"\n\n");
        fprintf(f, ".text\n%s:\n"
            "        pushq %%rbp\n"
            "        movq %%rsp, %%rbp\n"
            "        subq $%d, %%rsp\n"
            "        movq %%rsp, %%rbx\n", mode == 4 ? "_start" : "main",
                memory * (cell == 'l' ? 4 : (cell == 'w' ? 2 : 1)) + profiling * 32);
        if(profiling)
            fprintf(f,
                "        leaq -16(%%rbp), %%rdi\n"
                "        xorq %%rsi, %%rsi\n"
                "        call gettimeofday@PLT\n"
                "        movq -16(%%rbp), %%rax\n"
                "        xorq %%rdx, %%rdx\n"
                "        imulq $1000000, %%rax, %%rdx\n"
                "        movq -8(%%rbp), %%rax\n"
                "        addq %%rdx, %%rax\n"
                "        movq %%rax, -24(%%rbp)\n\n");
        /* use RBX as it is a callee saved GPR */
        for(i = 0; i < tsize; i++) {
            switch(tokens[i]) {
                case INC:
                    if(params[i] == 1) fprintf(f, "        incq %%rbx\n");
                    else fprintf(f, "        addq $%d, %%rbx\n", params[i]);
                    if(opt < 4)
                        fprintf(f,  "        cmpq %%rbx, %%rbp\n"
                                    "        jbe end\n");
                    break;
                case DEC:
                    if(params[i] == 1) fprintf(f, "        decq %%rbx\n");
                    else fprintf(f, "        subq $%d, %%rbx\n", params[i]);
                    if(opt < 4)
                        fprintf(f,  "        cmpq %%rbx, %%rsp\n"
                                    "        ja end\n");
                    break;
                case ADD:
                    if(params[i] == 1) fprintf(f, "        inc%c (%%rbx)\n", cell);
                    else fprintf(f, "        add%c $%d, (%%rbx)\n", cell, params[i]);
                    break;
                case SUB:
                    if(params[i] == 1) fprintf(f, "        dec%c (%%rbx)\n", cell);
                    else fprintf(f, "        sub%c $%d, (%%rbx)\n", cell, params[i]);
                    break;
                case JZ:
                    fprintf(f,  "        cmp%c $0, (%%rbx)\n"
                                "        jz .L%04X\n"
                                ".L%04X:\n", cell, params[i], i);
                    break;
                case JNZ:
                    fprintf(f,  "        cmp%c $0, (%%rbx)\n"
                                "        jnz .L%04X\n"
                                ".L%04X:\n", cell, params[i], i);
                    break;
                case PUT:
                    fprintf(f,  "        movz%cq (%%rbx), %%rdi\n"
                                "        call putchar@PLT\n", cell);
                    break;
                case GET:
                    fprintf(f,  "        call getchar@PLT\n"
                                "        cmpb $27, %%al\n"
                                "        je end\n"
                                "        mov%s %%al, (%%rbx)\n", cell == 'l' ? "zbl" : (cell == 'w' ? "zbw" : "b"));
                    break;
                case ZRO:
                    fprintf(f,  "        mov%c $0, (%%rbx)\n", cell);
                    break;
                case FFZ:
                    fprintf(f,  "1:      cmp%c $0, (%%rbx)\n"
                                "        jz 2f\n"
                                "        addq $%d, %%rbx\n", cell, params[i]);
                    if(opt < 4)
                        fprintf(f,  "        cmpq %%rbx, %%rbp\n"
                                    "        jbe end\n");
                    fprintf(f,  "        jmp 1b\n"
                                "2:\n");
                    break;
                case FLZ:
                    fprintf(f,  "1:      cmp%c $0, (%%rbx)\n"
                                "        jz 2f\n"
                                "        subq $%d, %%rbx\n", cell, params[i]);
                    if(opt < 4)
                        fprintf(f,  "        cmpq %%rbx, %%rsp\n"
                                    "        ja end\n");
                    fprintf(f,  "        jmp 1b\n"
                                "2:\n");
                    break;
                case MVD:
                    fprintf(f,  "        cmp%c $0, (%%rbx)\n"
                                "        jz 1f\n", cell);
                    if(opt < 4)
                        fprintf(f,  "        leaq -%d(%%rbx), %%rax\n"
                                    "        cmpq %%rax, %%rsp\n"
                                    "        ja end\n", params[i] * (cell == 'l' ? 4 : (cell == 'w' ? 2 : 1)));
                    fprintf(f,  "        mov%c (%%rbx), %%%s\n"
                                "        add%c %%%s, -%d(%%rbx)\n"
                                "        mov%c $0, (%%rbx)\n"
                                "1:\n", cell, cell == 'l' ? "eax" : (cell == 'w' ? "ax" : "al"),
                                cell, cell == 'l' ? "eax" : (cell == 'w' ? "ax" : "al"),
                                params[i] * (cell == 'l' ? 4 : (cell == 'w' ? 2 : 1)), cell);
                    break;
                case MVU:
                    fprintf(f,  "        cmp%c $0, (%%rbx)\n"
                                "        jz 1f\n", cell);
                    if(opt < 4)
                        fprintf(f,  "        leaq %d(%%rbx), %%rax\n"
                                    "        cmpq %%rax, %%rbp\n"
                                    "        jbe end\n", params[i] * (cell == 'l' ? 4 : (cell == 'w' ? 2 : 1)));
                    fprintf(f,  "        mov%c (%%rbx), %%%s\n"
                                "        add%c %%%s, %d(%%rbx)\n"
                                "        mov%c $0, (%%rbx)\n"
                                "1:\n", cell, cell == 'l' ? "eax" : (cell == 'w' ? "ax" : "al"),
                                cell, cell == 'l' ? "eax" : (cell == 'w' ? "ax" : "al"),
                                params[i] * (cell == 'l' ? 4 : (cell == 'w' ? 2 : 1)), cell);
                    break;
            }
        }
        fprintf(f, "\nend:\n");
        if(profiling)
            fprintf(f, "        leaq -16(%%rbp), %%rdi\n"
                "        xorq %%rsi, %%rsi\n"
                "        call gettimeofday@PLT\n"
                "        movq -16(%%rbp), %%rax\n"
                "        xorq %%rdx, %%rdx\n"
                "        imulq $1000000, %%rax, %%rdx\n"
                "        movq -8(%%rbp), %%rax\n"
                "        addq %%rdx, %%rax\n"
                "        subq -24(%%rbp), %%rax\n"
                "        xorq %%rdx, %%rdx\n"
                "        movq $1000000, %%rcx\n"
                "        idivq %%rcx\n"
                "        movq %%rdx,%%rcx\n"
                "        movq %%rax,%%rdx\n"
                "        leaq str(%%rip),%%rsi\n"
                "        movq stderr(%%rip),%%rdi\n"
                "        xorq %%rax,%%rax\n"
                "        call fprintf@PLT\n");
        fprintf(f, "        leave\n");
        if(mode == 4) {
            fprintf(f, "        xorq %%rdi, %%rdi\n        call exit@PLT\n");
            /* use "as" and "ld" from binutils to create ELF */
            fclose(f); f = stdout;
            src = (char*)malloc(128 + 2*strlen(out));
            if(!src) { fprintf(stderr, "bf: memory allocation error (%d bytes)\n", 128 + 2*(int)strlen(out)); exit(2); }
            sprintf(src, "as %s -o %s.o", tmp, out);
            if(system(src)) { fprintf(stderr, "bf: unable to execute '%s'\n", src); }
            else {
                sprintf(src, "ld --dynamic-linker /lib/ld-linux-x86-64.so.2 -lc %s.o -o %s", out, out);
                if(system(src)) {
                    sprintf(src, "ld --dynamic-linker /lib/ld-linux.so.2 -lc %s.o -o %s", out, out);
                    if(system(src)) { fprintf(stderr, "bf: unable to execute '%s'\n", src); }
                }
            }
            unlink(tmp);
            tmp[strlen(tmp)-1] = 'o';
            unlink(tmp);
            free(tmp);
            free(src);
        } else
            fprintf(f, "        ret\n");
        break;
    }
    if(profiling && !mode) {
        gettimeofday(&tv, NULL);
        tim = (long int)(tv.tv_sec * 1000000L + tv.tv_usec) - tim2;
        fprintf(stderr, "Execution:    %3ld.%06ld sec\n", tim / 1000000L, tim % 1000000L);
    }

    /* clean up */
    if(f != stdout) fclose(f);
    free(tokens);
    free(params);
    return 0;
}