CSAPP读书笔记与习题作业练习-第3章

CSAPP读书笔记与习题作业练习-第3章

• 疑问 * * 疑问一 练习题3.26中的原因是什么？循环加异或操作如何判定二进制数值中1的数量奇偶性（已解答）

本章节共有52个独立的小节习题需要完成
请各位同学认真完成以下各小节的内容
第一至第七章共计七章内容已全部结束
请同学们及时复习巩固已学知识
现在开始进入下一阶段的学习
第八章第一节至第八章第二节的所有习题都需要重点掌握
在此期间同学们应积极完成相关作业并做好笔记记录

• 整理
• • 定义与公式
  • • x86寄存器名称与功能
    • 操作数格式
    • 指令概览

疑问

在练习题3.26中,如何依据循环与异或操作判断二进制数中1的数量是否为奇数或偶数？（已解决）

在练习题3.26中，我们采用了一种位运算的方法来确定二进制数值val中1的数量奇偶特性：首先每次将val进行右移一位的操作；接着将每次右移后的结果与上一次操作前的原始val进行异或运算，并重复此步骤直至右移后的值变为零；最终此时最低位反映了二进制数值val中1的数量奇偶特性。

回答：该运算的核心是在最低有效位上对所有位执行异或操作。当奇数个输入为1时，结果必然是1；否则结果必然是0。

习题

练习题3.1

练习题3.2

练习题3.3

movb 0xF,(%ebx) 错误：操作数宽度不足1个字节 movl %rax,(%rsp) 错误：目标寄存器宽度与源操作数不匹配 movw (%rax),4(%rsp) 错误：内存移动指令参数配置不当 movb %al,%sl 错误：未定义的寄存器引用 movq %rax,0x123 错误：目标操作数必须为合法大小
movl %eax,%rdx 错误：目标操作数大小与源操作数不符
movb %si,8(%rbp) 错误：指令格式存在不兼容性（%si是16位寄存器）
更正：
movb 0xF,(%ebx) 错误：地址寄配体仅支持单字节访问 movl %rax,(%rsp) 错误：移动指令指定的操作码与目标寄存器类型不符 movw (%rax),4(%rsp) 错误：内存移动指令无法直接完成指定操作 movb %al,%sl 错误：引用无效或未定义的存储单元 movq %rax,0x123 错误：无法将立即值赋值给扩展型寄存器
movl %eax,%rdx 错误：目标扩展型寄存器大小超出允许范围
movb %si,8(%rbp) 错误：指定的操作码与当前状态不匹配

练习题3.4

| long| long| movq (%rdi),%rax
movq %rax,(%rsi) |
| char| int| movsbl (%rdi),%eax
movl %eax,(%rsi) |
| char| unsigned| movsbl (%rdi),%eax
movl %eax,(%rsi) |
| unsigned char| long| movzbl (%rdi),%eax
movq %rax,(%rsi) |
| int| char| movb (%rdi) ,%al
movb %al,(%rsi) |
| unsigned| unsigned char| movb (%rdi) ,%al
movb %al,(%rsi) |
| char| short| movsbw (%rdi) ,%ax
movw %ax,(%rsi) |

练习题3.5

    void decode1(long *xp, long *yp, long *zp) {
    	long x = *xp;
    	long y = *yp;
    	long z = *zp;
    	*yp = x;
    	*zp = y;
    	*xp = z;
    }

练习题3.6

练习题3.7

    long scale2(long x,long y,long z){
    	/** * t=x+4x=5x
    	 * t=t+2y=5x+2y
    	 * t=t+8z=5x+2y+8z
    	 */
    	long t = 5*x+2*y+8*z;
    	return t;
    }

练习题3.8

练习题3.9

salq设置%rax寄存器的标志位为十六进制数4
sarl执行条件跳转指令至%esi地址
更正：
salq设置%rax寄存器的标志位为数值4
sarl执行条件跳转指令至%cl地址
移位操作仅允许使用立即值或CL寄存器作为源操作数

练习题3.10

    long arith2(long x,long y,long z){
    	long t1=x|y;
    	long t2=t1>>8;
    	long t3=~t2;
    	long t4=z-t3;
    	return t4;
    }

更正：t2=t1>>3

练习题3.11

A: 将%rdx设置为零
B: movq 0 %rdx C: 执行低4字节更新操作 (%rdx,%rdx) 消耗3个指令周期 movq 0 %rdx (7个指令周期)
执行低4字节更新操作 (%edx,%edx) 消耗2个指令周期
movl $0 %edx (5个指令周期)
这两部分利用了执行低4字节更新操作时会将高位字段清零的特点。

练习题3.12

movq %rdx, %r8
movq %rdi,%rax
xorq %rdx %rdx
divq %rsi
movq %rax,(%r8)
movq %rdx,(%rcx)
ret

练习题3.13

A.
数据类型的data_t·COMP运算符为小于号。
B.
数据类型的data_t·COMP运算符为大于等于号。
C.
数据类型的unsigned char·COMP运算符为小于等于号。
D.
数据类型的long·COMP运算符不等于号。
数据类型的unsigned long·COMP运算符不等于号。
数据类型的某种指针·COMP运算符不等于号。

练习题3.14

晕

练习题3.15

A.je 4003fe
B.je 400425
C.400543
400545
D.400560

练习题3.16

A.
汇编代码：

    # void cond(long a,long * p)
    # a in %rdi, p in %rsi
    cond:
    	testq	%rsi,%rsi   将p的值与0进行比较
    	je		.L1			p为0时跳到L1
    	cmpq	%rdi,(%rsi) 比较p指向的值和a
    	jge		.L1			当p指向的值大于等于a时跳到L1
    	movq	%rdi,(%rsi) 将a的值写入p指向的位置
    .L1:
    	rep; ret			Return

所以可以写出c代码如下：

    void cond(long a,long * p) {
    	if (p==0)
    		goto L1;
    	if (*p>=a)
    		goto L1;
    	*p = a;
    L1:
    	return;
    }

B.因为一个if语句中有两个判断条件，所以要有两个条件分支。

练习题3.17

A.

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

B.运用该规则可以更直观地使用原来的判断条件。

练习题3.18

    long test(long x,long y,long z){
    	long val = x + y + z;
    	if (x < -3) {
    		if (y>=z) {
    			val = y*z;
    		} else {
    			val = y*x;
    		}
    	} else if (x > 2)
    		val = x*z;
    	return val;
    }

练习题3.19

A.T_{MP}=2(T_{ran}-T_{OK})=30
B.T_{OK}+T_{MP}=46

练习题3.20

更正：补码除法用算术右移实现时要注意加上偏置量(1<<k)-1。
A.#define OP /
B.

    arith:
    	leaq	7(%rdi),%rax	将x+7写入%rax
    	testq	%rdi,%rdi		测试x与0的关系
    	cmovns	%rdi,%rax		当x为非负数时将x写入%rax
    	sarq	$3, %rax		将%rax的数算术右移3位
    	ret						返回

练习题3.21

    long test(long x,long y){
    	long val = 8*x;
    	if (y > 0) {
    		if (x >= y) {
    			val = x & y;
    		} else {
    			val = y - x;
    		}
    	} else if (y <= -2)
    		val = x + y;
    	return val;
    }

练习题3.22

A.n=12,n!=479001600
B.n=20,n!=2432902008176640000

练习题3.23

A.%rax存x，%rcx存y，%rdx存n
B.通过加载有效地址指令
C.

    dw_loop:
    	movq	%rdi,%rax			将x设为返回值
    	movq	%rdi,%rcx			将%rcx的值置为x
    	imulq	%rdi,%rcx			#y=x*x
    	leaq	(%rdi,%rdi),%rdx	#n=2x
    .L2:
    	leaq	$1(%rcx,%rax),%rax	#计算x+=y和*p++
    	subq	$1,%rdx				n--
    	testq	$rdx,$rdx			比较n和0的关系
    	jg		.L2					n>0时跳到L2
    	rep;ret						return

更正：
B.编译器认为指针p总是指向x

练习题3.24

    long loop_while(long a,long b){
    	long result = 1;
    	while(a < b) {
    		result = result * (a + b);
    		a= a + 1;
    	}
    	return result;
    }

练习题3.25

    long loop_while2(long a,long b){
    	long result = b;
    	while(b > 0) {
    		result = result * a;
    		b = b - a;
    	}
    	return result;
    }

练习题3.26

A.jump to middle
B.

    long fun_a(unsigned long x){
    	long val = 0;
    	while(x != 0) {
    		val = val ^ x;
    		x>>1;
    	}
    	return val & 0x1;
    }

当x小于32bit时赋值一个具有相同bit位数量且全部为'1'的数值；如果x超出32bit范围则赋值0xFFFFFFFF值。
修正：该计算操作用于检验变量x在其二进制表示中包含奇数个'1'的情况。

练习题3.27

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

练习题3.28

A.

    long fun_b(unsigned long x){
    	long val = 0;
    	long i;
    	for(i=64;i!=0;i--) {
    		long y = x;
    		y &= 0x1;
    		val = (2 * val)| y;
    		x>>=1;
    	}
    	return val;
    }

B.因为初始测试一定满足条件？
C.
更正：

    long fun_b(unsigned long x){
    	long val = 0;
    	long i;
    	for(i=64;i!=0;i--) {
    		val = (val<<1) | (x&0x1);
    		x>>=1;
    	}
    	return val;
    }

该段代码的功能是获得和x在二进制序列上呈镜像关系的数字

练习题3.29

A. 当将 for 语句改为 while 语句时通常会将第三个参数——通常是控制循环的关键表达式——放置在循环体尾部。这种操作通常会导致该关键表达式失效。
B. 继续（continue）指令通常会被替换成执行 goto 语句以跳转至循环体结束前的上一个语句。

练习题3.30

A.标号为-1到7
B.case 2和4、case 0和7
更正：A.标号为-1,0,1,2,4,5,7

练习题3.31

    void switcher(long a,long b,long c,long* dest){
    	long val;
    	switch(a){
    		case 5:
    			c = b ^ 15;
    		case 0:
    			val = c + 112;
    			break;
    		case 2:
    		case 7:
    			val = (b+c)*4;//(b+c)<<2
    			break;
    		default:
    			val = b ;
    	}
    	*dest = val;
    }

练习题3.32

|指令|状态值（指令执行前）||||||||

-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
标号|PC|指令|%rdi|%rsi|%rax|%rsp|* %rsp|描述
M1|0x400560|callq|10|-|-|0x7fffffffe820|-|调用first(10)
F1|0x400548|lea|10|-|-|0x7fffffffe818|0x400565|计算x+1
F2|0x40054c|sub|10|11|-|0x7fffffffe818|0x400565|计算x-1
F3|0x400550|callq|9|11|-|0x7fffffffe818|0x400565|调用last(x-1,x+1)
L1|0x400540|mov|9|11|-|0x7fffffffe810|0x400555|u=x-1
L2|0x400543|imul|9|11|9|0x7fffffffe810|0x400555|u=u*(x+1)
L3|0x400547|ret|9|11|99|0x7fffffffe810|0x400555|从last(x-1,x+1)返回99
F4|0x400555|repz retq|9|11|99|0x7fffffffe818|0x400565|从first(x)返回99
M2|0x400565|mov|9|11|99|0x7fffffffe820|-|%rdx=99

练习题3.33

1.(int a,char b,int *u, char *v)
2.(int a,byte b,int *u, byte *v)
更正：
1.(int a,short b,long *u, char *v)
2.(int b,short a,long *v, char *u)
要注意movb只是传送低8位，不代表b的类型是char，而是说明v的类型是char指针。b的类型应该通过函数的返回值6确定为2字节大小的类型。

练习题3.34

A.a0-a5
B.a6、a7
C.寄存器不够用

练习题3.35

A.x
B.

    void rfun(unsigned long x){
    	if (x == 0)
    		return 0;
    	unsigned long nx = x>>2;
    	long rv = rfun(nx);
    	return rv + x;
    }

练习题3.36

练习题3.37

练习题3.38

%rdx=8i
%rdx = 8i-i=7i
%rdx = 7i+j
%rax = 5j
%rdi = 5j+i
%rax = Q[8(5j+i)]
%rax = Q[8(5j+i)] + P[8(7i+j)]
M=5 N=7

练习题3.39

3: \&A[i][0]=x_A+4(16*i+0)=x_A+64i
4: \&B[0][k]=x_B+4(16*0+k)=x_B+4k
5: \&B[N][k]=x_B+4(16*16+k)=x_B+4k+1024

练习题3.40

    void fix_set_diag_opt() {
    	int index = 0;
    	do{
    		*(A+index) = val;
    		index += N;
    	} while(index != 1088);
    }

更正：

    void fix_set_diag_opt() {
    	int *p = &A[0][0];  
    	long index = 0;
    	long iend = N*(N+1);
    	do{
    		p[index] = val;
    		index += (N+1);
    	} while(index != iend);
    }

练习题3.41

A.
p:0
s.x:8
s.y:12
next:16
B.24
C.

    void sp_init(struct prob *sp){
    	sp->s.x = sp->s.y;
    	sp->p = &(sp->s.x);
    	sp->next = sp;
    }

练习题3.42

A.

    long fun(struct ELE *ptr){
    	long result = 0;
    	while(ptr != NULL){
    		result += ptr->v;
    		ptr = ptr->p;
    	}
    	return result;
    }

B.这是一个储存long的单链表，fun返回链表中所有数据的和

练习题3.43

| up->t1.u | long型 | 将输入参数从寄存器%rdi移动至寄存器%rax |
movq %rax, (%rsi) |
| up->t1.v | short型 | 将输入参数从寄存器%rdi移动至扩展存储器单元(%rsi) |
movw 8(%rdi), %eax |
movq %rax, (%rsi) |
| &up->t1.w | long型 | 将输入参数从寄存器%rdi移动至临时寄存器组第1单元|
leaq 10(%di), %rax
movq %rax, (%rsi) |
| up->t2.a | 指针变量 | 将当前单元的内容加载到临时寄存器组第2单元|
lea %di, %rax
movq %rax, (%rsi) |
| up->t2.a[up->t1.u] | 指针变量偏移量 | 将输入参数从内存地址移动至临时寄存器组第2单元|
lea (%di), %rax
movq (%di,%rax), (%rsii)
movq %rak, (%rsii) |
注：更正以上内容时，请确保遵循以下原则：

• 原始数据应保持一致
• 新增内容需用方括号标注
• 修改部分需使用方括号标注

以下是经过同义改写的文本

练习题3.44

A. 行起始位置分别为i=1, c=3, j=7, d=13; 总长度设定值W设定值总计值S=16; 对齐方式选择X轴方向第四分量.
B. 行起始位置分别为i=2, c=5, d=9; W设定值S总计值S设定值W总计值总计值W总计设定值S总计设定值W总计设定期望达到的目标.
C. 宽度分量起点设定期望达到的目标; 宽度分量总数目设定期望达到的目标; 对齐方式选择Y轴方向第二分量.
D. 宽度分量起点设定期望达到的目标; 宽度分量总数目设定期望达到的目标; 对齐方式选择Z轴方向第八分量.
E. 字符串字段名留空(默认); 时间字段名指定'即时'类型, 并在缺省情况下启用自动重放功能.

练习题3.45

A.

    struct {
    	char   *a;
    	double  c;
    	long    g;
    	short   b;
    	char    d;
    	float   e;
    	char    f;
    	int     h;
    }rec;

练习题3.46

A.
00 00 00 00 00 40 00 76 返回地址
01 23 45 67 89 AB CD EF %rbx的值

栈顶位置指向%rsp。
B段：
内存偏移地址：从第16位开始依次排列：
堆栈起始位置：从高位到低位依次排列：
当前栈指针位于：在堆栈顶端存放着当前的位置信息：
C段：
内存偏移地址：具体数值为十六进制中的$416C。
D段：
变量名%rbx已经被重新定义为目标内存空间的位置。
E段：
在进行malloc操作时，请确保函数参数设置正确：建议将参数设置为buf长度加一（因为strlen不包括末尾的零字节），并确保分配结果不会超出预期范围。

练习题3.47

A.2的13次方
B.2^{13}/2^7=2^6=64

练习题3.48

A.针对a而言，在内存堆叠区域顶端位置存放着变量buf和变量v的位置信息。具体来说，在堆叠区域顶端位置上存放着变量buf的信息，在距离堆叠区域顶端24个字节的位置上存放着变量v的信息。
针对b而言，在堆叠区域顶端位置上存放着金丝雀值域寄存器中的值域信息以及一个寄存器域中的信息域值域信息。具体来说，在堆叠区域顶端位置上存放着金丝雀值域信息，在距离堆叠区域顶端8个字节的位置上存放着一个寄存器域中的信息域值域信息，并且位于距离堆叠区域顶端16个字节位置上的则是buf域的信息。
B.更正：为了使程序运行更加稳定可靠,建议将寄存器v排列至reg buf下方位置,以确保该操作不会导致缓冲溢出操作对寄存器v值进行破坏性修改。

练习题3.49

A.
5:%rax=8n+22
6:and$-16等价于对16取模运算再作差，%rax=8n+22-(8n+22)mod16=8n+8，
7:%rsp-8n-8

B.
8:%rax=%rsp+7
9:%rax=%rax/8
10:%r8=8%rax
设%rsp +7= 8m+n
等价于%r8=%rsp+7-(%rsp+7)mod8=8m+n-n=8m，实现的功能是使帧指针向上对齐到8的倍数

C.

练习题3.50

val1:d
val2:i
val3:l
val4:f

练习题3.51

| double| float| vmovddup %xmm0,%xmm0

| float| long| vunpcklps %xmm0,%xmm0,%xmm0
vcvt |

| double| float| vunpcklpd %xmm0,%xmm0,%xmm0
vcvtpd2ps %xmm0,%xmm0 |

练习题3.52

A源操作数← xmm0 ，目标操作数← rdi ，源操作数← xmm1 ， 操作寄存器← esi
B源操作数← edi ， 目标操作数← rsi ， 源操作数← rdx ， 操作寄存器← rcx
C源操作数← rdi ， 目标操作数← xmm0 ， 源操作→ esi ， 操作寄存器← xmm1
D源→ xmm0 ， 目标→ rdi ， 源→ xmm1 → 寄存器 ← xmm2

练习题3.53

四个参数类型可能为：int,long,float,double或int,float,long,double

练习题3.54

    funct2(double w, int x,float y,long z){
    	return x*y - w/z;
    }

练习题3.55

0x4040000000000000
指数字段为0x404(1028) 1028-1023=5
2^5=32,小数字段为0，隐含1。

练习题3.56

A.将符号位置为0，取绝对值
B.产生0
C.将符号位取反，取相反数

练习题3.57

    double funct3(int *ap, double b,long c,float *dp){
    	float f1 = *dp;
    	if (b <= (double)*ap) {
    		return (double)((float)c+2*f1);
    	} else {
    		return (double)((float)c * f1)
    	}
    }

整理

定义与公式

x86寄存器名称与功能

操作数格式

指令概览

| pushq \quad S| R[\%rsp]\gets R[\%rsp]-8
M[R[\%rsp]]\gets S| 将四字S压入栈 |
| popq \quad D| D\gets M[R[\%rsp]]
R[\%rsp]\gets R[\%rsp]+8| 将四字D弹出栈 |

| imulq\quad S\$ mulq\quad \$S\$ | R[ % rd x ]: R[ % rax ] \gets $S \times R[ % rax ]$ | 带有符号的全宽度乘法运算
无符号的全宽度乘法运算 |
|cqto\quad \$S\$ | R[ % rd x ]: R[ % rax ] 符号扩展(R[ rb x ]) 转换为八位(128-bit) |

| idivq\quad S| R[\%rdx]\gets R[\%rdx]: R[\%rax]\bmod S
R[\%rax]\gets R[\%rdx] :R[\%rax]\div S| 有符号除法 |
| divq\quad S| R[\%rdx]\gets R[\%rdx]: R[\%rax]\bmod S
R[\%rax]\gets R[\%rdx] :R[\%rax]\div S| 无符号除法 |