Tulis kompiler brainfuck

13

Tulis sebuah program yang mengambil program brainfuck dan kompilasikan ke kode mesin yang dapat dieksekusi. Anda dapat menargetkan x86, x86_64, jvm (java bytecode) atau armv6, dan menggunakan salah satu format yang dapat dieksekusi berikut: ELF, a.out, file kelas, exe, com. Yang dapat dieksekusi harus bekerja di Linux atau Windows (atau Java pada keduanya).

Baik program Anda maupun yang dapat dieksekusi tidak dapat menjalankan program eksternal (seperti kompiler, assembler, atau juru bahasa lain).

Kode terpendek menang.

aditsu berhenti karena SE adalah JAHAT
sumber
2
Ada alasan untuk downvoting?
Aditsu berhenti karena SE adalah JAHAT
Adakah kemungkinan Anda memiliki sumber untuk kode mesin? Ini akan menjadi latihan golf kode mesin pertama saya jika Anda memiliki sumber daya yang dapat saya gunakan sebagai contoh?
WallyWest
@ Eliseod'Annunzio Saya tidak memiliki sumber daya tertentu, tetapi secara umum Anda dapat mulai dengan melihat ke bahasa assembly untuk platform pilihan Anda, dan mengumpulkan / membongkar beberapa contoh. Google adalah teman Anda :) Beberapa waktu yang lalu saya berpartisipasi dalam beberapa kompetisi golf kode mesin , saya tidak melakukannya dengan baik tetapi saya ingat kami menggunakan format com untuk DOS, karena tidak memiliki header dan barang tambahan, hanya saja kode. Mungkin orang lain bisa memberi lebih banyak tautan dan saran.
Aditsu berhenti karena SE adalah EVIL

Jawaban:

5

C, 866 783 byte

Karena kode saya menghasilkan 32 bit ELF yang dapat dieksekusi, saya tidak bisa menjanjikan bahwa itu akan bekerja pada pengaturan semua orang. Butuh penyesuaian cukup untuk membuat executable untuk berhenti melakukan segfault di komputer saya.

Bagi siapa pun yang mencoba menjalankan ini:

$ 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

Program Brainfuck dibaca dari stdin dan ELF yang dikompilasi ditulis ke 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);}

Tidak disatukan

Dalam versi kode yang tidak diklik, Anda bisa mendapatkan ide yang lebih baik tentang apa yang terjadi. Array karakter di akhir kode golf adalah pengkodean dari ELF dan header program dalam kode yang tidak ditandai. Kode ini juga menunjukkan bagaimana setiap instruksi Brainfuck diterjemahkan ke dalam 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);
}

Memodifikasi Mandiri BrainFuck

Untuk menghemat byte, rekaman untuk kompiler saya tidak dialokasikan di .bssbagian atau sesuatu yang mewah seperti itu. Sebagai gantinya, rekaman itu 30.000 byte nol ditulis langsung setelah kode byte yang dikompilasi dari program Brainfuck. Mengetahui hal ini, dan mengetahui kode byte apa yang dihasilkan oleh kompiler saya berarti Anda dapat membuat atau memodifikasi kode byte saat runtime. Ilustrasi sederhana dari 'fitur' ini adalah program Brainfuck yang menetapkan nilai keluar sendiri.

 <<<<<<+ 

Program keluar dari tepi kiri kaset ke kode byte ke titik bahwa kode keluar biasanya diatur 0. Menambah byte ini menyebabkan kode keluar diatur ke 1 bukan 0 ketika program akhirnya keluar. Dengan kegigihan, ini bisa digunakan untuk melakukan pemrograman level sistem di Brainfuck.

ankh-morpork
sumber
Bagus; kode Anda sebenarnya memiliki 865 byte (Anda tidak perlu baris baru di akhir file). Anda juga dapat menggabungkan deklarasi variabel char. Saya ingin tahu apakah array panjang itu dapat dikompresi juga, karena memiliki banyak nol.
Aditsu berhenti karena SE adalah JAHAT
@aditsu Saya telah berusaha menemukan beberapa penyandian yang lebih baik untuk array header. C tidak datang dengan pustaka kompresi yang dibangun sehingga zip sepertinya bukan pertanyaan. Yang terbaik yang saya hasilkan adalah mengkodekannya sebagai array long long intbukan char. Pasti ada ruang bagi saya untuk bermain golf beberapa deklarasi variabel saya. Saya akan melihat seberapa banyak saya bisa sampai di sana dan memperbarui jawaban saya.
ankh-morpork
Saya sedang memikirkan beberapa bentuk RLE, tapi .. apa pun yang bekerja :)
aditsu berhenti karena SE JAHAT
Anda dapat mengganti '577727389698621440' dengan '4105 * pow (2,47)' menggunakan deklarasi implisit pow, untuk 4 byte (setidaknya ini bekerja dengan gcc) ~
Maliafo
13

Python, 1974 karakter

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')

Berikut ini adalah terjemahan ke bytecode java. local 0 adalah array byte yang mewakili tape, local 1 adalah pointer data.

>  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

The xx xxadalah offset untuk mencapai braket yang cocok. # 2 adalah System.in, # 3 adalah read(), # 4 adalah System.out, # 5 adalah write(), dan # 6 adalah flush().

Pembukaan mengalokasikan array 30000 byte dan menginisialisasi posisi pita ke 0.

Pembungkus raksasa pada akhirnya dihasilkan dengan mengkompilasi B.javafile dummy dengan kode untuk masing-masing opcode (untuk menginduksi generasi tabel konstan yang benar dan sampah lainnya), kemudian melakukan operasi halus di atasnya.

Jalankan seperti

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

Bongkar dengan

javap -c B

Saya yakin itu bisa bermain golf lagi. Aku senang itu berhasil ...

Keith Randall
sumber
1
Gunakan dari sys import * dan kemudian mencukur 2 karakter dengan menghapus kedua sys.
Timtech
2
Anda bisa menggunakan base64 untuk menyandikan data biner itu dan mencukur beberapa byte
tecywiz121
3

Kode rakitan x86 16-bit, 104 byte

Kode ini dari 2014, tetapi saya baru saja menemukan tugas.

;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
sumber
Apakah Anda yakin itu bukan juru bahasa ?
Aditsu berhenti karena SE adalah EVIL
1
Tidak, ini benar-benar kompiler. "bf.com <hello.bf> out.com", maka out.com akan dapat dieksekusi.
peter ferrie
1
Oke, bisa tolong jelaskan bagaimana cara mengompilasinya dan OS apa yang berfungsi? Saya belum bisa menjalankannya.
Aditsu berhenti karena SE adalah JAHAT
berkumpul dengan YASM, jalankan di MS-DOS (via DOSBox tidak apa-apa).
peter ferrie
1
'<' Dan '>' harus diloloskan. Bagaimanapun, Windows 32-bit memiliki konsol DOS di mana akan berjalan, dan "com" secara eksplisit adalah salah satu format yang diperbolehkan.
peter ferrie