문제

디지털하드웨어설계 과목의 최종 프로젝트는 16-bit CPU를 설계하고 Verilog 언어로 구현하는 것이다. 본인이 구현한 CPU가 제대로 동작하는지 테스트하기 위해서는 기계어 코드를 입력으로 주어야 한다. 하지만 대부분의 사람은 0과 1로만 이루어진 기계어 코드를 이해하기 힘들어서 C++, Java와 같은 프로그래밍 언어로 코드를 작성하고 컴파일러를 통해 기계어 코드로 번역하는 과정을 거친다.

여러 가지 프로그래밍 언어 중에서 어셈블리어는 사람이 이해하기 쉬우면서 기계어와 가장 유사한 언어이다. 어셈블리어 코드는 어셈블러를 통해 기계어 코드로 번역된다. 그리고 어셈블리어는 기계어와 일대일로 대응하는 특징이 있다. 예를 들면, 두 수의 합을 구하는 연산의 어셈블리어 코드가 ADD이고, 기계어 코드가 00000이면 어셈블러는 ADD를 읽어서 그대로 00000로 바꾸어주는 것이다.

아래의 그림은 민호가 설계한 CPU가 처리할 수 있는 16-bit 단위 명령어들의 구조를 모아놓은 표이다.

입력과 출력은 항상 명령어 단위이며, 어셈블리어 코드는 "opcode rD rA rB" 또는 "opcode rD rA #C"의 형태이다. 기본적으로 레지스터 rA와 rB에 있는 두 수 또는 레지스터 rA에 있는 수와 상수 #C를 opcode에 해당하는 연산을 수행하고, 그 결괏값을 레지스터 rD에 저장하는 명령어이다. rA는 opcode에 따라 사용하지 않을 수도 있다. 어셈블러는 opcode, rD, rA, rB, #C를 각 bit의 자리에 맞게 2진수 0과 1로 이루어진 16-bit 기계어 코드로 변역한다. bit마다 자리의 의미는 아래와 같다.

0~4 : CPU가 수행해야 할 연산을 나타내는 opcode이다. 만약 4번 bit가 0일 경우 레지스터 rB를, 1일 경우 상수 #C를 사용한다.
5 : 사용하지 않는 bit이며, 항상 0이다.
6~8 : 결괏값을 저장하는 레지스터 rD의 번호이다.
9~11 : 연산에 사용되는 레지스터 rA의 번호이다. 사용하지 않을 경우에는 000이다.
12~15 : 만약 4번 bit가 0일 경우 12~14번 bit는 연산에 사용되는 레지스터 rB의 번호이며, 15번 bit는 항상 0이다. 만약 4번 bit가 1일 경우 12~15번 bit는 상수 #C이다.

디지털하드웨어설계 과목을 듣는 민호는 Verilog로 16-bit CPU 구현을 일찍 끝내 놓은 상태이다. 이 16-bit CPU를 테스트하기 위해서는 기계어를 매번 입력으로 줘야 하는데, 너무나 귀찮은 민호는 이에 맞는 어셈블러를 구현하려고 한다. 민호가 직접 설계한 16-bit CPU의 명령어 구조 표를 보고, 어셈블리어 코드가 주어졌을 때 이를 기계어 코드로 번역하는 어셈블러를 만들어보자.

입력

첫 번째 줄에는 명령어의 개수를 의미하는 정수 N (1 ≤ N ≤ 500)이 주어진다.

다음 N개의 각 줄에는 명령어가 어셈블리어 코드로 "opcode rD rA rB" 또는 "opcode rD rA #C"의 형태로 주어진다. 문자열 opcode는 항상 대문자이다. 정수 rD, rA, rB (0 ≤ rD, rA, rB ≤ 7)는 레지스터 번호를 의미한다. 사용하는 레지스터 번호는 1부터 7까지이며, 사용하지 않을 경우에만 0이 주어진다. 정수 #C (0 ≤ #C ≤ 15)는 상수를 의미한다.

기계어 코드로 번역될 때 어긋나는 입력은 주어지지 않는다.

출력

N개의 각 줄에 어셈블리어 코드를 기계어 코드로 번역하여 출력한다.

예제 입력

4
MOVC 1 0 5
MOVC 2 0 10
ADD 3 1 2
SUB 4 1 2

예제 출력

0010100010000101
0010100100001010
0000000110010100
0001001000010100

내가 했던 풀이 방법

1. 명령어를 입력받고, 공백을 기준으로 나누어준다. (trim을 이용해 나누기 전 \r을 제거한 뒤 나누어준다.)

2. getOpcode 함수를 이용해 opcode를 기계어로 변환해준 값을 machine_code에 저장해준다. (getOpcode는 입력받은 명령어를 if문을 통해 값을 넣어준다. 만약, 명령어가 C로 끝날 경우에는 1을 뒤에 더해주고, 아닌 경우는 0을 더해준다. (ADD, ADDC를 예를 들면 0000으로 같지만, ADD는 00000, ADDC는 00001로 C로 끝나는 명령어는 4번 비트가 1이기 때문이다.) return시에 0을 추가로 더해준다. (5번 비트는 항상 0이기 때문에)

3. 그 이후 모든 값(레지스터 번호/상수)은 getBinary 함수를 이용해 기계어로 변역해준다. 이진수로 변환한 뒤, 입력받은 size를 통해 binary의 length가 size가 될 때까지 앞에 0을 붙여준다.

4. 4번비트의 값이 0일 경우 모든 값을 3비트로 표현해준 뒤 마지막에 0을 추가해주고, 1일 경우 상수를 4비트로 표현해준다. (이진수로 변환시 같은 함수를 사용해주기 위해 getBinary 함수에 size 파라미터를 추가해주었다.)

5. 해당 명령어가 마지막 명령어가 아니라면, 해당 명령어를 번역 후, \n을 추가해주어 명령어들을 구분해준다. (console.log를 한 번에 처리하기 위함)

코드

const fs = require('fs');
const [n, ...input] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let machine_code = '';
for (let i = 0; i < input.length; i++) {
  input[i] = input[i].trim().split(' ');
  machine_code += getOpcode(input[i][0]);
  if (getOpcode(input[i][0]).charAt(4) === '0') {
    machine_code += getBinary(parseInt(input[i][1]), 3);
    machine_code += getBinary(parseInt(input[i][2]), 3);
    machine_code += getBinary(parseInt(input[i][3]), 3);
    machine_code += '0';
  } else {
    machine_code += getBinary(parseInt(input[i][1]), 3);
    machine_code += getBinary(parseInt(input[i][2]), 3);
    machine_code += getBinary(parseInt(input[i][3]), 4);
  }
  if (i !== input.length - 1) {
    machine_code += '\n';
  }
}

console.log(machine_code);

function getOpcode(opcode) {
  let binary = '';

  if (opcode === 'ADD' || opcode === 'ADDC') {
    binary = '0000';
  } else if (opcode === 'SUB' || opcode === 'SUBC') {
    binary = '0001';
  } else if (opcode === 'MOV' || opcode === 'MOVC') {
    binary = '0010';
  } else if (opcode === 'AND' || opcode === 'ANDC') {
    binary = '0011';
  } else if (opcode === 'OR' || opcode === 'ORC') {
    binary = '0100';
  } else if (opcode === 'NOT') {
    binary = '0101';
  } else if (opcode === 'MULT' || opcode === 'MULTC') {
    binary = '0110';
  } else if (opcode === 'LSFTL' || opcode === 'LSFTLC') {
    binary = '0111';
  } else if (opcode === 'LSFTR' || opcode === 'LSFTRC') {
    binary = '1000';
  } else if (opcode === 'ASFTR' || opcode === 'ASFTRC') {
    binary = '1001';
  } else if (opcode === 'RL' || opcode === 'RLC') {
    binary = '1010';
  } else if (opcode === 'RR' || opcode === 'RRC') {
    binary = '1011';
  }

  if (opcode.charAt(opcode.length - 1) === 'C') {
    binary += 1;
  } else {
    binary += 0;
  }
  return binary + '0';
}

function getBinary(num, size) {
  let binary = '';

  while (true) {
    if (num === 0) break;
    binary = (num % 2) + binary;
    num = Math.floor(num / 2);
  }

  while (true) {
    if (binary.length === size) break;
    binary = '0' + binary;
  }

  return binary;
}

회고

문제 길이가 길기도 하고, 어셈블리어/기계어가 나오는 순간 이 문제를 풀기가 괜시리 겁이나 오랫동안 못본척하던 문제였는데 정답률도 높고, 티어도 낮은 편이라 쉬울 것 같으니 풀어보자는 마음이 들어서 풀어봤는데 정말 어렵게 구현할 부분이 없는 수준이었던 것 같다. 그냥 이진수 변환하는 문제? opcode 때문에 코드가 길어지긴 했지만, 막혔던 부분도 없고 재밌게 풀이한 것 같다. 앞으로는 문제의 길이에 쫄지 않도록 하겠다..