From Nand to Tetris系列（六）

Chapter 5. Machine Language (Part 2)

Hack程式語言

前面介紹的兩種指令格式(A-instruction, C-instruction)是為了方便人類閱讀，但實際上計算機只能理解由0與1組成的指令，因此指令還需要透過組譯器(assembler)轉譯成binary code才能讓機器執行。
另一種將指令轉為binary code的做法是透過CPU模擬器。

以較低層次的觀點來看，一個程式語言需要處理下面幾個問題：

• 如何操作暫存器(register)與記憶體(memory)
• 指令分歧(Branching)
• 變數(Variables)
• 迭代/迴圈(Iteration)
• 指標(Pointers)
• 輸入與輸出(Input/Output)

暫存器(register)與記憶體(memory)

Hack的架構中有兩個暫存器與一個記憶體：

D: Data Register
A: Address Register / Data Register
M: the currently select memory register, M=RAM[A]

Example 1:

// D=10
@10
D=A

Example 2:

// D++
D=D+1

Example 3:

//D=RAM[17]
@17
D=M

Example 4:

//RAM[17]=0
@17
M=D

Example 5:

// RAM[17]=10
@10
D=A
@17
M=D

Example 6:

//RAM[5] = RAM[3]
@3
D=M
@5
M=D

Example 7:

// Copmutes: RAM[2] = RAM[0] + RAM[1]
// Usage: put value in RAM[0], RAM[1]
@0
D=M // D= RAM[0]
@1
D=D+M // D= D+RAM[1]
@2
M=D // RAM[2] = D

使用模擬器時，可能會發現一個現象：程式一直跑下去，無法終止。
如果這時候在其他記憶體位置被植入惡意程式，很有可能就會意外的被執行，這種攻擊方式就是：NOP(Null Opertion) slide攻擊。

因此好的習慣是使用無窮迴圈來作為程式結束的地方：

@6 // in line 6
0; JMP

Built-in Symbols
16組Virtual Register與I/O：

Symbol	Value
R0	0
R1	1
R1	2
…	…
R15	15
SCREEN	16384
KBD	24576

透過這些virtual register symbols可以增加程式的可讀性：

//RAM[5] = 15
@15
D=A

@R5 // == @5
M=D

另外有一些symbols在目前沒有使用，是用於未來實作Hack虛擬機(Virtual Machine)用的：

Symbol	Value
SP	0
LCL	1
ARG	2
THIS	3
THAT	4

指令分歧(Branching)

分歧用來決定程式執行的順序。
Example:

// Computes: if R0 > 0
//               R1 = 1
//           else
//               R1 = 0

@R0
D=M // D=RAM[0]

@8
D;JGT

@R1
M=0 // RAM[1] = 0
@10
0;JMP // end of program

@R1 // Line 8
M=1 // R1 = 1

@10 // Line 10
0; JMP

不過上面的例子可讀性很低，這邊可以使用“符號引用(symbolic references)”與“標籤(label)”的功能來改寫：

@R0
D=M // D=RAM[0]

@POSITIVE
D;JGT

@R1
M=0 // RAM[1] = 0
@END
0;JMP // end of program

(POSITIVE)
@R1 // Line 8
M=1 // R1 = 1

(END)
@END
0; JMP

變數(Variables)

變數是一個用來儲存值的容器，在Hack中使用一個16bits大小的暫存器來表示所有的變數。
Example:

// Flips the values of RAM[0] and RAM[1]

// temp = R1
// R1 = R0
// R0 = temp

@R1
D=M
@temp
M=D // temp = R1

@R0
D=M
@R1
M=D // R1 = R0

@temp
D=M
@R0
M=D // R0 = temp

(END)
@END
0;JMP

使用@temp代表：找到一個可用的記憶體暫存器，並且用這個暫存器替代變數temp。
實作這個組譯器的人需要遵守兩個合約(Contract)：

1. 沒有對應label的symbol引用，會被視為變數
2. 變數要從位置16以後開始進行分配

透過上面的標籤方法，我們可以實現“可重定位程式碼(relocatable code)”。

迭代/迴圈(Iteration)

假設我們要計算下面這個公式：

1+2+…+n

可以用下面的方式實現：

// Computes RAM[1] = 1 + 2 + ... + RAM[0]

@R0
D=M

@n
M=D //n = R0

@i
M=1 // i = 1
@sum
M=0 // sum = 0

(LOOP)
@i
D=M
@n
D=D-M
@STOP
D;JGT // if i > n goto STOP

@sum
D=M
@i
D=D+M
@sum
M=D // sum = sum + i

@i
M=M+1 // i = i + 1
@LOOP
0;JMP

(STOP)
@sum
D=M
@R1
M=D // R1 = sum

(END)
@END
0;JMP

撰寫Hack的最佳實踐過程：

1. Design。先以pseudo code撰寫功能。
2. Write。再將其翻譯成組合語言。
3. Test。透過紙筆進行暫存器/記憶體的追蹤模擬。

指標(Pointers)

假設我們需要對一個陣列進行操作：
Example:

// for (i=0; i<n; i++){
//     arr[i] = -1;
// }
// suppose that arr=100 and n=10

// arr = 100
@100
D=A
@arr
M=D

// n = 10
@10
D=A
@n
M=D

// initialize i = 0
@i
M=0

(LOOP)
// if(i==n) goto END
@i
D=M
@n
D=D-M
@END
D;JEQ

// RAM[arr+i] = -1
@arr
D=M
@i
A=D+M // 直接指定Address
M=-1

// i++
@i
M=M+1

@LOOP
0;JMP

(END)
@END
0;JMP

像這樣保存記憶體位置的變數（例如arr、i）就稱為指標。
在HACK中的典型作法是：將“地址暫存器”設定為“記憶體暫存器的內容”，例如A=M這樣的指令。

輸入與輸出(Input/Output)

如先前提到的，輸入與輸出（鍵盤與螢幕）分別被對應在記憶體上。
螢幕(SCREEN)是從位址16384開始的8K範圍，鍵盤(KBD)則是在位址24576。

假設我們想在螢幕左上角畫一個16 pixel寬的矩形，而RAM[0]提供使用者定義矩形的長。

Example:

addr = SCREEN
n = RAM[0]
i = 0

LOOP:
    if i > n goto END
    RAM[addr] = -1 // 111111111111111
    addr = addr+32
    i = i+1
END:
    goto END

@R0
D=M
@n
M=D // n = RAM[0]

@i
M=D // i = 0

@SCREEN
D=A
@address
M=D // address = 16384

(LOOP)
@i
D=M
@n
D=D-M
@END
D;JGT // if i>n goto END

@address
A=M
M=-1 // RAM[address] = -1 (16 pixels)

@i
M=M+1 // i = i+1
@32
D=A
@address
M=D+M // address = address +32
@LOOP
0;JMP // goto LOOP

(END)
@END
0;JMP

本週的作業是使用Hack Assembly撰寫兩個程式：

1. 乘法運算：計算R2 = R0*R1
2. 簡單交互程式：偵測使用者按下任何按鍵，將螢幕顯示為黑色

幾個提示：

1. 使用變數(Variables)與標籤(Labels)
2. 使用有意義的變數與標籤名稱
3. 變數使用小寫
4. 標籤使用大寫
5. 使用縮排(indentation)
6. 先寫虛擬碼(pseudo code)