Escribe un compilador de brainfuck

13

Escriba un programa que tome un programa brainfuck y lo compile en código máquina ejecutable. Puede apuntar a x86, x86_64, jvm (java bytecode) o armv6, y usar uno de los siguientes formatos ejecutables: ELF, a.out, archivo de clase, exe, com. El ejecutable debería funcionar en Linux o Windows (o Java en cualquiera de los dos).

Ni su programa ni el ejecutable generado pueden ejecutar ningún programa externo (como otro compilador, ensamblador o intérprete).

El código más corto gana.

aditsu renunció porque SE es MALO
fuente
2
¿Alguna razón para votar a favor?
Aditsu se retiró porque SE es MALO el
¿Alguna posibilidad de que tenga alguna fuente para el código de máquina? Este sería mi primer ejercicio de golf con código de máquina si tiene algún recurso que pueda usar como ejemplo.
WallyWest
@ Eliseod'Annunzio No tengo ningún recurso en particular, pero en general puedes comenzar buscando en el lenguaje ensamblador la plataforma que elijas y ensamblar / desensamblar algunos ejemplos. Google es tu amigo :) Hace mucho tiempo participé en un par de competiciones de golf de código de máquina , no lo hice muy bien, pero recuerdo que estábamos usando el formato com para DOS, ya que no tenía encabezados y cosas adicionales, solo código. Quizás otras personas puedan dar más enlaces y sugerencias.
Aditsu se retiró porque SE es MALO el

Respuestas:

5

C, 866 783 bytes

Dado que mi código genera un ejecutable ELF de 32 bits, no puedo prometer que funcionará en la configuración de todos. Se necesitaron suficientes ajustes para que el ejecutable dejara de segfaularse en mi computadora.

Para cualquiera que intente ejecutar esto:

$ uname --all
Linux 4.4.0-24-generic #43-Ubuntu SMP Wed Jun 8 19:27:37 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

Se lee un programa Brainfuck de stdin y el ELF compilado se escribe en stdout.

#define P *(t++)
#define C case
#define B break
char a[30000],b[65535],f,*t=b;*c[100];**d=c;main(g){P=188;t+=4;while((f=getchar())!=-1)switch(f){C'>':P=68;B;C'<':P=76;B;C'+':P=254;P=4;P=36;B;C'-':P=254;P=12;P=36;B;C'.':P=187;t+=4;P=137;P=225;P=186;P=1;t+=3;P=184;P=4;t+=3;P=205;P=128;B;C',':P=187;P=1;t+=3;P=137;P=225;P=186;P=1;t+=3;P=184;P=3;t+=3;P=205;P=128;B;C'[':P=138;P=4;P=36;P=133;P=192;P=15;P=132;t+=4;*d=(int*)t-1;d++;B;C']':P=138;P=4;P=36;P=133;P=192;P=15;P=133;t+=4;d--;g=((char*)(*d+1))-t;*((int*)t-1)=g;**d=-g;B;}P=184;P=1;t+=3;P=187;t+=4;P=205;P=128;*(int*)(b+1)=0x8048054+t-b;long long z[]={282579962709375,0,4295163906,223472812116,0,4297064500,4294967296,577727389698621440,36412867248128,30064779550,140720308490240};write(1,&z,84);write(1,b,t-b);write(1,a,30000);}

Sin golf

En la versión no codificada del código, puede tener una mejor idea de lo que está sucediendo. La matriz de caracteres al final del código golfizado es una codificación del ELF y el encabezado del programa en el código no golfizado. Este código también muestra cómo cada instrucción Brainfuck se traduce en bytecode.

#include <linux/elf.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>

#define MAX_BIN_LEN 65535
#define MAX_JUMPS 100

unsigned int org = 0x08048000;



unsigned char move_right[] = {0x44};                              /*inc   esp         */

unsigned char move_left[]  = {0x4c};                              /*dec   esp         */

unsigned char inc_cell[]   = {0xfe,0x04,0x24};                    /*inc   [esp]       */

unsigned char dec_cell[]   = {0xfe,0x0c,0x24};                    /*dec   [esp]       */

unsigned char read_char[]  = {0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x03,0x00,0x00,0x00,           /*mov   eax,  3     */
                              0xcd,0x80};                         /*int   0x80        */

unsigned char print_char[] = {0xbb,0x01,0x00,0x00,0x00,           /*mov   ebx,  1     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x04,0x00,0x00,0x00,           /*mov   eax,  4     */
                              0xcd,0x80};                         /*int   0x80        */


unsigned char loop_start[] = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x84,0x00,0x00,0x00,0x00};     /*je    int32_t     */

unsigned char loop_end[]   = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x85,0x00,0x00,0x00,0x00};     /*jne   int32_t     */

unsigned char call_exit[]  = {0xb8,0x01,0x00,0x00,0x00,           /*mov   eax,  1     */
                              0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0xcd,0x80};                         /*int   0x80        */
unsigned char prelude[]    = {0xbc,0x00,0x00,0x00,0x00};          /*mov   esp, int32_t*/

unsigned char tape[100];

int main(){
    unsigned char text[MAX_BIN_LEN];
    unsigned char *txt_ptr = text;

    int32_t *loop_jmps[MAX_JUMPS];
    int32_t **loop_jmps_ptr = loop_jmps;

    Elf32_Off entry;

    entry = org + sizeof(Elf32_Ehdr) + 1 * sizeof(Elf32_Phdr);

    memcpy(txt_ptr,prelude,sizeof(prelude));
    txt_ptr += sizeof(prelude);
    char input;
    while((input = getchar()) != -1){
        switch(input){
            case '>':
                memcpy(txt_ptr,move_right,sizeof(move_right));
                txt_ptr += sizeof(move_right);
                break;
            case '<':
                memcpy(txt_ptr,move_left,sizeof(move_left));
                txt_ptr += sizeof(move_left);
                break;
            case '+':
                memcpy(txt_ptr,inc_cell,sizeof(inc_cell));
                txt_ptr += sizeof(inc_cell);
                break;
            case '-':
                memcpy(txt_ptr,dec_cell,sizeof(dec_cell));
                txt_ptr += sizeof(dec_cell);
                break;
            case '.':
                memcpy(txt_ptr,print_char,sizeof(print_char));
                txt_ptr += sizeof(print_char);
                break;
            case ',':
                memcpy(txt_ptr,read_char,sizeof(read_char));
                txt_ptr += sizeof(read_char);
                break;
            case '[':
                memcpy(txt_ptr,loop_start,sizeof(loop_start));
                txt_ptr += sizeof(loop_start);
                *loop_jmps_ptr = (int32_t*) txt_ptr - 1;
                loop_jmps_ptr++;
                break;
            case ']':
                memcpy(txt_ptr,loop_end,sizeof(loop_end));
                txt_ptr += sizeof(loop_end);
                loop_jmps_ptr--;
                int32_t offset = ((unsigned char*) (*loop_jmps_ptr + 1)) - txt_ptr;
                *((int32_t*)txt_ptr - 1) = offset;
                **loop_jmps_ptr = -offset;
                break;
        }
    }

    memcpy(txt_ptr,call_exit,sizeof(call_exit));
    txt_ptr += sizeof(call_exit);

    *(int32_t*)(text + 1) = entry + (txt_ptr - text);


    Elf32_Ehdr ehdr = {
        {0x7F,'E','L','F',ELFCLASS32,ELFDATA2LSB,EV_CURRENT,0,0,0,0,0,0,0,0,0},
        ET_EXEC,
        EM_386,
        EV_CURRENT,
        entry,
        sizeof(Elf32_Ehdr),
        0,
        0,
        sizeof(Elf32_Ehdr),
        sizeof(Elf32_Phdr),
        1,
        0,
        0,
        SHN_UNDEF,
    };

    Elf32_Phdr phdr = {
        PT_LOAD,
        0,
        org,
        org,
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        PF_R | PF_X | PF_W,
        0x1000,
    };

    int out = open("a.out",O_CREAT|O_TRUNC|O_WRONLY,S_IRWXU);
    write(out,&ehdr,sizeof(Elf32_Ehdr));
    write(out,&phdr,sizeof(Elf32_Phdr));

    write(out,text,txt_ptr-text);
    write(out,tape,sizeof(tape));
    close(out);
}

BrainFuck auto modificable

Para ahorrar en bytes, la cinta para mi compilador no está asignada en una .bsssección o algo así de elegante. En cambio, la cinta tiene 30,000 bytes nulos escritos directamente después del código de bytes compilado del programa Brainfuck. Saber esto y saber qué código de byte genera mi compilador significa que puede generar o modificar el código de byte en tiempo de ejecución. Una ilustración simple de esta 'característica' es un programa Brainfuck que establece su propio valor de salida.

 <<<<<<+ 

El programa sale del borde izquierdo de la cinta hacia el código de byte hasta el punto en que el código de salida normalmente se establece en 0. Al aumentar este byte, el código de salida se establece en 1 en lugar de 0 cuando el programa finalmente sale. Con persistencia, esto podría usarse para hacer programación a nivel de sistema en Brainfuck.

ankh-morpork
fuente
Agradable; su código en realidad tiene 865 bytes (no necesita una nueva línea al final del archivo). Además, puede fusionar declaraciones de variables char. Me pregunto si esa matriz larga también se puede comprimir, ya que tiene muchos ceros.
Aditsu se retiró porque SE es MALO
@aditsu He estado trabajando para encontrar una codificación mejor para la matriz de encabezado. C no viene con ninguna biblioteca de compresión incorporada, por lo que parece imposible de comprimir. Lo mejor que he encontrado es codificarlo como una matriz de en long long intlugar de char. Definitivamente, tengo espacio para jugar golf en algunas de mis declaraciones variables. Veré cuánto puedo llegar allí y actualizaré mi respuesta.
ankh-morpork
Estaba pensando en alguna forma de RLE, pero ... lo que sea que funcione :)
Aditsu dejó porque SE es MALO
puede reemplazar '577727389698621440' por '4105 * pow (2,47)' usando la declaración implícita de pow, para 4 bytes (esto funciona con gcc, al menos) ~
Maliafo
13

Python, 1974 caracteres

import sys
s='\x11\x75\x30\xbc\x08\x4b\x03\x3c'
k=[]
for c in sys.stdin.read():
 if'>'==c:s+='\x84\x01\x01'
 if'<'==c:s+='\x84\x01\xff'
 if'+'==c:s+='\x2a\x1b\x5c\x33\x04\x60\x91\x54'
 if'-'==c:s+='\x2a\x1b\x5c\x33\x04\x64\x91\x54'
 if'['==c:k+=[len(s)];s+='\x2a\x1b\x33\x99\x00\x00'
 if']'==c:a=k[-1];k=k[:-1];d=len(s)-a;s=s[:a+4]+'%c%c'%(d>>8,d&255)+s[a+6:]+'\xa7%c%c'%(-d>>8&255,-d&255)
 if','==c:s+='\x2a\x1b\xb2\x00\x02\xb6\x00\x03\x91\x54'
 if'.'==c:s+='\xb2\x00\x04\x59\x2a\x1b\x33\xb6\x00\x05\xb6\x00\x06'
s+='\xb1'
n=len(s)
sys.stdout.write('\xca\xfe\xba\xbe\x00\x03\x00-\x00+\n\x00\x08\x00\x13\t\x00\x14\x00\x15\n\x00\x16\x00\x17\t\x00\x14\x00\x18\n\x00\x19\x00\x1a\n\x00\x19\x00\x1b\x07\x00\x1c\x07\x00\x1d\x01\x00\x06<init>\x01\x00\x03()V\x01\x00\x04Code\x01\x00\x0fLineNumberTable\x01\x00\x04main\x01\x00\x16([Ljava/lang/String;)V\x01\x00\nExceptions\x07\x00\x1e\x01\x00\nSourceFile\x01\x00\x06B.java\x0c\x00\t\x00\n\x07\x00\x1f\x0c\x00 \x00!\x07\x00"\x0c\x00#\x00$\x0c\x00%\x00&\x07\x00\'\x0c\x00(\x00)\x0c\x00*\x00\n\x01\x00\x01B\x01\x00\x10java/lang/Object\x01\x00\x13java/io/IOException\x01\x00\x10java/lang/System\x01\x00\x02in\x01\x00\x15Ljava/io/InputStream;\x01\x00\x13java/io/InputStream\x01\x00\x04read\x01\x00\x03()I\x01\x00\x03out\x01\x00\x15Ljava/io/PrintStream;\x01\x00\x13java/io/PrintStream\x01\x00\x05write\x01\x00\x04(I)V\x01\x00\x05flush\x00!\x00\x07\x00\x08\x00\x00\x00\x00\x00\x02\x00\x01\x00\t\x00\n\x00\x01\x00\x0b\x00\x00\x00\x1d\x00\x01\x00\x01\x00\x00\x00\x05*\xb7\x00\x01\xb1\x00\x00\x00\x01\x00\x0c\x00\x00\x00\x06\x00\x01\x00\x00\x00\x03\x00\t\x00\r\x00\x0e\x00\x02\x00\x0b\x00\x00'+'%c%c'%((n+60)>>8,(n+60)&255)+'\x00\x04\x00\x03\x00\x00'+'%c%c'%(n>>8,n&255)+s+'\x00\x00\x00\x01\x00\x0c\x00\x00\x00*\x00\n\x00\x00\x00\x05\x00\x06\x00\x06\x00\x08\x00\t\x00\x0b\x00\x0b\x00\x13\x00\r\x00\x1d\x00\x0f\x00&\x00\x11\x00,\x00\x12\x002\x00\x14\x008\x00\x15\x00\x0f\x00\x00\x00\x04\x00\x01\x00\x10\x00\x01\x00\x11\x00\x00\x00\x02\x00\x12')

Debajo están las traducciones al código de bytes de Java. local 0 es una matriz de bytes que representa la cinta, local 1 es el puntero de datos.

>  iinc 1,+1
<  iinc 1,-1
+  aload_0;iload_1;dup2;baload;iconst_1;iadd;i2b;bastore
-  aload_0;iload_1;dup2;baload;iconst_1;isub;i2b;bastore
[  aload_0;iload_1;baload;ifeq xx xx
]  goto xx xx
,  aload_0;iload_1;getstatic #2;invokevirtual #3;i2b;bastore
.  getstatic #4;dup;aload_0;iload_1;baload;invokevirtual #5;invokevirtual #6

El xx xxson compensaciones para alcanzar el soporte correspondiente. # 2 es System.in, # 3 es read(), # 4 es System.out, # 5 es write(), y # 6 es flush().

El preámbulo asigna una matriz de 30000 bytes e inicializa la posición de la cinta a 0.

El envoltorio gigante al final se generó compilando un B.javaarchivo ficticio con código para uno de cada código de operación (para inducir la generación de las tablas constantes correctas y otra basura), y luego realizando una cirugía delicada en él.

Ejecútalo como

python bfc.py < input.b > B.class
java B

Desmontar con

javap -c B

Estoy seguro de que podría jugar más golf. Estoy feliz de que funcione ...

Keith Randall
fuente
1
Úselo desde sys import * y luego elimine 2 caracteres eliminando ambos sys.
Timtech
2
Podría usar base64 para codificar esos datos binarios y eliminar algunos bytes
tecywiz121
3

Código de ensamblaje x86 de 16 bits, 104 bytes

Este código es de 2014, pero acabo de encontrar la tarea.

;compliant version, non-commands are ignored, but 104 bytes long

[bits 16]  
[org 0x100]  
; assume bp=091e used  
; assume di=fffe  
; assume si=0100  
; assume dx=cs (see here)  
; assume cx=00ff  
; assume bx=0000  
; assume ax=0000 used (ah)  
; assume sp=fffe  
start:
        mov al, code_nothing - start  
code_start:
        mov ch, 0x7f ; allow bigger programs  
        mov bx, cx  
        mov di, cx  
        rep stosb  
        mov bp, find_right + start - code_start ;cache loop head for smaller compiled programs  
        jmp code_start_end  
find_right:
        pop si  
        dec si  
        dec si ;point to loop head  
        cmp [bx], cl  
        jne loop_right_end  
loop_right:
        lodsb  
        cmp al, 0xD5 ; the "bp" part of "call bp" (because 0xFF is not unique, watch for additional '[')  
        jne loop_left  
        inc cx  
loop_left:
        cmp al, 0xC3 ; ret (watch for ']')  
        jne loop_right  
        loop loop_right ;all brackets matched when cx==0  
        db 0x3c ;cmp al, xx (mask push)  
loop_right_end:
        push si  
        lodsw ; skip "call" or dummy "dec" instruction, depending on context  
        push si  
code_sqright:
        ret  
code_dec:
        dec byte [bx]  
code_start_end:
        db '$' ;end DOS string, also "and al, xx"  
code_inc:
        inc byte [bx]  
        db '$'  
code_right:
        inc bx ;al -> 2  
code_nothing:
        db '$'  
code_left:
        dec bx  
        db '$'  
code_sqleft:
        call bp  
        db '$'  
; create lookup table  
real_start:
        inc byte [bx+'<'] ;point to code_left  
        dec byte [bx+'>'] ;point to code_right  
        mov byte [bx+'['], code_sqleft - start  
        mov byte [bx+']'], code_sqright - start  
        lea sp, [bx+45+2] ;'+' + 4 (2b='+', 2c=',', 2d='-', 2e='.')  
        push (code_dec - start) + (code_dot - start) * 256  
        push (code_inc - start) + (code_comma - start) * 256  
pre_write:
        mov ah, code_start >> 8  
        xchg dx, ax  
; write  
        mov ah, 9  
        int 0x21  
; read  
code_comma:
        mov dl, 0xff  
        db 0x3d ; cmp ax, xxxx (mask mov)  
code_dot:
        mov dl, [bx]  
        mov ah, 6  
        int 0x21  
        mov [bx], al  
        db '$'  
        db 0xff ; parameter for '$', doubles as test for zero  
; switch  
        xlatb  
        jne pre_write  
  ; next two lines can also be removed  
  ; if the program ends with extra ']'  
  ; and then we are at 100 bytes... :-)  
the_end:
        mov dl, 0xC3  
        int 0x21  
        int 0x20 
Peter Ferrie
fuente
¿Estás seguro de que no es un intérprete ?
Aditsu renunció porque SE es MAL
1
No, es absolutamente un compilador. "bf.com <hello.bf> out.com", entonces out.com será ejecutable.
Peter Ferrie
1
Ok, ¿puedes explicar cómo compilarlo y en qué sistema operativo funciona? No he podido ejecutarlo todavía.
Aditsu se retiró porque SE es MAL
ensamblar con YASM, ejecutar en MS-DOS (a través de DOSBox está bien).
Peter Ferrie
1
El '<' y '>' necesitan ser escapados. De todos modos, Windows de 32 bits tiene una consola DOS donde se ejecutará, y "com" es explícitamente uno de los formatos permitidos.
Peter Ferrie