Brainfuck Interpreter in C - first day
Hi there
This blog is about hacking, but also about programming. So I came up with an idea to write a Brainfuck Interpreter in C language. I will show you my road from the first day of writing this project to last day when the project will ends. I hope that you will enjoy this series of articles.
Before start coding, we suppose to write a little plan what we are going to do and how to do it right. Let's ask a question - "What I want from my program and how it can be done?"
My program has to:
- a file has to be read as an argument
- react if the file is not specified
- react if the file extension is not right
- react if the file is not found
- read brainfuck instructions from a file
- check if the char from the file is brainfuck instruction
- if it is brainfuck instruction then add it to the linked list
- interpret brainfuck instructions right
- interpret nested loops correctly
- if the brainfuck instruction is '[' then push it on the stack
- if memory cell value is 0 then pop '[' from the stack
- clear the memory of the linked list and stack
And I think that's all. Now we can start to implement it in C language. We will use some pointers and structures to implement linked list and stack so prepare to some fun with SEG FAULT errors. :) Let's write the first point of our "to do list" - a file has to be read as an argument.
argc is the number of arguments when we execute our program in a terminal, argv is a pointer to the char array of this arguments and that's all - everything is clear. But what is EX_USAGE? This is preprocessor variable which is defined in the sysexits.h file. When some error occurs in the program and you want to exit it, you can do it with sysexits. This is the content of the sysexits.h which contains descriptions of each variable as well - https://android.googlesource.com/platform/prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.7-4.6/+/jb-dev/sysroot/usr/include/sysexits.h. Test:
Now we should check if the file extension is correct or not. I am going to implement a function that will do it.
To search for something in the string you can use strchr function from string.h. This is the documentation of this https://www.tutorialspoint.com/c_standard_library/c_function_strchr.htm. strchr returns a pointer to the searched byte of a string. So we check if returned pointer is pointing to NULL. If not we can add one to avoid dot and get an extension of the file. That's all. Defines above the function are here because we don't want to write magic expressions. Look at this:
If expression with preprocessor variables is more readable than if without it:
Now we should test if our solution works correctly.
Ok, this is my first mistake. I leave the code without preprocessor variables and I was trying to compare "bf" with the filename, but this is the incorrect way to check if the file extension is right. All we have to do it's to change the calls of strcmp to our preprocessor variables. After this intervention everything looks fine.
Now we should think about what if the file has correct extension and this file is an argument of the executed program, but not exists in the file system? Of course we need to check it. Have a look at this block of code:
fopen function returns a pointer to the struct of the file. If this pointer is pointing to NULL than our program will call perror function which prints the special error from our operating system to stdout. Execute of this function is based on special variable in each OS which name is errno. We can test it. Why not?
Awesome. We already have checking given file mechanism, now we can try to implement linked list for brainfuck instructions. If you don't know what is linked list there is a quick guide - https://en.wikipedia.org/wiki/Linked_list. This is very useful data structure so I suggest you to understand it. But wait... Why are we want to use this? Let me explain. We don't know how many instructions will be in the file so the idea with throw this instructions into an array is bad. This is why we have to use linked list. But first you can look at this site about syntax of Brainfuck language - https://en.wikipedia.org/wiki/Brainfuck. In this article we can see that Brainfuck operates on an array of the values with size of 30 000. If standard of the Brainfuck tells it, we need to implement this fact in our interpreter.
And this is the end of coding in this day. Tomorrow I will show how to implement linked list and maybe stack as well.
This blog is about hacking, but also about programming. So I came up with an idea to write a Brainfuck Interpreter in C language. I will show you my road from the first day of writing this project to last day when the project will ends. I hope that you will enjoy this series of articles.
Before start coding, we suppose to write a little plan what we are going to do and how to do it right. Let's ask a question - "What I want from my program and how it can be done?"
My program has to:
- a file has to be read as an argument
- react if the file is not specified
- react if the file extension is not right
- react if the file is not found
- read brainfuck instructions from a file
- check if the char from the file is brainfuck instruction
- if it is brainfuck instruction then add it to the linked list
- interpret brainfuck instructions right
- interpret nested loops correctly
- if the brainfuck instruction is '[' then push it on the stack
- if memory cell value is 0 then pop '[' from the stack
- clear the memory of the linked list and stack
And I think that's all. Now we can start to implement it in C language. We will use some pointers and structures to implement linked list and stack so prepare to some fun with SEG FAULT errors. :) Let's write the first point of our "to do list" - a file has to be read as an argument.
argc is the number of arguments when we execute our program in a terminal, argv is a pointer to the char array of this arguments and that's all - everything is clear. But what is EX_USAGE? This is preprocessor variable which is defined in the sysexits.h file. When some error occurs in the program and you want to exit it, you can do it with sysexits. This is the content of the sysexits.h which contains descriptions of each variable as well - https://android.googlesource.com/platform/prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.7-4.6/+/jb-dev/sysroot/usr/include/sysexits.h. Test:
Now we should check if the file extension is correct or not. I am going to implement a function that will do it.
To search for something in the string you can use strchr function from string.h. This is the documentation of this https://www.tutorialspoint.com/c_standard_library/c_function_strchr.htm. strchr returns a pointer to the searched byte of a string. So we check if returned pointer is pointing to NULL. If not we can add one to avoid dot and get an extension of the file. That's all. Defines above the function are here because we don't want to write magic expressions. Look at this:
If expression with preprocessor variables is more readable than if without it:
Now we should test if our solution works correctly.
Ok, this is my first mistake. I leave the code without preprocessor variables and I was trying to compare "bf" with the filename, but this is the incorrect way to check if the file extension is right. All we have to do it's to change the calls of strcmp to our preprocessor variables. After this intervention everything looks fine.
Now we should think about what if the file has correct extension and this file is an argument of the executed program, but not exists in the file system? Of course we need to check it. Have a look at this block of code:
fopen function returns a pointer to the struct of the file. If this pointer is pointing to NULL than our program will call perror function which prints the special error from our operating system to stdout. Execute of this function is based on special variable in each OS which name is errno. We can test it. Why not?
Awesome. We already have checking given file mechanism, now we can try to implement linked list for brainfuck instructions. If you don't know what is linked list there is a quick guide - https://en.wikipedia.org/wiki/Linked_list. This is very useful data structure so I suggest you to understand it. But wait... Why are we want to use this? Let me explain. We don't know how many instructions will be in the file so the idea with throw this instructions into an array is bad. This is why we have to use linked list. But first you can look at this site about syntax of Brainfuck language - https://en.wikipedia.org/wiki/Brainfuck. In this article we can see that Brainfuck operates on an array of the values with size of 30 000. If standard of the Brainfuck tells it, we need to implement this fact in our interpreter.
And this is the end of coding in this day. Tomorrow I will show how to implement linked list and maybe stack as well.
Comments
Post a Comment