Brainfuck de bas niveau

Partie I
Partie II
Partie III

Dans cet article, nous allons écrire un compilateur Brainfuck sur TurboAssembler
Ici, vous pouvez déboguer les programmes bf dans un mode pas à pas.

Tout d'abord, nous allons écrire l'interpréteur dans un langage de haut niveau, par exemple, en Pascal.

Le tableau data_arr représentera la mémoire de données, la chaîne str_arr contiendra les commandes.

Nous allons écrire un programme qui affiche un caractère dont le code ascii correspond au nombre + (donc nous n'avons besoin que des commandes + et . )

var data_arr:array[1..10] of integer; //   str_arr: string; //  i, j: integer; //     begin j:=1; //       readln(str_arr); //  for i:=1 to length(str_arr) do begin //     if (str_arr[i]='+') then data_arr[j]:= data_arr[j]+1; if (str_arr[i]='.') then write(chr(data_arr[j])); end; end. 

code bf ++++++++++++++++++++++++++++++++++++. va donner ! (le code ascii du caractère ! est 33).

Le programme peut être vérifié en ligne ide ideone.com

Ensuite, remplacez la boucle for par goto et ajoutez les commandes $$$- <>$
À la fin, nous afficherons le tableau data_arr

 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) then goto 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]='.') then write(chr(data_arr[j])); i:=i+1; goto prev; next: for k:=1 to 10 do begin write(data_arr[k]); write(' '); end; end. 

Code $$$+> ++> +++$donnera 1 2 3 0 0 0 0 0 0 0
Code $$$+> ++> +++ -$donnera 1 2 2 0 0 0 0 0 0 0
ideone.com

Ensuite, ajoutez [ et ]
Ajoutez une autre variable i_stor .
Si l'élément actuel a réussi le test sur [ , alors nous vérifions l'élément actuel du tableau data_arr à zéro, et si l'élément est supérieur à zéro, chargez la valeur de la variable i dans i_stor .

Lors du traitement de la parenthèse fermante ] , si data_arr n'est pas nul, nous chargeons l'adresse de la parenthèse ouvrante dans la variable i à partir de la variable i_stor [

Ensuite, passez à la commande i: = i + 1;
Si avant cela une valeur de i_stor était chargée dans i (pendant la vérification ] ), alors après le vidage, nous serons dans [ (sinon nous serons dans ] )

 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) then goto 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]='.') then write(chr(data_arr[j])); if (str_arr[i]='[') then begin if data_arr[j]>0 then i_stor:=i; end; if (str_arr[i]=']') then begin if data_arr[j]>0 then begin i:=i_stor; end; end; i:=i+1; goto prev; next: for k:=1 to 10 do begin write(data_arr[k]); write(' '); end; end. 

Code $$$+++++ [> + <-]$transfère le nombre 5 à la cellule suivante 0 5 0 0 0 0 0 0 0 0
ideone.com
Le code HelloWorld ressemble à ideone.com

Passons à l'assembleur

Pour organiser une boucle (boucle), il est nécessaire de mettre le nombre de cycles d'horloge dans le registre CX et de mettre une étiquette sur laquelle la transition sera effectuée à la fin du cycle (par la commande de boucle).

 mov CX, 28h ; -   prev: ;   ;  ;  ;   loop prev ;    prev 

Créez un tableau de commandes str_arr , placez-le $$$+++$
Créer un tableau de données data_arr , (pour plus de clarté) y mettre 1,1,1,1,1,1,1,1,1,1,1

En boucle, comparez le caractère actuel avec le caractère $$$+$et, si les caractères sont égaux, augmentez la valeur dans la cellule actuelle de 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] ; ,      1 next: 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 end begin 

L'assemblage (traduction) est effectué par la commande tasm.exe bf1.asm
La liaison est effectuée par tlink.exe bf1.obj

Après avoir exécuté le programme dans le débogueur TurboDebagger, vous pouvez voir qu'à partir de l'adresse 0130, les commandes se trouvent $$$+++$
Vient ensuite le tableau de données dans lequel nous avons changé le premier élément, puis la variable i , qui après l'exécution de la boucle devient égale à 0Ah.



Ajouter des commandes $$$- <>.$
Pour sortir un seul caractère en utilisant la fonction d'interruption 02h int 21h , il est nécessaire (avant d'appeler l'interruption) de placer le code de caractère dans le registre DL .

  mov AH,2 mov DL,   int 21h 

Nous écrirons tout le programme

 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 

La boucle fonctionne comme ceci:
si l'élément courant de str_arr n'est pas $$$+$puis passez à l'étiquette suivante: (sinon, exécutez $$$+$)
si l'élément courant de str_arr n'est pas $$$-$puis passez à l' étiquette next1:
si l'élément courant de str_arr n'est pas $$$>$puis passez à l' étiquette next2:
si l'élément courant de str_arr n'est pas $$$<$puis passez à l' étiquette next3:
si l'élément courant de str_arr n'est pas $$$.$puis passez à l' étiquette next4:
Après le label next4: augmentez l'index de la chaîne str_arr et passez au début de la boucle - au label prev:

Ensuite, ajoutez [ et ]
Ajoutez la variable i_stor .

Si l'élément actuel a réussi le test sur [ , alors nous vérifions l'élément actuel du tableau data_arr à zéro, et si l'élément est nul, nous sautons plus loin (jusqu'à l'étiquette suivante), sinon, chargez la valeur de la variable i dans 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: 

Lors du traitement de la parenthèse fermante ] , si data_arr n'est pas nul, chargez l'adresse de la parenthèse ouvrante dans la variable i à partir de la variable i_stor [

 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: 

Vérifiez le 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 

Ajouter une fonction à la ligne d'entrée 3fh interruption 21h

  mov ah, 3fh ;   mov cx, 100h ; 256  mov dx,OFFSET str_arr int 21h 

Nous quitterons la boucle après avoir atteint la fin de la chaîne '$' .
Pour ce faire, nous comparerons le caractère courant avec le caractère '$'

 cmp DL, 24h ;  '$' je exit_loop 

Remplacez la boucle loop par la commande jmp.

 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 

Lors de la compilation, nous obtenons une erreur

Saut relatif hors de portée de 0001h octets

Le fait est que les commandes je / jne ne peuvent sauter qu'après quelques lignes du programme (chaque ligne prend de 1 à 5 octets en mémoire).


Les sauts longs à la fin du programme je / jne ne peuvent pas être effectués.
Par conséquent, nous remplaçons l'expression

  cmp DL, 24h ;  '$' je exit_loop ... exit_loop: 

expression

 cmp DL, 24h ;  '$' jne exit_ jmp exit_loop exit_ ... exit_loop: 

Donc, si le caractère courant correspond à $ , alors allez dans exit_loop: label avec la commande jmp , sinon nous sautons par-dessus la commande jmp .
La commande jmp peut effectuer une transition courte relative intra-segment (transition inférieure à 128 octets, c'est-à-dire IP: = IP + i8) ou une transition longue relative intra-segment (transition inférieure à 327 octets, c'est-à-dire IP: = IP + i16).
Par défaut, la commande jmp effectue un saut en longueur relatif, ce dont nous avons besoin (en général, au lieu de cela, vous pouvez simplement ajouter la directive jumps au début du programme).

 ;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 

Lien vers github avec des listes de programmes.

PS Voici un article sur la création d'une calculatrice de notation polonaise inversée x86 (RPN).