# 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)