8.1 배경

위와 같이 고수준 언어를 사용하면 얻을 수 있는 고수준 언어의 표현력이 있다.

1. sqrt나 power 같은 고급 연산을 필요에 따라 자유롭게 정의할 수 있다.
2. 정의도니 서브루틴을 마치 +와 * 같은 기본 연산처럼 자유롭게 호출할 수 있다.
3. 호출된 서브루틴이 실행되고 나면, 자동으로 코드 내의 다음 명령을 반환한다.

이렇게 자유로운 표현이 가능해지면, 우리는 알고리즘의 세계에 한층 더 가까운 추상적인 코드를 작성할 수 있다. 물론 추상화 수준이 높아질수록 저수준에서 해야 할 작업은 더 늘어난다. 우리가 편하게 고수준에서 프로그래밍을 하면 뒷단에서는 다음과 같은 일들이 일어난다.

위의 그림은 Main 함수에서 Sub Routine을 호출하기 전 상황을 그리고 있다. call 명령을 만나면, 스택에는 Sub Routine으로 넘겨줄 인자 값과, 다시 돌아올 주소 값, Main에서 사용하던 각종 세그먼트 정보(주소) 그리고 Sub Routine에서 사용할 지역 변수공간이 저장된다. Sub Routine에서의 작업이 모두 끝나면 Main으로 넘길 리턴 값을 스택에 push한다. 다시 Main 함수로 돌아가기 전에 스택에 저장했던 Main에서 사용하던 세그먼트 정보를 다시 불러오고 돌아갈 리턴 주소를 설정한다. 그리고 스택에 남은 인자 값, 지역 변수 공간은 이제 무시하고 그들이 있던 위치를 리턴 값이 대신한다. 마지막으로 설정된 리턴 주소로 점프하는 것으로 call Sub Routine 연산이 끝난다.

8.2 VM 명세 2부

8.2.1 프로그램 흐름 제어 명령

이 VM 언어에는 세 가지 프로그램 흐름 제어 명령이 있다.

• label LABEL
  • 현재 함수 코드 위치에 레이블을 붙인다. 그 위치로만 점프가 가능하다.

• goto LABEL
  • 무조건 분기 명령으로, LABEL 위치부터 실행하라는 명령이다.
• if-goto LABEL
  • 스택의 최상단 값을 꺼내서 그 값이 0이 아니면 LABEL 위치에서 실행을 계속하고, 0이면 프로그램 다음 명령을 실행한다.

8.2.2 함수 호출 명령

• function F n
  • 이름이 F고 지역 변수가 n개인 함수 코드가 시작된다.

• call F m
  • 함수 F를 호출한다. 이때 스택에 m개의 인수가 push되었다는 정보도 같이 전달한다.
• return
  • 호출한 함수의 다음 위치로 점프한다.

8.2.3 함수 호출 규약

• 호출하는 함수 관점:

  • 함수를 호출하기 전에 호출자는 필요한 수의 인수를 스택에 푸시해야 한다.
  • 다음으로 호출자는 call 명령으로 함수를 불러온다.
  • 호출된 함수가 바노한된 후에는, 호출자가 호출하기 전에 푸시한 인수들은 스택에서 사라지고 반환 값이 스택 최상단에 있게 된다.
  • 호출된 함수가 반환된 후에, 호출자의 메모리 세그먼트들은 호출 전과 동일하며, temp 세그먼트는 미정의 상태다.

• 호출되는 함수 관점:

  • 호출된 함수가 실행을 시작할 때, argument 세그먼트는 호출자가 넘겨준 실제 인수 값으로 초기화되며, local 변수 세그먼트는 할당되고 0으로 초기화된다. 호출된 함수가 바라보는 static 세그먼트는 그 함수가 속하는 VM 파일의 static 세그먼트로 설정되며, 작업 스택은 비어있다. this, that, pointer, temp 세그먼트들은 시작 전에는 미정의 상태다.
  • 반환되기 전에, 호출된 함수는 값을 하나 스택에 푸시해야 한다.

8.3 구현

기본 개념은 이렇다. 코드를 실제 플랫폼에서 실행하는 대신, 가상 머신(Virtual Machine, VM)에서 실행 가능한 중간 코드를 만든다. VM은 실재하지는 않지만, 다른 컴퓨터 플랫폼 상에서 구현 가능한 추상적인 컴퓨터다.

이 아이디어는 코드 이동성, 즉 동일한 코드를 수정 없이, 또는 약간의 변경만으로 여러 컴퓨터 환경에서 실행시키도록 하기 때문에 매우 유용하게 사용할 수 있다.

VM은 다른 플랫폼에서 상대적으로 구현하기 쉽기 때문에, VM 기반 소프트웨어는 소스 코드를 수정할 필요 없이 여러 프로세서와 운영체제에서 실행 가능하다.

7.1 배경

7.1.1 가상 머신 패러다임

고수준 언어가 실행되려면 먼저 기계어로 번역되어야 한다. 이 과정을 보통 컴파일이라 부르며, 해당 아키텍처에 따라서 수많은 컴파일러가 생겨난다. 이러한 컴파일러의 기계 종속성 문제를 해결하기 위해서 전체 컴파일 과정을 두 단계로 쪼갰다.

1. 고수준 언어의 구문을 분석해서 명령들을 중간 처리 단계(VM 언어)로 번역한다. (front-end)
2. 중간 처리된 명령어들을 다시 대상 하드웨어의 기계어로 번역한다. (back-end)

또한 가상 머신 언어 개념은 실용적 장점이 몇 가지 있다.

1. 가상 머신 구현 부분(백엔드)만 바꾸면, 여러 플랫폼의 컴파일러들을 상대적으로 쉽게 만들 수 있다.
2. 여러 가지 언어의 컴파일러들이 같은 VM 백 엔드를 공유함으로써, 코드를 공유하고 상호 운용하기 편해진다. 예를 들어, 같은 VM 컴파일 단계를 공유한다면, 한 언어에서 다른 언어의 루틴을 호출해서 활용하는 문법을 만들기가 훨씬 더 수월해진다.
3. 모듈성을 가지고 있기 때문에, VM 구현이 더 효율적으로 개선될 때마다. 텀파일러들도 곧바고 그 이점을 누린다.

다음은 Jack 프로그램에 대한 컴파일 과정이다.

7.1.2 스택 머신 모델

스택 모신 모델에서 산술 명령은 스택의 최상단에서 피연산자를 꺼내고(pop), 그 결과를 다시 스택의 최상단에 넣는다(push). 그 외의 다른 명령들의 경우에는 스택의 최상단과 지정된 메모리 주소 사이에 데이터가 이동된다.

• 기본 스택 연산

  스택은 push와 pop을 기본 연산으로 삼는 추상 데이터 구조다. push는 한개의 데이터 원소를 스택의 최상단에 추가하는 연산이다. 이때 최상단에 있던 원소는 새로 추가된 원소의 아래로 내려간다. pop은 최상단 원소를 꺼낸 후 스택에서 삭제하는 연산이다. 이때 바로 아래 있던 원소는 최상단으로 올라오게 된다. 그래서 스택을 '후입선출'저장 방식이라 한다. 스택 데이터 구조를 구현할 수 있는 여러 방법 중 하나는 스택 배열과, 최상단 원소 바로 위 위치를 가리키는 스택 포인터 변수로 구현하는 것이다. push x 명령은 x를 sp가 가리키는 배열 위치에 저장하고 sp를 1증가시키는 방식으로 구현된다. (stack[sp]=x; sp=sp+1) 그리고 pop연산은 먼저 sp를 1 감소시키고 최상단 위치의 값을 반환하는 식이 된다. (sp=sp-1; return stack[sp])

• 스택 산술

  산술의 피연산자를 스택에서 꺼내서(POP), 필요한 연산을 수행한 후에 결과를 다시 스택에 넣으면(PUSH) 된다. 다음은 스택 산술 예시다.

7.2 VM 명세, 1부

7.2.1 일반

이 가상 머신은 스택 기반이다. 즉, 모든 연산이 스택 위에서 이루어진다. 또한 함수 기반이다. 그리고 이 언어는 다음과 같은 네 가지 종류의 명령으로 구성된다.

• 산술 명령(arithmetic command)은 스택에서 산술 및 논리 연산을 수행한다.
• 메모리 접근 명령(memory access command)은 스택과 가상 메모리 세그먼트 사이에 데이터를 주고받는 명령이다.
• 프로그램 흐름 명령(program flow command)은 조건 및 무조건 분기 연산을 가능하게 한다.
• 함수 호출 명령(function calling command)은 함수를 호출하고 결과를 반환한다.

이번 장에서는 산술, 메모리 접근 명령을 구현하고, 다음 장에서는 프로그램 흐름 제어, 함수 호출 명령을 구현할 것이다.

• 프로그램 명령 구조

  .vm 파일 내부에서 한 라인은 한 VM 명령이 되며, 다음과 같은 형식을 띈다. command(ex: add), command arg(ex: goto loop), 또는 command arg1 arg2(ex: push loacl 3). command 부분과 각 인수들은 임의 개수의 봉백문자로 구분된다.

7.2.2 산술 및 논리 명령

이 VM 언어는 9개의 스택 기반 산술 및 논리 명령들이 있다. 이 중 7개는 2항 명령이다. 즉, 스택에서 두 개의 항복을 꺼내서(POP), 2항 함수를 계산하고, 결과를 다시 넣는(PUSH) 명령이다. 나머지 두 함수는 하나의 항목을 꺼내서, 단항 함수를 계산하고, 결과를 다시 넣는 단항 명령이다. 여기에서 우리는 명령들이 단지 해당 피연산자를 결괏값으로 교체함을 알 수 있다.

여기에서의 boolean 값은 true와 false를 각각 -1(0xFFFF)과 0(0x0000)으로 표시한다.

7.2.3 메모리 접근 명령

지금까지는 단순히 스택에 데이터를 PUSH, POP 만을 했다면, 지금부터는 가상 메모리 세그먼트들을 조작해볼 것이다. 각각의 세그먼트에 대한 설명은 다음과 같다.

• 메모리 접근 명령

• 모든 메모리 세그먼트는 두 개의 동일한 명령으로 접근 가능하다.

  • push segment index -> segment[index] 값을 스택에 넣는다(PUSH).

  • pop segment index -> 최상단 스택 값을 꺼내서(POP) segment[index]에 저장한다.

    여기서 segment는 8개 세그먼트 이름 중 하나이면, index는 음수가 아닌 정수다. 예를 들어 push argument 2 다음의 pop local 1 명령은, 함수의 세 번째 인수 값을 함수의 두 번째 지역 변수에 저장하라는 뜻이다.

• 스택 VM 연산에서 데이터 값은 한 세그먼트에서 다른 세그먼트로 점프하는 대신에 스택을 거쳐서 이동한다.
• 힙 힙은 객체와 배열 데이터를 저장하는데 사용되는 RAM 영역의 명칭이다.

7.2.4 프로그램 흐름과 함수 호출 명령

지금까지 설명한 명령들 말고도 다음 장에서 설명할 명령들이 존재한다.

• 프로그램 흐름 명령

    label symbol    // 레이블 선언
    goto symbol        // 무조건 분기
    if-goto symbol    // 조건 분기

• 함수 호출 명령

    function fincionName nLocals        // 함수 선언. 함수의 지역 변수 개수를 지정함.
    call functionName nArgs                // 함수 호출. 함수의 인자 개수를 지정함
    return                                // 호출하는 함수로 제어를 되돌림

7.3 구현

우리는 지금부터 .vm 파일을 입력 받아, 핵 어셈블리 언어로 된 .asm 파일 하나를 출력으로 생성하는 프로그램을 구현할 것이다.

• RAM 사용

다음은 RAM의 주소별 활용 방법이다.

여기에서 각각의 세그먼트 활용법에 대해 헷갈릴 것이다. 이에 대해서는 nand2tetris가 기본으로 제공하는 tool에 있는 VMEmulater.sh 를 활용하면 쉽게 이해할 수 있을 것이다.

프로그램 구조

Parser 모듈

class Parser:
    def __init__(self, file_name):
        self._file_name = file_name
        self._read_f = open(self._file_name, 'r')

        self._cur_index = 0
        self._vm_instruction = self._read_f.readlines()

        for i in range(0, len(self._vm_instruction)):
            self._vm_instruction[i] = self._vm_instruction[i].replace("\n", "")
            if not self._vm_instruction[i].find('//'):
                self._vm_instruction[i] = self._vm_instruction[i].replace(self._vm_instruction[i][self._vm_instruction[i].find('/'):], '')

        for i in range(0, self._vm_instruction.count('')):
            self._vm_instruction.remove('')
        print(self._vm_instruction)

    def hasMoreCommands(self):
        if self._cur_index == len(self._vm_instruction):
            return False
        return True

    def advance(self):
        self._cur_index+=1

    def commandType(self):
        instruction = self._vm_instruction[self._cur_index].split()[0]
        arithmetic = ['add', 'sub', 'neg', 'eq', 'gt', 'lt', 'and', 'or', 'not']
        if instruction in arithmetic:
            return 'C_ARITHMETIC'
        elif instruction == 'push':
            return 'C_PUSH'
        elif instruction == 'pop':
            return 'C_POP'
        elif instruction == 'label':
            return 'C_LABEL'
        elif instruction == 'goto':
            return 'C_GOTO'
        elif instruction == 'if-goto':
            return 'C_IF'
        elif instruction == 'function':
            return 'C_FUNCTION'
        elif instruction == 'call':
            return 'C_CALL'
        elif instruction == 'return':
            return 'C_RETURN'

    def arg1(self):
        if self.commandType() == 'C_ARITHMETIC':
            return self._vm_instruction[self._cur_index].split()[0]
        elif self.commandType() in ['C_PUSH', 'C_POP', 'C_LABEL', 'C_GOTO', 'C_IF', 'C_FUNCTION', 'C_CALL']:
            return self._vm_instruction[self._cur_index].split()[1]
        else:
            return None

    def arg2(self):
        if self.commandType() in ['C_PUSH', 'C_POP', 'C_FUNCTION', 'C_CALL']:
            return self._vm_instruction[self._cur_index].split()[2]
        else:
            return None

    def printInstruction(self):
        print(self._vm_instruction)

CodeWriter 모듈

class CodeWriter:
    def __init__(self, file_name):
        self._file_name = file_name[:file_name.find('.')]
        self._write_file = open(self._file_name + '.asm', 'w')
        self._file_name = self._file_name.split('/').pop()
        self._true_counter = 1
        self._end_counter = 1

    def writeArithmetic(self, command):
        if command=='add':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('M=M+D\n')
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='sub':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('M=M-D\n')
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='neg':
            self._write_file.write('@SP\n')
            self._write_file.write('A=M-1\n')
            self._write_file.write('M=-M\n')
        elif command=='eq':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M-D\n')
            self._write_file.write('@TRUE_%d\n' % self._true_counter)
            self._write_file.write('D;JEQ\n')
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=0\n')
            self._write_file.write('@END_%d\n' % self._end_counter)
            self._write_file.write('0;JMP\n')
            self._write_file.write('(TRUE_%d)\n' % self._true_counter)
            self._true_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=-1\n')        #TRUE가 -1?
            self._write_file.write('(END_%d)\n' % self._end_counter)
            self._end_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='gt':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M-D\n')
            self._write_file.write('@TRUE_%d\n' % self._true_counter)
            self._write_file.write('D;JGT\n')
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=0\n')
            self._write_file.write('@END_%d\n' % self._end_counter)
            self._write_file.write('0;JMP\n')
            self._write_file.write('(TRUE_%d)\n' % self._true_counter)
            self._true_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=-1\n')        #TRUE가 -1?
            self._write_file.write('(END_%d)\n' % self._end_counter)
            self._end_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='lt':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M-D\n')
            self._write_file.write('@TRUE_%d\n' % self._true_counter)
            self._write_file.write('D;JLT\n')
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=0\n')
            self._write_file.write('@END_%d\n' % self._end_counter)
            self._write_file.write('0;JMP\n')
            self._write_file.write('(TRUE_%d)\n' % self._true_counter)
            self._true_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('A=M\n')
            self._write_file.write('M=-1\n')        #TRUE가 -1?
            self._write_file.write('(END_%d)\n' % self._end_counter)
            self._end_counter += 1
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='and':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('M=M&D\n')
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='or':
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('D=M\n')
            self._write_file.write('@SP\n')
            self._write_file.write('AM=M-1\n')
            self._write_file.write('M=M|D\n')
            self._write_file.write('@SP\n')
            self._write_file.write('M=M+1\n')
        elif command=='not':
            self._write_file.write('@SP\n')
            self._write_file.write('A=M-1\n')
            self._write_file.write('M=!M\n')
        else:
            pass

    def writePushPop(self, command, segment, index):
        if command=='C_PUSH':
            if segment=='constant':
                self._write_file.write('@%s\n' % index)
                self._write_file.write('D=A\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='argument':
                self._write_file.write('@ARG\n')
                self._write_file.write('A=M+%s\n' % index)
                self._write_file.write('D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='local':
                self._write_file.write('@LCL\n')
                self._write_file.write('A=M+%s\n' % index)
                self._write_file.write('D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='static':
                self._write_file.write('@{}.{}\n'.format(self._file_name, index))
                self._write_file.write('D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='pointer':
                if index==0:
                    self._write_file.write('@THIS\n')
                    self._write_file.write('D=M\n')
                    self._write_file.write('@SP\n')
                    self._write_file.write('A=M\n')
                    self._write_file.write('M=D\n')
                    self._write_file.write('@SP\n')
                    self._write_file.write('M=M+1\n')
                elif index==1:
                    self._write_file.write('@THAT\n')
                    self._write_file.write('D=M\n')
                    self._write_file.write('@SP\n')
                    self._write_file.write('A=M\n')
                    self._write_file.write('M=D\n')
                    self._write_file.write('@SP\n')
                    self._write_file.write('M=M+1\n')
            elif segment=='this':
                self._write_file.write('@THIS\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='that':
                self._write_file.write('@THAT\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            elif segment=='temp':
                self._write_file.write('@5\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('@D=M\n')
                self._write_file.write('@SP\n')
                self._write_file.write('A=M\n')
                self._write_file.write('M=D\n')
                self._write_file.write('@SP\n')
                self._write_file.write('M=M+1\n')
            else:
                pass
        if command=='C_POP':
            if segment=='argument':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@ARG\n')
                self._write_file.write('A=M+%s\n' % index)
                self._write_file.write('D=M\n')
            elif segment=='local':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@LCL\n')
                self._write_file.write('A=M+%s\n' % index)
                self._write_file.write('M=D\n')
            elif segment=='static':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@{}.{}\n'.format(self._file_name, index))
                self._write_file.write('M=D\n')
            elif segment=='pointer':
                if index==0:
                    self._write_file.write('@SP\n')
                    self._write_file.write('M=M-1\n')
                    self._write_file.write('A=M\n')
                    self._write_file.write('D=M\n')
                    self._write_file.write('@THIS\n')
                    self._write_file.write('M=D\n')
                elif index==1:
                    self._write_file.write('@SP\n')
                    self._write_file.write('M=M-1\n')
                    self._write_file.write('A=M\n')
                    self._write_file.write('D=M\n')
                    self._write_file.write('@THAT\n')
                    self._write_file.write('M=D\n')
            elif segment=='this':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@THIS\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('M=D\n')
            elif segment=='that':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@THAT\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('M=D\n')
            elif segment=='temp':
                self._write_file.write('@SP\n')
                self._write_file.write('M=M-1\n')
                self._write_file.write('A=M\n')
                self._write_file.write('D=M\n')
                self._write_file.write('@5\n')
                self._write_file.write('A=A+%s\n' % index)
                self._write_file.write('M=D\n')
            else:
                pass

리버스 엔지니어링과 관련된 소프트웨어 보안은 몇 년에 걸쳐서 지금까지도 활발히 연구되고 있는 분야이다. 그리고 이 연구는 굉장히 실용적이다. 실제로 악의적인 수정, 변조 또는 리버스 엔지니어링으로부터 소프트웨어를 보호하는 것은 매우 어럽다. 이 논문에서는 LLVM을 기반으로 하는 소프트웨어 난독화 프로토타입 도구를 제시하고 그에 대해 논의할 것이다. 우리의 툴은 LLVM IR 코드에서 작동하고, 그 중 일부는 오픈소스이며 무료로 사용할 수 있다. 이 접근 방식은 언어에 구애받지 않고 하드웨어 아키텍처와 독립적이라는 이점이 있다. 우리의 현재 프로토 타입은 기본 명령어 대체, 코드 난독화, 제어 흐름 병합, 절차 병합뿐만 아니라 제어 흐름 병합 메코니즘에 대한 코드 변조 방지 알고리즘을 지원한다.

I. INTRODUCTION

소프트웨어를 보호하는 것이 어려운 작업인 주된 이유는 공격자가 에뮬레이션, 디버거에서 실행, 디스어셈블, 디컴파일 등을 수행할 수 있는 소프트웨어에 대한 무제한 접근과 같은 비정상적인 권한을 가지고 있기 때문입니다. 따라서 공격자는 중요한 데이터를 포함해, 메모리의 데이터를 읽을 수 있고, 암호화 키 같은 소프트웨어 실행 중에 값을 수정해서 소프트웨어를 불법적으로 복사하는 등의 목적으로 분석한다.

컴퓨터의 형태가 모바일 및 클라우드로 발전함에 따라서 이 문제를 해결하는 것은 개인 정보 보호, 보안 측면에서 실제로 엄청난 영향을 미칠 것이다. 지금까지 우리는 실행 중인 코드의 무결성과 기밀성을 보호하는 문제가 암호화 및 소프트웨어 난독화에서 공격을 받았다는 것을 관찬했습니다. 그래서 고정키 구현과 같은 알고리즘을 인스턴스화 할 수 있는 소위 화이트 박스 암호화 기술이 제안되기도 했다. 하지만 이런 제안은 대부분 무산되었다. 이 화이트 박스 암호화의 문제는 공격자가 응용 프로그램에서 알고리즘을 들어올리는 이른바 코드 리프팅이 문제인다. 이 경우 공격자 알고리즘을 해제해서 자신의 제어 하에 원래 키를 알 필요도 없고, 알고리즘을 이해할 필요도 없다.

소프트웨어 난독화는 보다 실용적일 수 있다. 암호화 난독화로 얻을 수 있는 것 정도의 공격 저항 수준을 기대하는 것이 아니라, 적의 리버스 엔지니어링 비용을 증가시켜서, 공격자를 포기하기를 기대한다.

일반적인 보안 소프트웨어 접근 방식은 USB 토큰, HSM(하드웨어 보안 모듈), 스마트 카드, 원격 인증과 같은 하드웨어에 의존한다. 하지만 이런 솔루션들은 무시할 수 없는 비용이 들고, 모바일 또는 클라우트 컴퓨팅과 같은 환경이나 연결되지 않은 상태에서 구현하기가 항상 쉽지만은 않다. 그래서 휴대전화나 태블릿에서 실행되는 소프트웨어를 보호하기 위해서는 데이터나 알고리즘을 숨길 수 있는 소프트웨어 전용 보호 메커니즘에 의존해야 한다. 그러므로 리버스 엔지니어링에 대한 소프트웨어 저항을 증가시켜야 한다.

학계와 산업계 모두 소프트웨어 보안 향상을 목표로 하는 기술을 제안했다. 이러한 기술에는데이터 인코딩, 변수 분할 및 병합, 배열 접기 밎 병합, 정적 값을 런타임 생성 값으로 변환, 혼합 부울 산술 변환이 포함된다. 이 기술은 리버스 엔지니어링 비용을 증가시켰지만, 불가능하도록 만들지는 못한다.

변조 방지 소프트웨어는 일반적으로 실행 중인 코드를 보호하거나 프로그램을 통한 제어 흐름이 예상된 코드인지 확인함으로써 코드 조작을 감지하는 내장 무결성 검사를 사용한다. 하지만 이런 기법을 독립 실행형 응용 프로그램을 보호하는데 사용하는 경우, 기대 체크섬 값과 반응 레커니즘이 응용 프로그램 자체에서 하드 코딩되어 분석 및 변경될 수 있기 때문에 보안은 다소 제한된다. 자체 검사 소프트웨어는 디버거를 연결시켜 자동으로 공격당할 수 있다.

이것은 완전히 리버스 엔지니어들을 막을 수 없더라도, 이것들이 모두 리버스 엔지니어링의 비용을 크게 증가시킨다는 것을 다시 한번 강조한다.

A. Our Contributions

이 논문에서, 우리는 LLVM 컴파일 중간 단계에 구현된 난독화 코드 변환 세트, Obfuscator-LLVM(ollvm)을 제시한다. 구현된 보호 기술의 대부분은 무료로 사용이 가능한 오픈 소스 형태로 제공된다. ollvm은 현재 거의 완전히 언어 및 플랫폼에 독립적이다. 명령어 대체 , 가짜 제어 흐름 삽입, 기본 블록 분할, 제어 흐름 병합, 코드 변조 방지 메커니즘의 절차 병합 및 삽입을 구현할 수 있다. 하지만 마지막 두 기술은 현재 ollvm에서 무료로 사용할 수 없다.

B. Related Work

시중에서 구할 수 있는 상용 도구 외에도 C/C++와 같은 전통적인 프로그래밍 언어로 작성된 프로그램의 난독화를 지원할 수 있는 무료 도구는 많지 않다. 최근 눈에 띄는 예로는 Tigress, LOCO, Sandmark가 있다.

II. CODE TRANSFORMATIONS

다음에서는 LLVM 컴파일 제품군을 빠르게 검토하고 코드 다양화에 대해 논의하며 지금까지 ollvm에서 구현한 모든 난독화 기술에 대해 설명합니다.

A. The LLVM Compilation Suit

컴파일 제품군의 목적은 대상에 대해 올바르게 실행될 수 있는 코드를 생성하는 것이다. CPU 컴파일러는 고수준 언어로 쓰인 상위 코드를 저수준 언어인 어셈블러 코드로 변환하고, 어셈블러가 이를 번역해 오브젝트 코드로 변환한다. 컴파일러는 상위 코드가 올바를 구문을 가지고 있는지 확인하고 가능한 한 효율적으로 어셈블리 코드를 정확하게 생성해야 한다. 또한 컴파일러는 해당 아키텍저의 규칙을 준수하는 코드를 생성해야 한다.

LLVM은 크리스 래트너가 처음 작성한 오픈 소스 컴파일 제품군으로 임의의 프로그래밍 언어의 정적 컴파일 및 동적 컴파일을 모두 지원할 수 있는 현대의 정적-단일 할당(SSA) 기반 컴파일 전략을 제공하는 것을 목표로 한다. LLVM은 현재 대규모 개발자 커뮤니티에 의해 지원되고 있고, 오늘날 GNU컴파일러 컬렉션의 주요 오픈 소스 경쟁자로 간주되고 있다.

LLVM은 프론트 엔드, 옵티마이저, 백 엔드로 구성된다. 프론트엔드는 소스 코드를 분석하고 정확성을 확인하고, 옵티마이저라고도 하는 미들엔드에 전달될 이 코드의 중간 표현(IR)을 구축하는 일을 담당한다. LLVM에서 지원하는 두 가지 주요 프론트 엔드는 C/C++ 및 Objective-C를 컴파일 할 수 있는 clang과 GNU Compiler Collection 파서를 기반으로 하는 프론트엔드이다. 그 결과로, 중간표현은 LLVM 생태계에서 IR 코드라는 이름의 범용 의사 어셈블리 언어이며, 최적화 도구 또는 백엔드에 제공될 수 있다. 어떤 IR 코드가 주어지면, 옵티마지어는 중복 코드, 인라인 함수, 데드 루프 삭제, 제어 흐름 그래프 단순화 등을 담당한다. 이렇게 옵티마이저를 거친 최적화된 IR코드는 백엔드로 전달되고, 백엔드는 해당 아키텍처에 대한 효율적인 어셈블러 코드를 생성한다.

우리가 지금까지 구현한 난독화 및 변조 방지 메커니즘의 대부분은 중간 단계에서 발생한다. 이 접근 방식은 언어에 구애받지 않고 해당 아키텍처와 독립적이라는 사실과 함께 몇 가지 장점을 가지고 있다. 이러한 방법은 가능한 모든 보호를 구현하지 못하지만, 소스 및 타겟 하드웨어에 구애받지 않는 장점이 단점을 압도한다. 아키텍처별 보호 기능이 각 백엔드에서 구현될 수 있음은 말할 필요도 없다.

B. Bringing Code Diversification

일반적인 컴파일 과정은 결정론적이다. 즉, 동일한 소스코드를 두번 컴파일 하면 동일한 머신 코드가 생성된다. ollvm이 오픈 소스이기 때문에, 적이 추적할 수 없는 새로운 실행 파일을 만들기 쉬워지지만, 이것은 약간의 작업 없이는 불가능하다.

우리가 구현한 모든 코드 변환은 어떤 방식으로든 무작위화된다.

C. Instructions Substitution

명령어 대체 방식은 가장 간단한 난독화 기법일 수 있다. 산술 연산자나 부울 연산자와 같은 표준 이진 연산자를 기능적으론 같지만 더 복잡한 명령어 시퀸스로 대체한다. 명령어 대체는 ollvm의 -mllvm -sub 옵션으로 이용할 수 있다. 현재, 덧셈과 뺄셈, 부울 연산 AND(&), OR(|), XOR(^)를 지원한다.

이런 종류의 난독화는 오히려 간단하고 생성된 코드를 다시 최적화함으로써 쉽게 파훼될 수 있기 때문에 리버스 엔지니어링의 cost를 많이 올리지 못한다. 그래서 우리의 명령어 대체가 모든 LLVM 최적화가 이루어진 후에 실행되는 이유다. 그럼에도 불구하고, 주어진 연산자에 대해 여러 등가식들을 생성할 수 있다는 사실을 감안할 때, 무작위로 하나를 선택하는 것은 코드 다양화를 가져오는 쉬운 방법이다. 그리고 XOR과 같은 대칭 암호에서 특정 기계 명령 패턴을 자동으로 검색하는 작업을 더 어렵게 만들 수 있다.

다음은 ollvm에서 명령어 치환 표이다. 여기에서 r 은 무작위 pseudo-value이다.

D.Bogus Control Flow Insertion

가짜 제어 흐름 삽입은 원래 기본 블록을 가리키거나 조건부 점프 블록으로 다시 루프하는 가짜 기본 블록을 가리키는 조건부 점프구문을 추가하여 함수의 제어 흐름 그래프를 수정하는 것으로 구성됩니다. 불명확한 술어, 즉 항상 같은 값으로 평가되지만 정적으로 리버스 엔지니어링하기 어려운 표현식은 런타임에 원래 런타임에 원래 기본블록만 실행회도록 해야 한다. 불투명 술어는 또한 최적화 프로그램이 데드 코드를 식별하여 결과 호출 그래프를 단순화할 수 없도록 해야한다. 이 변환은 -mllvm -bcf 컴파일 플래그를 통해 사용할 수 있고, 삽입 밀도, 반복 횟수 등을 포함하여 다양한 방식으로 매개변수화될 수 있다. 가짜 제어 흐름 삽입의 효과는 Fig 1의 C 소스코드를 가지고 생각할 때 가장 잘 알 수 있을 것이다. Fig 2에는 수정 전후의 함수 f()의 제어 흐름 그래프가 그려져 있다. 추가된 코드의 대부분이 죽어서 실행되지 않을지라도 제어흐름 그래프는 상당히 복잡해진 것을 알 수 있다.

E.Control Flow Flattening and Basic-Block Splitting

코드 평면화의 이면에 있는 아이디어는 모든 조건부 및 루프 구조를 제고해서 함수의 제어흐름 그래프를 깨는 것이다.

개요

기본적으로 Xcode 프로젝트에 테스트 메소드를 추가해서 XCTest 기능을 사용할 수 있는데, 각 테스트 케이스는 .XCTestCase 의 subclass 다. 다음은 설명을 돕는 예시 코드다.

이 예제에서는 테스트 메소드 하나로 테스트 케이스를 정의한다. 이 테스트 메소드는 Table이라는 클래스의 새 인스턴스 table을 만들고 초기화 후 table의 행과 열이 모두 0인지 확인한다.

@interface TableValidationTests: XCTestCase                                    // 1
@end
@implementation TableValidationTests
/// Tests that a new table instance has zero rows and columns.
- (void)testEmptyTableRowAndColumnCount {                                    // 2
    Table *table = [[Table alloc] init];
    XCTAssertEqual(table.rowCount, 0, "Row count was not zero.");            // 3
    XCTAssertEqual(table.columnCount, 0, "Column count was not zero.");
}
@end

- 위의 코드처럼 프로젝트에 테스트를 추가하려면:

1. XCTestCase의 하위 클래스(테스트 케이스)를 만든다.
2. 테스트 케이스에 하나 이상의 테스트 메소드를 추가한다.
3. 각 테스트 메소드에 하나 이상의 XCTest Assertion을 추가한다.

여기에서 테스트 메소드는 매개변수, 리턴값이 없고 이름이 'test' 로 시작해야 한다.

상태 설정 및 해제

추가적인 내용은 애플 공식 문서 링크에서 확인하길 바란다.

테스트를 실행하기 전에 초기 상태를 준비하고 테스트가 완료된 후 리소스를 정리해야 한다. 어떤 경우에는 테스트 케이스의 모든 테스트 메소드의 상태를 설정해야 할 때도 있다. 또한 테스트가 완료된 후 임시 파일이나 스크린샷과 같이 필요하지 않는 파일을 삭제하고, 실패 진단을 돕기 위해 테스트 후 최종 상태를 캡처할 수도 있다.

테스트 클래스에서 언제 상태를 설정하고 해제할지 결정

테스트 케이스를 실행할 때, XCTest는 먼저 XCTestCase setUp() 메소드를 호출한다. 이 메소드로 테스트 케이스의 모든 테스트 메소드에 공통적인 상태를 설정한다. 다음은 각 메소드의 호출 순서다.

1. class func setUp()
2. func setUpWithError()
3. func setUp()
4. testMethod() and addTestdownBlock(_:)
5. func testDown()
6. func tearDownWithError()
7. class func tearDown()

1. class func setUp()

타입 메소드로 테스트 시작 전 딱 한 번만 호출된다. 그래서 보통 모든 테스트 메소드에서 실행 전에 정의하거나 초기화할 작업을 오버라이드하여 구현한다.

+ (void)setUp {
    // This is the setUp class method.
    // XCTest calls it before calling the first test method.
    // Set up any overall initial state here.
}

2. func setUpWithError()

각 테스트 메서드가 실행되기 전에 실행됩니다. 각각의 테스트 메서드 실행 전에 정의하거나 초기화할 작업을 오버라이드하여 구현합니다.

- (BOOL)setUpWithError:(NSError *__autoreleasing  _Nullable *)error {
    // This is the setUpWithError instance method.
    // XCTest calls it before each test method.
    // Set up any synchronous per-test state that might throw errors here.
    return YES;
}

3. func setUp()

setUpWithError() 메서드와 동일하게 각 테스트 메서드가 실행되기 전에 실행됩니다. 두 메서드의 차이점은 setUpWithError() 메서드는 실행 도중 발생한 에러를 처리할 수 있다는 점입니다.

4. testMethod() and addTestdownBlock(_:)

실질적인 테스트를 수행하는 메서드입니다. 꼭 테스트 메서드의 이름을 testMethod로 지을 필요없이 자유롭게 설정할 수 있습니다. addTestdownBlock(:) 메서드는 testMethod()가 종료될 때 실행되는 코드 블록입니다. addTestdownBlock(:) 메서드 블록은 먼저 선언된 블럭이 나중에 실행되는 LIFO 구조의 방식으로 호출됩니다.

5. func testDown()

각 테스트 메서드가 종료되고 나서 실행됩니다. 각각의 테스트 메서드를 수행하고 정리하는 작업을 오버라이드하여 구현합니다.

6. func tearDownWithError()

tearDown() 메서드와 마찬가지로 각 테스트 메서드가 종료되고 나서 실행됩니다. 두 메서드의 차이점은 setUpWithError() 메서드는 실행 도중 발생한 에러를 처리할 수 있다는 점입니다.

- (BOOL)tearDownWithError:(NSError *__autoreleasing  _Nullable *)error {
    // This is the tearDownWithError instance method.
    // XCTest calls it after each test method.
    // Perform any synchronous per-test cleanup that might throw errors here.
    return YES;
}

7. class func tearDown()

타입 메서드로 모든 테스트가 종료되고 딱 한 번만 호출됩니다. 그래서 모든 테스트를 마치고 정리해야 할 작업을 오버라이드하여 구현합니다.

+ (void)tearDown {
    // This is the tearDown class method.
    // XCTest calls it after the last test method completes.
    // Perform any overall cleanup here.
 }

다음은 애플 공식 문서에 있는 테스트 메소드 호출 순서도다.

6.1 배경

기계어는 직관적이지 않다. 다양한 연산 코드, 메모리 주소 지정 방식, 명령어 형식으로 인해서 110000101000000110000000000000111 같은 2진코드 보다는 LOAD R3 7처럼 약속된 문법으로 표기하는 것이 더 직관적이다. 그리고 기호를 2진 코드로 옮기기는 쉽기 때문에 어셈블리 코드를 거쳐서 최종 실행 바이너리 코드로 빌드하는 것이 효율적이다.

• 기호

  • 변수

    번역기가 기호로 표기된 변수명을 발견하면 '자동적으로'그 기호를 주소에 할당한다.

  • 레이블

    프로그래머는 프로그램 내 다양한 위치를 기호로 표시해놓을 수 있다. 2진 명령어들은 실제 숫자를 이용해서 해당 변수의 메모리 주소를 표기하지만, 하지만 어셈블리는 그 대신에 변수명을 직접 표기해서 사용할 수 있다. ex) LOAD R3, 7 -> LOAD R3, weight

    하지만 사용자 정의 변수명과 기호 레이블을 실제 메모리 주소에 매핑하는 것은 그리 간단하지 않다. 실제로 하드웨어에서 소프트웨어로 전환되는 과정 중에 가장 먼저 접하는 난관이 바로 이 기호 변환 작업이다.

• 기호 변환

  위의 그림은 기호가 포함된 코드를 기호가 해석된 코드로 바꾸는 과정을 그린 것이다. 먼저 사용자 정의 변수인 i와 sum은 차례대로 메모리 주소 1024, 1025를 할당받는다. 그리고 레이블 loop와 end는 그 선언된 위치에 따라서 명령어 주소 2와 6을 각각 할당 받는다. 이에 대한 내용을 가운데의 기호 테이블에 표시하고, 기호 테이블을 토대로 최종 코드를 만들 수 있다.

• 어셈블러

  어셈블러는 기본적으로 번역 기능이 있는 텍스트 처리 프로그램이다. 따라서 어셈블리 문법에 대한 전체 문서가 있어야 한다. 보통 기계어 명세라 불리는 이 규칙을 따르면 기호 명령마다 다음과 같은 작업을 수행하는 프로그램을 만드는 일은 그리 어렵지 않다.

  • 구문 분석을 통해 기호 명령 내 필드들 식별
  • 각 필드에 대응하는 기계어 비트 생성
  • 모든 기호 참조를 메모리 주소를 가리키는 숫자로 변환
  • 2진 코드들을 조립하여 완전한 기게 명령어로 변환

6.2 핵 어셈블리 - 2진 번역 명세서

6.2.1 문법 관례와 파일 형식

• 파일명

  관례적으로 어셈블리로 작성된 파일은 .asm, 2진 기계어 코드로 작성된 파일은 .hack 확장자를 가진다.

• 2진 코드(.hack) 파일

  16비트 기계어 명령어를 0과 1형태의 ASCII 문자열로 작성되어 있다. 프로그램의 라인 번호와 명령어 메모리(ROM)의 주소는 둘 다 0에서 시작한다.

• 어셈블리어(.asm) 파일

  명령어나 기호 선언이 어셈블리어로 작성되어 있다.

  • 명령어 : A-명령어 또는 C-명령어
  • (Label) : 실제 기계어 코드로 번역되지 않지만, Symbol table에 (Label, address)를 추가한다. 여기서 address는 (Label) 다음에 쓰인 명령어의 주소이다.

• 상수와 기호

  상수는 10진법으로 표기된 음수가 아닌 숫자이다. 기호는 문자, 숫자, 밑줄(_), 마침표(.), 달러 기호($), 콜론(:)들로 이루어진 문자열로 맨 앞 글자는 숫자가 아니어야 한다.

• 주석

  두개의 빗금(//)에서 라인 끝까지의 텍스트는 주석으로 간주되어 무시된다.

• 공백

  공백 문자와 빈 라인은 무시된다.

• 대소문자 규칙

  어셈블리 연상기호는 전부 대문자로 써야 한다. 사용자 정의 레이블과 변수명은 대소문자 구분을 한다.

6.2.2 명령어

핵 기계어는 주소 명령어(A-명령어)와 계산 명령어(C-명령어) 두 종류로 구성된다. 이에 대한 자세한 설명은 Chapter 4 : 기계어 파트에서 자세히 설명했다.

6.2.3 기호

핵 어셈블리는 상수나 기호로 메모리 위치(주소)를 참조할 수 있는데, 다음은 어셈블리에서 기호를 쓰는 방법 세가지다.

• 선언 기호

  핵 시스템이 기본적으로 제공하는 기호라고 생각하면 될 것이다.

• 레이블 기호

  실제 수행할 명령어는 아닌 의사명령 (Xxx)는 Xxx가 프로그램의 다음 명령이 있는 명령어 메모리 주소를 참조하도록 정의한다.

• 변수 기호

  프로그램 내에서 (Xxx)로 정의되지 않는 Xxx는 변수로 취급된다. 변수는 등장한 순서대로 RAM주소 16부터 차례대로 매핑된다.

  6.2.4 예제

  

• 주의 : 핵 어셈블러는 2진 코드를 생성하고 이 파일이 직접적으로 CPU에서 실행되지만, 일반적인 컴퓨터에서는 어셈블러가 16진수 objct파일을 만들고 만들어진 object 파일들을 linker가 조합하여 최종 실행파일을 만든다. 이를 Hex Fiend로 열어보면 첫 부분에 라이브러리를 불러오는 헤더가 있고 중간 부분에 오브젝트 파일의 내용이 들어있는 것을 확인 할 수 있다.

6.3 구현

핵 어셈블러는 기본적으로 위와 같이 Parser, SymbolTabel, Code 세 가지 모듈로 구성되어 있다. 지금부터 각 모듈이 어떤 역할을 하는지 알아보자

6.3.1 Parser 모듈

어셈블리 명령을 읽어 구문분석을 하고, 필드와 기호에 편리하게 접근하도록 한다. 추가로 모든 공백과 주석을 제거한다. 다음은 Parser class의 기본 메소드다.

6.3.2 Code 모듈

핵 어셈블리의 연상기호 ex) D=A, D;JMP 를 2진 코드로 번역한다. 다음은 Code class의 기본 메소드다.

6.3.3 SymbolTable 모듈

핵 명령어의 번역 과정에서 기호들을 실제 주소로 바꾸어야 하는데, 기호와 그 의미의 대응관계를 관리하는 기호 테이블(Symbol table)을 만들었다. 이를 자연스럽게 구현할 수 있는 해시 테이블이라는 데이터 구조가 있다. 다음은 SymbolTable class의 기본 메소드다.

6.3.4 어셈블러 구현

위의 그림은 내가 C++로 구현한 어셈블러의 실행 흐름을 표현한다.

1. Code 객체를 생성하는데, Code class는 Parser에게 상속 받는다.
2. 객체 생성후에 Parser의 생성자고 호출되는데, 인자로 받은 어셈블리 파일을 읽는다.
3. 1st pass와 2nd pass를 거치는데 이는 단계를 보기 쉽게 나눈것 뿐이므로 pass 자체가 가진 의미는 없다.
4. 1st pass : .asm 파일의 문자열을 읽어 vector로 저장하는데, 이때 주석과, 공백을 제거하고, (Xxx)를 만날 시에 (Xxx, address)를 symbol table에 저장하고 (Xxx) 문자열은 제거한다.
5. 2nd pass : 다시 처음부터 vector를 읽기 시작하는데, 변수를 만날 시에 (변수, address)를 symbol table에 저장하고, @Xxx에서 Xxx를 해당하는 주소로 대체한다.
6. 이로서 모든 기호가 주소값으로 대체된 명령어가 완성되었다. 이를 Code 모듈에서 2진 코드를 생성해 .hack 파일에 쓴다.

6.3.5 C++ Code

main.cpp

#include "Code.hpp"
#include "Parser.hpp"

int main(int argc, char **argv){
    Code *assembler = new Code(argv[1]);

    assembler->write_binary();

    return 0;
}

Parser.hpp

#ifndef Parser_hpp
#define Parser_hpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unistd.h>
#include <sys/types.h>

#include "Instruction.hpp"
#include "SymbolTable.hpp"

using namespace std;

class Parser {
private:
    int cur_index = 0;
    int numOfLine = 0;
    string write_file_name;
    ifstream readFile;
    vector<string> _assembly;
    SymbolTable symbols;
    // vector<string>::iterator _assembly_iterator;
public:
    Parser(){};
    Parser(string read_file_name) {
        this->readFile.open(read_file_name); 
        for(int i=0; i<3; i++)
            read_file_name.pop_back();
        this->write_file_name = read_file_name;
        write_file_name.push_back('h');
        write_file_name.push_back('a');
        write_file_name.push_back('c');
        write_file_name.push_back('k');
        // this->_assembly_iterator = this->_assembly.begin();
        this->first_pass();
        this->second_pass();
        // this->symbols.print_map();
        // this->_print_assembly();
    };
    ~Parser() {
    };
    void first_pass();
    void second_pass();

    int get_numOfLine();
    int get_cur_index();
    string get_cur_instruction(int index);
    string get_write_file_name();

    void reset();
    void _print_assembly();
    bool is_digit(string str);

    bool hasMoreCommands();
    void advance();
    COMMAND_TYPE commandType();
    string symbol();
    string dest();
    string jump();
    string comp();
    string to_binary(int num);
};

#endif

Parser.cpp

#include "Parser.hpp"

using namespace std;


void Parser::first_pass(){
    string instruction;
    if (this->readFile.is_open()){
        while(getline(this->readFile, instruction)){
            if(instruction.front()!='/' && instruction.size()!=1){
                while(instruction.front()==' '){
                    instruction.erase(instruction.begin());
                }
                if(instruction.find(" ")!=string::npos)
                    instruction.resize(instruction.find(" ")+1);
                this->_assembly.push_back(instruction);
                this->numOfLine++;
            }
        }
        this->cur_index = 0;
        while(this->hasMoreCommands()==1){
            if(this->commandType()==L_COMMAND) {
                this->numOfLine--;
                instruction = this->get_cur_instruction(this->get_cur_index());
                instruction = instruction.substr(1, instruction.size()-3);
                this->symbols.addEntry(instruction, this->get_cur_index());
                this->_assembly.erase(this->_assembly.begin()+cur_index);
            }
            this->advance();
        }
    }
}

void Parser::second_pass(){
    string label;
    this->cur_index=0;
    while(this->hasMoreCommands()==1){
        if(this->commandType()==A_COMMAND && !this->is_digit(this->_assembly[cur_index].substr(1, this->_assembly[cur_index].size()-1))){
            label = this->_assembly[cur_index].substr(1, this->_assembly[cur_index].size()-1);
            if(this->symbols.contains(label)){
                this->_assembly[cur_index].replace(1, -1, to_string(this->symbols.getAddress(label)));
            }
            else {
                this->symbols.addEntry(label, this->symbols.get_extra_address());
                this->_assembly[cur_index].replace(1, -1, to_string(this->symbols.getAddress(label)));
            }
        }
        this->cur_index++;
    }
    this->cur_index = 0;
}

int Parser::get_numOfLine(){
    return this->numOfLine;
};

string Parser::get_write_file_name(){
    return this->write_file_name;
}

int Parser::get_cur_index(){
    return this->cur_index;
}

string Parser::get_cur_instruction(int index){
    return this->_assembly[index];
}

void Parser::_print_assembly(){
    for(int i=0;i<this->_assembly.size();i++){
        cout << this->_assembly[i] << endl;
    }
}

bool Parser::hasMoreCommands(){
    if(this->cur_index==this->_assembly.size()-1)
        return 0;
    else
        return 1;
}

void Parser::advance(){
    if(this->hasMoreCommands()==1){
        this->cur_index++;
    }
}

void Parser::reset(){
    this->cur_index = 0;
}

COMMAND_TYPE Parser::commandType(){
    if(this->_assembly[this->cur_index].front()=='@')
        return A_COMMAND;
    else if(this->_assembly[this->cur_index].front()=='(')
        return L_COMMAND;
    else
        return C_COMMAND;
}

string Parser::symbol(){
    if(this->commandType()==A_COMMAND){
        return this->_assembly[this->cur_index].substr(1);
    }
    else if(this->commandType()==L_COMMAND){
        return this->_assembly[this->cur_index].substr(1,this->_assembly[this->cur_index].size()-2);
    }
    return "";
}

string Parser::dest(){
    int equal_index = this->_assembly[this->cur_index].find('=');
    if(equal_index==string::npos)
        return "null0";
    else
        return this->_assembly[this->cur_index].substr(0, equal_index);

}

string Parser::jump(){
    int semiColone_index = this->_assembly[this->cur_index].find(';');
    if(semiColone_index==string::npos)
        return "null";
    else
        return this->_assembly[this->cur_index].substr(semiColone_index+1, 3);
}

string Parser::comp(){
    int equal_index = this->_assembly[this->cur_index].find('=');
    int semiColone_index = this->_assembly[this->cur_index].find(';');
    size_t len;
    len = this->_assembly[cur_index].size()-equal_index-2;
    if(equal_index!=string::npos){
        return this->_assembly[this->cur_index].substr(equal_index+1, len);
    }
    else if(semiColone_index!=string::npos){
        return this->_assembly[this->cur_index].substr(0, semiColone_index);
    }
    else
        return "";
}

string Parser::to_binary(int num) {
    string binary15 = "000000000000000";
    string binary = "";
    while (num > 0) {
        if (num % 2 == 1) binary = "1" + binary;
        else binary = "0" + binary;
        num >>= 1;
    }
    binary15.replace(15-binary.size(), binary.size(), binary);
    return binary15;
}

bool Parser::is_digit(string str) {
    return atoi(str.c_str()) != 0;
}

SymbolTable.hpp

#ifndef SymbolTable_hpp
#define SymbolTable_hpp

#include <map>
#include <string>
#include <iostream>

using namespace std;

class SymbolTable
{
private:
    int extra_address = 16;
    map<string, int> _symbol_table;
    map<string, int>::iterator iter;
public:
    SymbolTable(){
        this->iter = _symbol_table.begin();

        this->_symbol_table["R0"] = 0;
        this->_symbol_table["R1"] = 1;
        this->_symbol_table["R2"] = 2;
        this->_symbol_table["R3"] = 3;
        this->_symbol_table["R4"] = 4;
        this->_symbol_table["R5"] = 5;
        this->_symbol_table["R6"] = 6;
        this->_symbol_table["R7"] = 7;
        this->_symbol_table["R8"] = 8;
        this->_symbol_table["R9"] = 9;
        this->_symbol_table["R10"] = 10;
        this->_symbol_table["R11"] = 11;
        this->_symbol_table["R12"] = 12;
        this->_symbol_table["R13"] = 13;
        this->_symbol_table["R14"] = 14;
        this->_symbol_table["R15"] = 15;

        this->_symbol_table["SCREEN"] = 16384;
        this->_symbol_table["KBD"] = 24576;
        this->_symbol_table["SP"] = 0;
        this->_symbol_table["LCL"] = 1;
        this->_symbol_table["ARG"] = 2;
        this->_symbol_table["THIS"] = 3;
        this->_symbol_table["THAT"] = 4;
    };

    ~SymbolTable(){

    }

    int get_extra_address();
    void addEntry(string symbol, int address);
    bool contains(string symbol);
    int getAddress(string Symbol);
    void print_map();
};

#endif

SymbolTable.cpp

#include "SymbolTable.hpp"

void SymbolTable::addEntry(string symbol, int address){
    this->_symbol_table[symbol] = address;
}

bool SymbolTable::contains(string symbol){
    this->iter = this->_symbol_table.find(symbol);
    return (iter!=this->_symbol_table.end());
}

int SymbolTable::getAddress(string symbol){
    return this->_symbol_table[symbol];
}

int SymbolTable::get_extra_address(){
    return this->extra_address++;
}

void SymbolTable::print_map() {
    for (map<string, int>::iterator itr = this->_symbol_table.begin(); itr != this->_symbol_table.end(); ++itr) {
        cout << itr->first << " " << itr->second << endl;
    }
}

Code.hpp

#ifndef Code_hpp
#define Code_hpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <unistd.h>
#include <sys/types.h>
#include "Parser.hpp"


using namespace std;

class Code : Parser {
private:
    ofstream writeFile;
public:
    Code(string read_file_name) : Parser(read_file_name){
        this->writeFile.open(this->get_write_file_name());
    }

    string incode_dest();
    string incode_jump();
    string incode_comp();

    void write_binary();
};

#endif

Code.cpp

#include "Code.hpp"

string Code::incode_dest(){
    string symbol = this->dest();

    if(symbol.compare("null0")==0)
        return "000";
    else if(symbol.compare("M")==0)
        return "001";
    else if(symbol.compare("D")==0)
        return "010";
    else if(symbol.compare("MD")==0)
        return "011";
    else if(symbol.compare("A")==0)
        return "100";
    else if(symbol.compare("AM")==0)
        return "101";
    else if(symbol.compare("AD")==0)
        return "110";
    else if(symbol.compare("AMD")==0)
        return "111";
    else
        return "";
}

string Code::incode_jump(){
    string symbol = this->jump();

    if(symbol.compare("null")==0)
        return "000";
    else if(symbol.compare("JGT")==0)
        return "001";
    else if(symbol.compare("JEQ")==0)
        return "010";
    else if(symbol.compare("JGE")==0)
        return "011";
    else if(symbol.compare("JLT")==0)
        return "100";
    else if(symbol.compare("JNE")==0)
        return "101";
    else if(symbol.compare("JLE")==0)
        return "110";
    else if(symbol.compare("JMP")==0)
        return "111";
    else
        return "";
}

string Code::incode_comp(){
    string symbol = this->comp();

    if(symbol.compare("0")==0)
        return "0101010";
    else if(symbol.compare("1")==0)
        return "0111111";
    else if(symbol.compare("-1")==0)
        return "0111010";
    else if(symbol.compare("D")==0)
        return "0001100";
    else if(symbol.compare("A")==0)
        return "0110000";
    else if(symbol.compare("!D")==0)
        return "0001101";
    else if(symbol.compare("!A")==0)
        return "0110001";
    else if(symbol.compare("-D")==0)
        return "0001111";
    else if(symbol.compare("-A")==0)
        return "0110011";
    else if(symbol.compare("D+1")==0)
        return "0011111";
    else if(symbol.compare("A+1")==0)
        return "0110111";
    else if(symbol.compare("D-1")==0)
        return "0001110";
    else if(symbol.compare("A-1")==0)
        return "0110010";
    else if(symbol.compare("D+A")==0)
        return "0000010";
    else if(symbol.compare("D-A")==0)
        return "0010011";
    else if(symbol.compare("A-D")==0)
        return "0000111";
    else if(symbol.compare("D&A")==0)
        return "0000000";
    else if(symbol.compare("D|A")==0)
        return "0010101";
    else if(symbol.compare("M")==0)
        return "1110000";
    else if(symbol.compare("!M")==0)
        return "1110001";
    else if(symbol.compare("-M")==0)
        return "1110011";
    else if(symbol.compare("M+1")==0)
        return "1110111";
    else if(symbol.compare("M-1")==0)
        return "1110010";
    else if(symbol.compare("D+M")==0)
        return "1000010";
    else if(symbol.compare("D-M")==0)
        return "1010011";
    else if(symbol.compare("M-D")==0)
        return "1000111";
    else if(symbol.compare("D&M")==0)
        return "1000000";
    else if(symbol.compare("D|M")==0)
        return "1010101";
    else 
        return "";
}

void Code::write_binary(){
    string str;
    int num;
    int i = 0;
    for(i=0; i<get_numOfLine(); i++){
        if(this->commandType()==C_COMMAND)
            str = "111"+this->incode_comp()+this->incode_dest()+this->incode_jump();
        if(this->commandType()==A_COMMAND){
            num = stoi(this->symbol());
            str = "0"+this->to_binary(num);
        }
        this->writeFile << str << endl;
        advance();
    }
}

Instruction.hpp

#ifndef Instruction_hpp
#define Instruction_hpp

enum COMMAND_TYPE {
    A_COMMAND = 0,
    C_COMMAND,
    L_COMMAND
};

#endif

5.1 배경

5.1.1 내장식 프로그램 개념

컴퓨터는 정해진 명령어 집합들을 실행하는 고정된 하드웨어 플랫폼에 기반한다. 그리고 컴퓨터가 실행하는 명령어들은 기본 블록이 되어 무한히 복잡한 프로그램으로 조합된다. 이 프로그램들은 하드웨어에 내장되지 않는 대신, 프로그램의 코드는 컴퓨터 메모리상에 바로 데이터처럼 저장되고 연산되는데, 이것을 '소프트웨어'라 부른다.

5.1.2 폰 노이만 구조

폰노이만 구조는 중앙 처리 장치(CPU)를 기반으로 하며, 이 장치는 메모리와 통신하고, 입력 장치에서 데이터를 받고, 출력 장치에 데이터를 보내는 일을 한다.

5.1.3 메모리

폰 노이만 기계의 메모리는 데이터와 명령어, 두 종류의 정보를 저장한다. 이 두 정보는 보통 다르게 취급되고, 어떤 컴퓨터에서는 메모리 장치를 분리해서 따로 저장하기도 한다. 두 정보의 기능은 다르지만, 동일한 무작위 접근 구조에 2진수로 저장된다는 점은 같다.

• 데이터 메모리

  고수준 프로그램은 변수, 배열, 객체같은 추상적 개념을 다룬다. 이런 추상적 데이터들을 기계어로 번역하면 2진 숫자열로 바뀌어 데이터 메모리에 저장된다.

• 명령어 메모리

  고수준 명령들을 기계어로 번역하면 2진수 기계어 명령어를 뜻하는 단어들이 된다. 이 명령어들은 명령어 메모리에 저장된다.

5.1.4 중앙 처리 장치

중앙 처리 장치(CPU)는 불러온 프로그램의 명령어를 실행하는 일을 담당한다. CPU는 이 명령어들을 통해 다양한 계산을 수행(ALU), 메모리에 값을 읽거나 쓰고(레지스터), 조건에 따라 다른 명령어로 점프(제어 장치)한다.

• 산술 논리 연산 장치(ALU)

  컴퓨터에서 지원하는 모든 저수준 산술, 논리 연산을 수행하는 장치다. 일반적인 ALU는 두 값을 더하거나, 어떤 숫자가 양수인지 확인하거나, 데이터 단어의 비트를 조작하는 등의 일을 할 수 있다.

• 레지스터

  CPU는 간단한 계산을 빠르게 수행하도록 설계된다. 이를 위해서 매번 데이터를 메모리에서 로드하고 저장하기 보다는, CPU 근처에 저장할 수 있는 고속 레지스터를 약간씩 갖추고 있다.

• 제어 장치

  보통 16, 32, 64 bit 2진 코드로 표현되는 컴퓨터 명령어를 해석해서 ALU, 레지스터, 메모리가 무엇을 해야 하는지를 전달한다. 동시에 어떤 명령어를 인출하고 다음에 실행할지 알아내는 역할도 한다.

이렇게 CPU 연산은 이제 명령어(단어)를 메모리에서 인출하고, 해석하고, 실행하고, 다음 명령어를 인출하는 루프가 반복되는 것으로 묘사할 수 있다.

5.1.5 레지스터

메모리 접근은 느린 작업이다. CPU가 메모리 주소 j의 내용을 가져오라는 지시를 받으면, 다음과 같은 과정이 진행된다.

1. j가 CPU에서 RAM으로 전달된다.
2. RAM의 직접 접근 논리에 따라 주소가 j인 메모리 레지스터가 선택된다.
3. RAM[j]의 내용이 CPU로 다시 전달된다.

하지만 레지스터는 CPU 칩 내부에 물리적으로 위치해 있고, 메모리 셀은 거의 수백만 개가 있지만 보통 레지스터는 소수만 있기 때문에 데이터를 옮기고 메모리를 탐색하는데 비용을 들이지 않는다.

CPU들은 여러 용도로 여러 가지 종류의 레지스터를 각각 다른 개수만큼 사용한다.

• 데이터 레지스터

  CPU의 단기 기억 메모리 기능을 한다. 예를 들어 (a-b)c 값을 계산한다고 할 때, (a-b)의 값을 메모리에 임시로 저장할 수 있긴 하지만, CPU 내부에 저장하는 편이 더 효율적이기 때문에 그 용도로 **'데이터 레지스터'*** 를 둔다.

• 주소 지정 레지스터

  CPU는 데이터를 읽고 쓰기 위해서 계속 메모리에 접근해야 한다. 그리고 메모리에 접근할 메모리 단어(주소)를 지정해야 한다. 이 주소가 현재 명령어에 포함되어 있지 않은 경우에, '주소 지정 레지스터' 에 저장된 예전 명령어의 실행 결과(주소)를 이용하기도 한다.

• 프로그램 계수기 레지스터(Program Counter Register)

  CPU가 명령어 메모리에서 인출해야 할 다음 명령어의 주소를 저장한다. 실행중인 명령어에 goto 문이 없는 경우에는 PC가 프로그램의 다음 명령어를 가리키도록 값을 증가시키고, goto n 문이 있는 경우에는 PC에 n 값을 로드한다.

5.1.6 입력과 출력

우리가 흔히 사용하는 모니터나 키보드 이외에도 수많은 입출력 장치가 존재한다. 각각의 설정을 만들기에는 너무 많은 비용이 들기 때문에, 모든 입출력 장치들을 똑같이 처리하는 기법인 '메모리 매핑 I/O'을 만들었다.

• 메모리 매핑 I/O

  I/O 장치와 컴퓨터가 연결되면 빈 메모리에 해당 장치가 사용할 공간을 할당한다. I/O 장치를 에뮬레이션해서, CPU가 그 장치를 일반적인 메모리 세그먼트처럼 보이도록 하는 것이다.

• 입력 장치

  입력 장치의 메모리 맵은 지속적으로 장치의 물리적 상태를 반영한다. 키보드에 키가 눌렸다면, 그 장치의 메모리 맵에 특정 값들이 기록된다.

• 출력 장치

  출력 장치의 메모리 맵은 지속적으로 장치의 물리적 상태를 구동하도록 만들어진다. 어떤 출력 장치를 조작하고 싶은 경우(스크린에 표시, 스피커 재생), 그 장치의 메모리 맵에 특정 값들을 기록한다.

하드웨어 측면에서 I.O 장치들은 메모리 장치와 유사한 인터페이스를 가져야 한다. 소프트웨어 관점으로는 각 I/O 장치에 통신 규약을 정의해서 프로그램이 올바르게 접근할 수 있도록 해야 한다.

5.2 핵 하드웨어 플랫폼 명세

5.2.1 개요

5.2.2 중앙 처리 장치

핵 기계어로 작성된 16비트 명령어를 실행할 수 있도록 설계되었다. CPU는 명령어 메모리, 데이터 메모리 모듈에 연결된다.

5.2.3 명령어 메모리

핵 명령어 메모리는 ROM(Rean-Only Memory)라 불리는 칩 상에 구현된다. 핵 ROM은 주소 지정 가능한 32K개의 16비트 레지스터들로 구성된다.

5.2.4 데이터 메모리

핵의 데이터 메모리 인터페이스는 3장에서 구현한 RAM 장치와 동일하다. 그래서 레지스터 n의 내용을 읽으려면 메모리의 address 입력에 n을 넣고 out 출력을 검사하면 된다. 이 연산은 클록과 무관하다. 레지스터 n에 값 v를 쓰려면, in 입력에 v를, address 입력에 n을 넣고, 메모리의 load 비트를 활성화하면 된다. 이 연산은 순차 연산으로, 다음 클록 주기에 데이터 변경이 일어난다.

• 메모리 맵

  핵 플랫폼의 I/O 장치로 스크린과 키보드는 메모리 매핑 버퍼를 통해 컴퓨터 플랫폼과 통신한다.

• '스크린 메모리 맵'*이라 불리는 특정 메모리 세크먼트에 단어를 읽고 쓰는 것으로 스크린 이미지를 확인하거나 그릴 수 있다.

• '키보드 메모리 맵'*이라 불리는 특정 메모리 단어를 조사함으로써 현재 어떤 키가 눌린 상태인지 알 수 있다.

• 전체 메모리

  RAM(표준 데이터 저장소)과 스크린 맵 및 키보드 맵이 포함된다.

5.2.5 컴퓨터

컴퓨터 칩은 CPU, 데이터 메모리(RAM), 명령어 메모리(ROM), 스크린, 키보드 및 그 외 컴퓨터 작동에 필요한 모든 하드웨어 장치들로 구성된다. 이 컴퓨터에서 프로그램을 실행하기 위해서는 프로그램 코드를 ROM에 미리 로드해야 한다.

5.3 구현

5.3.1 중앙 처리 장치

• 제어 장치 설계

• HDL 구현

  CHIP CPU {
  
    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).
  
    OUT outM[16],        // M value output
        writeM,          // Write to M? 
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction
  
    PARTS:
    // Put your code here:
    Mux16(a=instruction, b=ALUout, sel=instruction[15], out=AorC);      // 명령어의 종류(A or C)를 적용시킨다. 
    Not(in=instruction[15], out=A);
    Or(a=A, b=instruction[5], out=loadA);                               // i'+ d1
    ARegister(in=AorC, load=loadA, out=address, out[0..14]=addressM);   // A 명령어이거나 d1이 1인 경우에 A 레지스터에 새로운 값을 저장한다. 15비트 주소 값을 출력한다. 
  
    And(a=instruction[15], b=instruction[3], out=writeM);               // i * d3 -> C 명령어이고 d3가 1인 경우에 결과값을 확인하고 메모리에 저장한다. 
  
    Mux16(a=address, b=inM, sel=instruction[12], out=y);                // A 레지스터에 저장된 주소값을 사용할지, CPU의 입력값을 사용할지 a비트가 결정한다. 
  
    And(a=instruction[15], b=instruction[4], out=loadD);                // i * d2 -> C 명령어이고 d2가 1인 경우에 D 레지스터에 이전 결과값을 저장한다. 
    DRegister(in=ALUout, load=loadD, out=x);
  
    ALU(x=x, y=y, zx=instruction[11], nx=instruction[10],
        zy=instruction[9], ny=instruction[8], f=instruction[7], 
        no=instruction[6], out=outM, out=ALUout, zr=ALUzr, ng=ALUng);   // c1 ~ c6로 연산 종류를 결정한다. out=0 -> zr=1, out<0 -> ng=1
  
    Or(a=ALUzr, b=ALUng, out=outUpto0);                                 // out<=0   
    Not(in=outUpto0, out=outGThan0);                                    // out>0
    Not(in=ALUng, out=outDownto0);                                      // out>=0
    Not(in=ALUzr, out=outNot0);                                         // out!=0
  
    Mux(a=false, b=outGThan0, sel=instruction[0], out=muxAB);           
    Mux(a=ALUzr, b=outDownto0, sel=instruction[0], out=muxCD);
    Mux(a=muxAB, b=muxCD, sel=instruction[1], out=muxABCD);
  
    Mux(a=ALUng, b=outNot0, sel=instruction[0], out=muxEF);
    Mux(a=outUpto0, b=true, sel=instruction[0], out=muxGH);
    Mux(a=muxEF, b=muxGH, sel=instruction[1], out=muxEFGH);
  
    Mux(a=muxABCD, b=muxEFGH, sel=instruction[2], out=jmp);             // j1, j2, j3으로 가능한 점프 조건 결정
  
    And(a=instruction[15], b=jmp, out=PCload);                          // i * (해당하는 점프 조건) -> PC의 load비트
    Not(in=PCload, out=PCinc);                                          // PC의 load비트가 와 inc비트는 서로 반대다. 
  
    PC(in=address, load=PCload, inc=PCinc, reset=reset, out[0..14]=pc);     // A 레지스터에 저장된 주소값을 로드할지, 기존 명령어 주소를 increase할지 결정
  }

  5.3.2 메모리 칩

• 설계

• HDL 구현

  CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];
  
    PARTS:
    DMux4Way(in=load, sel=address[13..14], a=ramA, b=ramB, c=screen, d=keyboard);           // 최상위, 차상위 비트로 어떤 메모리에 접근할지 결정된다. 
    Or(a=ramA, b=ramB, out=ram);                                                            // ramA와 ramB는 같은 16K 메모리이므로 합연산으로 load를 통일한다. 
  
    RAM16K(in=in, load=ram, address=address[0..13], out=ramOut);                            // ram의 선택비트는 1bit로 통일했기 때문에 주소값으로 14bit를 넘긴다. 
    Screen(in=in, load=screen, address=address[0..12], out=screenOut);                      // screen의 용량은 8K이므로 주소값으로 13bit를 넘긴다. 
    Keyboard(out=keyOut);
    Mux4Way16(a=ramOut, b=ramOut, c=screenOut, d=keyOut, sel=address[13..14], out=out);     // 최초 선택 비트로 접근한 메모리의 출력값을 out으로 넘긴다. 
  }

5.3.3 컴퓨터 칩

• 설계

• HDL 구현

  CHIP Computer {
  
    IN reset;
  
    PARTS:
    ROM32K(address=pc, out=instruction);      
    Memory(in=outM, load=writeM, address=addressM, out=inM);
    CPU(inM=inM, instruction=instruction, reset=reset, outM=outM, writeM=writeM, addressM=addressM, pc=pc);
  }

4.1 배경

4.1.1 기계

기계어는 프로세서와 레지스터들을 이용해서 메모리를 조작할 수 있도록 미리 정의된 규칙이다.

• 메모리

  메모리는 컴퓨터에서 데이터와 명령어를 저장하는 하드웨어 장치이다.

• 프로세서

  보통 중앙 처리 장치(CPU)라고 불리는 프로세서는 미리 정해진 기초 연산들을 수행하는 장치다. 메모리와 레지스터에 있는 2진 값을 피연산자로 두고, 연산을 출력값은 선택된 메모리 주소나 레지스터에 저장된다.

• 레지스터

  항상 CPU와 거리가 있는 메모리와 데이터를 주고 받기에는 시간이 상대적으로 많이 걸리기 때문에 대부분의 프로세서는 값을 하나 저장할 수 있는 레지스터를 바로 옆에 여러 개 두고 있다.

4.1.2 언어

기계어 프로그램은 명령어들을 2진 코드화한 것이다. 예를 들어 16비트 컴퓨터에서 명령은 보통 1010 0011 0001 1001 같은 식으로 표현된다. 이 기계어 닽은 경우에는 4bit 씩 4개의 필드로 구성되어 있고 맨 왼쪽 필드는 CPU연산 종류를, 나머지는 피 연산자를 나타낸다.

2진 코드만 보고서는 해석을 하기 어렵기 때문에, 기계어는 보통 2진 코드와 연산기호를 둘 다 사용하도록 되어 있다. 예를 들어, 1010은 ADD, 나머지 필드는 각각 R3, R1, R9을 의미한다.

이런 연상기호들을 사용한 표기법을 '어셈블리 언어' 또는 간단히 '어셈블리'라고 부르며, 어셈블리를 2진 기계어 코드로 번역하는 프로그램을 '어셈블러'라 한다.

4.1.3 명령

• 산술 및 논리 연산

  모든 컴퓨터에는 덧셈이나 뺄셈 같은 기초 산술 연산 외에도 비트 반전, 비트 이동 등의 불연산, 논리 연산도 가능해야 한다.

    ADD R2,R1,R3 // R2<-R1+R3 R1, R2, R3는 레지스터다. 
    ADD R2,R1,foo // R2<-R1+foo, foo는 사용자가 정의한 이름으로, foo가 가리키는 메모리 주소의 값을 뜻한다. 
    AND R1,R1,R2 // R1<-R1과 R2을 비트 단위로 And 연산한 결과

• 메모리 접근

  메모리 접근은 산술 및 논리 명령에 자연스럽게 포함되어 있고, 레지스터와 메모리 사이에 데이터를 이동시키는 로드, 저장 명령이 있다. 메모리 접근 명령은 몇 가지 종류의 주소 지정 모드를 가지고 있다.

    // 직접 주소 지정 방식
    LOAD R1, 67        // R1<-Memory[67]
    // 또는 bar가 메모리 주소 67을 나타낸다고 가정하면
    LOAD R1, bar    // R1<-Memory[67]
  
    // 즉시 주소 지정 방식
    LOAD R1, 67        // R1<-67
  
    // 간접 주소 지정 방식
    // x=foo[j] 또는 x=*(foo+j)의 번역
    ADD R1, foo, j    // R1<-foo+j
    LOAD* R2, R1    // R2<-Memory[R1]
    STR R2, x        // x<-R2

• 제어 흐름

  프로그램의 명령들은 보통 순서대로 실행되지만, 갑자기 다른 위치로 분기해서 실행되기도 한다. 분기에는 반복, 조건 실행, 서브루틴 호출 등의 몇 가지 종류가 있다 .

  //고수준 // while 루프 while (R1>=0) {

    code segmnet 1

  } code segumnet 2 // ---------------------------------------------

  // 저수준 beginWhile:

    JNG R1, endWhile    // If R1<0 goto endWhile
    // 세그먼트 1의 번역은 여기에 위치한다. 
    JMP beginWhile        // goto beginWhile

  endWhile:

    // 세그먼트 2의 번역은 여기에 위치한다. 

4.2 핵 기계어 명세

기본적으로 핵 컴퓨터는 폰 노이만 플랫폼이고 CPU, 명령어 메모리, 데이터 메모리, 스크린과 키보드에 해당되는 메모리 매핑 I/O장치로 구성된 16비트 장치이다.

4.2.1 개요

• 메모리 주소 공간

  핵에서는 명령어를 저장하는 메모리, 데이터를 저장하는 메모리로 주소 공간이 분리 되어 있다. 폭이 16비트인 두 메모리의 주소 공간은 15비트로, 최대 32K개의 16비트 단어들에 주소를 할당할 수 있다. 그리고 핵의 CPU는 명령어 메모리(ROM)에 존재하는 프로그램만 수행할 수 있다.

• 레지스터

  핵 시스템에는 데이터 값만을 저장하는 D 레지스터와 데이터 값과 주소 값을 저장할 수 있는 A 16비트 레지스터가 있다. 예를 들어, D=M+1에서 M은 항상 A에 저장된 값을 주소로 하는 메모리 데이터를 의미한다. 또한 분기명령어의 도착 위치는 항상 A에 저장된 값을 목적지로 한다.

4.2.2 A-명령어

A-명령어는 A레지스터에 15비트 값을 설정하는 데 쓰인다.

1. 상수
2. 데이터 주소
3. 점프할 명령어 주소

사용법 : @value
value는 음수가 아닌 10진수, 또는 그 숫자를 참조하는 기호

4.2.3 C-명령어

C-명령어는 핵 플랫폼에서 거의 모든 일을 수행한다. 이 명령어는 다음 질문에 대한 답이 된다.

1. 무엇을 계산하나?
2. 계산된 값을 어디에 저장하나?
3. 그 다음에 할 일은 무엇인가?

C-명령어 : dest = comp;jump    // dest나 jump 필드는 공란일 수 있다. 
                            // dest가 공란이면 '='가 생략된다. 
                            // jump가 공란이면 ';'가 생략된다. 

최상위 비트 값 1은 이 명령어가 C-명령어임을 나타내는 코드다. 그다음 두 비트는 사용되지 않는다. comp 필드는 ALU가 할 연산이 무엇인지를 뜻하고 dest 필드는 계산된 값을 어디에 저장할지 가리킨다. jump 필드는 점프 조건을 의미한다.

• 계산 필드(computation field)

  계산 필드의 a비트는 A레지스터와 메모리의 값 중 어느 것을 계산할 것인지를 결정해준다. 그리고 나머지 c1~6은 어떤 계산을 할지 결정하는데, 이는 Chap2에 등장한 ALU와 흡사하다. 그 이유는 다음장에 설명될 것이다.

• 목적지 필드(destination field)

  목적지 필드는 comp 부분에서 계산된 값을 어디에 저장할지를 나타낸다. 여기에서 d1은 A레지스터, d2는 D레지스터, d3는 Memory[A]를 담당하는데, 활성화된 비트가 담당하는 장소에 값을 저장한다.

• 점프 필드(jump field)

  점프 필드는 명령을 수행한 컴퓨터가 이제 어느 위치의 명령을 수행할지 결정한다. 하지만 실제로 점프할지는 ALU의 출력값에 달렸는데, 출력값이 음수라면 j1, 0이라면 j2, 양수일 때는 j3 비트를 보고 점프 여부를 결정한다.

4.2.4 기호

어셈블리 명령은 상수나 기호를 이용해서 메모리 주소를 참조할 수 있다.

• 미리 정의된 기호

  • 가상 레지스터 : R0R15는 RAM 주소 015를 가리키도록 정의한다.
  • 미리 정의된 포인터 : SP, LCL, ARG, THIS, THAT 기호는 각각 RAM 주소 0~4를 참조하도록 정의한다. 이 규칙은 가상머신을 구현할 때 유용하게 사용된다.
  • I/O 포인터 : SCREEN과 KBD 기호는 각각 RAM 주소 16384(0x4000)과 24576(0x6000)을 참조한다. 이 주소들은 스크린 및 키보드의 메모리 매핑 시작 주소가 된다.

• 레이블 기호 분기 명령어의 목적지를 나타내는 레이블 기호는 사용자가 '(XXX)'라는 의사명령으로 직접 선언한다.

• 변수 기호 이전 두 가지 기호가 모두 아닌 경우다. 어셈블러는 RAM 주소 16에서부터 차례대로 변수마다 유일한 메모리 주소를 할당한다.

4.2.5 입력/출력 조작

핵 플랫폼은 키보드와 스크린 장치에 연결될 수 있다. 두 장치는 메모리 맵을 통해 컴퓨터와 통신한다. 키보드입력은 해당 메모리 맵에 저장되고, 스크린에 해당하는 메모리 위치에 값을 쓰면 그에 대응하는 스크린 위에 픽셀이 쓰여진다.

• 스크린

  핵 컴퓨터의 스크린은 512개 열 X 256개 행의 흑백 픽셀로 구성된다. 그리고 스크린의 픽셀은 RAM[16384]부터 시작하는 8K 메모리 맵에 대응한다. 각 열마다 32개의 16비트 단어로 표현된다.

• 키보드

  핵 컴퓨터는 RAM[24576]에 위치한 1단어 메모리 맵을 통해 키보드와 통신한다. 실제 키보드가 눌릴 때마다, 눌린 키의 16비트 ASCII 코드가 기록되는 식이다. 키가 눌리지 않는 동안에는 0이 기록된다.

4.2.6 명령어 예시

C 언어

  // 1+..+100 덧셈
      int i = 1;
      int sum = 0;
      While (i <= 100) {
          sum += i;
          i++;
      }

핵 기계어

  // Adds 1+...+100.
        @i        // i는 어떤 메모리 위치를 참조함
        M=1        // i=1
        @sum    // sum은 어떤 메모리 위치를 참조함
        M=0        // sum=0
  (LOOP)
          @i
        D=M        // D=i
          @100
          D=D-A        // D=i-100
         @END
         D;JGT        // if (i-100)>0 goto END
        @i
        D=M        // D=i
        @sum
        M=D+M        // sum=sum+i
        @i
        M=M+1        // i=i+1
        @LOOP
        0;JMP        // Goto LOOP
  (END)
          @END
        0;JMP    // 무한루프(남은 실행횟수 소모)

4.3 구현

4.3.1 곱셈 프로그램(Mult.asm)

    @2
    M=0     // R2를 0으로 초기화한다. R2에는 결과값이 저장된다. 
(LOOP)
    @0      
    D=M     // R0의 값을 D에 저장한다. R0은 몇번 곱할지 남은 횟수를 나타낸다. 
    @END
    D;JEQ   // D의 값이 0이 되었다면 계산을 종료한다. 
    @1
    D=M     // R1의 값을 D에 저장한다. 
    @2      
    M=M+D   // R2 += D
    @0
    M=M-1   // 남은 곱셈 횟수를 1감소시킨다. 
    @LOOP
    0;JMP   // 무조건 LOOP으로 점프한다. 
(END)
    @END
    0;JMP

4.3.2 I/O 조작 프로그램(Fill.asm)

@i
M=0     // i = 0 초기화

(LOOP)

    @KBD
    D=M     // 현재 키보드에 입력된 값을 D에 대입

    @NOINPUT
    D;JEQ   // D == 0 jump
    @INPUT
    D;JGT   // D > 0 jump

(NOINPUT)
    @16384      // 
    D=A         //
    @i          // 현재 스크린 위치 -> A
    D=D+M       // 16384+i(1)
    A=D         //

    M=0         // 현재 스크린위치에 0000 0000 0000 0000 대입

    @END
    0;JMP
(INPUT)
    @16384      // 
    D=A         //
    @i          // 현재 스크린 위치 -> A
    D=D+M       //
    A=D         //

    M=-1        // 현재 스크린 위치에 1111 1111 1111 1111 대입

    @END
    0;JMP
(END)
    @i
    M=M+1       // i = i + 1

    @LOOP
    0;JMP       // LOOP로 jump

조합 논리의 결과 데이터는 연산이 종료된 후 소멸되기 때문에 더 복잡한 연산을 하기 위해서는 데이터를 기억할 필요가 있다. 이때, 데이터를 기억하고 기억한 데이터를 사용하기 위해서 '순차 논리'를 사용한다.

• 클록

  마스터 클록(master-clock)이 연속적인 신호를 발생시킨다. 보통 0과 1로 표시된 두 상태를 연속해서 오가는 것으로 표현한다.

• 플립플롭

  가장 기본적인 순차 논리 소자이다. 1비트 데이터 입력과 클록 신호 입력에 따라 새로 입력된 데이터를 출력할지 잠금상태가 되어 이전 입력을 유지할지 결정 된다.

• 레지스터

  DFF(데이터 플립플롭)만으로는 데이터를 원하는대로 저장하고 가져올 방법이 없기 때문에, 이전 시간의 출력 데이터를 다시 입력하는 방법을 사용한 것이 레지스터이다. 여기에서 새로운 데이터를 입력할지 이전 결과를 입력할지를 MUX(멀티플렉서)가 결정한다. 이렇게 만든 1Bit 레지스터를 이어붙혀서 아래와 같은 w-bit 레지스터를 만들 수도 있다. 레지스터가 저장할 수 있는 비트의 개수는 폭(width)이라 부르며, 16, 32, 64비트가 그 폭을 뜻한다. 레지스터에 저장되는 멀티비트 값은 보통 단어(word)라 부른다.

• 메모리

  이제 레지스터를 여러개 쌓아 올려서 여러 저장 공간을 한번에 사용할 수 있는 임의 접근 메모리를 만들 수 있다. n개의 각 레지스터에는 접근할 때 사용되는 유일한 주소가 할당된다. 주소는 어떤 RAM 레지스터에 접근할지를 가리키고, 읽기 연산(load=0)인 경우, RAM은 선택된 레지스터의 값을 바로 출력한다. 쓰기 연산(load=1) 때는 다음 사이클 때 선택된 메모리 레지스터에서 입력값을 받아, 해당 값을 출력하기 시작한다.

• 계수기

  매 시간 단위마다 내부 상태 값을 증가시키는 순차 칩이다. 대표적인 예시로 프로그램 계수기(program counter)가 있다.

• 시간 문제

  컴퓨터는 짧은 시간 안에 수 많은 명령을 처리하기 때문에 조합 칩으로만 구성되어 있을 경우, 데이터 경쟁이 발생하기 쉽다. 하지만 순차 칩의 출력은 클록 사이클이 넘어갈 때만 바뀔 수 있기 때문에 '데이터 경쟁'을 피하고 전체 컴퓨터 구조를 동기화 시킬 수 있다.

3.2 명세

3.2.1 데이터 플립플롭

DFF는 모든 메모리 소자의 기본 부품이 된다. 이것들은 모두 하나의 마스터 클록에 연결되어, 거대한 '합창단' 같이 행동한다. 클록 사이클이 시작할 때, 컴퓨터 내 모든 DFF 출력들은 전 사이클의 입력에 따라 맞춰진다. 그 외 시간에는 DFF가 '잠금' 상태가 되는데, 이 말은 입력이 변해도 출력이 곧바로 영향을 받지 않는다는 뜻이다.

3.2.2 레지스터

우리가 비트, 또는 2진 셀이라 부르는 1비트 레지스터는 하나의 정보 비트(0 or 1)을 저장하도록 설계된 소자다. 레지스터(w-bit)는 멀티비트 값을 처리할 수 있다는 점을 제외하면 기본적으로 2진 셀과 API가 동일하다.

3.2.3 메모리

RAM은 직접 접근 메모리 장치로, n개의 w-비트 레지스터를 배열하고 직접 접근 회로를 연결한 소자다. 메모리에 들어간 레지스터의 개수(n) 및 비트 수(w)는 각각 메모리의 크기와 폭이라 부른다. 이제 우리는 폭이 16비트고 크기는 다양한 메모리 계층을 구축할 것이다.

3.2.4 계수기

컴퓨터가 다음번에 실행할 명령의 주소를 기록하는 계수기 칩을 생각해 보자. 일반적인 생태에서 계수기는 매 클록 사이클마다 단순히 상태 값을 1 증가시켜 프로그램의 다음번 명령어를 불러올 수 있게 한다. 그리고 프로그램의 첫 명령 주소가 0이라고 한다면 계수기를 0으로 리셋해서 프로그램을 언제든지 재시작시킬 수 있어야 한다.

3.3 구현

1Bit 레지스터

위에서 설명했듯이 DFF의 출력값을 다시 DFF의 입력으로 넣는 것이 기본 구성이다. 하지만 새로운 입력과 이전 데이터 중에서 충돌이 일어나기 때문에 Mux를 활용해 이를 해결했다.

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    // Put your code here:
    Mux(a=dout, b=in, sel=load, out=selected);
    DFF(in=selected, out=out, out=dout);
}

레지스터

기본적인 16비트 데이터를 저장할 수 있는 레지스터다. 위에서 구현한 1bit 레지스터를 16개 이어 붙혀서 만들었다.

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    // Put your code here:
    Bit(in=in[0], load=load, out=out[0]);
    Bit(in=in[1], load=load, out=out[1]);
    Bit(in=in[2], load=load, out=out[2]);
    Bit(in=in[3], load=load, out=out[3]);
    Bit(in=in[4], load=load, out=out[4]);
    Bit(in=in[5], load=load, out=out[5]);
    Bit(in=in[6], load=load, out=out[6]);
    Bit(in=in[7], load=load, out=out[7]);
    Bit(in=in[8], load=load, out=out[8]);
    Bit(in=in[9], load=load, out=out[9]);
    Bit(in=in[10], load=load, out=out[10]);
    Bit(in=in[11], load=load, out=out[11]);
    Bit(in=in[12], load=load, out=out[12]);
    Bit(in=in[13], load=load, out=out[13]);
    Bit(in=in[14], load=load, out=out[14]);
    Bit(in=in[15], load=load, out=out[15]);
}

RAM8

레지스터를 8개 가지고 있는 RAM이다. 여기서 부터는 주소값을 입력으로 받는데, 3비트 주소 데이터로 어디 레지스터에 접근할지 DMux가 결정하고 접근된 레지스터에만 load비트 입력이 주어진다. 그리고 모든 레지스터칩이 작동을 하지만, 결국 그중 RAM의 출력값으로 결정되는 레지스터는 주소값에 해당되는 레지스터다. 이것을 칩의 마지막에 Mux가 담당하게 된다.

CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

    PARTS:
    // Put your code here:
    DMux8Way(in=load, sel=address, a=r0, b=r1, c=r2, d=r3, e=r4, f=r5, g=r6, h=r7);
    Register(in=in, load=r0, out=out0);
    Register(in=in, load=r1, out=out1);
    Register(in=in, load=r2, out=out2);
    Register(in=in, load=r3, out=out3);
    Register(in=in, load=r4, out=out4);
    Register(in=in, load=r5, out=out5);
    Register(in=in, load=r6, out=out6);
    Register(in=in, load=r7, out=out7);
    Mux8Way16(a=out0, b=out1, c=out2, d=out3, e=out4, f=out5, g=out6, h=out7, sel=address, out=out);
}

이후의 RAM들은 저장공간이 점점 커지는데, RAM8에서 레지스터를 여러개 사용한 것처럼 RAM을 여러개 사용하면 된다. 그리고 그만큼 주소 비트를 늘리면 충분히 설계할 수 있을 것이다.

PC(Program Counter)

PC의 레지스터에 어떤 명령어 주소가 입력되는지가 중요하다. 그것을 load, inc, reset 비트를 활용해서 최종적으로 레지스터에 어떤 값을 넘겨줄지를 설계하자. 자세한 내용은 주석에 달아 놓았다.

CHIP PC {
    IN in[16],load,inc,reset;
    OUT out[16];

    PARTS:
    // Put your code here:
    Inc16(in=din, out=incd);    // 레지스터에서 선택된 입력값의 1증가값을 미리 계산해 놓는다. 
    Mux16(a=din, b=incd, sel=inc, out=out1);    // inc값에 따라서 증가값을 사용할지 결정한다. 
    Mux16(a=out1, b=in, sel=load, out=out2);    // load값에 따라서 새로운 입력을 사용할지 결정한다. 
    Mux16(a=out2, b[0..15]=false, sel=reset, out=reseted);  // reset값에 따라서 선택된 입력을 0으로 리셋할지 결정한다. 
    Register(in=reseted, load=true, out=din, out=out);  // 최종 결정된 입력을 레지스터에 넣어 저장한다. 
}

이 장에서는 논리 게이트를 사용해 숫자를 어떻게 표현하고 계산할지 고민하고, 1장에서 만든 논리 게이트를 사용해 온전히 작동하는 산술 논리 연산 장치를 완성할 것이다.

2.1 배경

• 2진수

  컴퓨터는 수를 2진수로 다룬다. 19라는 수를 나타내고자 하면 10011(2진수) = 2^4×1 + 2^3×0 + 2^2×0 + 2^1×1 + 2^0×1 으로 나타날 것이다.

• 2진 덧셈

  2개의 2진수를 더하려면 기존 덧셈과 마찬가지로 가장 오른쪽(최하위 비트)부터 가장 왼쪽(최상위 비트)까지 같은 자리의 수끼리 자리올림수까지 고려해 더해주면 된다. 만약 마지막 비트를 더하고 나서 자리올람수가 1이라면, 오버플로가 발생한다.

• 부호가 있는 2진수

  부호를 나타내기 위해 대부분의 컴퓨터는 2의 보수(2's complement) 방식을 이용한다. X의 보수 = 2^n-X (x가 0이 아닌 경우) // 0 (x가 0인 경우)

• 0은 1로, 1은 0으로 뒤집은 뒤 +1 해주면 음수가 된다. (모든 음수 코드는 1로 시작한다.)

  2.2 명세

  2.2.1 가산기

• 반가산기

  두 비트를 더하는 기능을 한다. 덧셈한 값의 최하위 비트를 sum, 최상위 비트를 carry라 하자

• 전가산기

  세 개의 비트를 더하는 기능을 한다. 출력은 반가산기(sum, carry)와 같다.

• 가산기

  메모리와 레지스터 칩은 n비트 패턴으로 된 정수를 저장하고, n은 플랫폼에 따라 16, 32, 64 등등의 값이 된다. 이런 숫자를 덧셈하는 칩을 멀티비트 가산기 혹은, 가산기라 부른다.

• 증분기

  주어진 숫자에 1을 더하는 기능을 한다.

2.2.2 산술 논리 연산 장치(ALU)

핵 플랫폼의 ALU는 x와 y가 칩의 두 16비트 입력이고, 16비트 출력 값을 가진다. 주어진 2진 값들에 대해 ALU가 어떤 연산을 할지는 '제어 비트'라는 6개의 입력 비트를 통해서 결정한다.

2.3 구현

Half-Adder (반가산기)

위의 반가산기의 진리표를 보면 sum은 Xor과 같고, carry는 And와 같다는 것을 알 수 있다.

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
    // Put you code here:
    And(a=a, b=b, out=carry);
    Xor(a=a, b=b, out=sum);
}

Full-Adder (전가산기)

전가산기의 sum 구현은 간단하다. 먼저 a와 b를 반가산기로 더한 sum을 c와 더하면 최종 sum을 구할 수 있다. 그리고 각각의 반가산기에서 발생한 carry를 Or 연산해줌으로 최종 carry값을 구한다.

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
    HalfAdder(a=a, b=b, sum=sumAB, carry=carryAB);
    HalfAdder(a=sumAB, b=c, sum=sum, carry=carrySumABSumC);
    Or(a=carryAB, b=carrySumABSumC, out=carry);

}

ALU(산술 및 논리 연산 장치)

ALU는 코드에 주석을 달아 놓았으니 주석을 참고하며 코드를 읽어보길 바란다.

CHIP ALU {
    IN  
        x[16], y[16],  // 16-bit inputs        
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
    // Put you code here:
    Mux16(a=x, b[0..15]=false, sel=zx, out=zX);     // zx가 1이라면 x를 0으로 초기화한다. 
    Not16(in=zX, out=notZx);                        
    Mux16(a=zX, b=notZx, sel=nx, out=znX);          // nx가 1이라면 현시점의 x값을 반전시킨다. 

    Mux16(a=y, b[0..15]=false, sel=zy, out=zY);     // zy가 1이라면 y를 0으로 초기화한다. 
    Not16(in=zY, out=notZy);
    Mux16(a=zY, b=notZy, sel=ny, out=znY);          // ny가 1이라면 현시점의 y값을 반전시킨다. 

    And16(a=znX, b=znY, out=andznXY);               
    Add16(a=znX, b=znY, out=addznXY);
    Mux16(a=andznXY, b=addznXY, sel=f, out=fout);       // f값으로 and, add 중 어떤 연산을 할지 결정한다. 
    Not16(in=fout, out=nfout);
    Mux16(a=fout, b=nfout, sel=no, out[0..7]=out1, out[8..15]=out2, out[15]=ng, out=out);   // no값이 1이면 결과값을 반전시킨다. 최종 출력값이 음수라면 ng를 1로 초기화한다. 

    Or8Way(in=out1, out=orOut1);
    Or8Way(in=out2, out=orOut2);
    Or(a=orOut1, b=orOut2, out=orOut);      // 출력값을 앞, 뒤로 나누어서 or연산을 해, 1이 존재하는지 검사한다. 

    Not(in=orOut, out=zr);  //  or연산의 최종값에 따라서 zr을 결정한다. 
}

1.1.1 불 대수

불 대수는 참(true)/거짓(false), 예/아니오, 켜짐/꺼짐 같은 불(2진수)값을 다루는 대수학이다. 컴퓨터는 진수를 표현하고 처리하는 하드웨어이기 때문에 2진수를 입력을 가공해 2진수 출력을 하는 불 함수를 정의하고 분석하는 것이 컴퓨터 아키텍처를 구축하는 첫 단계가 된다.

• 진리표 표현

  불 함수를 정의하는 가장 쉬운 방법으로, 함수의 입력값들과 결과값을 나란히 표로 나타낸 것이다. 위 그림의 앞쪽 x, y, z 부분은 함수 입력값이 될 수 있는 모든 2진 값 조합이다. 마지막 열은 해당 입력에 대한 함수 값이다.

• 불 표현식

  불 함수를 진리표가 아니라 수식처럼 표현도 가능하다. 예를 들어 기본적인 불 연산인 And, Or Not은 각각 X · Y, X + Y, X'으로 표현된다.

• 정준 표현

  어떤 함수의 진리표를 바로 불 표현식으로 만들 수 있다. 함수값이 1인 항의 입력값을 And연산으로 묶고 이렇게 묶인 항들을 Or연산으로 합치면 주어진 진리표와 동등한 불 표현식을 얻을 수 있다. 위의 진리표를 예시로 정준 표현을 얻어보면, x'yz'+xy'z'+xyz'이라는 진리표와 동일한 의미의 불 표현식을 얻을 수 있다.

1.1.2 게이트 논리

게이트는 불 함수를 구현한 물리적 장치다. 우리는 하드웨어 설계자로서 기본 게이트들로 서로 연결된 조합 게이트를 통해 더 복잡한 기능을 구현할 것이다.

논리 게이트들은 내부와 외부, 두 가지 관점으로 바라볼 수 있다. 아래 그림의 오른쪽은 게이트의 내부 아키텍처, 즉 구현(implementation)을, 왼쪽은 게이트의 인터페이스(interface), 즉 칩의 외부에 노출된 입력 핀과 출력 핀들을 그린 것이다.

1.1.3 실제 하드웨어 구성

위의 그림에서 보았듯이, 입력 값 3개의 And연산을 해주는 게이트를 사용할 때마다 And게이트 2개로 매번 만들기에는 비효율적이다. 이런 문제를 해결하기 위해서 기본 게이트들처럼 조합 게이트도 하나의 칩으로 만들어서 그 칩을 앞으로 기본 구성 블록으로 사용하면 된다.

1.1.4 하드웨어 기술 언어

오늘날 하드웨어 설계자들은 맨손으로 뭔가를 만들지 않는다. 대신 컴퓨터에서 하드웨어 기술 언어(Hardware Description Language)라는 도구를 사용해서 칩 아키텍처를 설계하고 최적화 한다.

• 예제: Xor 게이트 제작

HDL의 헤더 부분에서는 칩 인터페이스를 정의한다. 칩의 이름과 입력 및 출력 이름을 명시한다. 파트는 해당 칩의 내부 구현을 담당한다. 헤더에서 명시된 입력을 각종 불 함수를 사용해 원하는 출력값을 만들어 낸다.

테스트 스크립트는 설계한 칩을 실행시킨다. 실행하고자 하는 칩을 불러와서 입력 값을 설정하고 실행한다. 실행이 끝나고 나면 입력 값의 출력 데이터를 기록한 .out 파일을 생성한다.

1.2 명세

1.2.1 Nand 게이트

Nand 게이트는 다른 모든 게이트들의 기초가 되는 게이트다. Nand는 다음과 같은 불 함수를 계산한다.

1.2.2 기본 논리 게이트

• Not

  단일 입력 Not 게이트는 '컨버터(converter)'라고도 불리며, 입력값을 반전시킨다.

• And

  입력값이 둘다 1일 경우에 1을, 그 외에는 0을 반환한다.

• Or

  입력값 중 적어도 하나가 1일 때 1을, 그 외에는 0을 반환한다.

• Xor

  '배타적 논리합'이라고도 불리는 Xor 함수는 두 입력값이 다를 경우 1, 그 외에는 0을 반환한다.

• 멀티플렉서

  '선택 비트'입력에 따라서 두 개의 '데이터 비트'입력 중 하나를 선택해 반환한다.

• 디멀티플렉서

  멀티플렉서와 정반대 기능을 한다. '선택 비트'에 따라 두 출력선 중 하나를 선택해 입력 신호를 반환한다.

  1.3 구현

  몇가지 중요하다고 생각하는 칩만 적어놓았으니 나머지 칩들은 Chapter 1 프로젝트 구현 코드를 참고하라

  1.3.1 And

  CHIP And {
    IN a, b;
    OUT out;
  
    PARTS:
    // Put your code here:
    Nand(a=a, b=b, out=nandAB);
    Nand(a=nandAB, b=nandAB, out=out);
  }

1.3.2 Xor

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
    Not(in=a, out=notA);
    Not(in=b, out=notB);
    And(a=a, b=notB, out=AandNotB);
    And(a=notA, b=b, out=BandNotA);
    Or(a=AandNotB, b=BandNotA, out=out);
}

1.3.3 Mux16

16비트 게이트를 설계할 때에는 1비트 게이트를 이어붙혀 설계했다.

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);

}

1.3.4 Mux4Way16

토너먼트 형식으로 일전에 설계한 2X1 Mux로 4개의 입력을 2개로 추리고 추려진 2개의 입력중 마지막 Mux로 최종 출력값을 결정한다. 이때, 선택 비트를 2bit로 늘려서 첫 연산과 마지막 Mux 연산에 각각 선택 비트 한개씩을 사용한다.

CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];

    PARTS:
    // Put your code here:
    Mux16(a=a, b=b, sel=sel[0], out=muxAB);
    Mux16(a=c, b=d, sel=sel[0], out=muxCD);
    Mux16(a=muxAB, b=muxCD, sel=sel[1], out=out);
}