리더 보드-JIT 컴파일 (낮을수록 좋음)
- es1024-81.2 점 (작동중인 컴파일러 포함)
- 키 에트 랜달-116 포인트
- 엘-121 포인트
리더 보드-해석 됨 (낮을수록 좋음)
- Martin Büttner-706654 점 (약 2 시간 정도).
- criptych-30379 포인트 (97 초)
당신의 임무는 당신이 그것을 받아들이도록 선택한다면 가능한 가장 작은 바이트 코드 인터프리터 / VM을 작성하는 것입니다. VM / 인터프리터는 아래에 지정된 언어로 작은 CISC 아키텍처 (작업 크기가 다를 수 있음)를 사용합니다. 완료되면 3 개의 CPU 레지스터 값을 인쇄하여 올바른 출력이 인쇄되었음을 증명해야합니다 (3,126,900,366).
컴파일러
자체 테스트를 원한다면 컴파일러가 아래에 게시되어 있습니다. 답을 가지고 테스트를 게시하십시오.
window.compile=function(){var e=$("#text").val().toLowerCase().match(/[^\r\n]+/g);var t=[];for(var n=0;n<e.length;n++)compileLine(e[n],t);var r="";for(var n=0;n<t.length;n++)if(typeof t[n]=="string")r+="\n";else r+="0x"+t[n].toString(16)+" ";$("#compiledArray").val(r)};window.compileLine=function(e,t){var n=e.split(" ");if(n[0]=="load"){t.push(0);t.push(getInt(n[1]));t.pushArr(getInt(n[2]))}if(n[0]=="rload"){t.push(1);t.push(getInt(n[1]));t.push(getInt(n[1]))}if(n[0]=="push"){t.push(2);t.push(getInt(n[1]))}if(n[0]=="pop"){t.push(3);t.push(getInt(n[1]))}if(n[0]=="add"){t.push(4);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="sub"){t.push(5);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="mul"){t.push(6);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="div"){t.push(7);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="jmp"){t.push(8);t.pushArr(getInt(n[1]))}if(n[0]=="cmp"){t.push(9);t.push(getInt(n[1]));t.push(getInt(n[2]))}if(n[0]=="branchlt"){t.push(10);t.pushArr(getInt(n[1]))}if(n[0]=="brancheq"){t.push(11);t.pushArr(getInt(n[1]))}if(n[0]=="branchgt"){t.push(12);t.pushArr(getInt(n[1]))}if(n[0]=="branchne"){t.push(13);t.pushArr(getInt(n[1]))}t.push("NEW LINE")};window.getInt=function(e){if(e.trim().startsWith("<--"))return"COMMENT";if(e=="r0")return 0;if(e=="r1")return 1;if(e=="r2")return 2;if(e.startsWith("0x"))return parseInt(e,16);if(isNaN(parseInt(e)))alert(e);return getIntBytes(parseInt(e))};if(typeof String.prototype.startsWith!="function"){String.prototype.startsWith=function(e){return this.slice(0,e.length)==e}}Array.prototype.pushArr=function(e){this.push.apply(this,e)};window.getIntBytes=function(e){var t=[];var n=4;do{t[--n]=e&255;e=e>>8}while(n);return t}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<textarea id="text" cols="40" rows="10"></textarea>
<br/>
<button onclick="compile()">Compile</button>
<br/>
<textarea id="compiledArray" cols="40" rows="10" readonly></textarea>
“VM”사양
VM에는 3 개의 32 비트 부호없는 정수 레지스터 R0, R1, R2가 있습니다. 16 진수로 0x00, 0x01 및 0x02로 표시됩니다.
다음 작업이 지원되어야합니다.
형식은 [이름] [… 피연산자 …], [16 진수 연산 코드] [… 피연산자 반복 …]입니다.
- LOAD [레지스터] [4 바이트 값], 0x00 [레지스터] [4 바이트 값]
- PUSH [등록], 0x02 [등록]
- POP [등록], 0x03 [등록]
- ADD [레지스터, 1 바이트] [레지스터, 1 바이트], 0x04 [레지스터] [레지스터]
- SUB [레지스터, 1 바이트] [레지스터, 1 바이트], 0x05 [레지스터] [레지스터]
- MUL [레지스터, 1 바이트] [레지스터, 1 바이트], 0x06 [레지스터] [레지스터]
- DIV [register, 1 byte] [register, 1 byte], 0x07 [register] [register]
- JMP [코드 라인, 4 바이트], 0x08 [4 바이트 코드 라인 번호]
- CMP [레지스터, 1 바이트] [레지스터, 1 바이트], 0x09 [레지스터] [레지스터]
- BRANCHLT [코드 라인, 4 바이트], 0x0a [4 바이트 코드 라인 번호]
몇 가지 참고 사항 :
- 위의 수학 연산은 2 개의 레지스터 값을 더하여 출력을 첫 번째 레지스터에 배치합니다.
- 비교 연산자 인 CMP는 2 개의 레지스터 값을 비교하고 나중에 분기 명령어에서 사용할 수 있도록 일부 내부 플래그 (구현에 따라 다를 수 있음)에 출력을 저장해야합니다.
- CRAN 전에 BRANCH를 호출 한 경우 BRANCHEQ를 호출하지 않으면 “VM”은 분기되지 않아야합니다.
- PUSH / POP는 당연히 스택에서 숫자를 푸시하거나 팝합니다.
- 점프 및 분기 연산자는 이진 주소가 아닌 특정 작업 (코드 라인)으로 이동합니다.
- 지점 작업은 비교를 수행하지 않습니다. 오히려 마지막 비교에서 출력을 가져와 실행합니다.
- 분기 및 점프 연산자는 0부터 시작하는 라인 번호 인덱싱 시스템을 사용합니다. (예 : JMP 0이 첫 번째 줄로 이동)
- 모든 연산은 0으로 오버 플로우되고 정수 오버 플로우에서 예외를 발생시키지 않는 부호없는 숫자에 대해 수행됩니다.
- 0으로 나누는 것은 허용되지 않으므로 프로그램의 동작은 정의되지 않습니다. 예를 들면 다음과 같습니다.
- 프로그램을 중단하십시오.
- VM의 실행을 종료하고 현재 상태를 반환합니다.
- “ERR : Division by 0″메시지를 표시하십시오.
- 프로그램 종료는 명령 포인터가 프로그램 끝에 도달 할 때와 같이 정의됩니다 (비 비어있는 프로그램을 가정 할 수 있음).
출력
출력은 정확히이 값이어야합니다 (줄 바꾸기 포함).
R0 3126900366
R1 0
R2 10000
포인트
포인트는 다음 공식을 기반으로 계산됩니다.Number Of Characters * (Seconds Needed To Run / 2)
다른 시간을 유발하는 하드웨어 차이를 피하기 위해 각 테스트는 우분투 서버 또는 Windows 8의 내 컴퓨터 (i5-4210u, 8GB 램)에서 실행되므로 Dual G5에서만 컴파일되는 미친 이국적인 런타임을 사용하지 마십시오 정확히 762.66MB의 사용 가능한 RAM이있는 Mac Pro.
특수한 런타임 / 언어를 사용하는 경우 링크를 게시하십시오.
- 관심있는 사람들을 위해 테스트 코드 (C #으로 작성)를 게시했습니다 : http://pastebin.com/WYCG5Uqu
테스트 프로그램
아이디어는 여기 에서 왔 으므로 약간 수정 된 버전의 프로그램을 사용합니다.
프로그램의 올바른 출력은 다음과 같습니다. 3,126,900,366
C에서 :
int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
for (j = 0; j < 10000; j++)
s += (i * j) / 3;
}
코드에서 : [R0은 s, j의 R1, i의 R2를 나타냄]
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
이진 / 육각으로 :
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
보너스 포인트
(효과는 곱셈으로 적용됨) 예를 들어 세 가지 모두에 해당되는 경우 ((문자 * 0.50) * 0.75) * 0.90
- 인터프리터가 실제로 JIT 컴파일러 인 경우 50 % 감소
- 루프 언 롤링 / 의미있는 최적화를 적용하면 25 % 감소합니다.
- VM을 확장하면 10 % 감소
- BRANCHEQ [코드 라인, 4 바이트] (동일한 지점-opcode 0x0b)
- BRANCHGT [코드 라인, 4 바이트] (분기보다 큰 경우-opcode 0x0c)
- BRANCHNE [코드 라인, 4 바이트] (동일하지 않은 지점-opcode 0x0d)
- RLOAD [레지스터 1] [레지스터 2] (레지스터 2의 값을 이동하여 레지스터 1-opcode 0x01).
허용되지 않음
- 테스트 케이스를 프로그램에 사전 컴파일하는 것은 금지되어 있습니다. STDIN 또는 파일에서 바이트 코드를 승인해야합니다 (어떤 것이 든 상관 없습니다).
- 프로그램을 실행하지 않고 출력을 반환합니다.
- VM 요구 사항을 속이려는 다른 방법.
답변
C, 752 (플래그 정의의 경우 589 + 163) * 0.5 (JIT) * 0.9 (확장자) * (0.75 최적화) * (0.64 초 / 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);}
코드를 취합니다 (LOAD R0
등), 후행 문자, 단일 공백, 중간에 빈 줄, 주석 없음 등을 합니다. 후행 줄 바꿈이 필요합니다.
그런 다음 80386 바이트 코드로 변환되어 실행됩니다.
로드 0
레지스터에 의해 교체 xor
자체 레지스터를 보내고 대신 mov
보내고0
생성 바이트에서 3 바이트 짧다 레지스터로, 매우 근소하게 더 빠를 수있다.
다음과 같이 컴파일하십시오.
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 호환 OS가 필요합니다.
STDIN에서 입력을 읽습니다 (사용 ./bytecode < file
파일에서 파이프로 ).
테스트 프로그램의 결과 바이트 코드 :
; 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
언 골프 드 :
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);
}
답변
C, 점수 = 854 바이트 × (~ 0.8 초 / 2) × 0.5 [JIT] × 0.9 [확장] = ~ 154 바이트 초
#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]);}
gcc vm.c -ovm -m32 -w
x86 POSIX 호환 OS에서 컴파일하십시오 .
와 실행 ./vm < program
, 어디 program
바이너리 프로그램 파일입니다.
속도를 간다. 이 프로그램은 입력 프로그램을 x86 머신 코드로 매우 간단하게 변환하여 CPU가 나머지 작업을 수행하도록합니다.
예를 들어, 다음은 테스트 프로그램의 번역입니다.
ecx
, esi
및 edi
에 해당R0
, R1
및 R2
각각에 ; bh
상태 플래그를 보유합니다. eax
및 edx
스크래치 레지스터이고; 콜 스택은 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
언 골프
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
#define MAX_INST_COUNT (1 << 20)
#define MAX_CODE_SIZE (8 * MAX_INST_COUNT)
#define PAGE_SIZE (1 << 12)
uintptr_t *targets[MAX_INST_COUNT], **targets_ptr = targets;
int32_t *fixups[MAX_INST_COUNT], **fixups_ptr = fixups;
char code[MAX_CODE_SIZE], *code_ptr = code;
uint32_t R[3];
const char* inst_defs[] = {
/* LOAD */ "\5\xb8 \1\0\4\1",
/* RLOAD */ "\2\x8b\xc0\2\1\1\1",
/* PUSH */ "\1\x50\1\0",
/* POP */ "\1\x58\1\0",
/* ADD */ "\2\x03\xc0\2\1\1\1",
/* SUB */ "\2\x2b\xc0\2\1\1\1",
/* MUL */ "\6\x8b\xc0\xf7\xe0\x8b\xc0\3\1\5\1\3",
/* DIV */ "\x8\x33\xd2\x8b\xc0\xf7\xf0\x8b\xc0\3\3\7\1\5",
/* JMP */ "\5\xe9 \5\1",
/* CMP */ "\5\x3b\xc0\x9f\x8a\xfc\2\1\1\1",
/* BRANCHLT */ "\x9\x8a\xe7\x9e\x0f\x82 \5\5",
/* BRANCHEQ */ "\x9\x8a\xe7\x9e\x0f\x84 \5\5",
/* BRANCHGT */ "\x9\x8a\xe7\x9e\x0f\x87 \5\5",
/* BRANCHNE */ "\x9\x8a\xe7\x9e\x0f\x85 \5\5"
};
int main() {
int i;
{
const char prologue[] =
/* PUSHAD */ "\x60"
/* MOV EBP, ESP */ "\x8b\xec"
/* MOV BH, 46h */ "\xb7\x46"
;
memcpy(code_ptr, prologue, sizeof(prologue) - 1);
code_ptr += sizeof(prologue) - 1;
}
{
const char reg[] = {1, 6, 7};
char r;
int op;
while ((op = getchar()) != EOF) {
const char* def = inst_defs[op];
int len = def[0];
memcpy(code_ptr, def + 1, len);
for (def += len + 1; *def; ) {
switch (*def++) {
case 1: code_ptr[*def++] |= reg[getchar()]; break;
case 2: code_ptr[*def++] |= reg[getchar()] << 3; break;
case 3:
r = reg[getchar()];
code_ptr[*def++] |= r; code_ptr[*def++] |= r << 3;
break;
case 5: *fixups_ptr = code_ptr + *def; ++fixups_ptr;
case 4:
for (i = 4; i; --i) code_ptr[*def + i - 1] = getchar();
++def;
break;
}
}
*targets_ptr = code_ptr; ++targets_ptr;
code_ptr += len;
}
*targets_ptr = code_ptr; ++targets_ptr;
while (fixups_ptr != fixups) {
--fixups_ptr;
**fixups_ptr = (char*)targets[**fixups_ptr] - (char*)*fixups_ptr - 4;
}
}
{
const char epilogue[] =
/* MOV R[0], ECX */ "\x3e\x89\x0d "
/* MOV R[1], ESI */ "\x3e\x89\x35 "
/* MOV R[2], EDI */ "\x3e\x89\x3d "
/* MOV ESP, EBP */ "\x8b\xe5"
/* POPAD */ "\x61"
/* RET */ "\xc3"
;
memcpy(code_ptr, epilogue, sizeof(epilogue) - 1);
for (i = 0; i < 3; ++i) *(uintptr_t*)&code_ptr[3 + 7 * i] = &R[i];
code_ptr += sizeof(epilogue) - 1;
}
mprotect(
(uintptr_t)code / PAGE_SIZE * PAGE_SIZE, MAX_CODE_SIZE,
PROT_READ | PROT_WRITE | PROT_EXEC
);
{ void (*program)(void) = code; program(); }
for (i = 0; i < 3; ++i) printf("R%d %u\n", i, R[i]);
return 0;
}
답변
CJam, 222 (187) 185 바이트 (* 너무 느려 / 2)
CJam에서 바이트 코드 VM을 작성하여 얼마나 짧은 지 알고 싶었습니다. 200 바이트 미만은 꽤 괜찮은 것 같습니다. CJam 자체가 해석되기 때문에 속도가 느립니다. 테스트 프로그램을 실행하는 데 오랜 시간이 걸립니다.
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}/
그것을 실행하려면 이 sourceforge 링크 에서 Java 인터프리터를 다운로드 하고 코드를 저장하고 다음으로 vm.cjam
실행하십시오.
java -jar cjam-0.6.2.jar vm.cjam
프로그램은 STDIN의 바이트 코드를 예상합니다. PowerShell에서 후행 줄 바꿈을 추가하고 변환하지 않고 바이너리 데이터를 프로그램에 파이프하는 방법을 아직 찾지 못했습니다.0x0a
에 0x0d 0x0a
정말 짜증나이다. 코드에는 4 바이트가 포함되어 있습니다.D-);
포함되지 않은 포함되어 있습니다. . 누군가가 그에 대한 해결책을 알고 있다면 알려주십시오.
약간 골퍼되지 않음 :
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}/
내일 적절한 설명을 추가하겠습니다.
즉, 모든 레지스터, 명령어 포인터 및 비교 플래그를 변수에 저장하여 CJam의 스택을 VM의 스택으로 자유롭게 사용할 수 있습니다.
답변
파이썬 / C ++, 점수 = 56.66
1435 자 * .234 / 2 초 * .5 [JIT] * .75 [최적화] * .90 [추가 지침]
입력 프로그램을 c ++로 컴파일하고 gcc를 실행 한 다음 결과를 실행합니다. 대부분의 시간은 gcc 내부에서 소비됩니다.
내가하는 한 가지 최적화는 스택 연산이 의미 적으로 허용되는 경우 명시 적 변수로 줄이는 것입니다. 컴파일 된 코드의 런타임보다 약 10 배 더 나은 런타임을 제공합니다 (실제로 결과 바이너리를 실행하는 데 약 .056 초). 나는 gcc가 무엇을하고 있는지 잘 모르겠지만 그 개선을 얻는다.
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")
확실히 더 많은 골프를 쳤다.
답변
Lua 5.2 (또는 LuaJIT), 740 바이트
먼저 최소한의 골프 만 시도하십시오. 이 버전은 (적어도 테스트 프로그램에서) 작동하며 추가 opcode를 구현하지만 서명되지 않은 수학 요구 사항을지지하지 않으며 특히 빠르지 않습니다. 그러나 보너스로 VM에서 VM이 실행 중이며 해석 (PUC-Lua로 실행) 또는 JIT 정렬 (LuaJIT으로 실행; 여전히 해석되지만 인터프리터는 현재 해석 가능하도록 작성되었습니다) 적합).
편집 : 더 큰 골프 여전히 골프.
편집 : 주요 오류가 수정되었으며 이제 산술을 unsigned long
범위로 제한 합니다. 그러나 어떻게 든 크기를 벗어나지 못했지만 여전히 잘못된 대답을하고 있습니다.
편집 : 결과는 정확하지만 출력은 올바르지 않습니다. %u
대신 인쇄로 전환하면 %d
모두 정상입니다. 또한 크기 와 속도를 다소 향상시키기 위해 변수에 대한 테이블 기반 레지스터를 전환했습니다 .
편집 : Lua 5.2의 goto
문 (LuaJIT에서도 사용 가능)을 사용하여 인터프리터를 “JIT-to-Lua”로 교체하여 Lua VM 자체에서 직접 실행하는 코드를 생성했습니다. 이것이 실제로 JIT로 계산되는지 확실하지 않지만 속도가 향상됩니다.
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))
원본을 읽을 수있는 버전은 다음과 같습니다.
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))
답변
씨#
1505 1475 바이트
이것은 C #으로 작성된 인터프리터의 내 버전으로, 더 많은 것을 생각하고 최적화 할 수 있지만 실제로는 어디에 있는지 모르겠습니다.)
골프 버전 :
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]);}}
편집하다
불필요 public
하고 private
수정자를 제거했습니다 .
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]);}}
executable.exe filename
어디서나 불러filename
해석 할 코드가 들어있는 파일이있는
내 “테스트 프로그램”:
# 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
더 긴 이름의 변수, 클래스로 해석되지 않은 해석기 …
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]);
}
}