Low level brainfuck
- Tutorial
Part I
Part II
Part III
In this article we will write a Brainfuck-translator on TurboAssembler, but first we will write an interpreter in some high-level language, for example, in Pascal.
The data_arr array will represent the data memory, the string str_arr will contain commands.
We write a program that outputs a character whose ascii code corresponds to the number of + (so we will only need the + and . Commands )
bf code +++++++++++++++++++++++++++++++++. will give out ! (the ascii code of the symbol ! is 33).
The program can be checked in the online ide ideone.com.
Here you can debug the bf code step by step.
Next, replace the for loop with the goto statement and add the commands
At the end, we will output the data_arr array
Code
will issue 1 2 3 0 0 0 0 0 0 0
Code
will return 1 2 2 0 0 0 0 0 0 0
ideone.com
Next, add [ and ]
Add another variable i_stor .
If the current element passed the check for [ , then we check the current element of the data_arr array to zero, and, if the element is greater than zero, load the value from the variable i into i_stor . When processing the closing bracket ] , if data_arr is not zero, we load the address of the opening bracket into the variable i from the variable i_stor [ Next, go to the command i: = i + 1; If before
i the value from i_stor was loaded (when checking ] ), then after the jump we will be behind [ (otherwise we will be behind ] )
Code![$ +++++ [> + <-] $](https://habrastorage.org/getpro/habr/formulas/af3/ddc/8fa/af3ddc8fa6b566762a7c64d6133cd502.svg)
transfers the number 5 to the adjacent cell 0 5 0 0 0 0 0 0 0 0
ideone.com
The HelloWorld code looks like this ideone.com
To organize a loop (loop), you must put in the CX register the number of cycles of the loop and put a label on which the transition will be made at the end of the clock (by the loop command).
Create an array of commands str_arr , put there
Create data array data_arr , (for clarity) put there 1,1,1,1,1,1,1,1,1,1
In the loop we compare the current character with the character
and, if the characters are equal, increase the value in the current cell by 1.
Assembling (translation) is performed with the command tasm.exe bf1.asm
Linking is performed with the command tlink.exe bf1.obj
After executing the program in the TurboDebagger debugger, you can see that commands are located at address 0130
Next is the data array in which we changed the first element, then comes the variable i , which after the execution of the cycle became equal to 0Ah.
Add commands
In order to display a single character by using the 02h interrupt int 21h , needed (before the interrupt call) placed in the character code register DL .
Write the program entirely
The loop works like this:
if the current element of the string str_arr is notthen jump to the label next: (otherwise perform)
if the current element of the string str_arr is not
then jump to the label next1:
if the current element of the string str_arr is not
then jump to the label next2:
if the current element of the string str_arr is not
then jump to the label next3:
if the current element of the string str_arr is not
then jump to the label next4:
After the label next4: increase the index of the string str_arr and jump to the beginning of the cycle - to the label prev:
Next, add [ and ]
Add the variable i_stor .
If the current element passed the check for [ , then check the current element of the data_arr array to zero, and, if the element is zero, jump further (to the next label), otherwise load the value from the variable i into i_stor .
When processing the closing bracket ] , if data_arr is not zero, then in the variable i from the variable i_stor, we load the address of the opening bracket [
Check the code
Add the function to enter the line 3fh interrupt 21h
We will exit the loop upon reaching the end of the string '$' .
To do this, we will compare the current character with the symbol '$'
Replace the loop with the jmp command.
During the compilation process we get an error
The fact is that je / jne commands can jump over only a few lines of the program (each line takes from 1 to 5 bytes in memory).
Long jumps to the end of the je / jne program cannot.
Therefore, we replace the expression
by expression
So, if the current character matches $ , then go to the exit_loop label : with the jmp command , otherwise jump over the jmp command .
The jmp command can do an intrasegment relative short transition (transition less than 128 bytes, i.e. IP: = IP + i8) or an intrasegment relative long transition (transition less than 32767 bytes, i.e. IP: = IP + i16).
By default, the jmp command makes a relative long jump, which is what we need (and in general, instead, you can simply add the jumps directive to the beginning of the program).
Link to github with program listings.
Part II
Part III
In this article we will write a Brainfuck-translator on TurboAssembler, but first we will write an interpreter in some high-level language, for example, in Pascal.
The data_arr array will represent the data memory, the string str_arr will contain commands.
We write a program that outputs a character whose ascii code corresponds to the number of + (so we will only need the + and . Commands )
var
data_arr:array[1..10] of integer; // массив данных
str_arr: string; // команды
i, j: integer; // индексы строки и массиваbegin
j:=1; // нумерация элементов массива начинается с единицы
readln(str_arr); //считываем строкуfor i:=1to length(str_arr) dobegin// в цикле обрабатываем строкуif (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
if (str_arr[i]='.') thenwrite(chr(data_arr[j]));
end;
end.
bf code +++++++++++++++++++++++++++++++++. will give out ! (the ascii code of the symbol ! is 33).
The program can be checked in the online ide ideone.com.
Here you can debug the bf code step by step.
Next, replace the for loop with the goto statement and add the commands
At the end, we will output the data_arr array
LABEL prev,next;
var
data_arr:array[1..10] of integer; // массив данных
str_arr: string; // команды
i,j,k: integer; // индексы строки и массиваbegin
i:=1;
j:=1;
readln(str_arr); //считываем строку
prev:
if i>length(str_arr) thengoto next;
if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
if (str_arr[i]='-') then data_arr[j]:= data_arr[j]-1;
if (str_arr[i]='>') then j:=j+1;
if (str_arr[i]='<') then j:=j-1;
if (str_arr[i]='.') thenwrite(chr(data_arr[j]));
i:=i+1;
goto prev;
next:
for k:=1to10dobeginwrite(data_arr[k]);
write(' ');
end;
end.
Code
will issue 1 2 3 0 0 0 0 0 0 0 Code
will return 1 2 2 0 0 0 0 0 0 0 ideone.com
Next, add [ and ]
Add another variable i_stor .
If the current element passed the check for [ , then we check the current element of the data_arr array to zero, and, if the element is greater than zero, load the value from the variable i into i_stor . When processing the closing bracket ] , if data_arr is not zero, we load the address of the opening bracket into the variable i from the variable i_stor [ Next, go to the command i: = i + 1; If before
i the value from i_stor was loaded (when checking ] ), then after the jump we will be behind [ (otherwise we will be behind ] )
LABEL prev,next;
var
data_arr:array[1..10] of integer; // массив данных
str_arr: string; // команды
i,j,k: integer; // индексы строки и массива
i_stor: integer;
begin
j:=1;
i:=1;
readln(str_arr); //считываем строку
prev:
if i>length(str_arr) thengoto next;
if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1;
if (str_arr[i]='-') then data_arr[j]:= data_arr[j]-1;
if (str_arr[i]='>') then j:=j+1;
if (str_arr[i]='<') then j:=j-1;
if (str_arr[i]='.') thenwrite(chr(data_arr[j]));
if (str_arr[i]='[') thenbeginif data_arr[j]>0then i_stor:=i;
end;
if (str_arr[i]=']') thenbeginif data_arr[j]>0thenbegin
i:=i_stor;
end;
end;
i:=i+1;
goto prev;
next:
for k:=1to10dobeginwrite(data_arr[k]);
write(' ');
end;
end.
Code
transfers the number 5 to the adjacent cell 0 5 0 0 0 0 0 0 0 0 ideone.com
The HelloWorld code looks like this ideone.com
Let's go to the assembler
To organize a loop (loop), you must put in the CX register the number of cycles of the loop and put a label on which the transition will be made at the end of the clock (by the loop command).
mov CX, 28h ; кол-во тактов цикла
prev: ; метка цикла
; выполняем
; операции
; внутри цикла
loop prev ; возвращаемся на метку prev
Create an array of commands str_arr , put there
Create data array data_arr , (for clarity) put there 1,1,1,1,1,1,1,1,1,1
In the loop we compare the current character with the character
and, if the characters are equal, increase the value in the current cell by 1. text segment ; bf1.asm
assume cs:text, ds:data, ss:stk
begin:
;Подготовим все необходимое
mov AX,data ; настраиваем сегмент данных
mov DS,AX
mov DL, str_arr ; загружаем в DL 1ую команду
mov CX, 0Ah ; 10 тактов
prev:
cmp DL, 2Bh ; ячейка содержит +
jne next ; нет, переходим на метку next
mov BL, 00h ; загружаем в BL индекс
inc data_arr[BX] ; да, увеличиваем значение в ячейке на 1next:
inc i ; переходим на следующий символ массива команд
mov BL, i
mov DL, str_arr [BX]
loop prev
mov AX, 4c00h ; завершение программы
int 21h
text ends
data segment
str_arr DB 2Bh,2Bh,2Bh,'$' ; код +++
data_arr DB 1,1,1,1,1,1,1,1,1,1,'$' ; данные
i DB 0 ;индекс элемента массива команд
data ends
stk segment stack
db 100h dup (0) ; резервируем 256 ячеек
stk ends
endbeginAssembling (translation) is performed with the command tasm.exe bf1.asm
Linking is performed with the command tlink.exe bf1.obj
After executing the program in the TurboDebagger debugger, you can see that commands are located at address 0130
Next is the data array in which we changed the first element, then comes the variable i , which after the execution of the cycle became equal to 0Ah.
Add commands
In order to display a single character by using the 02h interrupt int 21h , needed (before the interrupt call) placed in the character code register DL .
mov AH,2
mov DL, код символа
int21h
Write the program entirely
text segment ; bf2.asm
assume cs:text,ds:data, ss:stk
begin:
;Подготовим все необходимое
mov AX,data ; настраиваем сегмент данных
mov DS,AX
mov DL, str_arr ; загружаем в DL 1ую команду
mov CX, 0Ah ; 10 тактов
prev:
cmp DL, 2Bh ; ячейка содержит +
jne next ; нет, переходим на метку next
mov BL, j ; загружаем в BL индекс данных
inc data_arr[BX] ; да, увеличиваем значение в ячейке на 1
next:
cmp DL, 2Dh ; ячейка содержит -
jne next1 ; нет, переходим на метку next1
mov BL, j
dec data_arr[BX]
next1:
cmp DL, 3Eh ; ячейка содержит >
jne next2 ; нет, переходим на метку next2
inc j ; да, переходим на сдедующий элемент массива data_arr
next2:
cmp DL, 3Ch ; ячейка содержит <
jne next3 ; нет, переходим на метку next3
dec j ; да, переходим на предыдущий элемент массива data_arr
next3:
cmp DL, 2Eh ; ячейка содержит .
jne next4 ; нет, переходим на метку next4
mov AH,2 ; да, выводим содержимое ячейки
mov BL, j
mov DL, data_arr[BX]
int 21h
next4:
inc i ; переходим на следующий символ массива команд
mov BL, i
mov DL, str_arr [BX]
loop prev
mov AX, 4c00h ; завершение программы
int 21h
text ends
data segment
str_arr DB 2Bh,3Eh,2Bh,2Bh,'$' ; код +>++
data_arr DB 0,0,0,0,0,0,0,0,0,0,'$' ; данные
i DB 0, '$' ;индекс элемента массива команд
j DB 0, '$' ;индекс элемента массива данных
data ends
stk segment stack
db 100h dup (0) ; резервируем 256 ячеек
stk ends
end begin
The loop works like this:
if the current element of the string str_arr is not
then jump to the label next: (otherwise perform) if the current element of the string str_arr is not
then jump to the label next1:if the current element of the string str_arr is not
then jump to the label next2:if the current element of the string str_arr is not
then jump to the label next3:if the current element of the string str_arr is not
then jump to the label next4:After the label next4: increase the index of the string str_arr and jump to the beginning of the cycle - to the label prev:
Next, add [ and ]
Add the variable i_stor .
If the current element passed the check for [ , then check the current element of the data_arr array to zero, and, if the element is zero, jump further (to the next label), otherwise load the value from the variable i into i_stor .
next4:
cmp DL, 5Bh ; ячейка содержит [
jne next5 ; нет, переходим на метку next5
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next5 ; если ноль, прыгаем дальше
mov DL, i ; иначе загружаем
mov i_stor, Dl ; в i_stor значение переменной i
next5:
When processing the closing bracket ] , if data_arr is not zero, then in the variable i from the variable i_stor, we load the address of the opening bracket [
next5:
cmp DL, 5Dh ; ячейка содержит ]
jne next6 ; нет, переходим на метку next6
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next6 ; если ноль, прыгаем дальше
mov DL, i_stor ; иначе загружаем
mov i, Dl ; в i_stor значение переменной i
next6:
Check the code
text segment ; bf4.asm
assume cs:text, ds:data, ss:stk
begin:
;Подготовим все необходимое
mov AX,data ; настраиваем сегмент данных
mov DS,AX
mov DL, str_arr ; загружаем в DL 1ую команду
mov CX, 50h ; 80 тактов
prev:
cmp DL, 2Bh ; ячейка содержит +
jne next ; нет, переходим на метку next
mov BL, j ; загружаем в BL индекс данных
inc data_arr[BX] ; да, увеличиваем значение в ячейке на 1
next:
cmp DL, 2Dh ; ячейка содержит -
jne next1 ; нет, переходим на метку next1
mov BL, j
dec data_arr[BX] ;BX, но не Bl
next1:
cmp DL, 3Eh ; ячейка содержит >
jne next2 ; нет, переходим на метку next2
inc j ; да, переходим на сдедующий элемент массива data_arr
next2:
cmp DL, 3Ch ; ячейка содержит <
jne next3 ; нет, переходим на метку next3
dec j ; да, переходим на предыдущий элемент массива data_arr
next3:
cmp DL, 2Eh ; ячейка содержит .
jne next4 ; нет, переходим на метку next4
mov AH,2 ; да, выводим содержимое ячейки
mov BL, j
mov DL, data_arr[BX]
int 21h
next4:
cmp DL, 5Bh ; ячейка содержит [
jne next5 ; нет, переходим на метку next5
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next5 ; если ноль, прыгаем дальше
mov DL, i ; иначе загружаем
mov i_stor, Dl ; в i_stor значение переменной i
next5:
cmp DL, 5Dh ; ячейка содержит ]
jne next6 ; нет, переходим на метку next6
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next6 ; если ноль, прыгаем дальше
mov DL, i_stor ; иначе загружаем
mov i, Dl ; в i_stor значение переменной i
next6:
inc i ; переходим к следующей команде
mov BL, i
mov DL, str_arr[BX]
loop prev ; прыгаем на метку prev:
mov AX, 4c00h ; завершение программы
int 21h
text ends
data segment
str_arr DB 2Bh,2Bh,2Bh,2Bh,5Bh, 3Eh,2Bh,3Ch,2Dh ,5Dh, '$' ; код ++++[>+<-]
data_arr DB 0,0,0,0,0,0,0,0,0,0,'$' ; данные
i DB 0,'$' ;индекс элемента массива команд
j DB 0,'$' ;индекс элемента массива данных
i_stor DB 0,'$'
data ends
stk segment stack
db 100h dup (0) ; резервируем 256 ячеек
stk ends
end begin
Add the function to enter the line 3fh interrupt 21h
mov ah, 3fh ; функция ввода
mov cx, 100h ; 256 символов
mov dx,OFFSET str_arr
int21h
We will exit the loop upon reaching the end of the string '$' .
To do this, we will compare the current character with the symbol '$'
cmp DL, 24h ; символ '$'
je exit_loop
Replace the loop with the jmp command.
text segment
assume cs:text,ds:data, ss: stk
begin:
;Подготовим все необходимое
mov AX,data ; настраиваем сегмент данных
mov DS,AX
; функция ввода
mov ah, 3fh
mov cx, 100h ; 256 символов
mov dx,OFFSET str_arr
int 21h
;
mov DL, str_arr ; загружаем в DL 1ую команду
;mov CX, 100h ; 256 тактов
prev:
cmp DL, 24h ; проверка на символ '$'
je exit_loop
cmp DL, 2Bh ; ячейка содержит +
jne next ; нет, переходим на метку next
mov BL, j ; загружаем в BL индекс данных
inc data_arr[BX] ; да, увеличиваем значение в ячейке на 1
next:
cmp DL, 2Dh ; ячейка содержит -
jne next1 ; нет, переходим на метку next1
mov BL, j
dec data_arr[BX] ;BX, но не Bl
next1:
cmp DL, 3Eh ; ячейка содержит >
jne next2 ; нет, переходим на метку next2
inc j ; да, переходим на следующий элемент массива data_arr
next2:
cmp DL, 3Ch ; ячейка содержит <
jne next3 ; нет, переходим на метку next3
dec j ; да, переходим на предыдущий элемент массива data_arr
next3:
cmp DL, 2Eh ; ячейка содержит .
jne next4 ; нет, переходим на метку next4
mov AH,2 ; да, выводим содержимое ячейки
mov BL, j
mov DL, data_arr[BX]
int 21h
next4:
cmp DL, 5Bh ; ячейка содержит [
jne next5 ; нет, переходим на метку next5
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next5 ; если ноль, прыгаем дальше
mov DL, i ; иначе загружаем
mov i_stor, Dl ; в i_stor значение переменной i
next5:
cmp DL, 5Dh ; ячейка содержит ]
jne next6 ; нет, переходим на метку next6
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next6 ; если ноль, прыгаем дальше
mov DL, i_stor ; иначе загружаем
mov i, Dl ; в i_stor значение переменной i
; здесь должен быть переход на метку prev:
next6:
inc i ; переходим к следующей команде
mov BL, i
mov DL, str_arr[BX]
; loop prev ; прыгаем на метку prev:
jmp prev
exit_loop:
MOV AH,2 ; переходим на новую строку
MOV DL,0Ah
INT 21h
mov AX, 4c00h ; завершение программы
int 21h
text ends
data segment
str_arr DB 256h DUP('$') ; буфер на 256 символов
data_arr DB 0,0,0,0,0,0,0,0,0,0,'$' ; данные
i DB 0,'$' ;индекс элемента массива команд
j DB 0,'$' ;индекс элемента массива данных
i_stor DB 0,'$'
data ends
stk segment para stack
db 100h dup (0) ; резервируем 256 ячеек
stk ends
end begin
During the compilation process we get an error
Relative jump out of range by 0001h bytes
The fact is that je / jne commands can jump over only a few lines of the program (each line takes from 1 to 5 bytes in memory).
Long jumps to the end of the je / jne program cannot.
Therefore, we replace the expression
cmp DL, 24h ; символ '$'
je exit_loop
...
exit_loop:
by expression
cmp DL, 24h ; символ '$'
jne exit_
jmp exit_loop
exit_
...
exit_loop:
So, if the current character matches $ , then go to the exit_loop label : with the jmp command , otherwise jump over the jmp command .
The jmp command can do an intrasegment relative short transition (transition less than 128 bytes, i.e. IP: = IP + i8) or an intrasegment relative long transition (transition less than 32767 bytes, i.e. IP: = IP + i16).
By default, the jmp command makes a relative long jump, which is what we need (and in general, instead, you can simply add the jumps directive to the beginning of the program).
;jumps
text segment
assume cs:text,ds:data, ss: stk
begin:
;Подготовим все необходимое
mov AX,data ; настраиваем сегмент данных
mov DS,AX
;;;
mov ah, 3fh ; функция ввода
mov cx, 100h ; 256 символов
mov dx,OFFSET str_arr
int 21h
;;;
mov DL, str_arr ; загружаем в DL 1ую команду
;mov CX, 100h ; 256 тактов
prev:
cmp DL, 24h ; символ '$'
;je exit_loop
jne l1
jmp SHORT exit_loop
l1:
cmp DL, 2Bh ; ячейка содержит +
jne next ; нет, переходим на метку next
mov BL, j ; загружаем в BL индекс данных
inc data_arr[BX] ; да, увеличиваем значение в ячейке на 1
next:
cmp DL, 2Dh ; ячейка содержит -
jne next1 ; нет, переходим на метку next1
mov BL, j
dec data_arr[BX] ;BX, но не Bl
next1:
cmp DL, 3Eh ; ячейка содержит >
jne next2 ; нет, переходим на метку next2
inc j ; да, переходим на следующий элемент массива data_arr
next2:
cmp DL, 3Ch ; ячейка содержит <
jne next3 ; нет, переходим на метку next3
dec j ; да, переходим на предыдущий элемент массива data_arr
next3:
cmp DL, 2Eh ; ячейка содержит .
jne next4 ; нет, переходим на метку next4
mov AH,2 ; да, выводим содержимое ячейки
mov BL, j
mov DL, data_arr[BX]
int 21h
next4:
cmp DL, 5Bh ; ячейка содержит [
jne next5 ; нет, переходим на метку next5
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next5 ; если ноль, прыгаем дальше
mov DL, i ; иначе загружаем
mov i_stor, Dl ; в i_stor значение переменной i
next5:
cmp DL, 5Dh ; ячейка содержит ]
jne next6 ; нет, переходим на метку next6
mov BL, j
mov DL, data_arr[BX]
cmp DL, 00 ; да, проверяем текущий элемент data_arr на ноль
jz next6 ; если ноль, прыгаем дальше
mov DL, i_stor ; иначе загружаем
mov i, Dl ; в i_stor значение переменной i
; здесь должен быть переход на метку prev:
next6:
inc i ; переходим к следующей команде
mov BL, i
mov DL, str_arr[BX]
; loop prev ; прыгаем на метку prev:
jmp prev
exit_loop:
MOV AH,2 ; переходим на новую строку
MOV DL,0Ah
INT 21h
mov AX, 4c00h ; завершение программы
int 21h
text ends
data segment
str_arr DB 256h DUP('$') ; буфер на 256 символов
data_arr DB 0,0,0,0,0,0,0,0,0,0,'$' ; данные
i DB 0,'$' ;индекс элемента массива команд
j DB 0,'$' ;индекс элемента массива данных
i_stor DB 0,'$'
data ends
stk segment para stack
db 100h dup (0) ; резервируем 256 ячеек
stk ends
end begin
Link to github with program listings.