인터프리터 해적

1. 인터프리터를 만들어라. 인터프리터는 int run_code(unsigned char* code, int size, int arg) 로 구현된다. run_code 는 arg 값을 R0 (0 번 레지스터) 에 저장 한 뒤 unsigned char 배열로 된 code 를 실행하고 R0 의 값을 반환한다. 배열의 각 인자(1 개의 unsigned char)은 하나의 명령어에 대응된다. 레지스터와 스택의 범위는 int 범위 이다. 코드는 아래와 같이 정의된다. 총 8 비트 중 상위 3 비트는 아래와 같이 명령어를 나타낸다. SET   000 ADD   001 SUB   010 MUL   011 POP   100 PUSH  101 GOTO  110 LABEL 111 SET 은 R0 에 하위 5 비트의 값을 저장한다. ex) 00010101 => R0 에 21 저장 ADD, SUB, MUL 명령에서 하위 5 비트는 피연산자 레지스터 번호를 나타낸다. 피연산자 레지스터는 0 ~ 16 번까지 총 17개만 존재한다. R0 과 해당 피연산자 레지스터의 연산의 결과를 R0 에 저장한다. 여기서 R0 는 항상 좌항 연산자이다. ex) 001 00010 => R0 + R2 의 값을 R0 에 저장 ex) 010 10000 => R0 - R16 의 값을 R0 에 저장 POP, PUSH 명령에서도 하위 5 비트는 피연산자 레지스터 번호를 나타낸다. 피연산자 레지스터로 데이터를 스택에 PUSH 또는 스택으로부터 POP 한다. 스택의 최대 크기는 1000 이며, 스택에 데이터가 없는 경우나, 스택이 가득찬 경우는 작동하지 않는다. ex) 100 01000 => 스택에서 값을 POP 하여 R8 에 반영한다. ex) 101 00000 => R0 의 값을 스택으로 PUSH 한다. GOTO 에서 하위 4 비트는 LABLE 번호를 나타낸다. 그리고 나머지 중간의 1비트 즉 상위에서 4번째, 하위에서 5번째 비트는 작동 방식을 결정한다. 나머지 중간의 1비트가 0 일 경우 R0 이 0 일 때, LABEL 로 이동한다. 1 일 경우, R0 이 0 이 아닐 때, LABEL 로 이동한다. 단, LABEL 이 존재하지 않는 경우 무시된다. ex) 110 1 0010 => R0 이 0 이 아닐때 LABEL2 로 이동 ex) 110 0 0101 => R0 이 0 일 때 LABEL5 로 이동 LABLE 에서 하위 4 비트는 LABLE 번호를 나타낸다. 그리고 나머지 중간비트는 사용되지 않는다. 같은 레이블은 코드에 오직 한 번 이하만 등장한다. ex) 111 0 0001 => LABLE 1 을 의미 2. 아래의 조건에 맞춰 위의 인터프리터의 코드를 int make_code(unsigned char* code) 에 작성하라. 수열 An 은 다음과 같이 정의된다. n 이 2 의 배수면서 3 의 배수가 아닐 때, An = 0; n 이 3 의 배수면서 2 의 배수가 아닐 때, An = 2n; n 이 6 의 배수, An = -n; 그 외, An = n 초기 R0 (0 번 레지스터) 번에 있는 값을 인자(arg)로 해서 수열 A_0 부터 A_R0 를 각각 구하고 그 합을 더한 결과 ( Sum_{k=1...R0} Ak ) 을  R0 에 저장하는 코드를 만들어라. 코드는 unsigned char* code 배열에 입력하고, 코드의 길이(int 형) 를 반환하여라. *** New Information *** 실제 결과에 맞게 PASS 점수 수정하였습니다.

#define SET 0 #define ADD 1 #define SUB 2 #define MUL 3 #define POP 4 #define PUSH 5 #define JMP 6 #define LABEL 7 #define JMPN 7 inline unsigned char masm(int cmd, int arg) { return cmd != JMP || arg >= 0 ? (cmd << 5) | arg : (cmd << 5) | 16 | (-arg); } int make_init(unsigned char *code, int p) { code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 2); code[p++] = masm(SET, 1); code[p++] = masm(ADD, 2); code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 2); // R2 = arg + 1; code[p++] = masm(SET, 1); code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); // R1 = 1 code[p++] = masm(SET, 0); return p; } int make_loopbegin(unsigned char *code, int p) { code[p++] = masm(LABEL, 1); return p; } int make_loop(unsigned char *code, int p) { code[p++] = masm(ADD, 1); // 1st, r0 = r0 + r1; code[p++] = masm(PUSH, 0); code[p++] = masm(SET, 1); code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(SET, 1); // 2nd code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(POP, 0); code[p++] = masm(ADD, 1); // 3rd, r0 = r0 + r1; code[p++] = masm(ADD, 1); code[p++] = masm(PUSH, 0); code[p++] = masm(SET, 1); code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(SET, 1); // 4th code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(POP, 0); code[p++] = masm(ADD, 1); // 5th, r0 = r0 + r1; code[p++] = masm(PUSH, 0); code[p++] = masm(SET, 1); code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(POP, 0); code[p++] = masm(SUB, 1); // 6th, r0 = r0 - r1; code[p++] = masm(PUSH, 0); code[p++] = masm(SET, 1); code[p++] = masm(ADD, 1); // ++r1; code[p++] = masm(PUSH, 0); code[p++] = masm(POP, 1); code[p++] = masm(SUB, 2); code[p++] = masm(JMP, 2); // if r0 == 0 goto end code[p++] = masm(POP, 0); return p; } int make_loopend(unsigned char *code, int p) { code[p++] = masm(JMP, -1); code[p++] = masm(LABEL, 2); return p; } int make_end(unsigned char *code, int p) { code[p++] = masm(POP, 0); // pop r0 return p; } int make_code(unsigned char *code) { int p = 0; p = make_init(code, p); p = make_loopbegin(code, p); p = make_loop(code, p); p = make_loopend(code, p); p = make_end(code, p); return p; } int run_code(unsigned char *code, int size, int arg) { int cmd[10000]; int par[10000]; int SP, S[1000]; int label[16]; int R[17]; for (int i = 0; i < 16; ++i) label[i] = -2; register int p = 0; for (register int i = 0; i < size; ++i) { cmd[p] = code[i] >> 5; if (cmd[p] == LABEL){ label[code[i] & 0x0f] = p - 1; continue; } if (cmd[p] == JMP) { if (code[i] & 0x10) cmd[p] = JMPN; par[p] = code[i] & 0x0f; } else { par[p] = code[i] & 0x1f; } ++p; } size = p; for (int i = 0; i < 16; ++i) R[i] = 0; R[0] = arg; SP = 0; p = 0; while(p < size) { int &c = cmd[p], &a = par[p]; if (c < 4) { if (c < 2) { if (c == 0) { R[0] = a; } else { R[0] += R[a]; } } else { if (c == 2) { R[0] -= R[a]; } else { R[0] *= R[a]; } } } else { if (c < 6) { if (c == 4) { if (SP > 0) R[a] = S[--SP]; } else { if (SP < 1000) S[SP++] = R[a]; } } else { if (c == 6) { if (!R[0] && label[a] != -2) p = label[a]; } else { if (R[0] && label[a] != -2) p = label[a]; } } } ++p; } return R[0]; }

1. 비트 연산자 2. 사용법 3. main, user 해석