《深入理解计算机系统(第二版)》CSAPP 第三章 家庭作业
这一章介绍了AT&T的汇编指令 比较重要 本人完成了《深入理解计算机系统(第二版)》(以下简称CSAPP)第三章的家庭作业，并与网上的一些答案进行了对比修正。
感谢博主summerhust的整理，以下贴出AT&T常用汇编指令
AT&T常用汇编指令
数据传送指令
| 指令 | 效果 | 描述 |
|---|---|---|
| movl S,D | D <-- S | 传双字 |
| movw S,D | D <-- S | 传字 |
| movb S,D | D <-- S | 传字节 |
| movsbl S,D | D <-- 符号扩展S | 符号位填充(字节->双字) |
| movzbl S,D | D <-- 零扩展S | 零填充(字节->双字) |
| pushl S | R[%esp] <-- R[%esp] – 4;M[R[%esp]] <-- S | 压栈 |
| popl D | D <-- M[R[%esp]]；R[%esp] <-- R[%esp] + 4; | 出栈 |
算数和逻辑操作地址：
| 指令 | 效果 | 描述 |
|---|---|---|
| leal S,D | D = &S | movl地版，S地址入D，D仅能是寄存器 |
| incl D | D++ | 加1 |
| decl D | D-- | 减1 |
| negl D | D = -D | 取负 |
| notl D | D = ~D | 取反 |
| addl S,D | D = D + S | 加 |
| subl S,D | D = D – S | 减 |
| imull S,D | D = D*S | 乘 |
| xorl S,D | D = D ^ S | 异或 |
| orl S,D | D = D | S | 或 |
| andl S,D | D = D & S | 与 |
| sall k,D | D = D << k | 左移 |
| shll k,D | D = D << k | 左移(同sall) |
| sarl k,D | D = D >> k | 算数右移 |
| shrl k,D | D = D >> k | 逻辑右移 |
特殊算术操作：
| 指令 | 效果 | 描述 |
|---|---|---|
| imull S | R[%edx]:R[%eax] = S * R[%eax] | 有符号64位乘 |
| mull S | R[%edx]:R[%eax] = S * R[%eax] | 无符号64位乘 |
| cltd S | R[%edx]:R[%eax] = 符号位扩展R[%eax] | 转换为4字节 |
| idivl S | R[%edx] = R[%edx]:R[%eax] % S;R[%eax] = R[%edx]:R[%eax] / S; | 有符号除法，保存余数和商 |
| divl S | R[%edx] = R[%edx]:R[%eax] % S;R[%eax] = R[%edx]:R[%eax] / S; | 无符号除法，保存余数和商 |
注：64位数通常存储为，高32位放在edx，低32位放在eax。
条件码：
条件码寄存器描述了最近的算数或逻辑操作的属性。
CF：进位标志，最高位产生了进位，可用于检查无符号数溢出。
OF：溢出标志，二进制补码溢出——正溢出或负溢出。
ZF：零标志，结果为0。
SF：符号标志，操作结果为负。
比较指令：
| 指令 | 基于 | 描述 |
|---|---|---|
| cmpb S2,S1 | S1 – S2 | 比较字节，差关系 |
| testb S2,S1 | S1 & S2 | 测试字节，与关系 |
| cmpw S2,S1 | S1 – S2 | 比较字，差关系 |
| testw S2,S1 | S1 & S2 | 测试字，与关系 |
| cmpl S2,S1 | S1 – S2 | 比较双字，差关系 |
| testl S2,S1 | S1 & S2 | 测试双字，与关系 |
访问条件码指令：
| 指令 | 同义名 | 效果 | 设置条件 |
|---|---|---|---|
| sete D | setz | D = ZF | 相等/零 |
| setne D | setnz | D = ~ZF | 不等/非零 |
| sets D | D = SF | 负数 | |
| setns D | D = ~SF | 非负数 | |
| setg D | setnle | D = ~(SF ^OF) & ZF | 大于（有符号>） |
| setge D | setnl | D = ~(SF ^OF) | 小于等于(有符号>=) |
| setl D | setnge | D = SF ^ OF | 小于(有符号<) |
| setle D | setng | D = (SF ^ OF) | ZF | 小于等于(有符号<=) |
| seta D | setnbe | D = ~CF & ~ZF | 超过(无符号>) |
| setae D | setnb | D = ~CF | 超过或等于(无符号>=) |
| setb D | setnae | D = CF | 低于(无符号<) |
| setbe D | setna | D = CF | ZF | 低于或等于(无符号<=) |
跳转指令：
| 指令 | 同义名 | 跳转条件 | 描述 |
|---|---|---|---|
| jmp Label | 1 | 直接跳转 | |
| jmp *Operand | 1 | 间接跳转 | |
| je Label | jz | ZF | 等于/零 |
| jne Label | jnz | ~ZF | 不等/非零 |
| js Label | SF | 负数 | |
| jnz Label | ~SF | 非负数 | |
| jg Label | jnle | ~(SF^OF) & ~ZF | 大于(有符号>) |
| jge Label | jnl | ~(SF ^ OF) | 大于等于(有符号>=) |
| jl Label | jnge | SF ^ OF | 小于（有符号<） |
| jle Label | jng | (SF ^ OF) | ZF | 小于等于(有符号<=) |
| ja Label | jnbe | ~CF & ~ZF | 超过(无符号>) |
| jae Label | jnb | ~CF | 超过或等于(无符号>=) |
| jb Label | jnae | CF | 低于(无符号<) |
| jbe Label | jna | CF | ZF | 低于或等于(无符号<=) |
转移控制指令：（函数调用）：
| 指令 | 描述 |
|---|---|
| call Label | 过程调用，返回地址入栈，跳转到调用过程起始处，返回地址是call后面那条指令的地址 |
| call *Operand | |
| leave | 为返回准备好栈，为ret准备好栈，主要是弹出函数内的栈使用及%ebp |
家庭作业参考答案
3.54
x at %ebp+8, y at %ebp+12, z at %ebp+16, return value at %eax
int decode2(int x,int y,int z){
int temp1 = z-y;
int temp2 = temp1<<15;
temp2 = temp2>>15;
return (x^temp1)*temp2;
}
3.55
**ll_t is defined as long long **
void store_prod(ll_t *dest, ll_t x, int y){
*dest = x*y;
}
dest at %ebp+8, x at %ebp+12, y at %ebp+20
movl 12(%ebp),%esi ;get x(long long)的低位
movl 20(%ebp),%eax ;get y(int)
movl %eax,%edx ;备份y
sarl $31,%edx ;获取y的符号位
movl %edx,%ecx ;备份y的符号位
imull %esi,%ecx ;x的低位无符号乘法乘以y的符号位(0或-1 即 全0或全1)
movl 16(%ebp),%ebx ;get x(long long)的高位
imull %eax,%ebx ;x的高位乘以y
addl %ebx,%ecx ;%ecx=x高位*y+x低位*y的符号位(补全下面无符号的缺少部分)
mull %esi ;%edx=(x的低位*y)的高位 %eax=(x的低位*y)的低位(这一步无符号)
leal (%ecx,%edx),%edx;%edx = %ecx+%edx
movl 8(%ebp),%ecx ;get dest
movl %eax,(%ecx) ;dest[0] = (x的低位*y)的低位
movl %edx,4(%ecx) ;dest[1] = (x的低位*y)的高位+x的高位*y+x的低位*y的符号位(0或者-1)
32位机器模拟64位机器的有符号乘法
x表示 long long x 的值
x = xh*2^32 + xl
x*y = y*xh*2^32 + y*xl 完整形式是96位长 但仅需要64位
因此我们需要y*xl的完整64位和y*xh的低32位 并分开存储
3.56
一个知识点：位移操作可以是一个立即数或者是存放在单字节寄存器元素%cl中
A.
x:%esi,n:%ebx,result:%edi,mask:%edx
B.
result=0x55555555; //0101 0101 0101 0101 0101 0101 0101 0101
mask=0x80000000;
C.
mask!=0
D.
mask每次循环右移n位
E.
result每次循环和x&mask的值进行异或
int loop(int x,int n){
int result = 0x55555555;
int mask;
for(mask = 0x80000000;mask!=0;mask=(unsigned)mask>>n){//需要注意逻辑右移 将有符号数转化为无符号
result ^= mask&x;
}
return result;
}
3.57
int cread_alt(int *xp){
int temp = 0;
int *p = xp?xp:&temp;
return *p;
}
3.58
typedef enum {MODE_A, MODE_B, MODE_C, MODE_D, MODE_E} mode_t;
int switch3(int *p1, int *p2, mode_t action){
int result = 0;
switch(action){
case MODE_A:
result = *p1;
*p1 = *p2;
break;
case MODE_B:
result = *p1+*p2;
*p2 = result;
break;
case MODE_C:
*p2 = 15;
result = *p1;
case MODE_D:
*p2 = *p1;
case MODE_E:
result = 17;
break;
default:
result = -1;
break;
}
return result;
}
选一个部分的汇编代码注释解释一下
.L14(MODE_B):
movl 12(%ebp),%edx ;get p2 reuslt = p2
movl (%edx),%eax ;temp_p2 = p2
movl %eax,%edx ;result = *p2
movl 8(%ebp),%ecx ;get p1 temp_p1 = p1
addl (%ecx),%edx ;result += *p1此时result = *p1+*p2
movl 12(%ebp),%eax ;get p2
movl %edx,(%eax) ;*p2 = result
jmp .L19 ;
3.59
int swith_prob(int x, int n){
int result = x;
switch(n){
case 40:
case 42:
result <<= 3;
break;
case 43:
result >>= 3;
break;
case 44:
result <<= 3;
result -= x;
case 45:
result *= result;
case 41:
default:
retult += 17;
break;
}
return result;
}
解释和部分汇编代码注释
从gdb打印出来的内容可以看出40的情况和42是一样的因此40内容为空，其后紧跟42
44跳转至后紧接着执行了45跳转的内容 45之后也无跳转 因此44和45没有break
41的情况与default相同因此41置为空写在defaul前
mov 0xc(%ebp),%eax ;%ebp+12的位置获取第二个参数，即n
sub 0x28,%eax ;n-40(0x28为16进制 转为10进制为2*16+8=40)
cmp 0x5,%eax ;n-40 与 5
ja 8048435(switch_pro+0x15);n-40-5>0? 即n若大于45直接返回
3.60
A.从汇编代码看出
A[i][j][k] = A+(63i+9j+k)*4
B.
解决方程T=9, S*T=63, R*S*T*4=2772
T = 9
S = 7
R = 11
3.61
int var_prod_ele(int n, int A[n][n], int B[n][n], int i,int k){
int result = 0;
int *a_l = &A[i][0];
int *a_r = &A[i][n];
int *b_l = &b[0][k];
while(a_l!=a_r){
result += (*a_l)*(*b_l);
b_l += n;
a_l++;
}
return result;
}
可自行查看汇编代码验证
L3:
movl (%ebx), %ecx
imull (%edx), %ecx
addl %ecx, %eax
addl %edi, %ebx
addl $4, %edx
cmpl %edx, %esi
jne L3
3.62
A.
M = 76/4 = 19
B.
%edi 保存 i
%ecx 保存 j
使用指针进行优化
void transpose(int A[M][M]){
int i,j;
for(i=0;i<M;i++){
int *temp1 = &A[i][0];
int *temp2 = &A[0][i];
for(j=0;j<i;j++){
int t = *temp1;
*temp1 = *temp2;
*temp2 = t;
temp1++;
temp2 += M;
}
}
}
3.63
#define E1(n) 3*n
#define E2(n) 2*n-1
3.64
A.
8(%ebp) result
12(%ebp) s1.p
16(%ebp) s1.v
B.
------------%ebp
s2.sum
s2.prod
s1.v
s1.p
&s2
------------%esp
C.
将结构体变量的各个成员的值传入函数
D.
将返回变量的地址传递出去
3.65
A=3,B=7
3.66
这个题看了好久，不得不佩服GCC
写下详细注释
push %ebp
mov %esp,%ebp
push %ebx
mov 0x8(%ebp),%eax ;get i
mov 0xc(%ebp),%ecx ;get *bp
imul $0x1c,%eax,%ebx ;28*i
lea 0x0(,%eax,8),%edx;8*i
sub %eax,%edx ;7*i
add 0x4(%ecx,%ebx,1),%edx ;7i+(bp+28i+4)注意bp+4是a_struct a的首地址 +28i即是bp->a[i]即一个a_struct大小是28 同时 有*ap = (bp+28i+4)
mov 0xc8(%ecx),%eax ;bp->right = bp+200
add (%ecx),%eax ;bp->left + bp->right 即 28*CNT = 200 - 4 即 CNT = 7
mov %eax,0x8(%ecx,%edx,4);bp+8+4*(7i+(bp+28i+4))=(bp+28*i+4+4)(即ap->idx+4，apx->x[0])+*(bp+0x1c*i+4)*4
pop %ebx
pop %ebp
ret
A.
CNT = 7
B.
a_struct{
int idx;
int x[6];
}
其实分析出大小就能做这个题 并不需要完全看懂汇编代码
3.67
A.
e1.p:0
e1.x:4
e2.y:0
e2.next:4
B.8
C.
void proc(union ele *up)
{
up->e2.next->e1.x=*(up->e2.next->e1.p) - up->e2.y;
}
3.68
void good_echo()
{
char c;
int x = 0;
while( x=getchar(), x!='\n' && x!=EOF)
{
putchar(x);
}
}
3.69
long trace(tree_ptr tp){
long result = 0;
while(tp){
result = tp->val;
tp = tp->left;
}
return result;
}
输出二叉树最左边节点的值
3.70
long traverse(tree_ptr tp){
if(!tp) return 9223372036854775807;
long v = tp->val;
long left = traverse(tp->left);
long result = traverse(tp->right);
if(left <= result) result = left;
if(v <= result) result = v;
return result;
}
或者换一种写法
long traverse(tree_ptr tp){
long result = 9223372036854775807;
if(tp){
long lv = traverse(tp->left);
long rv = traverse(tp->right);
result = lv <= rv ? lv : rv;
result = result > tp->val ? tp->val : result;
}
return result;
}
求二叉树节点最小值
| 指令 | 效果 |
|---|---|
| cmovle s,r | 小于或等于 s->r |
| cmovg s,r | 大于 s->r |
详见数据传送指令
参考文献
《深入理解计算机系统(第二版)》