I am working on a C to Brainfuck transpiler, based on the translation described in Brainfuck's Wikipedia page. Each program that I have tested works perfectly, until the end. In the beginning, I allocate an array of 30000 bytes, char* ptr = malloc(30000 * sizeof(char));, and in the end I free it via free(ptr);. My transpiler is below:
def make_tokens(chars):
return [char for char in chars if char in {">", "<", "+", "-", ".", ",", "[", "]"}]
def translate_instruction(i):
return {">": "++ptr;",
"<": "--ptr;",
"+": "++*ptr;",
"-": "--*ptr;",
".": "putchar(*ptr);",
",": "*ptr = getchar();",
"[": "while (*ptr) {",
"]": "}"}[i] + "\n"
def to_c(instructions):
with open("bfc.c", "w") as c_file:
for header in ("stdio", "stdlib", "string"):
c_file.write(f"#include <{header}.h>\n")
c_file.write("\nint main() {\n\tchar* ptr = malloc(30000 * sizeof(char));\n")
c_file.write("\tmemset(ptr, 0, 30000);\n")
indentation = 1
for i in make_tokens(instructions):
c_file.write("\t" * indentation + translate_instruction(i))
if i == "[": indentation += 1
elif i == "]": indentation -= 1
c_file.write("\tfree(ptr);\n}")
This Brainfuck program is Sierpinski's triangle, from here. I verified it with this online interpreter.
to_c("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[
-<<<[
->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
]>.>+[>>]>+
]""")
My program generates the following C code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char* ptr = malloc(30000 * sizeof(char));
memset(ptr, 0, 30000);
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
while (*ptr) {
++ptr;
++*ptr;
++ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
--ptr;
--ptr;
--*ptr;
}
++ptr;
++*ptr;
++*ptr;
++ptr;
++ptr;
++*ptr;
--ptr;
while (*ptr) {
--*ptr;
while (*ptr) {
++ptr;
++ptr;
++*ptr;
--ptr;
--ptr;
--*ptr;
}
++*ptr;
++ptr;
++ptr;
}
++ptr;
++*ptr;
while (*ptr) {
--*ptr;
--ptr;
--ptr;
--ptr;
while (*ptr) {
--*ptr;
++ptr;
while (*ptr) {
++*ptr;
while (*ptr) {
--*ptr;
}
++*ptr;
++ptr;
++*ptr;
++*ptr;
++ptr;
++ptr;
++ptr;
--*ptr;
--ptr;
--ptr;
}
--ptr;
while (*ptr) {
--ptr;
}
++ptr;
++ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
while (*ptr) {
--ptr;
--ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++*ptr;
++ptr;
++ptr;
--*ptr;
}
++*ptr;
--ptr;
--ptr;
++*ptr;
++*ptr;
putchar(*ptr);
while (*ptr) {
--*ptr;
}
--ptr;
--ptr;
}
++ptr;
putchar(*ptr);
++ptr;
++*ptr;
while (*ptr) {
++ptr;
++ptr;
}
++ptr;
++*ptr;
}
free(ptr);
}
The output of compiling and running that with clang was this:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
a.out(91318,0x11b627e00) malloc: *** error for object 0x7fb354808883: pointer being freed was not allocated
a.out(91318,0x11b627e00) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6
As you can see, the program runs just fine, just until the end. The free is what causes the abort trap, which I do not understand because I allocated my array via the heap, not the stack. LLDB does not help me very much here. This is so confusing! Does anyone know what I am doing wrong?
Process 93919 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
frame #0: 0x0000000100003f47 a.out`main at bfc.c:122:7
119 ++ptr;
120 ++*ptr;
121 }
-> 122 free(ptr);
123 }
Target 0: (a.out) stopped.
(lldb) n
a.out(93919,0x1000e7e00) malloc: *** error for object 0x100808883: pointer being freed was not allocated
a.out(93919,0x1000e7e00) malloc: *** set a breakpoint in malloc_error_break to debug
Process 93919 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
frame #0: 0x00007fff20340462 libsystem_kernel.dylib`__pthread_kill + 10
libsystem_kernel.dylib`__pthread_kill:
-> 0x7fff20340462 <+10>: jae 0x7fff2034046c ; <+20>
0x7fff20340464 <+12>: mov rdi, rax
0x7fff20340467 <+15>: jmp 0x7fff2033a6a1 ; cerror_nocancel
0x7fff2034046c <+20>: ret
Target 0: (a.out) stopped.
(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
* frame #0: 0x00007fff20340462 libsystem_kernel.dylib`__pthread_kill + 10
frame #1: 0x00007fff2036e610 libsystem_pthread.dylib`pthread_kill + 263
frame #2: 0x00007fff202c1720 libsystem_c.dylib`abort + 120
frame #3: 0x00007fff201a2430 libsystem_malloc.dylib`malloc_vreport + 548
frame #4: 0x00007fff201a54c8 libsystem_malloc.dylib`malloc_report + 151
frame #5: 0x0000000100003f50 a.out`main at bfc.c:122:2
frame #6: 0x00007fff20389621 libdyld.dylib`start + 1
(lldb)
Do this:
char* ptr = malloc(30000 * sizeof(char));
memset(ptr, 0, 30000);
char *orig = ptr;
// Code
free(orig);
Since you're incrementing and decrementing the pointer ptr you of course cannot trust it to point at the same place as it did upon initialization. If fact, that would be very unlikely.
And just for good habits:
sizeof(char) is ALWAYS 1, so either use malloc(30000 * sizeof *ptr) (Always works no matter the type) or simply malloc(30000)
Use calloc instead of malloc to save a call to memset
char *buffer = calloc(30000, sizeof *buffer);
char *ptr = buffer;
// Code
free(buffer);
But to be honest. While making sure that you always free resources is a good thing in general to avoid memory leaks, this is in general not necessary in the end of the main function. Unless you're programming embedded systems, operating systems or something very rare and special, you can trust the operating system to release all allocated memory for you upon program exit. For this application, you can skip the call to free if you want.