# Ch2：Instructions: Language of the Computer
:::warning
本筆記只有抄到 2-12，因為後面的出題機率過低就不寫了
之後應該會補上
:::
本章主要在讓讀者理解電腦真正能「聽懂」的是什麼語言——也就是機器指令（machine instructions），本章將從高階語言一路深入到底層的指令集結構。
## 2-1 Instruction
- **Instruction set（指令集）**：
- 不同電腦有不同的指令集（但大部分相同）
- 早期電腦使用**較簡單的指令集**
### MIPS 指令集
:::warning
本書所有指令都參考 MIPS
:::
- 是 **RISC** 結構的代表
- 被廣泛運用在**嵌入式系統**
- 是許多現代指令集的經典
## 2-2 Operations of the Computer Hardware
## 2-3 Operands of the Computer Hardware
### Regigster Operands
- 用於**算數操作**
- MIPS 共有 32 * 32-bit 的 register file
- 用於**高頻率存取**資料
- 編號從 0 ~ 31
- 32-bit 的資料稱為一個 **word**
- Assembler name
- **Temporary Value**：`$t0` 到 `$t9`
- **Static variables**：`$s0` 到 `$s7`
- `$zero`：MIPS register 中的預留常數，不可被 overwrite
### Memory Operands
- **Main memory** 用來儲存**複合資料**
- Array, Structure, Dynamic Data
- 每一個 memory address 對應到一個 bytes
- **MIPS** 是 **Big Endian** 的
- **Big Endian**：MSB first
- **Little Endian**：LSB first
- 範例：
- h in `$s2`, A in `$s3`
- C code
```c=
A[12] = h + A[8];
```
- MIPS
```mips=
lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)
```
### Immediate Operands
:::warning
注意：Immediate Operands 不可以進行減法
:::
- 在指令中的**常數資料**
- 不可被用於減法，可以透過**加負數**來進行減法
```mips=
addi $s2, $s1, -1
```
## 2-4 Unsigned and Signed
### Unsigned
- 無號數 -> 可以直接轉換
- e.g. $0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 1011_2 = 11_{10}$
- 範圍：$0$ ~ $2^n-1$
### 2's-Complement
- 有號數
- 轉換方式：
- 範例：-14(8-bit)
- **先把無號數轉成 2 進位**：$14 = 0000\ 1110_2$
- **0 -> 1, 1 -> 0**： $0000\ 1110_2 = 1111\ 0001_2$
- **加一**： $1111\ 0010_2$
- 範圍：$-2^{n-1}$ ~ $2^{n-1}-1$
- **Sign Extension**：
- 當我們要用更大容量的資料型態儲存我們的數字時，就必須做 sign extension
- **正數補 0，負數補 1**
### Sign-magnitude
- 有號數，把 sign 和 magnitude 分開表示
- 轉換方式：
- 範例：-14(8-bit)
- **Sign** = 1（Negative）
- **Magnitude** = $14 = 000\ 1110_2$
- **Sign + Magnitude**：$-14 = 1000\ 1110_2$
- 範圍：$-2^{n-1}+1$ ~ $2^{n-1}-1$
## 2-5 Representing Instructions in the Computer
- 所有 MIPS 指令大小都是 32-bits
### R-format
- `op`: operation code **(opcode)**
- ==**R-format 一律放 0**==
- `rs`: first source register number
- `rt`: second source register number
- `rd`: **destination** source register number
- `shamt`: shift amount
- `funct`: function code (extend opcode)
- ==R-format 放 opcode==
- 範例：
### I-format
- `rt`: **destination or source** register number
### J-format
## 2-6 Logical Operation
- **sll**：左移
- **srl**：右移
## 2-7 Conditional Operations
### 條件判斷
- 條件判斷：當條件符合時跳到指定的 instruction
- 若不符合：繼續往下執行
- **beq**：if
```mips=
beq rs, rt, L1
```
- if **(rs == rt)** branch to instruction labeled L1
- **bne**：if not
```mips=
bne rs, rt, L1
```
- if **(rs != rt)** branch to instruction labeled L1
- **slt**：
- MIPS：
```mips=
slt rd, rs, rt
```
- C code:
```c=
if (rs < rt) rd = 1; else rd = 0;
```
- **sle**：
- MIPS：
```mips=
slti rt, rs, constant
```
- C code:
```c=
if (rs < constant) rt = 1; else rt = 0;
```
- **j**：jump
- 直接跳到指定的 instruction
### Loop statement
- **C code**：
```c=
while (save[i] == k) i += 1;
```
- **MIPS**：
- i in `$s3`, k in `$s5`, address of save in `$s6`
```mips=
Loop:
sll $t1, $s3, 2
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
addi $s3, $s3, 1
j Loop
Exit:...
```
### Basic block
- **定義**：Basic block 是一連串代碼，包含以下兩個特性：
- **沒有內部分支（embedded branches）**，除了結尾（例如跳躍或條件分支）。
- 沒有分支目標（branch targets），除了在區塊開頭。
- Compiler 會辨別程式裡的 Basic block 進行優化
### Unsigned and Sign Comparison
- **Signed**：slt, slti
- **Unsigned**：sltu,sltui
## 2-8 Supporting Procedures in Computer Hardware
### Register 使用
- `$a0` ～ `$a3`: 參數暫存器（arguments）
- 對應 register 4 ~ 7。
- 用來傳遞函式的參數。
- `$v0`, `$v1`: 回傳值暫存器（result values）
- 對應 register 2 和 3。
- 用來存放函式的回傳值。
- `$t0` ~ `$t9`: 暫時暫存器（temporary values）
- 用來儲存**臨時計算**結果。
- 可以被呼叫者**覆寫**（callee 可以自由使用，不用保留）。
- `$s0` ~ `$s7`: 保存暫存器（saved variables）
- 用來儲存**需要保留的資料**。
- **必須由被呼叫者保存與恢復**（callee 必須在進入與離開時處理）。
- `$gp`: global pointer
- Register 28。
- 指向靜態資料的全域指標。
- `$sp`: stack pointer
- Register 29。
- 指向目前 stack 的頂端，管理函式呼叫時的堆疊空間。
- `$fp`: frame pointer
- Register 30。
- 協助存取目前函式的參數與區域變數。
- `$ra`: return address
- Register 31。
- 儲存函式呼叫的返回位址（通常由 `jal` 指令自動寫入）。
### Procedure call
- **jal**：jump and link
- 語法：
```mips=
jal ProcedureLabel
```
- 功能：
- 把下一條指令的 address 存到 `$ra` 裡，儲存跳回來的地方
- 跳到 `ProcedureLabel` 所代表的副程式位置執行。
- 執行完副程式後會自己跳回來
- **jr**：Jump register
- 語法：
```mips=
jr $ra
```
- 功能：
- 把 `$ra` 的內容複製到 PC(program counter)
- 放在**副程式**裡面，這樣就會跳回主程式
- 比較：
| 指令 | 全名 | 功能描述 | 是否儲存 return address | 用途範例 |
|---------|------|----|-------|-----------|
| `j` | jump | 無條件跳轉到指定的標籤（Address） | 否 | 跳過一段程式碼 |
| `jal` | jump and link | 跳轉到副程式並儲存返回 Address 至 `$ra` | 是 | 呼叫副程式（function call） |
| `jr` | jump register | 跳轉到暫存器指定的 Address（通常是 `$ra`） | 否 | 副程式返回、switch-case |
### Local Data on the Stack
:::warning
注意，Stack 是倒過來長的
:::
- Local data 會被 callee 分配的
- **Procedure frame**：
- 用來存放副程式執行所需的資料
- MIPS 會使用 `$fp`, `$sp`，來標記 procedure frame 的位置
- 程式可以存取 procedure frame 內部的資料
- **以下資料需要用 stack 存**：
- `$s0` ~ `$s7`
- `$ra`
- 第五個以上的 argument（`$a0` ~ `$a3` 不夠存）
### Leaf procedure
- **定義**：不呼叫任何其他函式的函式
- Example：
- C code：
```c=
int leaf_example (int g, h, i, j){
int f;
f = (g + h) - (i + j);
return f;
}
```
- MIPS code：
- Arguments g, …, j in `$a0`, …, `$a3`
- f in `$s0` (hence, need to save `$s0` on stack)
- result in `$v0`
```mips=
leaf_example:
# Save $s0 on stack
addi $sp, $sp, -4
sw $s0, 0($sp)
# Body
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
# Result
add $v0, $s0, $zero
# Restore $s0
lw $s0, 0($sp)
addi $sp, $sp, 4
# return
jr $ra
```
- `sw`：把 register 的資料 store 到 memory 中
- `lw`：把 memory 的資料 load 到 register 中
### Non Leaf Procedure
- **定義**：有呼叫其他函式的函式
- Example:
- C code：
```c=
int fact (int n){
if (n < 1) return 1;
else return n * fact(n - 1);
}
```
- MIPS：
- Argument n in `$a0`
- Result in `$v0`
```mips=
fact:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $a0, 0($sp)
# test for n < 1
slti $t0, $a0, 1
beq $t0, $zero, L1
addi $v0, $zero, 1
addi $sp, $sp, 8
jr $ra
L1:
# recursive call
jar fact
lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
mul $v0, $a0, $v0
jr $ra
```
- 呼叫在其他函式後，register 中的 `$a0`, `$ra` 會被改變，需要用 **lw** 來還原
### Memory layout
- **Text**：code
- **Static data**：Global variables
- **Dynamic data**：儲存於 heap，屬於動態分配的記憶體
- e.g. `malloc`
- **Stack**：自動存取
## 2-9 Communicating with People
- **ASCII**：128 characters
- **Unicode**：256 characters
## 2-10 MIPS Addressing for 32-bit Immediates and Addresses
### Byte/Halfword Operations
- 主要處理較小單位的應用
- byte = 8 bit
- halfword = 16 bit
- **lb**：讀取 **8 bits** 擴充**有號數**到 32 bits
```mips
lb rt, offset(rs)
```
- **lh**：讀取 **16 bits** 擴充**有號數**到 32 bits
```mips
lh rt, offset(rs)
```
- **lbu**：讀取 **8 bits** 擴充**無號數**到 32 bits
```mips
lbu rt, offset(rs)
```
- **lhu**：讀取 **16 bits** 擴充**無號數**到 32 bits
```mips
lhu rt, offset(rs)
```
- **sb**：只儲存**最低 byte**
```mips
sb rt, offset(rs)
```
- **sb**：只儲存**最低 byte**
```mips
sb rt, offset(rs)
```
- **sh**：只儲存**最低 halfword**
```mips
sh rt, offset(rs)
```
### 32-bit Constant
- 大部分的常數都只有 16 bit
- 我們可以透過下方方式來組合出一個 32 bit 常數
```mips=
lui $s0 upper_16_bits
ori $s0 $s0 lower_16_bits
```
- **lui**：把 16 bit 存到高 16 位
- **ori**：利用 **or** 運算儲存低 16 位
### Branch Addressing
:::warning
**Branch Addressing** 用於目標 address 在 PC 附近的情況（移動範圍：16 bit）
:::
- 大部分的目標都在鄰近的 branch 上
- 可以用前進、後退的方式查找
- **PC-relative addressing**：
- 目標 address = PC（現在的 address） + offset $\times$ 4
### Jump Addressing
:::warning
**Jump Addressing** 用於目標 address 離 PC 很遠的情況（移動範圍：26 bit）
:::
- Jump（j, jal）指令可以允許程式移動到 **Text segment** 中的任何地方
- **J format**：
- 目標 address = PC31...28 : (address $\times$ 4)
### Branch Far Away
我們可以使用 **j** 指令來取代 branch 太遠的情形
- **改善前**：
```mips=
beq $s0, $s1, L1 # 16 bits
```
- L1 太遠，我們抓不到
- **改善後**：
```mips=
bne $s0, $s1, L2 # 16 bits
j L1 # 26 bits
L2: ...
```
- 使用 **j** 來存取 L1
### MIPS 存址的五大模式
## 2-12 Translating and Starting a Program
Sign in with Wallet
Connect another wallet