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:
1
2
3
4
5
6
7
8
9
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:
1
counter = value; (power of 2: 2, 4, 8)
1
2
3
4
5
6
while (counter) {
x += n;
counter--;
}
if (odd)
x += 1;
It basically is equivalent to:
1
2
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:
1
>++++++++[<+++++++++++++>-]<+>
Here is my code for “Hello World!”:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
>++++++++[<+++++++++>-]
>++++[<+++++++++++++++++++++++++>-]<+>
>++++[<+++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++++>-]
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++++++++[<++++>-]
>++[<+++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]<+>
>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++++>-]
>++++[<+++++++++++++++++++++++++>-]
>++++++++[<++++>-]<+>
<<<<<<<<<<<<
.>.>.>.>.>.>.>.>.>.>.>.>
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[
[-] 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:
1
+++
And for 1:
1
+
Basically the idea is to decrement one of the cells and add it to the other using a loop.
The code:
1
2
3
4
5
6
7
8
9
10
+++ 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#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