Brainfuck Interpreter in C - fourth day

Hello guys

As you remember (or not) our interpreter has these functionalities for now:
- 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
- prints all of the instructions
- clear the memory (more precisely the cheap memory) from the elements of the linked list

When we will have these functionalities our program should interpret any brainfuck code:
- 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



So today I am going to show you how to implement some awesome stuff like a stack for example. A stack is necessary to store '[' instruction which is simply the start of the loop. But first, we need to interpret brainfuck instructions right. I think the best thing to do is to implement it using a switch case instead of the block of if expressions. Let's try to write execute_instructions function.

This is the template of our function. First of all you should take a look at the switch case. I decided to do another function to each instruction. You don't have to do it, for example '.' is just putchar(*values_ptr);. I will avoid explanation of the passed arguments to these functions and I will go to show you every of this function. So take a look at this pictures:

What does brainfuck instructions really do? Let's try to figure it out:
>    -->   increments pointer   (in C:  ++values_ptr;)
<    -->   decrements pointer  (in C:   --values_ptr;)
+    -->   increments value from the pointer (in C: ++(*values_ptr);)
 -    -->   decrements value from the pointer (in C: --(*values_ptr);)
 .    -->   print the char to the stdout (in C: putchar(*values_ptr);)
 ,    -->   get value from stding to the pointer (in C: *values_ptr = getchar();)
 [    -->   start of the loop while the memory cell value isn't 0 (in C: while( *values_ptr ) {   )
 ]    -->   end of the loop (in C: } )

When you already know it now let's take a look at the parameters of these functions. As you remember for the earlier post on my blog, we need to pass the pointer via reference to change it. So the function accepts this argument like a pointer to pointer. To change the value that the pointer points to, we don't have to pass the pointer via reference so we can accept it like a copy. But the record of these two differences is the same - (*values_ptr). I assume that you understand already why. :)

But to understand what is start_loop and end_loop functions really do, I have to show you my implementation of the stack. Take a look at this:

 Our stack will be based on the linked list. Each element will have a pointer to the pushed brainfuck instruction and pointer to the higher element.

Now we should think about how to write push and pop function. When you are interested in Assembly you should know what are the push and pop instructions. If you don't then you can read this article - https://stackoverflow.com/questions/4584089/what-is-the-function-of-the-push-pop-instructions-used-on-registers-in-x86-ass.

The stack data structure is LIFO. (Last In First Out) So we can write push and pop function like this:

Let's go through instructions of push. First look at the parameters - this function accept esp_ptr (pointer to the top of the stack) by pointer to pointer because we will change esp_ptr in this function on the last instruction. current_instr_ptr points to the current brainfuck instruction in the text file - we are not going to change it so we can pass it by a simple copy and accept it like a pointer with one star on the left.

What is interesting in the push function is this instruction - new_element_on_the_stack->link = *esp_ptr. Each element of the stack which will be the top of the stack need to has a link with the current top. It is necessary because of pop function which will take a top element of the stack and it will set the esp_ptr to the element after the taken top (*esp_ptr = (*esp_ptr)->link) Notice that we don't store the instruction at bf_instr_ptr filed, but we store the pointer to that instruction. The last line of code sets the esp_ptr to the added element.

Our pop function it's different than assembly instruction pop in the one case because processor instruction pop returns the "poped" value to the eax register. Our function doesn't return any value because this functionality is useless in our case. The body of this method is very simple. First, it creates tmp pointer to store (temporarily) the pointer to the current top of the stack. Second instruction sets the esp_ptr to the element after the current top. The last instruction releases the memory and removes the earlier top of the stack.


And now when we fully understand the stack implementation we can look into start_loop and end_loop functions.

The start_loop function is called when the '[' instruction appears. If we want to interpret the nested loops right, we have to store each '[' instruction address on the stack and pop it from the stack when the checked memory cell is 0. So if the instruction is '[' then throw its address on the stack.

end_loop is also easy to understand. First, if expression checks if the value in the checked memory cell is different than 0. If it is true than current_instr_ptr is set to the top element of the stack which stores the pointer to the nearest '[' brainfuck instruction (*esp_ptr)->bf_instr_ptr. And when current_instr_ptr points to the '[' than we can move it to the next brainfuck instruction *current_instr_ptr = (*current_instr_ptr)->next_element
When the value in the memory cell is equal to 0 then we can call function pop to remove '[' instruction from the stack. 

Now we have all the functions to execute brainfuck instructions. Let's test our interpreter. I have this brainfuck code in the file with the .bf extension:

This is the test of our program:

This is the polish version of the error - Violation of memory protection (memory dump). Unfortunately Undefined Behavior occurs. In the next article, we will try to debug it.

The whole code of the program: