Plus petit interprète / VM Bytecode

17

Leaderboard - JIT Compiled (Lower is better)

  1. es1024 - 81,2 points (y compris un compilateur fonctionnel!)
  2. Kieth Randall - 116 points
  3. Ell - 121 points

Classement - Interprété (plus c'est bas, mieux c'est)

  1. Martin Büttner - 706654 points (environ 2 heures).
  2. manuscrit - 30379 points (97 secondes)

Votre mission, si vous l'acceptez, est d'écrire le plus petit interprète / VM de bytecode possible. La VM / interprète utilise une petite architecture CISC (les opérations peuvent varier en taille), avec la langue spécifiée ci-dessous. Une fois terminé, vous devez imprimer la valeur des 3 registres CPU pour prouver que la sortie correcte est imprimée (3 126 900 366).

Compilateur

Si vous souhaitez faire vos propres tests, un compilateur est affiché ci-dessous. N'hésitez pas à poster vos tests avec votre réponse.

Afficher l'extrait de code

Spécifications "VM"

La VM a 3 registres intégraux non signés 32 bits: R0, R1, R2. Ils sont représentés en hexadécimal comme 0x00, 0x01 et 0x02.

Les opérations suivantes doivent être prises en charge:

Le format est [nom] [... opérandes ...], [code op hexadécimal] [... opérandes répétés ...]

  • LOAD [registre] [valeur 4 octets], 0x00 [registre] [valeur 4 octets]
  • PUSH [registre], 0x02 [registre]
  • POP [registre], 0x03 [registre]
  • ADD [registre, 1 octet] [registre, 1 octet], 0x04 [registre] [registre]
  • SUB [registre, 1 octet] [registre, 1 octet], 0x05 [registre] [registre]
  • MUL [registre, 1 octet] [registre, 1 octet], 0x06 [registre] [registre]
  • DIV [registre, 1 octet] [registre, 1 octet], 0x07 [registre] [registre]
  • JMP [ligne de code, 4 octets], 0x08 [numéro de ligne de code de 4 octets]
  • CMP [registre, 1 octet] [registre, 1 octet], 0x09 [registre] [registre]
  • BRANCHLT [ligne de code, 4 octets], 0x0a [numéro de ligne de code 4 octets]

Quelques notes:

  • Les opérations mathématiques ci-dessus additionnent les valeurs de 2 registres ensemble, plaçant la sortie dans le premier registre.
  • CMP, l'opérateur de comparaison, doit comparer les valeurs de 2 registres et stocker la sortie dans un indicateur interne (cela peut être spécifique à l'implémentation) pour une utilisation future sur les instructions de branchement.
  • Si BRANCH est appelé avant CMP, sauf si BRANCHEQ est appelé, la «VM» ne doit pas se ramifier.
  • PUSH / POP sans surprise, push ou pop numéros de la pile.
  • Les opérateurs de saut et de branche passent à une opération spécifique (ligne de code), et non à une adresse binaire.
  • Les opérations des succursales ne font pas la comparaison. Au lieu de cela, ils prennent la sortie de la dernière comparaison pour s'exécuter.
  • Les opérateurs de branche et de saut utilisent un système d'indexation de numéro de ligne basé sur zéro. (Par exemple, JMP 0 saute à la première ligne)
  • Toutes les opérations doivent être effectuées sur des nombres non signés qui débordent à zéro et ne lèvent pas d'exception sur un dépassement d'entier.
  • La division par zéro n'est pas autorisée et en tant que tel, le comportement du programme n'est pas défini. Vous pouvez (par exemple) ...
    • Arrêtez le programme.
    • Arrêtez l'exécution de la machine virtuelle et retournez son état actuel.
    • Afficher un message "ERR: Division by 0".
  • La fin du programme est définie comme lorsque le pointeur d'instruction atteint la fin du programme (un programme non vide peut être supposé).

Sortie La sortie doit être exactement celle-ci (nouvelles lignes incluses)

R0 3126900366
R1 0
R2 10000

Points Les points sont calculés selon la formule suivante:Number Of Characters * (Seconds Needed To Run / 2)

Pour éviter les différences matérielles provoquant des heures différentes, chaque test sera exécuté sur mon ordinateur (i5-4210u, 8 Go de RAM) dans le serveur Ubuntu ou Windows 8, alors essayez de ne pas utiliser un runtime fou-exotique qui ne se compile que sur un Dual G5 Mac Pro avec exactement 762,66 Mo de RAM libre.

Si vous utilisez un runtime / langage spécialisé, veuillez poster un lien vers celui-ci.

Programme de test

L'idée est venue d' ici , nous allons donc utiliser une version quelque peu modifiée de leur programme.

La sortie correcte pour le programme est: 3 126 900 366

En C:

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

Dans le code: [R0 est représentatif de s, R1 de j, R2 de 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

En binaire / 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

Points bonus (les effets sont appliqués de manière multiplicative) Par exemple, si vous vous qualifiez pour les trois, ce serait ((caractères * 0,50) * 0,75) * 0,90

  • Baisse de 50% si l'interpréteur est en fait un compilateur JIT
  • 25% de diminution si elle applique une quelconque sorte de déroulement de boucle / optimisation significative.
  • 10% de diminution si vous étendez la machine virtuelle avec
    • BRANCHEQ [ligne de code, 4 octets] (Branche si égale - opcode 0x0b)
    • BRANCHGT [ligne de code, 4 octets] (Branche si supérieure à - opcode 0x0c)
    • BRANCHNE [ligne de code, 4 octets] (Branche si différente - opcode 0x0d)
    • RLOAD [registre 1] [registre 2] (déplacez la valeur du registre 2 vers le registre 1 - opcode 0x01).

Rejeté

  • La précompilation du cas de test dans le programme est interdite. Vous devez accepter le bytecode de STDIN ou d'un fichier (peu importe lequel).
  • Renvoyer la sortie sans exécuter le programme.
  • De toute autre manière à laquelle vous pouvez penser pour tromper l'exigence VM.
code-challenge interpreter stack Coloré monochrome
la source
Pourquoi ne pas inclure quelques programmes de test supplémentaires pour décourager les choses que vous avez dites interdites? S'il s'agit d'une machine virtuelle, elle devrait pouvoir exécuter tout ce qui est écrit dans la spécification de bytecode, non?
Kasran
J'essaierai de le faire ce soir. J'écris le compilateur en ce moment.
Monochrome coloré
Le compilateur est ici jsfiddle.net/aL9y19bd/23
Colorfully Monochrome
1
CMPVérifie- t-il moins que ou l'égalité? Et qu'advient-il de son résultat?
es1024
1
MULet DIVsont également sous-spécifiés. Doivent-ils être signés ou non signés? Que se passe-t-il en cas de débordement de multiplication?
feersum

Réponses:

8

C, 752 (589 + 163 pour définir les drapeaux) * 0,5 (JIT) * 0,9 (extensions) * (0,75 optimisation) * (0,64 seconde / 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);}

Prend du code (LOAD R0 , etc.), pas de caractères de fin, un seul espace, pas de lignes vides au milieu, pas de commentaires, etc. Retour à la ligne requis.

Il est ensuite converti en 80386 bytecode et exécuté.

Le chargement 0dans un registre est remplacé par xoring le registre avec lui-même au lieu d' moving 0dans le registre, qui est trois octets plus court dans le bytecode généré, et peut être très légèrement plus rapide.

Compiler avec:

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

Système d'exploitation compatible POSIX requis.

L'entrée est lue depuis STDIN (à utiliser ./bytecode < filepour diriger à partir d'un fichier).

Bytecode résultant pour le programme de test: 

; 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

Non golfé: 

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
la source
Sensationnel. Je souhaite que j'aurais ajouté un bonus pour inclure le compilateur dans la machine virtuelle.
Monochrome coloré
Moyenne de 0,67 seconde par course sur 15 courses.
Monochrome coloré du
Je ne suis pas d'accord pour dire que le xoring est une optimisation. Bien que intelligent en termes de taille de code, xoring ne change pas les caractéristiques de performance de VM (corrigez-moi si je me trompe). Ce que je voulais dire par optimisation, c'était de changer ou de supprimer des instructions du code d'entrée (par exemple, supprimer le POP ... PUSH redondant) ou de réaliser 2 instructions d'affilée charger le registre, de sorte qu'une puisse être supprimée, etc.
Monochrome coloré
EDIT: En fait, c'est une optimisation: elle est tombée à 0,64 seconde par exécution sur 15 exécutions. Je suppose que cela empêche le cache du cache ou quelque chose en raccourcissant le code (ou supprime les accès mémoire redondants)?
Monochrome coloré
@ColorfullyMonochrome Certaines architectures, lorsqu'elles sont présentées avec le xoring d'un registre pour elles-mêmes, n'exécutent pas réellement l'instruction, mais simplement mettent à zéro le registre lui-même.
es1024
7

C, Score = 854 octets × (~ 0,8 s / 2) × 0,5 [JIT] × 0,9 [Extensions] = ~ 154 octets 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]);}

Compilez avec gcc vm.c -ovm -m32 -wsur un système d'exploitation compatible x86 POSIX.
Exécuter avec ./vm < program, où programest un fichier programme binaire.

Aller pour la vitesse. Le programme effectue une traduction assez simple du programme d'entrée en code machine x86 et laisse le CPU faire le reste.

Par exemple, voici la traduction du programme de test. ecx, esiEt edicorrespondent à R0, R1et R2, respectivement; bhdétient les drapeaux d'état; eaxet edxsont des registres à gratter; la pile d'appels correspond à la pile de la 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

Non golfé

Afficher l'extrait de code

Aune
la source
Wow ... mon JIT était ~ 900 lignes de code (écrit en c ++) ...
Colorfully Monochrome
Moyenne de 0,63 seconde par course pour 15 courses.
Monochrome coloré
2

CJam, 222 187 185 octets * (trop lent / 2)

Je voulais juste voir combien de temps je peux obtenir une machine virtuelle bytecode en l'écrivant dans CJam. Moins de 200 octets semble assez décent. C'est sacrément lent, car CJam lui-même est interprété. Il faut du temps pour exécuter le programme de test.

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

Pour l'exécuter, téléchargez l'interpréteur Java sur ce lien sourceforge , enregistrez le code vm.cjamet exécutez-le avec

java -jar cjam-0.6.2.jar vm.cjam

Le programme attend le bytecode sur STDIN. Je n'ai pas encore trouvé de moyen de transférer des données binaires dans un programme, sans que PowerShell ajoute un saut de ligne de fin et ne se convertisse 0x0aen0x0d 0x0a , ce qui est vraiment ennuyeux. Le code comprend 4 octets pour corriger cela ( D-);), que je n'ai pas inclus dans le nombre total, car ce n'est pas quelque chose que le programme devrait faire s'il a effectivement reçu le bytecode lui-même sur STDIN, au lieu d'une version étrangement encodée de celui-ci . Si quelqu'un connaît un correctif pour cela, faites-le moi savoir.

Légèrement non golfé:

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

J'ajouterai une explication appropriée demain.

En bref, je stocke tous les registres, le pointeur d'instruction et l'indicateur de comparaison dans des variables, afin que je puisse garder la pile de CJam libre d'utiliser comme pile de la VM.

Martin Ender
la source
Continuons cette discussion dans le chat .
Martin Ender
1
15,279 secondes en moyenne pour 20 itérations. - 15 tests. Cela signifie 2,12208333 heures par test.
Monochrome coloré
1

python / c ++, score = 56,66

1435 caractères * .234 / 2 secondes * .5 [JIT] * .75 [Optimisation] * .90 [Instructions supplémentaires]

Compile le programme d'entrée en c ++, exécute gcc dessus, puis exécute le résultat. La plupart du temps est passé à l'intérieur de gcc.

La seule optimisation que je fais est de réduire les opérations de pile en variables explicites si cela est autorisé sémantiquement. Cela aide beaucoup, environ 10 fois mieux l'exécution du code compilé (environ 0,056 sec pour exécuter réellement le binaire résultant). Je ne sais pas ce que fait gcc qui vous apporte cette amélioration, mais c'est bien.

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

Pourrait certainement être joué au golf un peu plus.

Keith Randall
la source
Moyenne de 0,477 seconde par course sur 15 courses.
Monochrome coloré
1

Lua 5.2 (ou LuaJIT), 740 octets

Premier essai, golf minimalement. Cette version fonctionne (au moins sur le programme de test) et implémente les opcodes supplémentaires, mais ne respecte pas l'exigence mathématique non signée et n'est pas particulièrement rapide. En bonus, cependant, c'est une machine virtuelle exécutée dans une machine virtuelle, et est écrite de telle sorte qu'elle peut être interprétée (exécutée avec PUC-Lua) ou sorte de JIT (exécutée avec LuaJIT; toujours interprétée, mais l'interpréteur est maintenant JITted).

EDIT: Golf mieux, toujours gros.

EDIT: correction d'une erreur majeure et restreignant désormais l'arithmétique à la unsigned longplage. D'une manière ou d'une autre, j'ai réussi à empêcher la taille de devenir incontrôlable, mais cela donne toujours la mauvaise réponse.

EDIT: Il s'avère que le résultat était correct mais la sortie ne l'était pas. Passé à l'impression avec %uau lieu de %det tout va bien. Également désactivé les registres basés sur des tables pour les variables afin d'améliorer quelque peu la taille et la vitesse.

EDIT: En utilisant la gotodéclaration de Lua 5.2 (également disponible dans LuaJIT), j'ai remplacé l'interpréteur par "JIT-to-Lua", générant du code qui est exécuté directement par la machine virtuelle Lua elle-même. Je ne sais pas si cela compte vraiment comme JIT, mais cela améliore la vitesse.

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

Voici la version originale et lisible.

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))
criptych se tient avec Monica
la source
Lorsque j'ai exécuté votre programme, j'ai eu l'erreur suivante: pastebin.com/qQBD7Rs8 . Vous attendez-vous au bytecode sur stdin ou sous forme de fichier?
Monochrome coloré
Pardon. Mon binaire pour Windows a été corrompu. Ainsi, toutes les versions de gcc / linux ont fonctionné mais les tests windows se sont tous plantés. Cependant, il indique toujours que R0 et R1 sont 0, tandis que R2 est 1.
Colorically Monochrome
Je soupçonne qu'il ne s'exécute pas réellement: il a fallu 33,8 ms pour fonctionner en moyenne (GCC prend ~ 0,25 seconde).
Monochrome coloré
Le script attend le bytecode en tant que fichier, avec le nom de fichier transmis sur la ligne de commande. Vous avez raison cependant, je l'ai tracé et on dirait qu'il ne fait que la première boucle externe. Retour à la planche à dessin...
manuscrit se tient avec Monica
C'est ce que j'obtiens en pensant en C et en écrivant en Lua: j'ai utilisé < dans mes boucles au lieu de <=, donc l'instruction finale de branchement a été laissée de côté. Il obtient toujours la mauvaise réponse, mais cela prend maintenant quelques minutes pour le faire. :)
criptych se tient avec Monica
1

C #

1505 1475 octets

Ceci est ma version de l'interpréteur, écrite en C # pourrait être optimisée / golfée plus je pense, mais je ne sais pas vraiment où;)

version golfée:

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

Éditer

supprimé certains inutiles publicet privatemodificateurs:

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

appeler avec executable.exe filenameoù se filenametrouve le fichier contenant le code à interpréter

Mon "programme de test":

# 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

Interprète non golfé avec des variables de noms plus longs, des classes, ...

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
la source