Kleinster Bytecode-Interpreter / VM

17

Leaderboard - JIT Compiled (Weniger ist besser)

  1. es1024 - 81.2 Punkte (einschließlich eines funktionierenden Compilers!)
  2. Kieth Randall - 116 Punkte
  3. Ell - 121 Punkte

Bestenliste - Ausgelegt (Weniger ist besser)

  1. Martin Büttner - 706654 Punkte (ungefähr 2 Stunden).
  2. Kriptychon - 30379 Punkte (97 Sekunden)

Wenn Sie dies akzeptieren, besteht Ihre Aufgabe darin, den kleinstmöglichen Bytecode-Interpreter / VM zu schreiben. Der VM / Interpreter verwendet eine kleine CISC-Architektur (Operationen können unterschiedlich groß sein) mit der unten angegebenen Sprache. Nach Abschluss müssen Sie den Wert der 3 CPU-Register drucken, um zu beweisen, dass die richtige Ausgabe gedruckt wird (3.126.900.366).

Compiler

Wenn Sie Ihre eigenen Tests durchführen möchten, finden Sie unten einen Compiler. Fühlen Sie sich frei, Ihre Tests mit Ihrer Antwort zu posten.

Code-Snippet anzeigen

"VM" Spezifikationen

Die VM hat 3 vorzeichenlose 32-Bit-Integralregister: R0, R1, R2. Sie werden hexadezimal als 0x00, 0x01 und 0x02 dargestellt.

Die folgenden Vorgänge müssen unterstützt werden:

Das Format ist [Name] [... Operanden ...], [hexadezimaler Op-Code] [... Operanden wiederholt ...]

  • LOAD [Register] [4-Byte-Wert], 0x00 [Register] [4-Byte-Wert]
  • PUSH [register], 0x02 [register]
  • POP [register], 0x03 [register]
  • ADD [Register, 1 Byte] [Register, 1 Byte], 0x04 [Register] [Register]
  • SUB [Register, 1 Byte] [Register, 1 Byte], 0x05 [Register] [Register]
  • MUL [Register, 1 Byte] [Register, 1 Byte], 0x06 [Register] [Register]
  • DIV [Register, 1 Byte] [Register, 1 Byte], 0x07 [Register] [Register]
  • JMP [Codezeile, 4 Byte], 0x08 [4 Byte Codezeilennummer]
  • CMP [Register, 1 Byte] [Register, 1 Byte], 0x09 [Register] [Register]
  • BRANCHLT [Codezeile, 4 Byte], 0x0a [4 Byte Codezeilennummer]

Einige Notizen:

  • Die obigen mathematischen Operationen addieren die Werte von 2 Registern und platzieren die Ausgabe im ersten Register.
  • CMP, der Vergleichsoperator, sollte die Werte von 2 Registern vergleichen und die Ausgabe in einem internen Flag (dies kann implementierungsspezifisch sein) für die zukünftige Verwendung in Verzweigungsanweisungen speichern.
  • Wenn BRANCH vor CMP aufgerufen wird, sollte die "VM" nicht verzweigen, es sei denn, BRANCHEQ wird aufgerufen.
  • PUSH / POP drücken oder knacken Zahlen aus dem Stapel.
  • Sprung- und Verzweigungsoperatoren springen zu einer bestimmten Operation (Codezeile), nicht zu einer binären Adresse.
  • Verzweigungsoperationen führen den Vergleich nicht durch. Sie nehmen vielmehr die Ausgabe des letzten Vergleichs zur Ausführung.
  • Branch- und Jump-Operatoren verwenden ein auf Null basierendes Indizierungssystem für Zeilennummern. (ZB JMP 0 springt in die erste Zeile)
  • Alle Operationen müssen an vorzeichenlosen Zahlen ausgeführt werden, die auf Null überlaufen und bei einem Ganzzahlüberlauf keine Ausnahme auslösen.
  • Eine Division durch Null ist nicht zulässig und daher ist das Verhalten des Programms nicht definiert. Sie können (zum Beispiel) ...
    • Programm zum Absturz bringen.
    • Beenden Sie die Ausführung der VM und geben Sie den aktuellen Status zurück.
    • Meldung "ERR: Division by 0" anzeigen.
  • Die Beendigung des Programms ist definiert als wenn der Befehlszeiger das Programmende erreicht (ein nicht leeres Programm kann angenommen werden).

Ausgabe Die Ausgabe muss genau das sein (Zeilenumbrüche inklusive)

R0 3126900366
R1 0
R2 10000

Punkte Punkte werden nach folgender Formel berechnet:Number Of Characters * (Seconds Needed To Run / 2)

Um zu vermeiden, dass Hardwareunterschiede zu unterschiedlichen Zeiten führen, wird jeder Test auf meinem Computer (i5-4210u, 8 GB RAM) auf einem Ubuntu-Server oder unter Windows 8 ausgeführt. Versuchen Sie daher, keine wahnsinnig exotische Laufzeit zu verwenden, die nur auf einem Dual G5 kompiliert wird Mac Pro mit genau 762,66 MB freiem RAM.

Wenn Sie eine spezielle Laufzeit / Sprache verwenden, senden Sie bitte einen Link zu dieser.

Testprogramm

Die Idee kam von hier , also werden wir eine etwas modifizierte Version ihres Programms verwenden.

Die korrekte Ausgabe für das Programm lautet: 3.126.900.366

In C:

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

Im Code: [R0 steht stellvertretend für s, R1 für j, R2 für 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

In binär / hex:

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

Bonuspunkte (Effekte werden multipliziert angewendet) Wenn Sie sich beispielsweise für alle drei qualifizieren, sind dies ((Zeichen * 0,50) * 0,75) * 0,90

  • Reduzierung um 50%, wenn der Interpreter tatsächlich ein JIT-Compiler ist
  • Reduzierung um 25%, wenn eine Art Loop-Unrolling / sinnvolle Optimierung angewendet wird.
  • 10% weniger, wenn Sie die VM mit erweitern
    • BRANCHEQ [Codezeile, 4 Bytes] (Verzweigen, wenn gleich - Opcode 0x0b)
    • BRANCHGT [Codezeile, 4 Bytes] (Branch, wenn größer als - opcode 0x0c)
    • BRANCHNE [Codezeile, 4 Bytes] (Verzweigen, wenn nicht gleich - Opcode 0x0d)
    • RLOAD [register 1] [register 2] (verschiebe den Wert von register 2 nach register 1 - opcode 0x01).

Nicht erlaubt

  • Das Vorkompilieren des Testfalls in das Programm ist verboten. Sie müssen entweder den Bytecode von STDIN oder von einer Datei akzeptieren (spielt keine Rolle, welche).
  • Die Ausgabe zurückgeben, ohne das Programm auszuführen.
  • Eine andere Möglichkeit, die VM-Anforderung zu umgehen.
code-challenge interpreter stack Bunt einfarbig
quelle
Warum nicht noch ein paar Testprogramme hinzufügen, um die Dinge, die Sie gesagt haben, nicht zu erlauben? Wenn es sich um eine VM handelt, sollte sie in der Lage sein, alles auszuführen, was in der Bytecode-Spezifikation angegeben ist, oder?
Kasran
Ich werde heute Abend versuchen, das zu tun. Ich schreibe gerade den Compiler.
Bunt einfarbig
Der Compiler ist hier jsfiddle.net/aL9y19bd/23
Colourful Monochrome
1
Prüft CMPauf weniger als oder Gleichheit? Und was passiert mit dem Ergebnis?
Es1024
1
MULund DIVsind auch unterbestimmt. Sollten sie unterschrieben oder nicht unterschrieben sein? Was passiert beim Multiplikationsüberlauf?
Feersum

Antworten:

8

C 752 (589 + 163 zum Definieren von Flags) * 0,5 (JIT) * 0,9 (Erweiterungen) * (0,75 Optimierung) * (0,64 Sekunden / 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);}

Nimmt Code ( LOAD R0usw.), keine abschließenden Zeichen, ein Leerzeichen, keine Leerzeilen in der Mitte, keine Kommentare usw. abschließende Zeilenumbrüche erforderlich.

Dieser wird dann in 80386 Bytecode konvertiert und ausgeführt.

Das Laden 0in ein Register wird ersetzt, indem xordas Register mit sich selbst anstatt in das Register movgeladen wird 0, das im generierten Bytecode drei Bytes kürzer ist und möglicherweise sehr geringfügig schneller ist.

Kompilieren mit:

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

POSIX-kompatibles Betriebssystem erforderlich.

Die Eingabe wird aus STDIN gelesen (wird ./bytecode < filezum Pipeen aus einer Datei verwendet).

Resultierender Bytecode für das Testprogramm: 

; 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

Ungolfed: 

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
quelle
Beeindruckend. Ich wünschte, ich hätte einen Bonus für die Aufnahme des Compilers in die VM hinzugefügt.
Bunt einfarbig
Durchschnittlich 0,67 Sekunden pro Lauf über 15 Läufe.
Colourful Monochrome
Ich muss nicht zustimmen, dass das Xoring eine Optimierung ist. Auch wenn die Codegröße klug ist, ändert Xoring die Leistungseigenschaften von VM nicht (korrigieren Sie mich, wenn ich falsch liege). Was ich mit Optimierung meinte, war das Ändern oder Entfernen von Anweisungen aus dem Eingabecode (z. B. Entfernen des redundanten POP ... PUSH) oder das Realisieren von 2 Anweisungen in einer Reihe, laden Sie das Register, damit eine entfernt werden kann usw.
Colourly Monochrome
EDIT: Eigentlich ist das eine Optimierung: Es fiel auf 0,64 Sekunden pro Lauf über 15 Läufe. Ich vermute, es verhindert Cache Thrashing oder etwas durch Verkürzen des Codes (oder entfernt redundante Speicherzugriffe)?
Bunt einfarbig
@ColorfullyMonochrome Einige Architekturen führen, wenn sie mit dem Xoring eines Registers für sich selbst dargestellt werden, den Befehl nicht aus, sondern setzen das Register einfach auf Null.
es1024
7

C, Score = 854 Byte × (~ 0,8 s / 2) × 0,5 [JIT] × 0,9 [Extensions] = ~ 154 Byte Sek

#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]);}

Kompilieren Sie mit gcc vm.c -ovm -m32 -weinem x86 POSIX-kompatiblen Betriebssystem.
Führen Sie mit ./vm < program, wo programeine binäre Programmdatei ist.

An der Geschwindigkeit arbeiten. Das Programm führt eine recht einfache Übersetzung des Eingabeprogramms in x86-Maschinencode durch und überlässt den Rest der CPU.

Hier ist zum Beispiel die Übersetzung des Testprogramms. ecx, esiUnd edientspricht R0, R1und R2verbunden ist; bhhält die Statusflags; eaxund edxsind Rubbelregister; Der Aufruf-Stack entspricht dem Stack der VM:

# 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

Ungolfed

Code-Snippet anzeigen

Ell
quelle
Wow ... mein JIT war ~ 900 Codezeilen (geschrieben in c ++) ...
Bunt einfarbig
Durchschnittlich 0,63 Sekunden pro Lauf für 15 Läufe.
Bunt einfarbig
2

CJam, 222 187 185 Bytes * (zu langsam / 2)

Ich wollte nur sehen, wie kurz ich eine Bytecode-VM bekommen kann, indem ich sie in CJam schreibe. Weniger als 200 Bytes scheinen ziemlich anständig zu sein. Es ist verdammt langsam, weil CJam selbst interpretiert wird. Das Ausführen des Testprogramms dauert Ewigkeiten.

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}/

Um es auszuführen, laden Sie den Java-Interpreter unter diesem SourceForge-Link herunter , speichern Sie den Code in vm.cjamund führen Sie ihn mit aus

java -jar cjam-0.6.2.jar vm.cjam

Das Programm erwartet den Bytecode auf STDIN. Ich habe keine Möglichkeit , noch Rohr binäre Daten in ein Programm gefunden, ohne Powershell ein abschließendes Zeilenumbruch Hinzufügen und Konvertieren 0x0azu 0x0d 0x0a, was wirklich ärgerlich ist. Der Code enthält 4 Bytes zum Korrigieren von that ( D-);), die ich nicht in die Gesamtzahl einbezogen habe, da das Programm diesen Bytecode nicht auf STDIN empfangen sollte, sondern nur in einer seltsam codierten Version . Wenn jemand eine Lösung dafür kennt, lass es mich wissen.

Leicht ungolfed:

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}/

Ich werde morgen eine richtige Erklärung hinzufügen.

Kurz gesagt, ich speichere alle Register, den Befehlszeiger und das Vergleichsflag in Variablen, damit ich den Stapel von CJam freihalten kann, um ihn als Stapel der VM zu verwenden.

Martin Ender
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Martin Ender
1
Durchschnitt von 15,279 Sekunden für 20 Iterationen. - 15 Tests. Das sind 2.12208333 Stunden pro Test.
Bunt einfarbig
1

python / c ++, score = 56.66

1435 Zeichen * .234 / 2 Sekunden * .5 [JIT] * .75 [Optimierung] * .90 [Zusätzliche Anweisungen]

Kompiliert das Eingabeprogramm nach c ++, führt gcc darauf aus und führt dann das Ergebnis aus. Die meiste Zeit wird in gcc verbracht.

Die eine Optimierung, die ich mache, ist, die Stapeloperationen auf explizite Variablen zu reduzieren, wenn es semantisch erlaubt ist. Es hilft viel, die Laufzeit des kompilierten Codes um das 10-fache zu verbessern (etwa 0,056 Sekunden, um die resultierende Binärdatei tatsächlich auszuführen). Ich bin nicht sicher, was gcc tut, um diese Verbesserung zu erzielen, aber es ist gut.

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

Könnte sicherlich noch etwas mehr golfen werden.

Keith Randall
quelle
Durchschnittlich 0,477 Sekunden pro Lauf über 15 Läufe.
Bunt einfarbig
1

Lua 5.2 (oder LuaJIT), 740 Bytes

Erster Versuch, nur minimal golfen. Diese Version funktioniert (zumindest im Testprogramm) und implementiert die zusätzlichen Opcodes, erfüllt jedoch nicht die vorzeichenlosen mathematischen Anforderungen und ist nicht besonders schnell. Als Bonus ist es jedoch eine VM, die in einer VM ausgeführt wird und so geschrieben ist, dass sie entweder interpretiert (ausgeführt mit PUC-Lua) oder als JIT (ausgeführt mit LuaJIT; weiterhin interpretiert, aber der Interpreter ist es jetzt JITted).

EDIT: Golf besser, immer noch groß.

BEARBEITEN: Ein schwerwiegender Fehler wurde behoben und die Arithmetik ist jetzt auf den unsigned longBereich beschränkt. Irgendwie ist es gelungen, die Größe davon abzuhalten, außer Kontrolle zu geraten, aber es gibt immer noch die falsche Antwort.

EDIT: Es stellte sich heraus, dass das Ergebnis korrekt war, die Ausgabe jedoch nicht. Umgestellt auf Drucken mit %ustatt %dund alles ist gut. Es wurden auch tabellenbasierte Register für Variablen herausgeschaltet, um die Größe und Geschwindigkeit etwas zu verbessern .

BEARBEITEN: Unter Verwendung der gotoAnweisung von Lua 5.2 (auch in LuaJIT verfügbar) habe ich den Interpreter durch "JIT-to-Lua" ersetzt, wodurch Code generiert wird, der direkt von der Lua-VM selbst ausgeführt wird. Ich bin nicht sicher, ob dies wirklich als JIT gilt, aber es verbessert die Geschwindigkeit.

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

Hier ist die ursprüngliche, lesbare Version.

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))
Criptychon steht bei Monica
quelle
Beim Ausführen Ihres Programms wurde folgende Fehlermeldung angezeigt : pastebin.com/qQBD7Rs8 . Erwarten Sie den Bytecode über stdin oder als Datei?
Bunt einfarbig
Es tut uns leid. Meine Binärdatei für Windows wurde beschädigt. Somit funktionierten alle GCC / Linux-Versionen, aber die Windows-Tests stürzten alle ab. Es wird jedoch weiterhin berichtet, dass R0 und R1 0 sind, während R2 1 ist.
Colourful Monochrome
Ich vermute, dass es nicht wirklich ausgeführt wird: Es dauerte durchschnittlich 33,8 ms (GCC dauert ~ 0,25 Sekunden).
Bunt einfarbig
Das Skript erwartet Bytecode als Datei, wobei der Dateiname in der Befehlszeile übergeben wird. Du hast aber recht, ich habe es verfolgt und es sieht so aus, als ob es nur die erste äußere Schleife macht. Zurück zum Zeichenbrett ...
Criptychon steht mit Monica
Das ist es, was ich bekomme, um in C zu denken und in Lua zu schreiben: Ich habe <in meinen Schleifen stattdessen verwendet <=, sodass die letzte Verzweigungsanweisung weggelassen wurde. Es wird immer noch die falsche Antwort angezeigt, aber jetzt dauert es ein paar Minuten, bis es fertig ist. :)
Criptychon steht mit Monica
1

C #

1505 1475 Bytes

Dies ist meine Version des Interpreters, die in C # geschrieben wurde. Ich glaube, ich könnte mehr optimiert / golfen, aber ich weiß nicht wirklich, wo;)

Golf Version:

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]);}}

bearbeiten

einige unnötige publicund privateModifikatoren entfernt:

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]);}}

nennen Sie es mit executable.exe filenamewo filenameist die Datei, die den zu interpretierenden Code enthält

Mein "Testprogramm":

# 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

Dolmetscher ungolfed mit längeren Namen Variablen, Klassen, ...

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
quelle