7
\$\begingroup\$

See this post for the previous question. I have made several enhancements to this compiler and language that make it a lot easier to work with, as well as slightly decreasing executable size (if new features are used properly). I've decided to call the new language brainfix, as I don't think anyone has used this name before.

Here's the compiler:

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

void usage(const char *);
void compile_and_write(int);
void print_header(void);
void print_footer(void);

static FILE *in = NULL;
static FILE *out = NULL;

int main(int argc, char *argv[])
{
    int ch;
    int opt;

    while ((opt = getopt(argc, argv, "i:o:h")) != -1) {
        switch (opt) {
        case 'i':
            in = fopen(optarg, "r");
            break;
        case 'o':
            out = fopen(optarg, "w");
            break;
        case 'h':
            usage(argv[0]);
            return EXIT_SUCCESS;
        default:
            usage(argv[0]);
            return EXIT_FAILURE;
        }
    }

    in = in ? in : stdin;
    out = out ? out : stdout;

    print_header();

    while ((ch = fgetc(in)) != EOF) {
        compile_and_write(ch);
    }

    compile_and_write('\0');
    print_footer();

    fclose(in);
    fclose(out);
    return EXIT_SUCCESS;
}

void print_header(void)
{
    fputs("[bits 64]\n"
          "[section .bss]\n"
          "mem: resb 32768\n"
          "hld: resb 1\n"
          "[section .text]\n"
          "[global _start]\n"
          "putc:\n"
          "xor rax, rax\n"
          "xor rdi, rdi\n"
          "xor rdx, rdx\n"
          "inc rax\n"
          "inc rdi\n"
          "inc rdx\n"
          "syscall\n"
          "ret\n"

          "getc:\n"
          "xor rax, rax\n"
          "xor rdi, rdi\n"
          "xor rdx, rdx\n"
          "inc rdx\n"
          "syscall\n"
          "ret\n"

          "exit:\n"
          "mov rax, 60\n"
          "movzx rdi, byte [rsi]\n"
          "syscall\n"
          "ret\n"

          "_start:\n"
          "mov rsi, mem\n", out);
}

void print_footer(void)
{
    fputs("mov byte [rsi], 0\n"
          "call exit\n", out);
}

void compile_and_write(int ch)
{
    static int loop = 0;
    static int loops[0x10000] = { 0 };
    static size_t lp = 0;
    static unsigned cnt = 1;
    static int last = ' ';
    static unsigned call = 0;
    static int comment = 0;

    if (ch == '#') {
        comment = comment ? 0 : 1;
    }

    if (comment) {
        return;
    }

    if ((last == '>' && ch == '<') ||
        (last == '<' && ch == '>') ||
        (last == '+' && ch == '-') ||
        (last == '-' && ch == '+') ||
        (last == '(' && ch == ')') ||
        (last == ')' && ch == '(') ||
        (last == '^' && ch == '^')) {
        /* If two conflicting directives that together have no
         * effect whatsoever appear, do nothing and don't write
         * them out. */
        goto cleanup_exit;
    }

    if (ch == last) {
        ++cnt;
        return;
    }

    switch (last) {
    case '+':
        if (cnt == 1) {
            fputs("inc byte [rsi]\n", out);
        } else {
            fprintf(out, "add byte [rsi], %u\n", cnt);
        }
        break;
    case '-':
        if (cnt == 1) {
            fputs("dec byte [rsi]\n", out);
        } else {
            fprintf(out, "sub byte [rsi], %u\n", cnt);
        }
        break;
    case '>':
        if (cnt == 1) {
            fputs("inc rsi\n", out);
        } else {
            fprintf(out, "add rsi, %u\n", cnt);
        }
        break;
    case '<':
        if (cnt == 1) {
            fputs("dec rsi\n", out);
        } else {
            fprintf(out, "sub rsi, %u\n", cnt);
        }
        break;
    case '.':
        if (cnt < 4) while (cnt--) {
            fputs("call putc\n", out);
        } else {
            fprintf(out, "mov rcx, %u\n", cnt);
            fprintf(out, "C%u:\n", call);
            fputs("call putc\n", out);
            fprintf(out, "loop C%u\n", call++);
        }
        break;
    case ',':
        if (cnt < 4) while (cnt--) {
            fputs("call getc\n", out);
        } else {
            fprintf(out, "mov rcx, %u\n", cnt);
            fprintf(out, "C%u:\n", call);
            fputs("call getc\n", out);
            fprintf(out, "loop C%u\n", call++);
        }
        break;
    case '[':
        while (cnt--) {
            loops[lp] = loop++;
            fprintf(out, "L%d:\n", loops[lp]);
            fprintf(out, "cmp byte [rsi], 0\n");
            fprintf(out, "jz E%d\n", loops[lp]);
            ++lp;
        }
        break;
    case ']':
        while (cnt--) {
            --lp;
            fprintf(out, "jmp L%d\n", loops[lp]);
            fprintf(out, "E%d:\n", loops[lp]);
        }
        break;
    case '$':
        fputs("mov al, byte [rsi]\n", out);
        fputs("mov byte [hld], al\n", out);
        break;
    case '!':
        fputs("mov al, byte [hld]\n", out);
        fputs("mov byte [rsi], al\n", out);
        break;
    case '^':
        if (cnt % 2) {
            fputs("mov al, byte [rsi]\n", out);
            fputs("xor al, byte [hld]\n", out);
            fputs("mov byte [rsi], al\n", out);
        }
        break;
    case '|':
        if (cnt % 2) {
            fputs("mov al, byte [rsi]\n", out);
            fputs("xor al, byte [hld]\n", out);
            fputs("mov byte [rsi], al\n", out);
        }
        break;
    case '~':
        if (cnt % 2) {
            fputs("not byte [rsi]\n", out);
        }
        break;
    case '&':
        if (cnt % 2) {
            fputs("mov al, byte [rsi]\n", out);
            fputs("and al, byte [hld]\n", out);
            fputs("mov byte [rsi], al\n", out);
        }
        break;
    case '}':
        fprintf(out, "shr byte [rsi], %u\n", cnt);
        break;
    case '{':
        fprintf(out, "shl byte [rsi], %u\n", cnt);
        break;
    case ')':
        fprintf(out, "ror byte [rsi], %u\n", cnt);
        break;
    case '(':
        fprintf(out, "rol byte [rsi], %u\n", cnt);
        break;
    case '@':
        fputs("call exit\n", out);
        break;
    case '%':
        fputs("nop\n", out);
        break;
    default:
        break;
    }

cleanup_exit:
    last = ch;
    cnt = 1;
}

void usage(const char *pname)
{
        fprintf(stderr, "usage: %s [-h] -i input -o output\n", pname);
}

Changes from previous post:

  • new language features
  • change static functions to normal ones
  • removed useless header files
  • used ternary operator instead of if statements

Compilation command:

$ clang -O2 -Weverything -Werror -o bfc bfc.c

Testing:

$ ./bfc -i mandelbrot.bf -o mandelbrot.asm
$ nasm -f elf64 mandelbrot.asm
$ ld.gold -s -o mandelbrot mandelbrot.o
$ strip -s mandelbrot
$ ./mandelbrot
... mandelbrot fractal appears here ...

I also made a quick document summarising the changes from vanilla Brainfuck if anyone's interested. If it's off topic or something I'll remove it:

Compiler Directives
===================

Standard Brainf*ck
------------------

+ increment the value of current cell
- decrement the value of current cell
> increment pointer
< decrement pointer
[ jump to ] if cell value is zero, else jump past
] jump to [
. output current cell as ascii
, input to current cell as ascii

Brainfix Extensions
-------------------

$ place value of current cell into hold space (NOT a stack!).
! place value of hold space into current cell.
^ xor hold space with current cell and place result in cell.
| or hold space with current cell and place result in cell.
& and hold space with current cell and place result in cell.
~ not hold space with current cell and place result in cell.
} shift right current cell by 1.
{ shift left current cell by 1.
) rotate right current cell by 1.
( rotate left current cell by 1.
@ exit program with status as value of current cell.
% instruct compiler to emit literal NOP instruction, unoptimised.

Comments are started and ended by # character. Multi line comments are
permitted.

Language Idioms
===============

[-] set current cell to zero.

$^  set current cell to zero in more efficient manner.

[>] find and move to zero cell to the right of ptr

[<] find and move to zero cell to the left of ptr

[.>]    print null terminated string

$^> ,[>,] <[<]>
    get delimited string until EOF and move to start of string
\$\endgroup\$
  • 2
    \$\begingroup\$ Just so you know for the future, you can disable syntax highlighting for certain code blocks by appending <!-- language: lang-none --> just before it in your post. \$\endgroup\$ – Phrancis Dec 12 '15 at 19:36
  • \$\begingroup\$ @Phrancis Thanks, the unwanted syntax highlighting had been bugging me for a while now. \$\endgroup\$ – user73265 Dec 12 '15 at 19:38
3
\$\begingroup\$

Assembly

I don't have much to say about your assembly code; it looks very nice. I just have a few possible optimizations.


You are accessing the memory address of rsi a lot in your assembly code:

[rsi]

As you may know, memory access is inefficient and it would be best to access registers instead.

A possible optimization would be to store the value of [rsi] in a different register and to use that register instead of accessing the memory address. Then, when you need to change the memory address, simply reset the value of the register.

Here is what that would be in psuedo-code:

mov reg, [rsi]
...
... using reg instead of [rsi] ...
...
... the > instruction was entered:
inc rsi
mov reg, [rsi]

This will reduce your interaction with memory and will speed up compiled assembly code by a lot.


This recommendation would be a little difficult, and can be easily dismissed.

Right now you are compiling to assembly. If the user wishes to run this code, they must then use an external assembler to assemble the code. This can be tedious for the user (or not, if they are using a bash file).

However, you can reduce this middle step. Instead, why not compile straight to binary?

You can read up on the op-codes for each instruction that you are using and write methods for encoding them with the correct value (this can be merged in with a below tip about structs). Then, when the user compiles their code, they will have an executable all ready in the end.

Of course, this may not be the best choice. You will have to deal with platform if you are compiling to an executable and not just a binary, and the compiled binary may not be compatible with the different architectures that run your code.

C

if (ch == '#') {
    comment = comment ? 0 : 1;
}

if (comment) {
    return;
}

Not exactly sure what this is supposed to do, but it doesn't seem right to me. In Brainfuck, any non-valid Brainfuck character is a comment; you don't need to worry about what is an what isn't a comment based on a character.


Most Brainfuck code has a lot of comments (duh - it's Brainfuck). And, for every character in the code, the compile_and_write function is being called. Those characters include the comment characters.

This can slow your code down a lot. Every time this function is called, it has to do some memory prep, go through some conditionals, and go through the entire switch statement only to return.

To speed this up, the very first thing you should do in this function is see if the character is a valid Brainfuck character. If it's not, return immediately; there is no point in going on.


Right now, your "commands" are simple characters that are checked for in a big switch statement along with some code in the case statement. This is fine, but it could be more structured (get it?).

A better way to organize this would be to store the possible instructions in structs. As a note, I recommend moving this struct declaration to a different file (header file?) to keep things organized.

A sample struct might look like this:

struct Instruction {
    char symbol;
    void (*func)(void);
}

(you may need to modify this)

After you have this, create an array of the different instructions (you can just stick right on to the end of the struct definition). Then, in place of the switch statement, you can do something like this:

for(int i = 0; i < length_of_instruction_array; i++) {
    if(instructions[i]->symbol == last) {
        instructions[i]->func();
    }
}

note: I didn't try compiling this

Now your code is much more structured. And, you might be able to use the instruction data in other functions, too.


goto cleanup_exit;

Scream

Goto is not good practice in C. Avoid it at all costs. Here's why.

Why does that have to be a goto? Why do you have to jump to the end of the function? All you are technically doing is returning.

To fix this, move the goto label into the conditional itself and just return at the end:

if(...) {
    last = ch;
    cnt = 1;
    return;
}

if ((last == '>' && ch == '<') ||
    (last == '<' && ch == '>') ||
    (last == '+' && ch == '-') ||
    (last == '-' && ch == '+') ||
    (last == '(' && ch == ')') ||
    (last == ')' && ch == '(') ||
    (last == '^' && ch == '^')) {

This logic can be extracted into a separate function. It's not specifically about compiling the code, and is rather awkward there in the code.


You did a good job merging your fputs and fprintf calls in the beginning of your code, but you didn't do it for the rest of your code. Ex:

fprintf(out, "mov rcx, %u\n", cnt);
fprintf(out, "C%u:\n", call);
fputs("call putc\n", out);
fprintf(out, "loop C%u\n", call++);
\$\endgroup\$
  • \$\begingroup\$ Yes, I know that this isn't brainfuck. I thought I'd offer it, though, as that is how traditional brainfuck works (and I think that your code would still benefit from having the traditional comments). I don't think that you should be using system to assemble the code; there are too many things that can go wrong with that (and it just smells like bad practice). And yes; that is what I meant for number to. However, it would be the other way around: only put the contents of that memory into the register when you change the pointer. Happy Winterbash! \$\endgroup\$ – SirPython Dec 15 '15 at 0:58

Your Answer

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