Brainfuck Interpreter in C - fifth day

Hello everyone

On the last article about writing a brainfuck interpreter, we saw that it did not works well. So today I will show how I debug this program. I solve the problem by the print it method.


The C language is well known from Linux source code for example but in the other hand, this language is well known from undefined behaviors. I admit that I spent a lot of time on finding a way to debug this interpreter but finally I achieve the goal. Now I want to show how I did it.

I throw to the code some puts("instruction: <instruction>"); fflush(stdout); instructions. These lines are under the most important instructions of our interpreter. "What is fflush(stdout) call?" - you can ask. This is the answer:

C standard library throws each character to the buffer when we want to print something to stdout. After this, it sends all characters to stdout and redraws the screen. For example:

puts("a");
puts("b");

The buffer will look like: [ab]

It works when no error appears, but when we have for example undefined behavior like in our program then the C standard library doesn't send characters from the buffer to stdout. But we can tell - "Hey, I want to see my characters on the screen and you have to send it to stdout right now!". To force it we can call fflush(stdout).

I assume that you understand this so now take a look at the code with these added debugging instructions:
 

Now let's test in and see what we will get on the screen.

Now we have something more than only the error. But the most important part of this is the end of all executed instruction:

Well, the last instruction of this set is decrementing value. I think this is not what we are looking for. SEGFAULT error usually raises when the pointer is set on the protected memory page. So we should find an error with some pointer in our program.

And here it is! These instructions appear when current_instr_ptr is pointing to the ']' instruction and the memory cell from the values array is not equal to zero. What we are going to do is to set our current_instr_ptr  to the start of the loop so to the '[' instruction and move it to the next instruction. So we should do it like this:

1) *current_instr_ptr = (*esp_ptr)->bf_instr_ptr;
2) *current_instr_ptr = (*current_instr_ptr)->next_element;

This is the correct way to handle nested loops. After 'print it' debugging we can see that our program does it in a bad way:
 
1) *current_instr_ptr = (*esp_ptr)->bf_instr_ptr;
2) *current_instr_ptr = (*current_instr_ptr)->next_element;
3) *current_instr_ptr = (*current_instr_ptr)->next_element;

When we already know what is the issue we can look at the end_loop function and correct the mistake.

And now we can take look at the execute_instructions function. 

After executing of each instruction our instruction pointer is moved to the next instruction. So we can throw our *current_instr_ptr = (*current_instr_ptr)->next_element; from the end_loop function and everything should be fine. Let's try.

Ok! Now we don't get any SEGFAULT error! But we should check what our program prints at the screen and check if it is correct. First of all, we need to comment each puts(<Something>); fflush(stdout); in the code. When we do this, we can compile the interpreter and execute it.

For this example, our program works correctly. But we should check more examples to prove that the interpreter handles all correct brainfuck codes.

This is the code of our example now. You can copy it from https://copy.sh/brainfuck/?file=https://copy.sh/brainfuck/prog/quine505.b 

Let's try to execute this code with our interpreter.

Unfortunately, the infinite loop is not a good sign. Where is the problem? We can guess that the problem is on the representation of values because the pointers work correctly after the fix. So we should print the values to look where is the issue.

Let's execute the program and see what we have got here.

Ok, we have the values from the interpretation of the brainfuck code. Now I will show you such a great tool for debugging brainfuck interpreters or brainfuck programs. This tool is brainfuck visualizer - https://fatiherikli.github.io/brainfuck-visualizer/ 

One click on the step section is enough to indicate an error! Our brainfuck interpreter works on the 8-bits memory cells, right? So we should add to the program this checks:

if( *values_ptr < 0 )
     *values_ptr = 255;
else if( *values_ptr > 255 )
    *values_ptr = 0; 

Let's add it to the functions which work with the values. Hmm... This is not a good idea because we don't want to repeat our code. This is not a good practice. We should write a function which will check if the value is less than 0 or more than 255.

 And now we can check if our interpreter works correctly with this example.

This is not what we are exactly looking for. :D But we are close to the solution of this issue. The problem is in the implementation of loops. When our pointer is pointing to the '[' instruction and if the memory cell is equal to zero then we have to jump over the whole loop. To do this we need to implement a loop and count the '[' and ']'. We will do it like this:

int balance;
if( *current_instr_ptr->bf_instruction == '[' )
     balance++;
else if( *current_instr_ptr->bf_instruction == ']' )
    balance--;
if( balance == 0 )
    jump over the whole loop

Look at the code:

Let's compile our code and execute it.

Hurray, it finally works! And this is the end of the road. Thanks for your attention.

I note that I'm not an expert so the code might not be perfect. Constructive criticism is welcome!

The whole code of the program: