2018quiz7-7

contributed by <PunchShadow , jia05>

---

程式理解

Swith.c

/* 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

• 背景知識補充：

  • $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)
    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，用來初始化一個變數用

• 流程圖：

解題方法

• 先 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
  ​​​​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 做完回傳值

  • 這邊認為 1, -1, 3, 5 的順序寫錯，由於 $r10 是儲存 Array 第一個 address 的地方，第6行程式的rmmovq %rax, (%r10) 是將值 store 到 Array 第一個位址，因此若照這個 main 的程式邏輯去判斷，第一個位址應該要是存放 idx = -1 之值
    因此寫入到 %rdi 值的順序要改為 -1, 1, 3, 5才對

  • 接著進入 switchv 的部分
  ​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
  

  • • 這邊我們認為 第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 的部分
  ​ 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 部分
  ​addr: # jump using table address
  ​	addq %r8, %rcx
  ​	mrmovq (%rcx), %rdi
  ​	pushq %rdi
  ​	ret
  

  • 將所取得到的 table address push 到 stack 內，並跳躍到指定的 table中
  • table 之值
  ​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 的挖空部分

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