Brainfuck: Get ready to get your brain crushed!

Hello!

Here it is ... maybe another useless post about a useless langage :p.
Today, ... it will be about brainfuck!
The name really fit the langage ... cause in the end, your brain get completely crushed from it :p. Worst than ASM I swear :) ... but fun nonetheless ;).

Well, what can you do in brainfuck? Well basically anything, it's turing complete.

Let's first start with basic instructions.

Basic instructions

In Brainfuck you only have 8 instructions to remember:

inst  equivalent
>     ++ptr;
<     --ptr;
+     ++*ptr;
-     --*ptr;
.     putchar(*ptr);
,     *ptr=getchar();
[     while (*ptr) {
]     }

That's all you basically get :).

Let's see what we can do with it.

Hello world!

Brainfuck as you'll see is mostly about value generation than "real logic".

We would like to print the famous "Hello World!".
Well, brainfuck use the ASCII standard for its characters so we have to generate the ASCII value for H, e, l, etc un til we get our whole string.
This is done using loops, I generally do it using the following pattern:
counter = value; (power of 2: 2, 4, 8)

while (counter) {
    x += n;
    counter--;
}
if (odd)
    x += 1;

It basically is equivalent to:
odd: value * n + 1
even: value * n

For H we have the ASCII value of 72, this value is divisible by 8 (and 9).
counter = 8 and n = 9. It gives the following brainfuck code:

>++++++++[<+++++++++++++>-]<+>

Here is my code for "Hello World!":

>++++++++[<+++++++++>-]
>++++[<+++++++++++++++++++++++++>-]<+>
>++++[<+++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++++>-]
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++++++++[<++++>-]
>++[<+++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++>-]
>++++++++[<++++>-]<+>
<<<<<<<<<<<<
.>.>.>.>.>.>.>.>.>.>.>.>

Yeah it is complicated :).
Basically I first construct my whole string in memory then I go back to the beginning of the string and print it all.

Conditions

We will do the basic if ... else construct, afterward you will be able to construct more complex conditions.

The idea is to use the loop and execute only once depending of the value of a cell.
My construct is as follow:

[
[-]         make sure we execute the loop only once

put your code here

>
-
>        end the loop
]

<+       if we already went into the first branch then the cell = 0 and the loop doesn't execute
[
[-]         make sure we execute the loop only once

put another code here

>        end the loop
]

Try it with a different prepend such as nothing, ++++, ++++----, etc.

Addition

Let's say we want to add 3+1?

We would have the following brainfuck code for 3:
+++
And for 1:
+

Basically the idea is to decrement one of the cells and add it to the other using a loop.

The code:

+++    cell[0] = 3
>
+         cell[1] = 1

<         go to cell 0
[          while (cell[0]) {
-              --cell[0]
>+          cell++; ++cell[1]
<             go back to cell 0
]          }

And here it is, we have 4 in cell 1.

Substraction

It's the same principle as the addition but with the - symbol ;).

Multiplication

Look at the "Hello World!" part, that's how we do multiplication.

Division

Not really though about it.

That's it!

That's it for my post on brainfuck but if you want to continue the fun, feel free to do so.
Here is my brainfuck code generator for printing messages if you want to play with it a bit:

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

#define MAX_LEN     1024

// construct a string with a n length and the same byte
unsigned char* repeat_byte (unsigned char byte, int n) {
    char *repeated;
    int idxRepeat;

    repeated = calloc(n + 1, sizeof(byte));
    for (idxRepeat = 0; idxRepeat < n; idxRepeat++) {
        repeated[idxRepeat] = byte;
    }

    return repeated;
}

/*
>  ++ptr;
<  --ptr;
+  ++*ptr;
-  --*ptr;
.  putchar(*ptr);
,  *ptr=getchar();
[  while (*ptr) {
]  }
*/
// generate value in cell[0]
char* val2bf (unsigned char byte) {
    char *bf;
    int remainder, maxcount, divisor;
    // index into brainfuck str
    int idxBf;
    //
    unsigned char *repeated;

    // allocation
    bf = calloc(MAX_LEN, sizeof(*bf));
    if (!bf)
        return NULL;

    // counter value
    remainder = byte % 8;
    if (remainder == 0 || remainder == 1)
        maxcount = 8;
    else {
        remainder = byte % 4;
        if (remainder == 0 || remainder == 1)
            maxcount = 4;
        else {
            remainder = byte % 2;
            maxcount = 2;
        }
    }

    divisor = (byte - remainder) / maxcount;

    //
    strncat(bf, ">", MAX_LEN - strlen(bf));

    //
    repeated = repeat_byte('+', maxcount);
    strncat(bf, repeated, MAX_LEN - strlen(bf));
    free(repeated);

    // loop
    strncat(bf, "[", MAX_LEN - strlen(bf));
    // go forward
    strncat(bf, "<", MAX_LEN - strlen(bf));
    // increment
    repeated = repeat_byte('+', divisor);
    strncat(bf, repeated, MAX_LEN - strlen(bf));
    free(repeated);
    // go back to counter
    strncat(bf, ">-", MAX_LEN - strlen(bf));
    // end loop
    strncat(bf, "]", MAX_LEN - strlen(bf));
    if (remainder)
        strncat(bf, "<+>", MAX_LEN - strlen(bf));

    // ajust allocation
    bf = realloc(bf, strlen(bf) + 1);

    return bf;
}

// ascii string to bf string
char* ascii2bf (char *ascii, int len) {
    char *bf, *bfVal, *rewind;
    //
    int idxAscii;
    //
    int szBf = MAX_LEN, lenBf = 0;

    // allocate memory
    bf = calloc(szBf, sizeof(*bf));
    if (!bf)
        return NULL;

    for (idxAscii = 0; idxAscii < len; idxAscii++) {
        bfVal = val2bf(ascii[idxAscii]);

        // track bf len and size
        lenBf += strlen(bfVal);
        if (lenBf > szBf) {
            szBf *= 2;
            bf = realloc(bf, szBf);
        }

        // construct bf string
        strncat(bf, bfVal, szBf - strlen(bf));
        strncat(bf, "\n", szBf - strlen(bf));
        free(bfVal);
    }
    // return to beginning of string
    rewind = repeat_byte('<', len);
    strncat(bf, rewind, szBf - strlen(bf));
    free(rewind);
    strncat(bf, "\n", szBf - strlen(bf));

    return bf;
}

// print given ascii string
char* bfPrint (char *ascii, int len) {
    char *bf = ascii2bf(ascii, len);
    int szBf;

    // bf size + free space ">." and null
    szBf = strlen(bf) + 2 * len + 1;
    bf = realloc(bf, szBf * sizeof(*bf));
    if (!bf)
        return NULL;

    while (len--)
        strncat(bf, ".>", szBf - strlen(bf));

    return bf;
}

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

    // check arguments
    if (argc < 2) {
        printf("usage: %s str\n", argv[0]);
        return 1;
    }

    bf = bfPrint(argv[1], strlen(argv[1]));
    if (!bf)
        printf("Allocation failed\n");
    else {
        printf("%s\n", bf);
        free(bf);
    }        

    return 0;
}

It certainly does not generate optimized brainfuck code but at least it works :). Moreover, I digged out most of the important bugs so it should mostly be bug free ... should you find any bugs ... don't hesitate to tell me/contribute :p.

Conclusion

If you managed to survive up to here, you saw what is brainfuck, some stuffs we can do with it. Mostly an esoteric langage but still "fun" and "interesting" to study it for its theory.

Cheers,

Have fun,

m_101

Resources:
- Brainfuck on Wikipedia
- BrainFuck Beginners Tutorial
- Javascript Brainfuck Interpreter / Debugger
- Brainfuck JS (interpreter & debugger) 
- Brainfuck interpreter (JavaScript)
- Brainfuck Developer