owned this note
owned this note
Published
Linked with GitHub
# 2018quiz7-7
contributed by <`PunchShadow` , `jia05`>
---
## 程式理解
### Swith.c
```clike=
/* switch.c */
#include <stdio.h>
long switchv(long idx) {
long ret = 0;
switch (idx) {
case 0: ret = 0xaaa; break;
case 2: case 5: ret = 0xbbb; break;
case 3: ret = 0xccc; break;
default: ret = 0xddd;
}
return ret;
}
int main() {
long vals[8];
for (long i = 0; i < 8; i++) {
vals[i] = switchv(i - 1);
printf("idx = %ld, val = 0x%lx\n", i - 1, vals[i]);
}
return 0;
}
```
可以預期這段程式的作用是將 `swithv()` 中 印出 cases -1~6，並以16進位的列印，由於 `long` type 是 ==unsigned== 的，因此 assign 進去 vals 的值都皆為正數，而預期輸出結果應為：
```
idx = -1, val = 0xddd
idx = 0, val = 0xaaa
idx = 1, val = 0xddd
idx = 2, val = 0xbbb
idx = 3, val = 0xccc
idx = 4, val = 0xddd
idx = 5, val = 0xbbb
idx = 6, val = 0xddd
```
### switch.s
接著看 Y86-64 的 assembling code 部份，指令集的話可以參考 [Instruction Set of Y86-64](https://github.com/boginw/js-y86-64/wiki/Instruction-set)
* 背景知識補充：
* $rsp 為 stack pointer register，指向 stack 的第一個位置（最高位置），並向下成長（由大到小) ，且須在一開始就設定好
* 有3個 Condition codes : ZF(Zero), SF(Negative), OF(Overflow)，用來判斷==最近一次的算術或邏輯運算的情形==，若產生 Zero 則將 ZF 設為1，依此類推
* Branch Instructions 皆可以由 ZF, SF, OF 三者的邏輯運算進行判斷，簡易的判斷方法及為照指令上翻譯即可，如下：
| Instruction | Meaning | Description |
| :------: | ----------- | -------- |
| JE | Jump If Equal | Jumps to `Dest` if `ZF` |
| JNE | Jump If Not Equal | Jumps to `Dest` if `~ZF` |
| JL | Jump If Less Than | Jumps to `Dest` if `SF^OF` |
| JLE | Jump If Less or Equal | Jumps to `Dest` if `(SF^OF)|ZF` |
| JG | Jump if Greater Than | Jumps to `Dest` if `~(SF^OF)&~ZF` |
| JGE | Jump If Greater or Equal | Jumps to `Dest` if `~(SF^OF)` |
| JMP | Uncondition | Jumps to `Dest` unconditionaly |
* Common directive：
* .pos x : 顯示程式開始於 address x
* .align x : 將下行程式之 boundary 設定成 x-byte i.e. 以本題來說，long 需要 32 bits 及為 8 bytes 所以宣告 Array 時要 `.align 8`
* .quad x : 將一個 8-byte x 值放入目前的 address，用來初始化一個變數用
* 流程圖：
```flow
st=>start: Initialze
e=>end: Halt
op=>operation: main
op2=>operation: switchv
op3=>operation: def
op4=>operation: mul
op5=>operation: addr
op6=>operation: table
cond=>condition: idx>5？
cond2=>condition: idx<0?
cond3=>condition: %r10 == %rdi
cond_end=>condition: is main ended?
st->op->cond_end
op2(right)->cond
op3(left)->op2
cond_end(yes)->e
cond_end(no,right)->op2
cond(yes)->op3
cond(no,right)->cond2
cond2(yes,left)->op3(bottom)
cond2(no)->op4->cond3
cond3(yes)->op5
cond3(no)->op4(right)->op
```
### 解題方法
* 先 trace 一遍
``` =
/* switch.s */
.pos 0
irmovq stack, %rsp
call main
halt
.align 8
array:
.quad 0x0000000000000000
.quad 0x0000000000000000
.quad 0x0000000000000000
.quad 0x0000000000000000
```
* `.pos 0` : 程式開始於 0 這個 address
* `irmovq stack, %rsp` : 設定 stack 起始位置存於 %rsp 內
* `call main` : 跳到 main 的部份並將 return address `push` 到 `stack` 中
* `7-12` : 為進行 initialize array
``` assembly=
main:
irmovq array, %r10
irmovq $1,%rdi
call switchv
rmmovq %rax, (%r10)
irmovq $-1,%rdi
call switchv
rmmovq %rax, 8(%r10)
irmovq $3,%rdi
call switchv
rmmovq %rax, 16(%r10)
irmovq $5,%rdi
call switchv
rmmovq %rax, 24(%r10)
ret
```
* 這段為主程式，可以將其看作 4 個相似的部份，分別將 1、-1、3、5送入 `.swithv` 內進行運算
* `$r10` : 儲存 Array 第一個 component address
* `$rdi` : 當作 arugment 傳入 swithv 中
* `$rax` : swithv 做完回傳值
* :::info
這邊認為 1, -1, 3, 5 的順序寫錯，由於 $r10 是儲存 Array 第一個 address 的地方，第6行程式的`rmmovq %rax, (%r10)` 是將值 store 到 Array 第一個位址，因此若照這個 main 的程式邏輯去判斷，第一個位址應該要是存放 ==idx = -1== 之值
因此寫入到 %rdi 值的順序要改為 ==-1, 1, 3, 5==才對
:::
* 接著進入 switchv 的部分
```assembly=
switchv:
# contant
irmovq $8, %r8
irmovq $0, %r10
irmovq $1, %r11
irmovq $0, %rax
irmovq table, %rcx # table address
rrmovq %rdi, %rdx
________
jg def # idx > 5
subq %r10, %rdi
jl def # idx < 0
```
* :::info
* 這邊我們認為 ==第10行程式的註解錯誤== ，原因在於 idx 相對於 switch.c 中的 `i` ，因此應該是判斷 ==#idx > 8== 才對
* 可以推導得到上方缺少部分一定是要用目前儲存 idx 值的 register %rdi 或 %rdx 去減掉 %r8 (value = 8)
* 但 subq 這個指令會將改掉 rB register 內的值，因 第11行 指令已經使用了 %rdi 因第九行就只能使用 ==subq %r8 %rdx== 去判斷是否 %rdx > 8
* 若 idx > 8 或 idx < 0 都會跳到 def 內執行，由此可知 ==def 是進行超出邊界的處理==
* mul 的部分
```assembly=
mul: # calculate 8 * %rdi
subq %r10, %rdi # %r10 = 0
je addr
addq %r8, %rcx # %r8 = 8, %rcx = table address
subq %r11, %rdi # %r11 = 1
jmp mul
```
* 利用判斷 %rdi 內的值是否等於0去將 ==%rcx = %rcx + 8 * %rdi== 得到的值可以去選取 table 內的值
* addr 部分
```assembly=
addr: # jump using table address
addq %r8, %rcx
mrmovq (%rcx), %rdi
pushq %rdi
ret
```
* 將所取得到的 table address push 到 stack 內，並跳躍到指定的 table中
* table 之值
```assembly=
table:
.quad LD # default branch
.quad L0 # idx == 0
.quad L1 # idx == 1
.quad L2 # idx == 2
.quad L3 # idx == 3
.quad L4 # idx == 4
.quad L5 # idx == 5
```
* 由此表可看出 table + 8 為 default branch(相當於 switch.c 中 switch 內 default 的部分)，這也是為何在 addr 中要先將 %rcx+8 的原因
* 根據不同的位址，會跑到LD~L5中執行不同的運算，其中 L0-L5 就相當於 switch.c 中不同的 cases 一樣，將不同的值寫入 ==%rax== 中
* 最後跳回 main 時再將 %rax 內容存到對應的 Array address 中
* 最後看到 def 的挖空部分
```assembly=
def: # default branch
irmovq table, %rcx
________
pushq %rdi
ret
```
* 會進入到這邊的情況，都應該屬於 cases 中 default 的情形，包刮 <0 和 >8
* 因此從將 table 之 address load 進 %rcx，後面是 pushq %rdi 可推測，中間這個不分應該是要將 ==處理 default 的位置存到 %rdi 中==
* 而 LD 位置為 &(%rcx) ，使用 ==mrmovq (%rcx), %rdi==
>所以本題兩個答案應為：
>==subq %r8 %rdx== 和 ==mrmovq (%rcx), %rdi==
>
>參考：[Introduction to X86-64 Assembly for Compiler Writers](https://www3.nd.edu/~dthain/courses/cse40243/fall2015/intel-intro.html)
Sign in with Wallet
