900字范文 > [第三章] 深入理解计算机系统第三版家庭作业参考答案

[第三章] 深入理解计算机系统第三版家庭作业参考答案

时间：2020-04-17 05:11:34

人非圣贤孰能无过，欢迎大家提问与纠错

3.58

long decode2(long x, long y, long z) {y -= z;x *= y;return ((y << 63) >> 63) ^ x;}

3.59

∵ x = 2^64 * xh + xl; y = 2^64 * yh + yl;

∴ x * y = 2^128 * xh * yh + 2^64 * xh * yl + 2^64 * yh * xl + xl * yl

因为是128位，所以(x * y) mod 2^128 才是正解

∴ x * y = 2^64 * xh * yl + 2^64 * yh * xl + xl * yl

rdi = dest； rsi = xl； rdx = yl；

cqto 是将 rax 符号扩展到 rdx : rax，即 yh : yl；而 xh : xl 是用 rcx : rsi 来表示的；

store_prod:movq %rdx, %rax # rax = ylcqto# 符号扩展 rdx : rax = yh : ylmovq %rsi, %rcx # rcx = xlsarq $63, %rcx # 符号扩展 rcx : rsi = xh : yl；与cqto功能相同imulq %rax, %rcx # rcx = xh * ylimulq %rsi, %rdx # rdx = yh * xladdq %rdx, %rcx # rcx = xh * yl + yh * xlmulq %rsi # rdx : rax = xl * yl；# mul是无符号运算，因为此时 x 和 y 都是 128 位的值，符号在高位上，低位运算不应使用有符号运算；# 注意这里 xl * yl 可能产生向高位的进位addq %rcx, %rdx # rdx = rdx + xh * yl + yh * xl# 因为可能有低位进位，所以不直接使用 rcx 作为结果的高位，而是要加上 rdxmovq %rax, (%rdi) # 将 rax 的值放到结果的低位movq %rdx, 8(%rdi)# 将 rdx 的值放到结果的高位ret

3.60

loop:movl %esi, %ecx # ecx = esimovl $1, %edx # edx = 1 = maskmovl $0, %eax # eax = 0 = resultjmp .L2.L3:movq %rdi, %r8 # r8 = xandq %rdx, %r8 # r8 = r8 & rdx = x & maskorq %r8, %rax # rax = rax | r8 = result | (x & mask)salq %cl, %rdx # rdx = rdx << cl = mask << (n & 0xFF).L2:testq %rdx, %rdxjne .L3 # if rdx != 0 -> jmp L3rep; ret

A.rdi = x; rsi = n; rax = reault; rdx = mask

B.result = 0; mask = 1;

C.mask != 0

D.mask << (n & 0xFF)

E.result | (x & mask)

long loop(long x, int n){long result = 0;long mask;for(mask = 1;mask != 0;mask = mask << (n&0xFF)){result |= x & mask;}return result;}

3.61

不要在判断指针是否为空之前就解引用

long cread_alt(long *xp) {long zero = 0;return *(xp ? xp : (&zero));}

3.62

很简单，不要忘记 break

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;result = 27;break;case MODE_E:result = 27;break;default:result = 12;

3.63

简单的 switch 和跳转表，只需注意 break 和顺延

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;case 61:default:result = x + 75;}return result;}

3.64

扩展到三维：

定义 T D[R][S][T]；

&D[i][j][k] = xa + L(S * T * i + T * j + k)

根据公式，知索引为 S * T * i + T * j + k；

则 R = 3640/5/13/8 = 7；S = 65/13 = 5；T = 13

3.65

根据 rdx 和 rax 每次循环的递增值即可判断

A.rdx

B.rax

C.M = 120/8 = 15

3.66

sum_col:leaq 1(, %rdi, 4), %r8 # r8 = 4 * n + 1leaq (%rdi, %rdi, 2), %rax # rax = 3 * nmovq %rax, %rdi# rdi = rax = 3 * ntestq %rax, %raxjle .L4 # if rax == 0 -> jmp L4salq $3, %r8 # r8 = 8 * (4 * n + 1)leaq (%rsi, %rdx, 8), %rcx # rcx = A + 8 * j = A[0][j]movl $0, %eax # result = 0movl $0, %edx # i = 0.L3:addq (%rcx), %rax # result = result + A[i][j]addq $1, %rdx # i += 1addq %r8, %rcx# 每次加8 * (4n + 1),说明每一行有 4n + 1 个元素，因此 NC(n) 为 4n + 1cmpq %rdi, %rdxjne .L3 # rdx != 3*n 就继续循环，因此 NR(n) 为 3 * nrep; ret.L4:movl $0, %eaxret

宏定义如下：

#define NR(n) (3 * (n))#define NC(n) (4 * (n) + 1)

3.67

表格中的地址指的是相对于 eval 的原始栈顶的地址，自上向下递减的

传递了整个结构体 strA，包括 x y &z

使用 rsp 加偏移访问

使用 rdi 加偏移访问

同样是使用 rsp 加偏移访问

由于结构体的复杂性，是通过存储在栈上访问的

3.68

做这个题时应注意数据对齐

对齐原则：任何 K 字节的基本对象的地址必须是 K 的倍数

setVal:movslq 8(%rsi), %rax # 为使 int 四字节对齐，可得 5 <= B <= 8addq 32(%rsi), %rax # 为使 long 八字节对齐，7 <= A <= 10movq %rax, 184(%rdi) # 180 <= A * B * 4 <= 184ret

解得 A=9 B=5

3.69

<test>:mov 0x120(%rsi), %ecx # ecx = *(bp + 288)add (%rsi), %ecx # ecx += *bp# 上两行可推断 288 是 last 与 first 的首地址之差lea (%rdi, %rdi, 4), %rax # rax = 5ilea (%rsi, %rax, 8), %rax # rax = bp + 40imov 0x8(%rax), %rdx# rdx = *(bp + 40i + 8)movslq %ecx, %rcx# rcx = ecx(符号扩展)# ecx = n，将其符号扩展，赋值给 x # 由此推断 a_struct 中的 x 是长整型 long 的数组mov %rcx, 0x10(%rax, %rdx, 8)# 8 * (*(bp + 40i + 8)) + bp + 40i + 16 = rcxretq

比较简单的推断在上图中列出；

难点在mov 0x8(%rax), %rdx # rdx = *(bp + 40i + 8)和mov %rcx, 0x10(%rax, %rdx, 8)# 8 * (*(bp + 40i + 8)) + bp + 40i + 16 = rcx，bp + 8 + 40i 很容易猜出它是 b_struct 中 a[i] 的首地址，且 b_struct 八字节对齐，结构 a_struct 的字节数为 40；

而 8 * ( *(bp + 40i + 8) ) 可以知道这是索引，进而推断 a_struct 中 idx 排在 x 前面；

那么 bp + 40i + 16 就可以写成 bp + 8 + 40i + 8，前一个 8 是 first 的偏移，后一个 8 是 idx 的偏移；

根据推断，结构 a_struct 的字节数为 40

CNT = (288 - 8)/40 = 7

typedef struct {long idx;long x[4];} a_struct;

3.70

e1.p0 e1.y8 e2.x0 e2.next 8

proc:movq 8(%rdi), %rax # rax = *(up + 8)movq (%rax), %rdx # rdx = *(*(up + 8))movq (%rdx), %rdx # rdx = *(*(*(up + 8)))subq 8(%rax), %rdx # rdx = *(*(*(up + 8))) - *(*(up + 8) + 8) movq %rdx, (%rdi) # *up = rdxret

根据上图注释推理出下图代码：

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

3.71

我并没有读过c程序设计语言([61]The C Programming Language)，只能凭自己的理解写；

使用库函数fgets，详情请点击/reference/cstdio/fgets/

#include<stdio.h>#define MAX 10void good_echo() {char buffer[MAX];while (fgets(buffer, MAX, stdin) != NULL) {printf("%s", buffer);if (ferror(stdin)) {printf("\nError\n");return;}}}int main() {good_echo();system("pause");}

3.72

第5行 leaq 计算得到 8n + 30，然后 andq 将其向下舍入到最近接近的 16 的倍数；-16 = 0xFFFF…FFF0；

(8n + 30) & 0xFFFF…FFF0

= 8n + 30 - (8n + 30) mod 16

当 n 为偶数时:

上式 = 8n + 30 - (16 * n/2 + 30) mod 16

= 8n + 30 - 30 mod 16

= 8n + 16

当 n 为奇数时:

上式 = 8n + 30 - (16 * ((n+1)/2 - 1/2) + 30) mod 16

= 8n + 30 - ((-8 + 30)mod 16)

= 8n + 24

所以：

当 n 为偶数时:

s2 = s1 − (8n + 16)

当 n 为奇数时:

s2 = s1 − (8n + 24)

p = (s2 + 15) & 0xFFFF…FFF0

利用了“偏置”将 s2 向上舍入到最近的 16 的倍数；

这里给出数学证明：

已知：

p = s1 - 8n - e1(1)

当 n 为偶数时:

p = (s2 + 15) & 0xFFFF…FFF0

= (s1 − (8n + 16) + 15) & 0xFFFF…FFF0

= (s1 - 8n - 1) & 0xFFFF…FFF0

= (s1 - 8n - 1) - (s1 - 8n - 1) mod 16

= s1 - 8n - 1 - (s1 - 1) mod 16(2)

由 s2 = s1 − (8n + 16) 可得 e1 + e2 = 16

进而可设 0 <= e1 <= 16(3)

结合(1)(2)式可得：

s1 - 8n - 1 - (s1 - 1) mod 16 = s1 - 8n - e1

(-s1 + 1) mod 16 = -e1 + 1

-s1 + 1 = 16t - e1 + 1 （t 可为任意整数）

s1 = -16t + e1(4)

结合(3)(4)式可得：

MAX_e1 = 16：s1 = 16t（t 可能为任意正整数）

MIN_e1 = 0：s1 = 16t（t 可能为任意正整数）

同理，当 n 为奇数时:

p = (s2 + 15) & 0xFFFF…FFF0

= s1 - 8n - 9 - (s1 - 1) mod 16

s1 - 8n - 9 - (s1 - 1) mod 16 = s1 - 8n - e1

(-s1 + 1) mod 16 = -e1 + 9

-s1 + 1 = 16t -e1 + 9

s1 = 16t + e1 - 8

0 <= e1 <= 24

MAX_e1 = 24：s1 = 16t（t 可能为任意正整数）

MIN_e1 = 0：s1 = 16t - 8（t 可能为任意正整数）

因此：

MIN_e1 = 0，n 为偶数，s1 为 16t ； n 为奇数，s1 为 16t -8;

MAX_e1 = 24，n 为奇数，s1 为 16t（t 可能为任意正整数）

s2 将 8 * n 大小的空间偏移量保留为最小的 16 的倍数

p 以 16 字节的倍数对齐

3.73

关于在 c 中嵌入汇编，可以参考网络旁注 http://csapp.cs.cmu.edu/3e/waside/waside-embedded-asm.pdf

下面的代码需要在linux下运行

#include<stdio.h>typedef enum {NEG, ZERO, POS, OTHER } range_t;range_t find_range(float x) {int result;float zero = 0.0;asm("vucomiss %[x], %[z]# Compare 0:x\n\t""jp.O# NaN \n\t""ja.N# 0 > x\n\t""jb.P# 0 < x\n\t""je.Z# 0 = x\n\t"".O: mov $3, %[r] # NaN\n\t""jmp.Done# jmp done\n\t"".P: mov $2, %[r] # POS \n\t""jmp.Done# jmp done \n\t"".N: mov $0, %[r]# NEG \n\t""jmp.Done# jmp done \n\t"".Z: mov $1, %[r]# ZERO \n\t""jmp.Done# jmp done \n\t"".Done:nop": [r] "=r" (result)/*output*/: [x] "x" (x), [z] "x" (zero)/*input*/);return result;}int main() {printf("%d %d %d %d\n", find_range(12.234), find_range(0.0), find_range(-11.433), find_range(0.0 / 0.0));return 0;}

最开始我是想用 xmm1 的，却总是有错误（见下图），灵活变通一下，将 0.0 保存在了一个局部变量 zero 里就行了。

findrange.c: In function ‘find_range’:findrange.c:10:2: error: invalid 'asm': operand number missing after %-letterasm("vxorps %%xmm1, %%xmm1, %%xmm1 # Set %xmm1 = 0 \n\t"^~~

3.74

关于在 c 中嵌入汇编，可以参考网络旁注 http://csapp.cs.cmu.edu/3e/waside/waside-embedded-asm.pdf

下面的代码需要在linux下运行

#include<stdio.h>typedef enum {NEG, ZERO, POS, OTHER } range_t;range_t find_range(float x) {int result, temp;float zero = 0.0;asm("mov $0, %%r8\n\t""mov $2, %%r9\n\t""mov $3, %%r10\n\t""vucomiss %[x], %[z] # Compare 0:x\n\t""mov $1, %%rax # result = 0\n\t""cmovb %%r9, %%rax# POS\n\t""cmova %%r8, %%rax# NEG\n\t""cmovp %%r10, %%rax# NaN\n\t":: [x] "x" (x), [z] "x" (zero)/*input*/: "%rax");}int main() {printf("%d %d %d %d\n", find_range(12.234), find_range(0.0), find_range(-11.433), find_range(0.0 / 0.0));return 0;}