CSAPP深入理解计算机系统(第二版)第三章家庭作业答案

时间：2021-05-06 02:16:16

《深入理解计算机系统(第二版)》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

详见数据传送指令

参考文献

《深入理解计算机系统(第二版)》

https://blog.csdn.net/summerhust/article/details/7404340

https://blog.csdn.net/maidou0921/article/details/53907971

相关文章