Najmniejszy interpreter kodu wirtualnego / VM

17

Tabela liderów - Kompilacja JIT (Im niższa, tym lepiej)

  1. es1024 - 81,2 punktów (w tym działający kompilator!)
  2. Kieth Randall - 116 punktów
  3. Ell - 121 punktów

Tabela liderów - interpretowana (im niższa, tym lepiej)

  1. Martin Büttner - 706654 punktów (około 2 godzin).
  2. criptych - 30379 punktów (97 sekund)

Twoim zadaniem, jeśli zdecydujesz się to zaakceptować, jest napisanie możliwie najmniejszego interpretera kodu wirtualnego / VM. VM / interpreter używa małej architektury CISC (operacje mogą różnić się rozmiarem), z językiem określonym poniżej. Po zakończeniu należy wydrukować wartość 3 rejestrów procesora, aby udowodnić, że wydrukowano prawidłowe dane wyjściowe (3 126 900 366).

Kompilator

Jeśli chcesz wykonać własne testy, poniżej znajduje się kompilator. Możesz opublikować swoje testy wraz z odpowiedzią.

Pokaż fragment kodu

Specyfikacje „VM”

Maszyna wirtualna ma 3 32-bitowe rejestry integralne bez znaku: R0, R1, R2. Są one reprezentowane w postaci szesnastkowej jako 0x00, 0x01 i 0x02.

Obsługiwane są następujące operacje:

Format to [nazwa] [... operandy ...], [szesnastkowy kod operacji] [... operandy powtórzone ...]

  • LOAD [rejestr] [wartość 4 bajtów], 0x00 [rejestr] [wartość 4 bajtów]
  • PUSH [rejestr], 0x02 [rejestr]
  • POP [rejestr], 0x03 [rejestr]
  • ADD [rejestr, 1 bajt] [rejestr, 1 bajt], 0x04 [rejestr] [rejestr]
  • SUB [rejestr, 1 bajt] [rejestr, 1 bajt], 0x05 [rejestr] [rejestr]
  • MUL [rejestr, 1 bajt] [rejestr, 1 bajt], 0x06 [rejestr] [rejestr]
  • DIV [rejestr, 1 bajt] [rejestr, 1 bajt], 0x07 [rejestr] [rejestr]
  • JMP [linia kodu, 4 bajty], 0x08 [4 bajtowy numer linii kodu]
  • CMP [rejestr, 1 bajt] [rejestr, 1 bajt], 0x09 [rejestr] [rejestr]
  • BRANCHLT [linia kodu, 4 bajty], 0x0a [4 bajtowy numer linii kodu]

Niektóre uwagi:

  • Powyższe operacje matematyczne sumują wartości 2 rejestrów, umieszczając dane wyjściowe w pierwszym rejestrze.
  • CMP, operator porównania, powinien porównywać wartości 2 rejestrów i przechowywać dane wyjściowe w jakiejś wewnętrznej fladze (może to być specyficzne dla implementacji) do przyszłego wykorzystania w instrukcjach oddziału.
  • Jeśli BRANCH zostanie wywołany przed CMP, chyba że BRANCHEQ zostanie wywołany, „VM” nie powinno się rozgałęziać.
  • PUSH / POP nie zaskakuje push i pop numery ze stosu.
  • Operatory skoku i rozgałęzienia skaczą do określonej operacji (wiersza kodu), a nie do adresu binarnego.
  • Oddziały nie wykonują porównania. Zamiast tego wykonują dane wyjściowe z ostatniego porównania.
  • Operatorzy rozgałęzień i skoków korzystają z systemu indeksowania numerów linii opartego na zerach. (Np. JMP 0 przeskakuje do pierwszej linii)
  • Wszystkie operacje należy wykonywać na liczbach bez znaku, które przepełniają się do zera i nie zgłaszają wyjątku w przypadku przepełnienia liczb całkowitych.
  • Dzielenie przez zero jest niedozwolone i jako takie zachowanie programu nie jest zdefiniowane. Możesz (na przykład) ...
    • Awaria programu.
    • Zakończ wykonywanie maszyny wirtualnej i zwróć jej bieżący stan.
    • Pokaż komunikat „ERR: Dzielenie przez 0”.
  • Zakończenie programu definiuje się, gdy wskaźnik instrukcji osiąga koniec programu (można założyć, że program nie jest pusty).

Dane wyjściowe Dane wyjściowe muszą być dokładnie takie (łącznie z nowymi wierszami)

R0 3126900366
R1 0
R2 10000

Punkty Punkty są obliczane na podstawie następującego wzoru:Number Of Characters * (Seconds Needed To Run / 2)

Aby uniknąć różnic sprzętowych powodujących różne czasy, każdy test będzie uruchamiany na moim komputerze (i5-4210u, 8 GB pamięci RAM) na serwerze Ubuntu lub w systemie Windows 8, więc staraj się nie używać szalonego, egzotycznego środowiska wykonawczego, które kompiluje się tylko na Dual G5 Mac Pro z dokładnie 762,66 MB wolnej pamięci RAM.

Jeśli używasz specjalistycznego środowiska wykonawczego / języka, opublikuj link do niego.

Program testowy

Pomysł przyszedł stąd , więc użyjemy nieco zmodyfikowanej wersji ich programu.

Prawidłowe wyjście dla programu to: 3 126 900 366

W C:

int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
    for (j = 0; j < 10000; j++)
        s += (i * j) / 3;
}

W kodzie: [R0 jest reprezentatywne dla s, R1 dla j, R2 dla i]

LOAD R0 0
LOAD R2 0 <--outer loop value
LOAD R1 0 <--inner loop value
     --Begin inner loop--
PUSH R1 <--push inner loop value to the stack
MUL R1 R2 <--(i*j)
PUSH R2
LOAD R2 3
DIV R1 R2 <-- / 3
POP R2
ADD R0 R1 <-- s+=
POP R1
PUSH R2 
LOAD R2 1
ADD R1 R2 <--j++
POP R2
PUSH R2
LOAD R2 10000
CMP R1 R2 <-- j < 10000
POP R2
BRANCHLT 3 <--Go back to beginning inner loop
--Drop To outer loop--
LOAD R1 1
ADD R2 R1 <--i++
LOAD R1 10000
CMP R2 R1 <-- i < 10000
LOAD R1 0 <--Reset inner loop
BRANCHLT 2

W systemie binarnym / szesnastkowym:

0x00 0x00 0x00 0x00 0x00 0x00
0x00 0x02 0x00 0x00 0x00 0x00
0x00 0x01 0x00 0x00 0x00 0x00
0x02 0x01
0x06 0x01 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x03
0x07 0x01 0x02
0x03 0x02
0x04 0x00 0x01
0x03 0x01
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x01
0x04 0x01 0x02
0x03 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x27 0x10
0x09 0x01 0x02
0x03 0x02
0x0a 0x00 0x00 0x00 0x03
0x00 0x01 0x00 0x00 0x00 0x01
0x04 0x02 0x01
0x00 0x01 0x00 0x00 0x27 0x10
0x09 0x02 0x01
0x00 0x01 0x00 0x00 0x00 0x00
0x0a 0x00 0x00 0x00 0x02

Punkty bonusowe (Efekty są stosowane multiplikacyjnie) Np. Jeśli zakwalifikujesz się do wszystkich trzech, będzie to ((znaki * 0,50) * 0,75) * 0,90

  • 50% mniej, jeśli interpreter jest w rzeczywistości kompilatorem JIT
  • Zmniejszenie o 25%, jeśli zastosuje jakiekolwiek rozwinięcie pętli / znaczącą optymalizację.
  • 10% mniej, jeśli rozszerzysz maszynę wirtualną o
    • BRANCHEQ [linia kodu, 4 bajty] (rozgałęzienie, jeśli jest równe - kod operacji 0x0b)
    • BRANCHGT [linia kodu, 4 bajty] (rozgałęzienie, jeśli jest większe niż - kod operacji 0x0c)
    • BRANCHNE [linia kodu, 4 bajty] (Rozgałęzienie, jeśli nie jest równe - kod operacji 0x0d)
    • RLOAD [rejestr 1] [rejestr 2] (przenieś wartość rejestru 2 do rejestru 1 - kod operacji 0x01).

Niedozwolone

  • Kompilowanie przypadku testowego w programie jest zabronione. Musisz zaakceptować kod bajtowy ze STDIN lub z pliku (nie ważne które).
  • Zwracanie wyniku bez uruchamiania programu.
  • W inny sposób możesz oszukać wymaganie maszyny wirtualnej.
code-challenge interpreter stack Kolorowo Monochromatyczny
źródło
Dlaczego nie dołączyć jeszcze kilku programów testowych, aby zniechęcić do rzeczy, o których mówiłeś, że są niedozwolone? Jeśli jest to maszyna wirtualna, powinna być w stanie uruchomić wszystko zapisane w specyfikacji kodu bajtowego, prawda?
Kasran
Spróbuję to dziś wieczorem. Piszę teraz kompilator.
Colorfully Monochrome
Kompilator jest tutaj jsfiddle.net/aL9y19bd/23
Colorfully Monochrome
1
Czy CMPsprawdza mniej niż lub równość? A co dzieje się z jego wynikiem?
es1024,
1
MULi DIVsą również nieokreślone. Czy powinny być podpisane czy niepodpisane? Co dzieje się w przypadku przepełnienia mnożenia?
feersum

Odpowiedzi:

8

C, 752 (589 + 163 dla definicji flag) * 0,5 (JIT) * 0,9 (rozszerzenia) * (optymalizacja 0,75) * (0,64 sekundy / 2) = 81,216

C[S],J[S],i,j,k,y,c,X,Y,Z;char*R,a,b[9];main(x){R=mmap(0,S,6,34,-1,0);N=85;while(scanf("%c%s%*[ R]%d%*[ R]%d",&a,b,&x,&y)&&~getchar())a-=65,a-1?a-15?a-9?a?a-2?a-3?a-11?a-12?a-17?(N=41,v):(N=137,v):(N=137,u,N=247,g(H,4),N=139,u):(y?N=189+x,s(y):(N=51,g(G,G))):(N=137,u,N=247,g(H,6),N=139,u):(N=57,v,s(0xFC8A9F),--j):(N=1,v):(N=233,J[k++]=i,s(x)):b[1]-80?N=85+x:(N=93+x):(c=b[5],s(0x0F9EE78A),N=(c-69?c-71?c-76?1:8:11:0)+132,J[k++]=i,s(x)),C[++i]=j;U(E8,X)U(F0,Y)U(F8,Z)s(50013);i=j;while(k--)j=C[J[k]]+1,R[j-1]-233&&(j+=4),s(C[*(int*)(R+j)]-j-4);((int(*)())R)();printf("%u %u %u\n",X,Y,Z);}

Pobiera kod ( LOAD R0itp.), Bez znaków końcowych, pojedynczej spacji, bez pustych linii na środku, bez komentarzy itp. Wymagany jest znak nowej linii.

Jest to następnie konwertowane na kod bajtowy 80386 i wykonywane.

Ładowanie 0do rejestru otrzymuje xoring rejestr ze sobą zamiast moving 0do rejestru, który jest trzy bajty krótszy w wygenerowanego kodu bajtowego, a może być bardzo nieznacznie szybciej.

Połącz z:

gcc -m32 -D"g(a,b)=(N=192|b<<3|a)"-D"s(b)=(*(int*)(R+j)=b,j+=4)"-DN=R[j++]-D"G=((x+1)|4)"
-D"H=((y+1)|4)"-DS=9999-D"u=g(0,G)"-D"v=g(G,H)"-D"U(b,c)=s(0xA3##b##89),--j,s(&c);"
bytecode.c -o bytecode

Wymagany system operacyjny zgodny z POSIX.

Dane wejściowe są odczytywane ze STDIN (użyj ./bytecode < filedo potokowania z pliku).

Wynikowy kod bajtowy dla programu testowego: 

; start
 0:   55                      push   %ebp
; LOAD R0 0
 1:   33 ed                   xor    %ebp,%ebp
; LOAD R2 0
 3:   33 ff                   xor    %edi,%edi
; LOAD R1 0
 5:   33 f6                   xor    %esi,%esi
; PUSH $1
 7:   56                      push   %esi
; MUL R1 R2
 8:   89 f0                   mov    %esi,%eax
 a:   f7 e7                   mul    %edi
 c:   8b f0                   mov    %eax,%esi
; PUSH R2
 e:   57                      push   %edi
; LOAD R2 3
 f:   bf 03 00 00 00          mov    $0x3,%edi
; DIV R1 R2
14:   89 f0                   mov    %esi,%eax
16:   f7 f7                   div    %edi
18:   8b f0                   mov    %eax,%esi
; POP R2
1a:   5f                      pop    %edi
; ADD R0 R1
1b:   01 f5                   add    %esi,%ebp
; POP R1
1d:   5e                      pop    %esi
; PUSH R2
1e:   57                      push   %edi
; LOAD R2 1
1f:   bf 01 00 00 00          mov    $0x1,%edi
; ADD R1 R2
24:   01 fe                   add    %edi,%esi
; POP R2
26:   5f                      pop    %edi
; PUSH R2
27:   57                      push   %edi
; LOAD R2 10000
28:   bf 10 27 00 00          mov    $0x2710,%ed
; CMP R1 R2
2d:   39 fe                   cmp    %edi,%esi
2f:   9f                      lahf
30:   8a fc                   mov    %ah,%bh
; POP R2
32:   5f                      pop    %edi
; BRANCHLT 3
33:   8a e7                   mov    %bh,%ah
35:   9e                      sahf
36:   0f 8c cb ff ff ff       jl     0x7
; LOAD R1 1
3c:   be 01 00 00 00          mov    $0x1,%esi
; ADD R2 R1
41:   01 f7                   add    %esi,%edi
; LOAD R1 10000
43:   be 10 27 00 00          mov    $0x2710,%es
; CMP R2 R1
48:   39 f7                   cmp    %esi,%edi
4a:   9f                      lahf
4b:   8a fc                   mov    %ah,%bh
; LOAD R1 0
4d:   33 f6                   xor    %esi,%esi
; BRANCHLT 2
4f:   8a e7                   mov    %bh,%ah
51:   9e                      sahf
52:   0f 8c ad ff ff ff       jl     0x5
; copy R0 to X
58:   89 e8                   mov    %ebp,%eax
5a:   a3 28 5b 42 00          mov    %eax,0x425b
; copy R1 to Y
5f:   89 f0                   mov    %esi,%eax
61:   a3 38 55 44 00          mov    %eax,0x4455
; copy R2 to Z
66:   89 f8                   mov    %edi,%eax
68:   a3 40 55 44 00          mov    %eax,0x4455
; exit
6d:   5d                      pop    %ebp
6e:   c3                      ret

Nie golfowany: 

C[9999],J[9999],i,j,k,y,c,X,Y,Z;
char *R,a,b[9];
main(x){
    // 6 is PROC_WRITE|PROC_EXEC
    // 34 is MAP_ANON|MAP_PRIVATE
    R=mmap(0,'~~',6,34,-1,0);

    N=0x55;
    while(scanf("%c%s%*[ R]%d%*[ R]%d",&a,b,&x,&y)&&~getchar())
        a-=65,
        a-1? // B[RANCH**]
            a-15? // P[USH/OP]
                a-9? // J[MP]
                    a? // A[DD]
                        a-2? // C[MP]
                            a-3? // D[IV]
                                a-11? // L[OAD]
                                    a-12? // M[UL]
                                        a-17? // R[LOAD]
                                            // SUB
                                            (N=0x29,g(G,H))
                                        :(N=0x89,g(G,H))
                                    :(N=0x89,g(0,G),N=0xF7,g(H,4),N=0x8B,g(0,G))
                                :(y?N=0xBD+x,s(y):(N=0x33,g(G,G)))
                            :(N=0x89,g(0,G),N=0xF7,g(H,6),N=0x8B,g(0,G))
                        :(N=0x39,g(G,H),s(0xfc8a9f),--j)
                    :(N=0x1,g(G,H))
                :(N=0xE9,J[k++]=i,s(x))
            :b[1]-80? 
                N=0x55+x // PUSH
            :(N=0x5D+x) // POP
        :(c=b[5],s(0x0f9ee78a),N=(
        c-69? // EQ
            c-71? // GT
                c-76? // LT
                    1 // NE
                :8
            :11
        :0
        )+0x84,J[k++]=i,s(x)),
        C[++i]=j
        ;
    // transfer registers to X,Y,Z
    s(0xA3E889),--j,s(&X);
    s(0xA3F089),--j,s(&Y);
    s(0xA3F889),--j,s(&Z);

    // pop and ret
    s(0xC35D);

    i=j;
    // fix distances for jmp/branch**
    while(k--)
        j=C[J[k]]+1,R[j-1]-0xE9&&(j+=4),
        s(C[*(int*)(R+j)]-j-4);

    // call
    ((int(*)())R)();

    // output
    printf("%u %u %u\n",X,Y,Z);
}
es1024
źródło
Łał. Chciałbym dodać premię za włączenie kompilatora do maszyny wirtualnej.
Colorfully Monochrome
Średnio 0,67 sekundy na przebieg przez 15 przebiegów.
Colorfully Monochrome
Nie mogę się zgodzić, że xoring jest optymalizacją. Chociaż sprytny rozmiar kodu jest mądry, xoring nie zmienia charakterystyki wydajności VM (popraw mnie, jeśli się mylę). Miałem na myśli optymalizację: zmianę lub usunięcie instrukcji z kodu wejściowego (np. Usunięcie redundantnego POP ... PUSH) lub wykonanie 2 instrukcji z rzędu ładuje rejestr, aby można było go usunąć itp.
Colorfully Monochrome
EDYCJA: W rzeczywistości jest to optymalizacja: spadła do 0,64 sekundy na przebieg w ciągu 15 przebiegów. Wydaje mi się, że zapobiega to przeładowaniu pamięci podręcznej lub coś takiego poprzez skrócenie kodu (lub usuwa zbędny dostęp do pamięci)?
Colorfully Monochrome
@ColorfullyMonochrome Niektóre architektury, które mają xoring rejestru dla siebie, nie wykonają instrukcji, lecz po prostu wyzerują sam rejestr.
es1024
7

C, wynik = 854 bajtów × (~ 0,8 s / 2) × 0,5 [JIT] × 0,9 [Rozszerzenia] = ~ 154 bajtów s

#define G getchar()
#define L for(i=0;i<3;++i)
#define N*(int*)
#define M(x)"P\x8a\xe7\x9e\xf"#x"    KL"
*T[1<<20],**t=T,*F[1<<20],**f=F,R[3],r[]={1,6,7};char*I[]={"L\xb8    GGJH","I\x8b\xc0HHGH","H\x50GG","H\x58GG","I\3\xc0HHGH","I\53\xc0HHGH","M\x8b\xc0\xf7\xe0\x8b\xc0IHLGJ","O\63\xd2\x8b\xc0\xf7\xf0\x8b\xc0IJNGL","L\xe9    KH","L\73\xc0\x9f\x8a\xfcHHGH",M(\x82),M(\x84),M(\x87),M(\x85)},C[1<<24],*c=C;main(i,o,l,g){N c=0xb7ec8b60;c[4]=70;c+=5;while((o=G)>=0){char*s=I[o];l=*s-'G';memcpy(c,s+1,l);for(s+=l+1;o=*s++;){o-='G';if(o<3){g=r[G];c[*s++-'G']|=g<<3*(o&1);if(o>1)c[*s++-'G']|=g<<3;}else{if(o>3)*f++=c+*s-'G';for(i=4;i;--i)c[*s-'G'+i-1]=G;++s;}}*t++=c;c+=l;}*t=c;while(f>F)--f,**f=(int)T[**f]-(int)*f-4;L N&c[7*i]=0x5893e|r[i]<<19,N&c[3+7*i]=R+i;N&c[21]=0xc361e58b;mprotect((int)C>>12<<12,1<<24,7);((void(*)())C)();L printf("R%d %u\n",i,R[i]);}

Kompiluj z gcc vm.c -ovm -m32 -wsystemem operacyjnym zgodnym z POSIX x86.
Uruchom z ./vm < program, gdzie programjest binarny plik programu.

Idę po prędkość. Program wykonuje dość proste tłumaczenie programu wejściowego na kod maszynowy x86 i pozwala procesorowi wykonać resztę.

Na przykład oto tłumaczenie programu testowego. ecx, esiI ediodpowiadają R0, R1i R2, odpowiednio; bhposiada flagi stanu; eaxi edxsą rejestrami typu scratch; stos wywołań odpowiada stosowi maszyny wirtualnej:

# Prologue
     0:   60                      pusha
     1:   8b ec                   mov    ebp,esp
     3:   b7 46                   mov    bh,0x46
# LOAD R0 0
     5:   b9 00 00 00 00          mov    ecx,0x0
# LOAD R2 0 <--outer loop value
     a:   bf 00 00 00 00          mov    edi,0x0
# LOAD R1 0 <--inner loop value
     f:   be 00 00 00 00          mov    esi,0x0
#      --Begin inner loop--
# PUSH R1 <--push inner loop value to the stack
    14:   56                      push   esi
# MUL R1 R2 <--(i*j)
    15:   8b c6                   mov    eax,esi
    15:   f7 e7                   mul    edi
    19:   8b f0                   mov    esi,eax
# PUSH R2
    1b:   57                      push   edi
# LOAD R2 3
    1c:   bf 03 00 00 00          mov    edi,0x3
# DIV R1 R2 <-- / 3
    21:   33 d2                   xor    edx,edx
    23:   8b c6                   mov    eax,esi
    25:   f7 f7                   div    edi
    27:   8b f0                   mov    esi,eax
# POP R2
    29:   5f                      pop    edi
# ADD R0 R1 <-- s+=
    2a:   03 ce                   add    ecx,esi
# POP R1
    2c:   5e                      pop    esi
# PUSH R2
    2d:   57                      push   edi
# LOAD R2 1
    2e:   bf 01 00 00 00          mov    edi,0x1
# ADD R1 R2 <--j++
    33:   03 f7                   add    esi,edi
# POP R2
    35:   5f                      pop    edi
# PUSH R2
    36:   57                      push   edi
# LOAD R2 10000
    37:   bf 10 27 00 00          mov    edi,0x2710
# CMP R1 R2 <-- j < 10000
    3c:   3b f7                   cmp    esi,edi
    3e:   9f                      lahf
    3f:   8a fc                   mov    bh,ah
# POP R2
    41:   5f                      pop    edi
# BRANCHLT 4 <--Go back to beginning inner loop
    42:   8a e7                   mov    ah,bh
    44:   9e                      sahf
    45:   0f 82 c9 ff ff ff       jb     0x14
# --Drop To outer loop--
# LOAD R1 1
    4b:   be 01 00 00 00          mov    esi,0x1
# ADD R2 R1 <--i++
    50:   03 fe                   add    edi,esi
# LOAD R1 10000
    52:   be 10 27 00 00          mov    esi,0x2710
# CMP R2 R1 <-- i < 10000
    57:   3b fe                   cmp    edi,esi
    59:   9f                      lahf
    5a:   8a fc                   mov    bh,ah
# LOAD R1 0 <--Reset inner loop
    5c:   be 00 00 00 00          mov    esi,0x0
# BRANCHLT 3
    61:   8a e7                   mov    ah,bh
    63:   9e                      sahf
    64:   0f 82 a5 ff ff ff       jb     0xf
# Epilogue
    6a:   3e 89 0d 60 ac 04 09    mov    DWORD PTR ds:0x904ac60,ecx
    71:   3e 89 35 64 ac 04 09    mov    DWORD PTR ds:0x904ac64,esi
    78:   3e 89 3d 68 ac 04 09    mov    DWORD PTR ds:0x904ac68,edi
    7f:   8b e5                   mov    esp,ebp
    81:   61                      popa
    82:   c3                      ret

Bez golfa

Pokaż fragment kodu

Łokieć
źródło
Wow ... mój JIT zawierał ~ 900 linii kodu (napisanych w c ++) ...
Colorfully Monochrome
Średnio 0,63 sekundy na przebieg przez 15 przebiegów.
Colorfully Monochrome
2

CJam, 222 187 185 bajtów * (za wolny / 2)

Chciałem tylko zobaczyć, jak krótko mogę uzyskać maszynę wirtualną z kodem bajtowym, pisząc ją w CJam. Mniej niż 200 bajtów wydaje się całkiem przyzwoite. Ale to cholernie powolne, ponieważ sam CJam jest interpretowany. Uruchomienie programu testowego trwa wieki.

304402480 6b:P;q:iD-);{(_P=@/(\L*@@+\}h;]:P;TTT]:R;{_Rf=~}:Q;{4G#%R@0=@t:R;}:O;{TP=("R\(\GG*bt:R;  ~R= R\~@t:R; Q+O Q4G#+-O Q*O Q/O ~(:T; Rf=~-:U; GG*bU0<{(:T}*;"S/=~T):TP,<}g3,{'R\_S\R=N}/

Aby go uruchomić, pobierz interpreter Java pod tym linkiem sourceforge , zapisz kod vm.cjami uruchom go

java -jar cjam-0.6.2.jar vm.cjam

Program oczekuje kodu bajtowego na STDIN. Nie znalazłem jeszcze sposobu na przesłanie danych binarnych do programu, bez dodania przez PowerShell łamania linii końcowej i konwersji 0x0ado 0x0d 0x0a, co jest naprawdę denerwujące. Kod zawiera 4 bajty do naprawienia tego ( D-);), którego nie uwzględniłem w całkowitej liczbie, ponieważ nie jest to coś, co program powinien zrobić, jeśli faktycznie otrzymał kod bajtowy na STDIN, zamiast jakiejś dziwnie zakodowanej jego wersji . Jeśli ktoś zna rozwiązanie tego problemu, daj mi znać.

Nieznacznie nie golfista:

304402480 6b:P; "Create lookup table for instruction sizes. Store in P.";
q:i             "Read program and convert bytes to integers.";
D-);            "Remove spurious carriage returns. This shouldn't be necessary.";
{(_P=@/(\L*@@+\}h;]:P; "Split into instructions. Store in P.";
"We'll use T for the instruction pointer as it's initialised to 0.";
"Likewise, we'll use U for the CMP flag.";
TTT]:R; "Store [0 0 0] in R for the registers.";
{_Rf=~}:Q; "Register lookup block.";
{4G#%R@0=@t:R;}:O; "Save in register block.";
{TP=("R\(\GG*bt:R;

~R=
R\~@t:R;
Q+O
Q4G#+-O
Q*O
Q/O
~(:T;
Rf=~-:U;
GG*bU0<{(:T}*;"N/=~T):TP,<}g "Run program.";
3,{'R\_S\R=N}/

Dodam jutro właściwe wyjaśnienie.

Krótko mówiąc, przechowuję wszystkie rejestry, wskaźnik instrukcji i flagę porównania w zmiennych, dzięki czemu mogę zachować stos CJam jako stos maszyny wirtualnej.

Martin Ender
źródło
Daj nam kontynuować tę dyskusję w czacie .
Martin Ender
1
15,279 sekund średnio dla 20 iteracji. - 15 testów. Oznacza to 2,12208333 godziny na test.
Colorfully Monochrome
1

python / c ++, wynik = 56,66

1435 znaków *. 234/2 sekundy * .5 [JIT] * .75 [Optymalizacja] * .90 [Dodatkowe instrukcje]

Kompiluje program wejściowy do c ++, uruchamia na nim gcc, a następnie uruchamia wynik. Większość czasu spędza się w gcc.

Jedyną optymalizacją, którą wykonuję, jest zredukowanie operacji stosu do zmiennych jawnych, jeśli jest to dozwolone semantycznie. To bardzo pomaga, około 10-krotnie lepszy czas działania skompilowanego kodu (około 0,056 s, aby uruchomić wynikowy plik binarny). Nie jestem pewien, co robi gcc, co daje ci taką poprawę, ale to dobrze.

import sys,os
x=map(ord,sys.stdin.read())
w=lambda x:(x[0]<<24)+(x[1]<<16)+(x[2]<<8)+x[3]
I=[]
while x:
 if x[0]==0:f='r%d=%d'%(x[1],w(x[2:]));n=6
 if x[0]==1:f='r%d=r%d'%(x[1],x[2]);n=3
 if x[0]==2:f='P%d'%x[1];n=2
 if x[0]==3:f='O%d'%x[1];n=2
 if x[0]==4:f='r%d=r%d+r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==5:f='r%d=r%d-r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==6:f='r%d=r%d*r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==7:f='r%d=r%d/r%d'%(x[1],x[1],x[2]);n=3
 if x[0]==8:f='goto L%d'%w(x[1:]);n=5
 if x[0]==9:f='a=r%d;b=r%d'%(x[1],x[2]);n=3
 if x[0]==10:f='if(a<b)goto L%d'%w(x[1:]);n=5
 if x[0]==11:f='if(a==b)goto L%d'%w(x[1:]);n=5
 if x[0]==12:f='if(a>b)goto L%d'%w(x[1:]);n=5
 if x[0]==13:f='if(a!=b)goto L%d'%w(x[1:]);n=5
 I+=[f];x=x[n:]
D=[]
d=0
for f in I:D+=[d];d+='P'==f[0];d-='O'==f[0]
J=[]
if all(d==D[int(f[f.find('L')+1:])]for f,d in zip(I,D)if f[0]in'gi'):
 H='uint32_t '+','.join('s%d'%i for i in range(max(D)))+';'
 for f,d in zip(I,D):
  if f[0]=='P':f='s%d=r'%d+f[1:]
  if f[0]=='O':f='r'+f[1:]+'=s%d'%(d-1)
  J+=[f]
else:
 H='std::vector<uint32_t>s;'
 for f,d in zip(I,D):
  if f[0]=='P':f='s.push_back(r'+f[1:]+')'
  if f[0]=='O':f='r'+f[1:]+'=s.back();s.pop_back()'
  J+=[f]
P='#include<vector>\n#include<cstdint>\nuint32_t r0,r1,r2,a,b;'+H+'int main(){'
for i,f in enumerate(J):P+='L%d:'%i+f+';'
P+=r'printf("R0 %u\nR1 %u\nR2 %u\n",r0,r1,r2);}'
c=open("t.cc", "w")
c.write(P)
c.close()
os.system("g++ -O1 t.cc")
os.system("./a.out")

Z pewnością można by jeszcze zagrać w golfa.

Keith Randall
źródło
Średnio 0,477 sekund na przebieg w ciągu 15 przebiegów.
Colorfully Monochrome
1

Lua 5.2 (lub LuaJIT), 740 bajtów

Pierwsza próba, tylko minimalnie golfa. Ta wersja działa (przynajmniej w programie testowym) i implementuje dodatkowe kody operacyjne, ale nie spełnia wymogu matematycznego niepodpisanego i nie jest szczególnie szybka. Jako bonus jest to jednak maszyna wirtualna działająca na maszynie wirtualnej i jest napisana w taki sposób, że może być interpretowana (uruchamiana za pomocą PUC-Lua) lub w rodzaju JIT (uruchamiana za pomocą LuaJIT; nadal interpretowana, ale interpreter jest teraz JITted).

EDYCJA: Lepsza gra w golfa, wciąż duża.

EDYCJA: Naprawiono poważny błąd, a teraz ogranicza arytmetykę do unsigned longzasięgu. Jednak jakoś udało się uchronić rozmiar przed wymknięciem się spod kontroli, ale nadal daje złą odpowiedź.

EDYCJA: Okazuje się, wynik był poprawny, ale wynik nie. Przełączono na drukowanie z %uzamiast %di wszystko jest w porządku. Wyłączyłem również rejestry tabel dla zmiennych, aby nieco poprawić rozmiar i prędkość.

EDYCJA: Używając gotoinstrukcji Lua 5.2 (dostępnej również w LuaJIT) zastąpiłem interpreter „JIT-to-Lua”, generując kod, który jest uruchamiany bezpośrednio przez samą maszynę wirtualną Lua. Nie jestem pewien, czy to naprawdę liczy się jako JIT, ale poprawia prędkość.

U,S,P,F=table.unpack,table.insert,table.remove,math.floor X,r0,r1,r2,p,m,s=2^32,0,0,0,1,0,{}C={{'r%u=%u',1,4},{'r%u=r%u',1,1},{'S(s,r%u)',1},{'r%u=P(s)',1},{'r%u=(r%u+r%u)%%X',1,0,1},{'r%u=(r%u-r%u)%%X',1,0,1},{'r%u=(r%u*r%u)%%X',1,0,1},{'r%u=F(r%u/r%u)%%X',1,0,1},{'goto L%u',4},{'m=r%u-r%u',1,1},{'if m<0 then goto L%u end',4},{'if m==0 then goto L%u end',4},{'if m>0 then goto L%u end',4},{'if m~=0 then goto L%u end',4}}t={io.open(arg[1],'rb'):read('*a'):byte(1,-1)}i,n,r=1,0,{}while i<=#t do c,i,x,a=C[t[i]+1],i+1,0,{}for j=2,#c do y=c[j]if y>0 then x=0 for k=1,y do i,x=i+1,x*256+t[i]end end S(a,x)end S(r,('::L%d::'):format(n))n=n+1 S(r,c[1]:format(U(a)))end load(table.concat(r,' '))()print(('R0 %u\nR1 %u\nR2 %u'):format(r0,r1,r2))

Oto oryginalna, czytelna wersja.

U,S,P,F=table.unpack,table.insert,table.remove,math.floor

X,r0,r1,r2,p,m,s=2^32,0,0,0,1,0,{}

C={
    {'r%u=%u',1,4},
    {'r%u=r%u',1,1},
    {'S(s,r%u)',1},
    {'r%u=P(s)',1},
    {'r%u=(r%u+r%u)%%X',1,0,1},
    {'r%u=(r%u-r%u)%%X',1,0,1},
    {'r%u=(r%u*r%u)%%X',1,0,1},
    {'r%u=F(r%u/r%u)%%X',1,0,1},
    {'goto L%u',4},
    {'m=r%u-r%u',1,1},
    {'if m<0 then goto L%u end',4},
    {'if m==0 then goto L%u end',4},
    {'if m>0 then goto L%u end',4},
    {'if m~=0 then goto L%u end',4},
}

t={io.open(arg[1],'rb'):read('*a'):byte(1,-1)}
i,n,r=1,0,{}
while i<=#t do
    c,i,x,a=C[t[i]+1],i+1,0,{}
    for j=2,#c do
        y=c[j]
        if y>0 then
            x=0 
            for k=1,y do 
                i,x=i+1,x*256+t[i]
            end 
        end
        S(a,x)
    end
    S(r,('::L%d::'):format(n)) 
    n=n+1
    S(r,c[1]:format(U(a)))
end
load(table.concat(r,' '))()
print(('R0 %u\nR1 %u\nR2 %u'):format(r0,r1,r2))
cryptych stoi z Moniką
źródło
Po uruchomieniu programu wystąpił następujący błąd: pastebin.com/qQBD7Rs8 . Czy spodziewasz się kodu bajtowego zamiast standardowego lub jako pliku?
Colorfully Monochrome
Przepraszam. Mój plik binarny dla systemu Windows został uszkodzony. Tak więc wszystkie wersje gcc / linux działały, ale wszystkie testy systemu Windows uległy awarii. Jednak nadal podaje, że R0 i R1 mają wartość 0, a R2 ma wartość 1.
Kolorowo monochromatyczny
Podejrzewam, że tak naprawdę nie działa: trwało średnio 33,8 ms (GCC zajmuje ~ .25 sekund).
Colorfully Monochrome
Skrypt oczekuje bytecode jako pliku z nazwą pliku przekazaną w wierszu poleceń. Masz rację, prześledziłem to i wygląda na to, że wykonuje tylko pierwszą zewnętrzną pętlę. Wróć do deski kreślarskiej ...
cryptych stoi z Moniką
Tak właśnie myślę w C i piszę w Lua: <zamiast tego użyłem pętli <=, więc ostatnia instrukcja rozgałęzienia została pominięta. Nadal otrzymuje złą odpowiedź, ale teraz zajmuje to kilka minut. :)
cryptych stoi z Monicą
1

DO#

1505 1475 bajtów

To jest moja wersja interpretera, napisana w C # może być zoptymalizowana / gra w golfa, myślę, ale tak naprawdę nie wiem gdzie;)

wersja golfowa:

using System;using System.Collections.Generic;using System.IO;using System.Linq;class M{static void Main(string[]a){if(a.Length==1&&File.Exists(a[0])){B.E(B.P(File.ReadAllLines(a[0])));Console.WriteLine(B.O);}}}class B{public enum I{L=0x00,P=0x02,Q=0x03,A=0x04,S=0x05,M=0x06,D=0x07,J=0x08,C=0x09,BL=0x0a,BE=0x0b,BG=0x0c,BN=0x0d}public enum R{A,B,C}enum C{N,L,E,G}public static Dictionary<R,uint>r=new Dictionary<R,uint>{{R.A,0},{R.B,0},{R.C,0}};public static Stack<uint>s=new Stack<uint>();static C c=C.N;public static string O{get{return string.Format("R0 {0}\nR1 {1}\nR2 {2}",r[R.A],r[R.B],r[R.C]);}}public static void E(byte[][]l){for(uint i=0;i<l.Length;i++){var q=l[i];switch((I)q[0]){case I.L:r[(R)q[1]]=U(q,2);break;case I.P:r[(R)q[1]]=s.Pop();break;case I.Q:s.Push(r[(R)q[1]]);r[(R)q[1]]=0;break;case I.A:s.Push(r[(R)q[1]]+r[(R)q[2]]);break;case I.S:s.Push(r[(R)q[1]]-r[(R)q[2]]);break;case I.M:s.Push(r[(R)q[1]]*r[(R)q[2]]);break;case I.D:s.Push(r[(R)q[1]]/r[(R)q[2]]);break;case I.J:i=U(q,1)-1;break;case I.C:{uint x=r[(R)q[1]],y=r[(R)q[2]];c=x<y?C.L:x>y?C.G:C.E;}break;case I.BL:if(c==C.L)i=U(q,1)-1;break;case I.BG:if(c==C.G)i=U(q,1)-1;break;case I.BE:if(c==C.E)i=U(q,1)-1;break;case I.BN:if(c!=C.E)i=U(q,1)-1;break;}}}public static byte[][]P(string[]c){return c.Where(l=>!l.StartsWith("#")).Select(r=>r.Split(' ').Where(b=>b.Length>0).Select(b=>Convert.ToByte(b,16)).ToArray()).Where(l=>l.Length>0).ToArray();}static uint U(byte[]b,int i){return(uint)(b[i]<<24|b[i+1]<<16|b[i+2]<<8|b[i+3]);}}

edytować

usunięto niektóre niepotrzebne publici privatemodyfikatory:

using System;using System.Collections.Generic;using System.IO;using System.Linq;class M{static void Main(string[]a){if(a.Length==1&&File.Exists(a[0])){B.E(B.P(File.ReadAllLines(a[0])));Console.Write(B.O);}}}class B{enum I{L=0x00,P=0x02,Q=0x03,A=0x04,S=0x05,M=0x06,D=0x07,J=0x08,C=0x09,BL=0x0a,BE=0x0b,BG=0x0c,BN=0x0d}enum R{A,B,C}enum C{N,L,E,G}static Dictionary<R,uint>r=new Dictionary<R,uint>{{R.A,0},{R.B,0},{R.C,0}};static Stack<uint>s=new Stack<uint>();static C c=C.N;public static string O{get{return string.Format("R0 {0}\nR1 {1}\nR2 {2}\n",r[R.A],r[R.B],r[R.C]);}}public static void E(byte[][]l){for(uint i=0;i<l.Length;i++){var q=l[i];switch((I)q[0]){case I.L:r[(R)q[1]]=U(q,2);break;case I.P:r[(R)q[1]]=s.Pop();break;case I.Q:s.Push(r[(R)q[1]]);r[(R)q[1]]=0;break;case I.A:s.Push(r[(R)q[1]]+r[(R)q[2]]);break;case I.S:s.Push(r[(R)q[1]]-r[(R)q[2]]);break;case I.M:s.Push(r[(R)q[1]]*r[(R)q[2]]);break;case I.D:s.Push(r[(R)q[1]]/r[(R)q[2]]);break;case I.J:i=U(q,1)-1;break;case I.C:{uint x=r[(R)q[1]],y=r[(R)q[2]];c=x<y?C.L:x>y?C.G:C.E;}break;case I.BL:if(c==C.L)i=U(q,1)-1;break;case I.BG:if(c==C.G)i=U(q,1)-1;break;case I.BE:if(c==C.E)i=U(q,1)-1;break;case I.BN:if(c!=C.E)i=U(q,1)-1;break;}}}public static byte[][]P(string[]c){return c.Where(l=>!l.StartsWith("#")).Select(r=>r.Split(' ').Where(b=>b.Length>0).Select(b=>Convert.ToByte(b,16)).ToArray()).Where(l=>l.Length>0).ToArray();}static uint U(byte[]b,int i){return(uint)(b[i]<<24|b[i+1]<<16|b[i+2]<<8|b[i+3]);}}

nazwij go, executable.exe filenamegdzie filenamejest plik zawierający kod do interpretacji

Mój „program testowy”:

# LOAD R0 5
# CMP R0 R1
# BRANCHEQ 13
# LOAD R1 1
# LOAD R2 1
# CMP R0 R2
# MUL R1 R2
# LOAD R1 1
# ADD R2 R1
# PUSH R2
# PUSH R1 
# BRANCHEQ 13
# JMP 5
# POP R2
# POP R0
# POP R1
# PUSH R0

0x0 0x0 0x0 0x0 0x0 0x5
0x9 0x0 0x1 
0xb 0x0 0x0 0x0 0xd 
0x0 0x1 0x0 0x0 0x0 0x1 
0x0 0x2 0x0 0x0 0x0 0x1 
0x9 0x0 0x2 
0x6 0x1 0x2 
0x0 0x1 0x0 0x0 0x0 0x1 
0x4 0x2 0x1 
0x2 0x2 
0x2 0x1 
0xb 0x0 0x0 0x0 0xd 
0x8 0x0 0x0 0x0 0x5 
0x3 0x2 
0x3 0x0 
0x3 0x1 
0x2 0x0

Interpreter niepolity z długimi nazwami zmiennych, klas, ...

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        if (args.Length == 1 && File.Exists(args[0]))
        {
            var code = ByteCodeInterpreter.ParseCode(File.ReadAllLines(args[0]));
            ByteCodeInterpreter.Execute(code);
            Console.WriteLine(ByteCodeInterpreter.Output);
        }
    }
}

public static class ByteCodeInterpreter
{
    public enum Instruction : byte
    {
        LOAD = 0x00,
        PUSH = 0x02,
        POP = 0x03,
        ADD = 0x04,
        SUB = 0x05,
        MUL = 0x06,
        DIV = 0x07,
        JMP = 0x08,
        CMP = 0x09,
        BRANCHLT = 0x0a,
        BRANCHEQ = 0x0b,
        BRANCHGT = 0x0c,
        BRANCHNE = 0x0d
    }

    public enum Register : byte
    {
        R0 = 0x00,
        R1 = 0x01,
        R2 = 0x02
    }

    private enum CompareFlag : byte
    {
        NONE = 0x00,
        LT = 0x01,
        EQ = 0x02,
        GT = 0x03,
    }

    public static readonly Dictionary<Register, uint> register = new Dictionary<Register, uint>
    {
        {Register.R0, 0},
        {Register.R1, 0},
        {Register.R2, 0}
    };

    public static readonly Stack<uint> stack = new Stack<uint>();
    private static CompareFlag compareFlag = CompareFlag.NONE;

    public static string Output
    {
        get
        {
            return string.Format("R0 {0}\nR1 {1}\nR2 {2}", register[Register.R0], register[Register.R1],
                register[Register.R2]);
        }
    }

    public static void Execute(byte[][] lines)
    {
        for (uint i = 0; i < lines.Length; i++)
        {
            var line = lines[i];
            switch ((Instruction)line[0])
            {
                case Instruction.LOAD:
                    register[(Register)line[1]] = GetUint(line, 2);
                    break;
                case Instruction.PUSH:
                    register[(Register)line[1]] = stack.Pop();
                    break;
                case Instruction.POP:
                    stack.Push(register[(Register)line[1]]);
                    register[(Register)line[1]] = 0;
                    break;
                case Instruction.ADD:
                    stack.Push(register[(Register)line[1]] + register[(Register)line[2]]);
                    break;
                case Instruction.SUB:
                    stack.Push(register[(Register)line[1]] - register[(Register)line[2]]);
                    break;
                case Instruction.MUL:
                    stack.Push(register[(Register)line[1]] * register[(Register)line[2]]);
                    break;
                case Instruction.DIV:
                    stack.Push(register[(Register)line[1]] / register[(Register)line[2]]);
                    break;
                case Instruction.JMP:
                    i = GetUint(line, 1) - 1;
                    break;
                case Instruction.CMP:
                    {
                        uint v0 = register[(Register)line[1]], v1 = register[(Register)line[2]];
                        if (v0 < v1)
                            compareFlag = CompareFlag.LT;
                        else if (v0 > v1)
                            compareFlag = CompareFlag.GT;
                        else
                            compareFlag = CompareFlag.EQ;
                    }
                    break;
                case Instruction.BRANCHLT:
                    if (compareFlag == CompareFlag.LT)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHGT:
                    if (compareFlag == CompareFlag.GT)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHEQ:
                    if (compareFlag == CompareFlag.EQ)
                        i = GetUint(line, 1) - 1;
                    break;
                case Instruction.BRANCHNE:
                    if (compareFlag != CompareFlag.EQ)
                        i = GetUint(line, 1) - 1;
                    break;
            }
        }
    }

    public static byte[][] ParseCode(string[] code)
    {
        return
            code.Where(line => !line.StartsWith("#"))
                .Select(line => line.Split(' ').Where(b => b.Length > 0).Select(b => Convert.ToByte(b, 16)).ToArray())
                .Where(line => line.Length > 0)
                .ToArray();
    }

    private static uint GetUint(byte[] bytes, int index)
    {
        return (uint)(bytes[index] << 24 | bytes[index + 1] << 16 | bytes[index + 2] << 8 | bytes[index + 3]);
    }
}
Stefan
źródło