这篇文章是csapp第三章第六节的阅读笔记。

0x00 条件码

控制语句需要进行条件判断，根据不同的判断值进行不同的操作。

这里涉及到的主要指令就是JUMP了。

不过在跳转之前，先看看如何来判断条件。

这就是条件码（Condition Codes）的作用了。

条件码使用只有一个bit的寄存器来标识，一共有四个：

• CF：进位标志。用来检测无符号数的溢出；
• ZF：零标志位。用来检测最近一次操作的值是否是0；
• SF：符号标志位。用来检测最近一次操作的值是否是负数；
• OF：溢出标志位。用来检测有符号数是否溢出。

前面介绍的指令对这些标志位的影响：

• leaq指令不设置任何标志位；
• 之外的所有算术运算指令都设置标志位。

还有一些指令不改变寄存器的值，但是可以该表标志位：

其中TEST指令经常这样使用testq %rax, %rax，用来检测%rax的值是正数负数还是0。

0x01 访问条件码

除了直接访问条件码外，有三种方式可以读取条件码：

• 根据条件码的组合设置一个字节为0或1；
• 根据条件码的组合情况来跳到程序的另一个地方执行；
• 条件转移数据（conditionally transfer data）。

下面的指令就是第一种读取条件码的方式：

这里对于比较同样是区分了有符号和无符号整数。

而且不像其他带有字节大小的后缀的指令，这些指令不区分字节大小，因为根据操作数就可以判断了。

0x02 Jump指令

对于控制语句来说，最重要的就是根据条件执行不同的代码了，这就需要Jump指令。

Jump指令和上面的Set指令类似，不同在于Jump的结果是跳转到不同的地方执行指令。

跳转有两种，无条件跳转和有条件跳转。

上面的jmp Label和jmp *Operand就是无条件跳转，其余的都是有条件跳转。

其中无条件跳转还有两种：直接跳转和间接跳转。

直接跳转直接给出跳转的地址，跳过去就好了。

间接跳转给出的相当于一个地址的地址，根据里面的地址再跳到对应的地方。

比如jmp *%rax使用%rax里面的值作为跳转的地址。

0x03 跳转指令的编码

接下来需要了解跳转指令的编码。有几种方式，但是最常见的还是PC计算器相对地址。

比如：

    movq    %rdi, %rax
    jmp        .L2
.L3:
    sarq    %rax
.L2:
    testq    %rax, %rax
    jg        .L3
    rep; ret

对生成的.o文件进行反编译的结果：

0: 48 89 f8     mov %rdi,%rax
3: eb 03         jmp 8 
5: 48 d1 f8     sar %rax
8: 48 85 c0     test %rax,%rax
b: 7f f8         jg 5 
d: f3 c3         repz retq

第一个跳转的目标是0x8，就是对应的第4行的test指令，那么这个地址0x8是怎么来的呢？

看一下jmp指令的操作数是0x03，下一个指令的地址是0x05，想加刚好是0x8。

第二个跳转的目标是0x5，对应的就是第3行的sar指令。jg的操作数是0xf8，补码表示的是-8，下一条指令的地址是0x0d，想加得到对应的跳转目的0x5。

PC计数器相对地址跳转：相对的是Jump指令的下一个指令的地址，而不是Jump本身。

0x04 用条件控制来实现条件分支

一个简单的实现条件分支的想法就是根据判断条件去跳转。

在C语言中是这样的：

if (test-expr)
    then-statement
else
    else-statement

汇编代码是基于如下的C格式来实现的：

    t = test-expr;
    if (!t)
        goto false;
    then-statement;
false:
    else-statement
done:

一个简单的C语言例子：

long lt_cnt = 0;
long ge_cnt = 0;

long absdiff_se(long x, long y) {
    long result;
    if (x < y) {
        lt_cnt++;
        result = y - x;
    } else {
        ge_cnt++;
        result = x - y
    }
    return result;
}

那么，编译的时候是基于下面这个C代码来编译的（这个是为了理解方便）：

long gotodiff_se(long x, long y) {
    long result;
    if (x >= y)
        goto x_ge_y;
    lt_cnt++;
    result = y - x;
    return result;
x_ge_y:
    ge_cnt++;
    result = x - y;
    return result;
}

对应的汇编代码如下：

absdiff_se:
    cmpq %rsi, %rdi            ; Compare x:y
    jge .L2                    ; If >= goto x_ge_y
    addq $1, lt_cnt(%rip)         ; lt_cnt++
    movq %rsi, %rax
    subq %rdi, %rax             ; result = y - x
    ret Return
.L2: x_ge_y:
    addq $1, ge_cnt(%rip)         ; ge_cnt++
    movq %rdi, %rax
    subq %rsi, %rax             ; result = x - y
    ret                         ; Return

0x05 用条件传送来实现条件分支

直接Jump的坏处就是破坏了流水线。

这样在一些情况下会降低流水线的使用。

如果能一直顺序执行就好了，这就是通过条件传送的方式来实现条件分支。

它是基于这样的想法，要么if，要么else，我把两个都算出来，然后根据条件选择一个值就好了，不需要去做跳转。

那么就需要一个特别的指令，能够做到根据条件来选择值。

这就是CMOV：

有了这些指令之后，就可以实现这种类型的条件了：

v = test-expr ? then-expr : else-expr

正常情况下编译器可以根据这种类型的格式来生成汇编代码：

    if (!test-expr)
        goto false;
    v = then-expr;
    goto done;
false:
    v = else-expr;
done:

这是需要跳转的。那么有了上面的指令之后，就可以依据下面的结构编译了：

v = then-expr;
ve = else-expr;
t = test-expr;
if (!t) v = ve;

这就不需要跳转了。

比如下面的代码：

long arith(long x) {
    return x / 8;
}

编译结果如下：

arith:
    leaq    7(%rdi), %rax
    testq    %rdi, %rdi
    cmovns    %rdi, %rax
    sarq    $3, %rax
    ret

因为需要向零取整，所以对于负数需要加一个bias。

0x06 循环

循环也可以使用跳转来实现，只不过需要多个跳转以及条件判断。

6.1 Do-While循环

Do-While循环格式如下：

do
    body-statement
    while (test-expr);

那么使用goto形式的话就是：

loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;

比如下面的例子：

long fact_do(long n) {
    long result = 1;
    do {
        result *= n;
        n = n - 1;
    } while (n > 1);
}

使用goto就是：

long fact_do_goto(long n) {
    long result = 1;
loop:
    result *= n;
    n = n - 1;
    if (n > 1) 
        goto loop;
    return result;
}

编译后：

fact_do:
    movl    $1, %eax
.L2:
    imulq    %rdi, %rax
    subq    $1, %rdi
    cmpq    $1, %rdi
    jg        .L2
    rep; ret

6.2 While循环

While循环的格式如下：

while (test-exr)
    body-statement

对于while循环，有两种实现方式。第一种叫jump to middle：

    goto test;
loop:
    body-statement
test:
    t = test-expr
    if (t)
        goto loop;

比如：

long fact_while(long n) {
    long result = 1;
    while (n > 1) {
        result *= n;
        n = n - 1;
    }
    return result;
}

对应的goto代码：

long fact_while_jm_goto(long n) {
    long reuslt = 1;
    goto test;
loop:
    result *= n;
    n = n - 1;
test:
    if (n > 1)
        goto loop;
    return result;
}

汇编代码：

fact_while:
    movl $1, %eax
    jmp .L5
.L6:
    imulq %rdi, %rax
    subq $1, %rdi
.L5:
    cmpq $1, %rdi
    jg .L6
    rep; ret

另一种实现方式叫做guarded do，是do-while的变型：

t = test-expr
if (!t)
    goto done;
do
    body-statement
    while (test-expr);
done:

首先检查一次，不符合就直接结束，然后就是正常的Do-While循环。

编译器使用更高级别的优化选项的时候就是使用这种方式，比如-O1。

6.3 For循环

For循环的格式如下：

for (init-expr; test-expr; update-expr)
    body-statement

For循环可以转换成一个while循环：

init-expr;
while (test-expr) {
    body-statement;
    update-expr;
}

这样就可以使用while循环的方式来编译for循环了。

比如：

long fact_for(long n) {
    long i;
    long result = 1;
    for (i = 2; i <= n; i++)
        result *= i;
    return result;
}

对应的goto格式：

long fact_for_jm_goto(long n) {
    long i = 2;
    long result =1;
    goto test;
loop:
    result *= i;
    i++;
test:
    if (i <= n)
        goto loop;
    return result;
}

编译结果：

fact_for:
    movl $1, %eax
    movl $2, %edx
    jmp .L8
.L9: loop:
    imulq %rdx, %rax
    addq $1, %rdx
.L8: test:
    cmpq %rdi, %rdx
    jle .L9
    rep; ret

0x07 Switch语句

首先可以通过一系列的Jump指令来实现switch。

在一些情况下，还可以通过使用Jump table的形式来实现。

这里就介绍Jump table的格式。

比如下面的代码：

void swith_eg(long x, long n, long *dest) {
    long val = x;
    switch (n) {
        case 100:
            val *= 13;
            break;
        case 102:
            val += 10;
        case 103:
            val += 11;
            break;
        case 104:
        case 106:
            val *= val;
            break;
        default:
            val = 0;
    }
    *dest = val;
}

对应的goto格式：

void switch_eg_impl(long x, long n, long *dest) {
    /* Table of code pointers */
    static void *jt[7] = {
        &&loc_A, &&loc_def, &&loc_B, &&loc_C, &&loc_D, &&loc_def, &&loc_D
    };
    unsigned long index = n - 100;
    long val;

    if (index > 6)
        goto loc_def;
    /* Multiway branch */
    goto *jt[index];
loc_A:
    val = x * 13;
    goto done;
loc_B:
    x = x + 10;
loc_C:
    val = x + 11;
    goto done;
loc_D:
    val = x * x;
    goto done;
loc_def:
    val = 0;
done:
    *dest = val;
}

编译后：

switch_eg:
    subq $100, %rsi
    cmpq $6, %rsi
    ja .L8
    jmp *.L4(,%rsi,8)
.L3: loc_A:
    leaq (%rdi,%rdi,2), %rax
    leaq (%rdi,%rax,4), %rdi
    jmp .L2
.L5: loc_B:
    addq $10, %rdi
.L6: loc_C:
    addq $11, %rdi
    jmp .L2
.L7: loc_D:
    imulq %rdi, %rdi
    jmp .L2
.L8: loc_def:
    movl $0, %edi
.L2: done:
    movq %rdi, (%rdx)
    ret Return

不过如果case里的值太过分散的话，就不使用jump table，而是使用多个jmp。