CSAPP Homework 20251119

发表于 更新于 分类于 ， ，

CSAPP Homework 20251119

3.58

1
2
3
4
5
6
7
8
9
long decode2(long x, long y, long z) {
    y -= z;
    x *= y;
    long res = y;
    res <<= 63;
    res >>= 63;
    res ^= x;
    return res;
}

3.59

$x=2^{64}\times x_h+x_l,y=2^{64}\times y_h+y_l$.

乘积为 $P=xy=2^{128}x_h y_h+2^{64}(x_h y_l+y_h x_l)+x_l y_l$.

由于 __int128 类型只能存储 128 位，所以 $2^{128}x_h y_h$ 溢出不考虑。

故 $P=2^{64}(x_h y_l+y_h x_l)+x_l y_l$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
store_prod:
    movq    %rdx, %rax  // 把 y 复制给 %rax
    cqto			    // 将 %rax 扩展成 128 位
    movq    %rsi, %rcx  // 将 x 复制给 %rcx
    sarq    $63, %rcx   // 算术右移 63 位
    imulq   %rax, %rcx  // 计算 y * x_h，结果存入 %rcx
    imulq   %rsi, %rdx  // 计算 x * y_h，结果存入 %rdx
    addq    %rdx, %rcx  // 将两部分相加，存入 %rcx
    mulq    %rsi		
    // 将 %rsi 乘入 %rax , 低 64 位放入 %rax, 高 64 位放入 %rdx
    addq    %rcx, %rdx    // 把 x 加给 %rdx
    movq    %rax, (%rdi)  // 把低 64 位存到 dest[0]
    movq    %rdx, 8(%rdi) // 把高 64 位存到 dest[1]
    ret

3.60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
loop:
    movl    %esi, %ecx
    movl    $1, %edx
    movl    $0, %eax
    jmp     .L2
.L3:
    movq    %rdi, %r8
    andq    %rdx, %r8
    orq     %r8, %rax
    salq    %cl, %rdx
.L2:
    testq   %rdx, %rdx
    jne     .L3
    rep; ret

A: x: %rdi, n: %esi, result: %rax, mask: %rdx.

B: result = 0, mask = 0.

C: mask != 0.

D: mask <<= n.

E: result |= (x & mask).

F:

1
2
3
4
5
6
7
8
long loop(int x, int n) {
    long result = 0;
    long mask;
    for (mask = 1; mask != 0; mask = mask << n) {
        result |= (x & mask);
    }
    return result;
}

3.61

1
2
3
4
5
long cread(long* xp) {
    long zero = 0;
    long* p = xp ? xp : &zero;
    return *p;
}

3.62

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
long switch3(long *p1, long *p2, mode_t action)
{
    long result = 0;
    switch(action) {
        case MODE_A:
            result = *p2;
            *p2 = *p1;
            break;

        case MODE_B:
            result = *p1 + *p2;
            *p1 = result; 
            break;

        case MODE_C:
            *p1 = 59; 
            result = *p2; 
            break;

        case MODE_D:
            *p1 = *p2;
            
        case MODE_E:
            result = 27;
            break;

        default:
            result = 12; 
            break;
    }
    return result;
}

3.63

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
long switch_prob(long x, long n) {
    long result = x;
    switch(n) {
        case 60:
        case 62:
            result = 8 * x;
            break;

        case 63:
            result = x >> 3;
            break;

        case 64:
            x = x * 15;
            
        case 65:
            x = x * x;
            
        case 61: 
            
        default:
            result = x + 75;
            break;
    }
    return result;
}

3.65

**A：**循环中地址应该增加 8，指令 addq $8, %rdx 显示寄存器 %rdx 每次增加 8，故答案为：%rdx

**B：**一行的字节大小为 $M \times 8$，指令 addq $120, %rax 显示寄存器 %rax 每次增加 120，故答案为：%rax

C：$M = 120 / 8 = 15$。

3.66

NR(n): 寄存器 %rdi 保存循环的终止界限。指令 leaq (%rdi,%rdi,2), %rax 计算出 $n + 2n = 3n$，随后指令 movq %rax, %rdi 将其存入 %rdi。循环条件 cmpq %rdi, %rdx 表明循环执行次数为 %rdi 的值，故 NR(n) 为： 3n

NC(n): 寄存器 %r8 保存数组行与行之间的字节步长。指令 leaq 1(,%rdi,4), %r8 计算出 $4n + 1$，指令 salq $3, %r8 将其左移 3 位（乘以 8），得到 $(4n + 1) \times 8$。由于在列中移动时，地址增量等于一行的总字节数 $NC(n) \times 8$，故 NC(n) 为： 4n + 1

3.67

A: eval 在栈上分配 104 字节。结构体 s 位于栈顶，偏移量为 0~23。结构体 r（返回值）的存储空间分配在偏移量 64~87 处。变量 z 位于偏移量 24 处。

B: eval 传递了一个指针（地址）给 process，该地址存储在 %rdi 中，指向 eval 栈帧中偏移量为 64 的位置，用于存放返回的结构体 r。

C: process 通过相对于栈指针 %rsp 的偏移量来访问 s 的元素。由于 call 指令压入了返回地址，偏移量比 eval 中增加了 8。即 s.a[0] 在 8(%rsp)，s.a[1] 在 16(%rsp)，s.p 在 24(%rsp)。

D: process 使用传入的 %rdi 作为基址来写入结果。r.u[0] 存入 (%rdi)，r.u[1] 存入 8(%rdi)，r.q 存入 16(%rdi)。

E: 返回后，eval 通过栈帧偏移量访问 r。r.u[0] 位于 64(%rsp)，r.u[1] 位于 72(%rsp)，r.q 位于 80(%rsp)。

F: 当结构体作为参数传递且过大无法放入寄存器时，它们通过栈传递。当函数返回结构体时，调用者分配空间并将其地址作为第一个参数（隐藏参数）传递给被调用者。

3.70

A:

e1.p: 0

e1.y: 8

e2.x: 0

e2.next: 8

B: 16

C:

1
2
3
void proc (union ele *up) {
    up->e2.x = *(up->e2.next->e1.p) - up->e2.next->e1.y;
}