Brainfuck de bajo nivel

Parte 1
Parte II
Parte III

En este artículo, escribiremos un compilador Brainfuck en TurboAssembler
Aquí puede depurar programas bf en un modo paso a paso.

Primero, escribiremos el intérprete en un lenguaje de alto nivel, por ejemplo, en Pascal.

La matriz data_arr representará la memoria de datos, la cadena str_arr contendrá los comandos.

Escribiremos un programa que muestre un carácter cuyo código ascii corresponda al número + (por lo tanto, solo necesitaremos los comandos + y . )

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. 

código bf +++++++++++++++++++++++++++++++++++. se dará por vencido ! (¡el código ascii del personaje ! es 33).

El programa se puede consultar en línea ide ideone.com

Luego, reemplace el bucle for con goto y agregue los comandos $$$- <>$
Al final, mostraremos la matriz 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. 

Código $$$+> ++> +++$dará 1 2 3 0 0 0 0 0 0 0
Código $$$+> ++> +++ -$dará 1 2 2 0 0 0 0 0 0 0
ideone.com

A continuación, agregue [ y ]
Agregue otra variable i_stor .
Si el elemento actual pasó la prueba en [ , entonces verificamos el elemento actual de la matriz data_arr a cero, y si el elemento es mayor que cero, cargamos el valor de la variable i en i_stor .

Al procesar el corchete de cierre ] , si data_arr no es cero, cargamos la dirección del corchete de apertura en la variable i desde la variable i_stor [

A continuación, vaya al comando i: = i + 1;
Si antes de eso se cargó un valor de i_stor en i (durante la verificación ] ), luego del volcado estaremos en [ (de lo contrario estaremos en ]]

 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. 

Código $$$+++++ [> + <-]$transfiere el número 5 a la siguiente celda 0 5 0 0 0 0 0 0 0 0
ideone.com
El código de HelloWorld se parece a ideone.com

Pasemos al ensamblador

Para organizar un ciclo (ciclo), debe colocar en el registro CX el número de ciclos del ciclo y colocar una etiqueta en la que se realizará la transición al final del ciclo (mediante el comando de ciclo).

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

Crear una matriz de comandos str_arr , poner allí $$$+++$
Crear una matriz de datos data_arr , (para mayor claridad) poner allí 1,1,1,1,1,1,1,1,1,1,1

En un bucle, compare el personaje actual con el personaje $$$+$y, si los caracteres son iguales, aumente el valor en la celda actual en 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 

El ensamblaje (traducción) se realiza mediante el comando tasm.exe bf1.asm
La vinculación se realiza mediante tlink.exe bf1.obj

Después de ejecutar el programa en el depurador TurboDebagger, puede ver que a partir de la dirección 0130, los comandos se encuentran $$$+++$
Luego está la matriz de datos en la que cambiamos el primer elemento, luego la variable i , que después de la ejecución del bucle se vuelve igual a 0Ah.



Agregar comandos $$$- <>. $$
Para generar un solo carácter utilizando la función de interrupción 02h int 21h , es necesario (antes de llamar a la interrupción) colocar el código de carácter en el registro DL .

  mov AH,2 mov DL,   int 21h 

Escribiremos todo el programa

 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 

El bucle funciona así:
si el elemento actual de str_arr no es $$$+$luego salte a la siguiente etiqueta : (de lo contrario, ejecute $$$+$)
si el elemento actual de str_arr no es $$$-$luego salta a la etiqueta next1:
si el elemento actual de str_arr no es $$$>$luego salta a la etiqueta next2:
si el elemento actual de str_arr no es $$$<$luego salta a la etiqueta next3:
si el elemento actual de str_arr no es $$$.$luego salta a la etiqueta next4:
Después de la etiqueta next4: aumente el índice de la cadena str_arr y salte al comienzo del ciclo - a la etiqueta prev:

A continuación, agregue [ y ]
Agregue la variable i_stor .

Si el elemento actual pasó la prueba en [ , entonces verificamos el elemento actual de la matriz data_arr a cero, y si el elemento es cero, saltamos más lejos (a la siguiente etiqueta), de lo contrario cargamos el valor de la variable i en 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: 

Al procesar el corchete de cierre ] , si data_arr no es cero, cargue la dirección del corchete de apertura en la variable i desde 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: 

Revisa el código $$$+++++ [> + <-]$

 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 

Agregar función a la línea de entrada 3fh interrupción 21h

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

Saldremos del bucle después de llegar al final de la cadena '$' .
Para hacer esto, compararemos el carácter actual con el carácter '$'

 cmp DL, 24h ;  '$' je exit_loop 

Reemplace el bucle de bucle con el comando 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 

Durante la compilación recibimos un error

Salto relativo fuera de rango en 0001h bytes

El hecho es que los comandos je / jne pueden saltar solo después de unas pocas líneas del programa (cada línea ocupa de 1 a 5 bytes en la memoria).


No se pueden realizar saltos largos al final del programa je / jne .
Por lo tanto, reemplazamos la expresión

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

expresión

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

Entonces, si el carácter actual coincide con $ , vaya a la etiqueta exit_loop: con el comando jmp , de lo contrario saltaremos sobre el comando jmp .
El comando jmp puede hacer una transición corta relativa intrasegmento (transición de menos de 128 bytes, es decir, IP: = IP + i8) o una transición larga relativa intrasegmento (transición de menos de 327 bytes, es decir, IP: = IP + i16).
De manera predeterminada, el comando jmp realiza un salto largo relativo, que es lo que necesitamos (en general, simplemente puede agregar la directiva de saltos al comienzo del programa).

 ;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 

Enlace a github con listados de programas.

PD: Aquí hay un artículo sobre cómo crear una calculadora de notación polaca inversa (RPN) x86.