From Nand to Tetris系列（五）

Chapter 5. Machine Language (Part 1)

大多數的裝置只能完成單一的任務，例如洗碗機只負責洗碗，但是像電腦、手機(也算是電腦的一種)這類裝置，可以單靠同樣的硬體完成不同的工作。

電腦最早可以追朔到由Alan Turing提出的概念：圖靈機。
他發現雖然有許多圖靈機，但其中有一種可以在給定正確的程式下執行各種任務(即：通用圖靈機)。

而Von Neumann是最早的電腦實作者，透過將軟體放入硬體中，用來控制硬體的各種運作，實作各種功能，成為現代電腦最早的雛形。

要了解通用電腦，解開祕密的原理就在於存在於電腦系統記憶體裡的程式，硬體是固定的，但是軟體可以改變，程式其實就是一連串的指令，不同的指令與順序就可以組合出不同的功能。

指令的幾個元素

第一個元素是operation：這個指令是做什麼樣的運算？
第二是元素是program counter：我們怎麼知道何時執行什麼指令？
第三是元素是addressing: 指令執行的對象？運算元在哪？要存到哪？

Compilation

目前描述的程式對硬體來說很容易，但是對人類閱讀就不太方便，因此現實上人不會直接撰寫machine language，而是寫高階語言(high level language)再透過編譯器(compiler)將高階語言轉換成機器語言。

機器語言是一串二進位數值，難以閱讀，為了方便起見會將一些指令給一個註記詞，例如“ADD”來取代“011000”，相同的，Register可以用R2, R3等註記詞來表示。

關於這種symbolic有兩種看法(或解釋interpretation)：

1. symbolic form實際上不存在，只是為了方便人類記憶用(現階段)
2. 可以進一步實際撰寫assembly language，再透過組譯器(assembler)將組合語言轉換為機器語言

另一件事情需要留意的是symbols。
有時候我們需要指定記憶體位置，但位置對人類來說只是數字沒有意義也不方便記憶，這時候可以透過組譯器的幫助，建立一個用來替代的符號(symbolic symbol)，例如記憶體位置129 (mem[129])我們可以用一個index的符號來表示。

機器語言的基本元素

定義一個機器語言需要考量三個方面：

1. 機器語言是硬體與軟體之間的一個介面
2. 通常與實際的硬體架構有關
3. 最後要考慮的是cost-performance之間的取捨(tradeoff)

機器支援的運算

機器語言支援幾種不同類型的運算，例如算術運算、邏輯運算、流程控制，另外也要考慮支援的資料型別，有些系統支援更豐富的資料型別，例如：浮點數。

下一個議題是定址(addressing)，我們要如何決定什麼資料用來進行運算？如何取得資料？

記憶體階層(Memory Hierarchy)

支援存取的記憶體越大則需要的定址線越多，花費的時間也越多，反之，若希望存取速度加快就必須犧牲大小。
一種折衷的解法就是採用記憶體階層(memory hierarchy)，用較小的記憶體(cache)換取較快的存取速度，離CPU越遠則大小越大，但花費時間較多(記憶體memory、硬碟disk)。
通常CPU內部都有包含暫存器，機器語言主要操作的對象也是暫存器，暫存器也與記憶體之間有一定的映射關係，可以用暫存器來指定要操作的記憶體位址，或將暫存器內容保存回記憶體。

回到一開始的問題，如何決定什麼資料進行運算？有四種可能或者四種定址模式(addressing mode)：
暫存器(Register)：操作的對象為暫存器，add R1, R2
直接定址(Direct)：可以直接操作記憶體，add R1, M[200]
間接定址(Indirect)：暫存器保存的是記憶體位置，add R1,@A
立即值(Immediate)：在運算過程中直接定義數值，add 73,R1

輸入與輸出

一般來說輸入/輸出裝置會映射到記憶體的某個區段，系統的驅動程式會知道如何透過這個記憶體區段與裝置進行溝通。

流程控制

通常CPU是循序執行，不過有時候我們可能需要調整執行順序，例如進行迴圈，jump指令用來進行無條件轉跳(unconditional jump)，另外也有條件式轉跳(conditional jump)。

Hack電腦與機器語言

Hack的硬體部分包含(16-bit)：指令記憶體(ROM, instruction memory)、CPU與資料記憶體(DAM, data memory)、總線(instruction bus/data bus/address bus)。

軟體的部分包含：16-bit A類型的指令(A-instructions)與C類型的指令(C-instructions)。

控制(Control)：只有一個重置按鈕(reset button)。

整個程式執行流程如下：
1.將program讀取至ROM
2.按下reset button
3.程式開始執行

其他部分：
3種暫存器：D(data): 16-bit value / A(address): 16-bit資料或位置 / M(Memory):在RAM內部，16-bit RAM暫存器位置，用來選取記憶體中的資料。

A-instruction：

syntax: @value

Example 1:

@21 // 設定A暫存器內容為21，且RAM[21]為選取的暫存器(M)

Example 2:

// set RAM[100] to -1
@100 // A=100
M=-1 //RAM[100]=-1

C-instruction：

syntax: dest = comp ; jump // dest, jump為選擇性參數

計算結果之後，可以保存數值(將結果保存於dest)或者以計算結果作為是否跳躍的依據

comp可以是：0, 1, -1, D, A, !D, !A, …
dest可以是：null, M, D, MD, A, AM, AD, AMD
jump可以是：null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP
先進行comp的運算後，根據jump進行比較，若為真則跳躍到ROM[A]，jump永遠與數值0做比較。

Example 1:

// Set the D register to -1
D=-1

Example 2:

// Set RAM[300] to value of the D register minus 1
@300 // A=300
M=D-1

Example 3:

// if (D-1==0) jump to excute the instruction stored in ROM[56]
@56
D-1;JEQ

Example 4:

0;JMP // Unconditional jump

Hack語言規格

你可以使用兩種方式撰寫Hack語言：

1. Symbolic
2. Binary

例如A-instruction的symbolic與binary格式分別為：

Symbolic syntax: @21
Binary syntax: 0000000000010101 // 0開頭為A-instruction

而C-instruction則定義如下：

Symbolic syntax: dest = comp; jump
Binary syntax: 1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
(opcode: 1 bit)(not used: 2 bits)(comp bits: 7 bits)(dest bits: 3 bits)(jump bits: 3 bits)

使用symbolic需要再透過assembler轉換為binary的格式才能夠執行。

Comp對應表

comp (a=0)	comp (a=1)	c1	c2	c3	c4	c5	c6
0		1	0	1	0	1	0
1		1	1	1	1	1	1
-1		1	1	1	0	1	0
D		0	0	1	1	0	0
A	M	1	1	0	0	0	0
!D		0	0	1	1	0	1
!A	!M	1	1	0	0	0	1
-D		0	0	1	1	1	1
-A	-M	1	1	0	0	1	1
D+1		0	1	1	1	1	1
A+1	M+1	1	1	0	1	1	1
D-1		0	0	1	1	1	0
A-1	M-1	1	1	0	0	1	0
D+A	D+M	0	0	0	0	1	0
D-A	D-M	0	1	0	0	1	1
A-D	M-D	0	0	0	1	1	1
D&A	D&M	0	0	0	0	0	0
D|A	D|M	0	1	0	1	0	1

Dest對應表

dest	d1	d2	d3	effect: the value is store in:
null	0	0	0	The value is not stored
M	0	0	1	RAM[A]
D	0	1	0	D register
MD	0	1	1	RAM[A] and D register
A	1	0	0	A register
AM	1	0	1	A register and RAM[A]
AD	1	1	0	A register and D register
AMD	1	1	1	A register, RAM[A], and D register

Jump對應表

jump	j1	j2	j3	effect
null	0	0	0	no jump
JGT	0	0	1	if out>0 jump
JEQ	0	1	0	if out=0 jump
JEG	0	1	1	if out>=0 jump
JLT	1	0	0	if out<0 jump
JNE	1	0	1	if out!=0 jump
JLE	1	1	0	if out<=0 jump
JMP	1	1	1	unconditional jump

輸入與輸出

I/O裝置可以用來接收使用者的輸入資料，或顯示資料給使用者。
如果使用高階語言(例如：Java等)，可以透過函式庫(library)對硬體應形操作，但如果是在較低階的層級，我們必須以bit為單位對硬體進行控制。

輸出(螢幕)
會有一塊記憶體(Screen Memory Map)對應到實體記憶體，當更新這塊記憶體，就會對應的更新螢幕上顯示的內容。
本課程使用的顯示大小高寬為256*512，由於螢幕寬度為512，一個word為16 bits，因此總共有8k個word，其中一個bit對應一個pixel。
由於螢幕是二維的，而記憶體是一維，我們需要定義某種規則將兩邊關聯(映射)起來，其規則是每32個word(512個bits)對應一行(row)。
值得注意的是，我們存取的最小單位(bus寬度)為16 bits，所以我們想要修改一個pixel時，我們需要讀取16個bits之後，對其中要操作的bit進行運算，再將其存回記憶體中。

bit i = 32row + col/16
word = Screen[32row + col/16]

而由於這個“代表螢幕的8k記憶體”會對映到整個系統的記憶體中的某個區段，因此對於整體記憶體來看，要存取螢幕的記憶體還需要加上一個base address，其正好是16384。

word = RAM[16384 + 32*row + col/16]

最後透過modulo(%)取得要操作的bit，就可以操作對應的pixel。

set the (col%16)th bit of word to 0 or 1

輸入(鍵盤)
與螢幕類似，鍵盤也會對映到一個記憶體範圍，稱為Keyboard Memory Map，而實際上只需要一個16 bit的register即可。
每個按鍵會對映到一個key code，當按下按鍵時鍵盤就會將對應的key code放入register中。
當沒有任何按鍵的狀態下，register的內容會是0，藉此可以用來判斷是否有輸入產生。
在Hack中，Keyboard Memory Map對應到記憶體位置RAM[24576]。