6
\$\begingroup\$

I wrote simple compiler for Brainfuck with tcc backend (dont ask for assembler/assembly code generator!). It's output runs incredibly slow. Even Hello World program takes a LOOONG while to execute. I have added some optimizations, but it didnt help. This is code i actually made; It actually doesn't hang, but output work VERY slow (i need to wait ~4 minutes to Hello World display...):

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

int minus(FILE* f){
    int c;
    int amount = 0;
    while ((c = getc(f)) == '-')
        amount++;
    ungetc(c, f);
    return amount;
}

int plus(FILE* f){
    int c;
    int amount = 0;
    while ((c = getc(f)) == '+')
        amount++;
    ungetc(c, f);
    return amount;
}

int main(int argc, char** argv){
    int pos = 0;
    int brackets = 0;
    if(argc!=3){
        printf("Brainfuck Compiler by Joel.\n");
        printf("Cannot open input file.");
        exit(0);
    }
    int amount = 1;
    FILE* f = fopen(argv[1], "r");
    printf("Brainfuck Compiler by Joel. All rights reserved.\n");
    if(f!=NULL){
        char* outbuffer = (char*)malloc(1024*1024);
        strcpy(outbuffer, "int getch(void);\nvoid putch(int);\nint mem[65537];\nint main(){\n");
        while(!feof(f)){
            char c = fgetc(f);
            if(c == '<'){
                if(pos==0)pos=65536;
                else pos--;
            }
            if(c == '>'){
                if(pos==65536)pos=0;
                else pos++;
            }
            if(c == '['){
                brackets++;
                sprintf(outbuffer, "%swhile(mem[%d]){",outbuffer,pos);
            }
            if(c == ']'){
                brackets--;
                sprintf(outbuffer, "%s}", outbuffer);
            }
            if(c == '+'){
                amount = plus(f)+1;
                sprintf(outbuffer, "%smem[%d]+=%d;",outbuffer, pos, amount);
            }
            if(c == '-'){
                amount = minus(f)+1;
                sprintf(outbuffer, "%smem[%d]-=%d;",outbuffer, pos, amount);
            }
            if(c == '.'){
                sprintf(outbuffer, "%sputch(mem[%d]);",outbuffer, pos);
            }
            if(c == '.'){
                sprintf(outbuffer, "%smem[%d]=getch();",outbuffer, pos);
            }
        }
        if(brackets == 0){
            sprintf(outbuffer, "%sreturn 0;\n}\n",outbuffer);
            printf("Translation Succesful. ");
            compile(argv[2], outbuffer);
            free(outbuffer);
        }
        else{
            printf("Comilation fault. Unbalanced brackets.");
            free(outbuffer);
        }
    }
    else{
        printf("Cannot open one of specified files.");
    }
}

I don't think it's optimal code, and i need to "optimize" output somewhat. I have generated assembly listing here (shown with output c code): link. I cant find solution, why its so SLOW. Can anyone help me?

\$\endgroup\$
7
\$\begingroup\$

First off, your code does not compile, because (at least my just installed) libtcc does not contain a compile function.

As far as I can see it, your code is that slow because you emit a getch() and a putch() when you run across a . (as a side note: according to MSDN, the correct signature for the latter is int putch(int) and both getch() and putch() are deprecated. For portability, you should use int getchar(void) and int putchar(int) anyway).

You must always check the return value of malloc calls, because an allocation request can fail.

You should use a switch instead of multiple if statements for handling the characters, like in the following:

switch (c) {
case '<':
    /* Do work */
    break;
case '>':
    /* Do work */
    break;
case '[':
    /* Do work */
    break;
case ']':
    /* Do work */
    break;
case '+':
    /* Do work */
    break;
case '-':
    /* Do work */
    break;
case '.':
    /* Do work */
    break;
case ',':
    /* Do work */
    break;
default:
    /* Comment */
    break;
}

The advantages are that the intention is more obvious, the compiler may be able to generate better code and it prints an error if you try to handle a character twice.

The main function should always return a value and that value should allow the user to distinguish between a successful compiler run and an error. So you should add a return 0; to the end of the function and add a return 1; (or whatever nonzero value you like) at the end of every error path.

You should always close files you have opened.

Error messages should be printed to stderr, not stdout.

For protection against buffer overflows, you can use snprintf (which is available since C99) instead of sprintf. It returns either a negative value (if an error occurred) or the number of written bytes (excluding the \0 terminator), but it does not write more than size bytes (including the \0 terminator) to the output. Thus you can use

int ret = snprintf(outbuffer, 1024*1024, format, ...);
if (ret < 0 || ret >= 1024*1024) {
    /* Error or overflow */
    free(outbuffer);
    return 1;
}

Another thing you may want to consider is to reduce the memory size by one byte (thus every allowed pos value uses only 16 bits) and then replace

if (pos == 0) pos = 65536;
else pos--;

by

pos = (pos - 1) & 0xFFFF;

and

if (pos == 65536) pos = 0;
else pos++;

by

pos = (pos + 1) & 0xFFFF;

and thus make those two operations branchless. The effect of those two statements is that the operation is carried out on the pos variable, but only the lower 16 bits of the result are used (that is, 65535+1 becomes zero and 0-1 becomes 65535 (*)).

Putting all this together, you would have (including a compile function that can indicate an error and ):

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

static int compile(char const *out, char const *buf) {
    TCCState *tcc = tcc_new();
    if (tcc_set_output_type(tcc, TCC_OUTPUT_EXE) < 0) {
        fprintf(stderr, "Internal compiler error.\n");
        tcc_delete(tcc);
        return 1;
    }
    if (tcc_compile_string(tcc, buf) < 0) {
        fprintf(stderr, "Failed compiling generated code.\n");
        tcc_delete(tcc);
        return 1;
    }
    if (tcc_add_library(tcc, "c") < 0) {
        fprintf(stderr, "Failed linking in C library.\n");
        tcc_delete(tcc);
        return 1;
    }
    if (tcc_output_file(tcc, out) < 0) {
        fprintf(stderr, "Failed writing program to file.\n");
        tcc_delete(tcc);
        return 1;
    }
    tcc_delete(tcc);
    return 0;
}

int minus(FILE* f){
    int c;
    int amount = 0;
    while ((c = getc(f)) == '-')
        amount++;
    ungetc(c, f);
    return amount;
}

int plus(FILE* f){
    int c;
    int amount = 0;
    while ((c = getc(f)) == '+')
        amount++;
    ungetc(c, f);
    return amount;
}

int main(int argc, char** argv){
    static int const buflen = 1024*1024;
    int pos = 0;
    int brackets = 0;
    fprintf(stderr, "Brainfuck Compiler by Joel. All rights reserved.\n");
    if(argc!=3){
        fprintf(stderr, "Usage: %s <input> <output>", argv[0]);
        return 1;
    }
    int amount = 0;
    int ret;
    FILE* f = fopen(argv[1], "r");
    if(f!=NULL){
        char* outbuffer = (char*)malloc(buflen);
        if (outbuffer == NULL) {
            fprintf(stderr, "Internal compiler error.\n");
            fclose(f);
            return 1;
        }
        ret = snprintf(outbuffer, buflen, "int getchar(void);\nint putchar(int);\nint mem[65536] = {0};\nint main(){\n");
        if (ret < 0 || ret >= buflen) {
            fprintf(stderr, "Internal compiler error.\n");
            free(outbuffer);
            fclose(f);
            return 1;
        }
        while(!feof(f)){
            switch (fgetc(f)) {
            case '<':
                pos = (pos - 1) & 0xFFFF;
                break;
            case '>':
                pos = (pos + 1) & 0xFFFF;
                break;
            case '[':
                ++brackets;
                ret = snprintf(outbuffer, buflen, "%swhile(mem[%d]){", outbuffer, pos);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }           
                break;
            case ']':
                --brackets;
                ret = snprintf(outbuffer, buflen, "%s}", outbuffer);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }
                break;
            case '+':
                amount = plus(f)+1;
                ret = snprintf(outbuffer, buflen, "%smem[%d]+=%d;", outbuffer, pos, amount);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }
                break;
            case '-':
                amount = minus(f)+1;
                ret = snprintf(outbuffer, buflen, "%smem[%d]-=%d;", outbuffer, pos, amount);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }
                break;
            case '.':
                ret = snprintf(outbuffer, buflen, "%sputchar(mem[%d]);", outbuffer, pos);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }
                break;
            case ',':
                ret = snprintf(outbuffer, buflen, "%smem[%d]=getchar();", outbuffer, pos);
                if (ret < 0 || ret >= buflen) {
                    fprintf(stderr, "Internal compiler error.\n");
                    free(outbuffer);
                    fclose(f);
                    return 1;
                }
                break;
            default:
                break;
            }
        }
        fclose(f);
        if(brackets == 0){
            ret = snprintf(outbuffer, buflen, "%sreturn 0;\n}\n",outbuffer);
            if (ret < 0 || ret >= buflen) {
                fprintf(stderr, "Internal compiler error.\n");
                free(outbuffer);
                fclose(f);
                return 1;
            }
            if (compile(argv[2], outbuffer)) {
                free(outbuffer);
                return 1;
            }
            free(outbuffer);
        }
        else{
            fprintf(stderr, "Compilation fault. Unbalanced brackets.\n");
            free(outbuffer);
            return 1;
        }
    }
    else{
        fprintf(stderr, "Cannot open one of specified files.\n");
        return 1;
    }
    return 0;
}

(*) This is only true for systems representing signed integers using two's complement, where (using signed 16 bit integers) -1 equals 0xFFFF. When using one's complement representation, -1 equals 0xFFFE (with 0xFFFF being -0), but practically every machine commonly available today uses two's complement for representing signed integers.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ There's a lot of duplicated code in your final code, with the ret check. Why do it this way and not by a function call or at least a check outside of the switch-statement? \$\endgroup\$ – JHBonarius Nov 19 '17 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.