深入理解计算机系统 第3章 习题解析 Part2

这次更新第3章剩余习题。

参考资料：

http://csapp.cs.cmu.edu/3e/waside/waside-embedded-asm.pdf

https://github.com/DreamAndDead/CSAPP-3e-Solutions

https://dreamanddead.github.io/CSAPP-3e-Solutions/

https://cs.nyu.edu/wies/teaching/cso-fa19/class13_machine.pdf

Chapter 3

3.68

C代码：

typedef struct {
    int x[A][B]; /* Unknovn constants A and B */
    long y;
} str1;

typedef struct {
    char array[B];
    int t;
    short s[A];
    long u;
} str2;

void setVal(str1 *p, str2 *q) {
    long v1 = q->t;
    long v2 = q->u;
    p->y = v1 + v2;
}

汇编代码：

void setVal(str1 *p, str2 *q)
p in %rdi, q in %rsi
setVal:
    movslq	8(%rsi), %rax		#t1 = q->t(符号拓展)
    addq	32(%rsi), %rax		#t1 += q->u
    movq	%rax, 184(%rdi)		#p->y = t1
    ret

这里涉及到对齐的概念，列出不等式

$$\begin{aligned} B&\le 8\\ B & > 0 \\ 8+ 4 + 2\times A &\le 32\\ 8+ 4 + 2\times A &> 24\\ 4\times A\times B & \le 184\\ 4\times A\times B & >176 \end{aligned}$$

因此

$$\begin{aligned} 0&< B \le 8\\ 6& < A \le 10\\ 44 & <AB < 46 \end{aligned}$$

因此

$$\begin{aligned} A &= 9\\ B&= 5 \end{aligned}$$

3.69

C代码：

typedef struct {
    int first;
    a_struct a[CNT] ;
    int last;
} b_struct;

void test(long i, b_struct *bp)
{
    int n = bp->first + bp->last;
    a_struct *ap = &bp->a[i];
    ap->x[ap->idx] = n;
}

汇编代码：

void test(long i, b_struct *bp)
i in %rdi, bp in %rsi:
000000000000000 <test>:
	0:	8b 8e 20 01 00 00	mov	0x120(%rsi),%ecx   		#t1 = *(bp + 288) (t1 = bp->last)
	6:	03 0e            	add	(%rsi),%ecx		   		#t1 += *b
	8:	48 8d 04 bf      	lea	(%rdi,%rdi,4), %rax	 	#t2 = 5 * i
	c:	48 8d 04 c6      	lea	(%rsi,%rax,8), %rax   	#t2 = bp + 8 * t2 = bp + 40 * i (t2 = bp + 40 * i, t2 + 8是ap的初始地址)
	10:	48 8b 50 08 		mov	0x8(%rax),%rdx       	#t3 = *(t2 + 8) (t3 = ap->idx)
	14:	48 63 c9         	movslq %ecx,%rcx			#t1 = t1 (带符号拓展)
	17:	48 89 4c d0 10   	mov	%rcx,0x10(%rax,%rdx,8)	 #*(t2 + 8 * t3 + 16) = t1 (ap->x[ap->idx] = n)
	1c:	c3               	retq

根据定义可得（int对齐为8字节）

$$8 + \text{CNT}\times \text{sizeof(a_struct)} = 288$$

根据

8:	48 8d 04 bf				lea	(%rdi,%rdi,4), %rax			#t2 = 5 * i
c:	48 8d 04 c6				lea	(%rsi,%rax,8), %rax			#t2 = bp + 8 * t2 = bp + 40 * i (t2 = bp + 40 * i, t2 + 8是ap的初始地址)

可得

$$\text{sizeof(a_struct)} = 40$$

因此

$$\text{CNT}=7$$

根据

17:	48 89 4c d0 10   	mov	%rcx,0x10(%rax,%rdx,8)	 #*(t2 + 8 * t3 + 16) = t1 (ap->x[ap->idx] = n)

可得x的数据类型为long。

从而a_struct的定义如下

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

3.70

参考资料：

https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter3/3.70/

C代码：

union ele {
    struct {
        long *p;
        long y;
    } e1;
    struct {
        long x;
        union ele *next;
    } e2;
};

注意这里是union。

A

e1.p 0
e1.y 8
e2.x 0
e2.next 8

B

一共需要16字节。

C

汇编代码：

void proc (union ele *up)
up in %rdi
proc:
    movq	8(%rdi), %rax		#t1 = *(up + 8) = ((up->e1.y) / (up->e2.next))
    movq	(%rax), %rdx		#t2 = *t1 = *(up->e2.next) = (*(up->e2.next).e1.p / *(up->e2.next).e2.x)
    movq	(%rdx), %rdx		#t2 = *t2 = *(*(up->e2.next).e1.p)
    subq	8(%rax), %rdx		#t2 = t2 - *(t1 + 8) = *(*(up->e2.next).e1.p) - *(up->e2.next).e1.y
    movq	%rdx, (%rdi)		#up->e2.x = *(*(up->e2.next).e1.p) - up->e2.next.e1.y
    ret

C代码：

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

3.71

#include <stdio.h>
const int buff_size = 3;

void good_echo(){
    char buff[buff_size];
    while(fgets(buff, buff_size, stdin)){
        for (int i = 0; i < buff_size; i++){
            printf("%c", buff[i]);
        }
    }
}

int main(){
    good_echo();

    return 0;
}

3.72

C代码：

#include <alloca.h>
long aframe(long n, long idx, long *q) f
	long i;
	long **p = alloca(n * sizeof (long *)) ;
	p[O] = &i;
	for(i = 1; i < n; i++)
		p[i] = q;
	return *p[idx] ;
}

汇编代码：

long aframe(long n, long idx, long *q)
n in %rdi, idx in %rsi, q in %rdx
aframe : 
	pushq	%rbp
	movq	%rsp, %rbp					
	subq	$16, %rsp        	Allocate space for i (%rsp = s1)
	leaq	30(,%rdi,8), %rax	#t1 = 30 + 8 * n
	andq	$-16, %rax       	#t1 = t1 & (-1), 设置末4位为0
	subq	%rax, %rsp       	Allocate space for array p (%rsp = s2)
	leaq	15(%rsp), %r8    	#t2 = %rsp + 15
	andq	$-16, %r8        	set %r8 to &p[0]

示意图：

|______|
|______| %rsp
|______| s1 = %rsp - 16
|______| 
|______| p, (s2 + 15) - (s2 + 15) mod 16
|______| s2, s1 - ((30 + 8 * n) - (30 + 8 * n) mod 16)

A

$$\begin{aligned} s_1 &=\%\text{rsp} - 16\\ s_2 &=s_1- \left((30 + 8 \times n )- (30 + 8 \times n )\bmod 16 \right) \end{aligned}$$

B

$$p= (s_2 + 15) - \left((s_2 + 15)\bmod 16 \right)$$

C

记数组结尾为$p_1$。

如果$n=2n_1,n_1\ge 1$，那么

$$\begin{aligned} s_2&= s_1- \left((30 + 8 \times n )- (30 + 8 \times n )\bmod 16 \right) \\ &= s_1-\left((30 + 16 \times n_1 )- 14\right)\\ &= s_1-16 -16 \times n_1 \\ p&= (s_2 + 15) - \left((s_2 + 15)\bmod 16 \right)\\ &=(s_1-1 -16 \times n_1) -(s_1-1) \bmod 16 \\ p_1 &= p + 8\times n \\ &= (s_1-1 -16 \times n_1) -(s_1-1) \bmod 16 + 16\times n_1\\ &=(s_1-1) -(s_1-1) \bmod 16 \end{aligned}$$

如果$n=2n_1+1,n_1\ge 0$，那么

$$\begin{aligned} s_2&=s_1- \left((30 + 8 \times n )- (30 + 8 \times n )\bmod 16 \right) \\ &= s_1- \left((30 +16 \times n_1 + 8 )- (30 +16 \times n_1 + 8 )\bmod 16 \right) \\ &= s_1-32 - 16 \times n_1 \\ p&= (s_2 + 15) - \left((s_2 + 15)\bmod 16 \right)\\ &= (s_1-17 - 16 \times n_1) -(s_1 - 1)\bmod 16\\ &= (s_1-17 - 16 \times n_1) -(s_1 - 1)\bmod 16 \\ p_1 &= p+ 8\times n\\ &= (s_1-17 - 16 \times n_1) -(s_1 - 1)\bmod 16 + 16\times n_1 + 8\\ &= (s_1-1)-(s_1 - 1)\bmod 16- 8 \end{aligned}$$

设

$$s_1 = 1 + 16k+i ,k\ge 0, 0\le i\le 15$$

那么在第一种情形下

$$\begin{aligned} p_1 & = 16k+i - i \\ &= 16k\\ s_1 &=1 + 16k + i \end{aligned}$$

此时

$$e_1 = i+ 1 \in [1, 16]$$

在第二种情形下

$$\begin{aligned} p_1 & = 16k+i - i -8\\ &= 16k-8\\ s_1 &=1 + 16k + i \end{aligned}$$

此时

$$e_1 = i+ 9 \in [9, 24]$$

因此

	$e_1$	$s_1$
最小值	$1$	$16k+1$
最大值	$24$	$16k+16$

D

保证了数组的起始位置都是16的倍数。

3.73

#include <stdio.h>
#include <limits.h>

typedef enum { NEG, ZERO, POS, OTHER } range_t;

range_t find_range_origin(float x){
    range_t result;
    if (x < 0){
        result = NEG;
    }else if (x == 0){
        result = ZERO;
    }else if (x > 0){
        result = POS;
    }else{
        result = OTHER;
    }

    return result;
}

range_t find_range(float x){
    //不能使用ret
    asm(
        "vxorps %xmm1, %xmm1, %xmm1\n\t"
        "vucomiss %xmm0, %xmm1\n\t"
        "ja .LA\n\t"
        "je .LB\n\t"
        "jb .LC\n\t"
        "jp .LD\n\t"
        ".LA:\n\t"
            "movl $0, %eax\n\t"
            "jmp .LE\n\t"
        ".LB:\n\t"
            "movl $1, %eax\n\t"
            "jmp .LE\n\t"
        ".LC:\n\t"
            "movl $2, %eax\n\t"
            "jmp .LE\n\t"
        ".LD:\n\t"
            "movl $3, %eax\n\t"
        ".LE:\n\t"
    );
}

void test(){
    bool flag = true;
    int cnt = 0;
    for (short i = SHRT_MIN; i < SHRT_MAX; i++){
        if (find_range_origin(i) != find_range(i)){
            printf("Wrong result for %d!\n", i);
            flag = false;
            break;
        }
    }

    if (flag){
        printf("Passed the test!\n");
    }
}

int main(){
    test();
    
    return 0;
}

3.74

#include <stdio.h>
#include <limits.h>

typedef enum { NEG, ZERO, POS, OTHER } range_t;

range_t find_range_origin(float x){
    range_t result;
    if (x < 0){
        result = NEG;
    }else if (x == 0){
        result = ZERO;
    }else if (x > 0){
        result = POS;
    }else{
        result = OTHER;
    }

    return result;
}

range_t find_range(float x){
    //不能使用ret
    asm(
        "vxorps %xmm1, %xmm1, %xmm1\n\t"
        "vucomiss %xmm0, %xmm1\n\t"
        "movl $0, %esi\n\t"
        "movl $1, %edx\n\t"
        "movl $2, %ecx\n\t"
        "movl $3, %r10d\n\t"
        "ja .LA\n\t"
        "je .LB\n\t"
        "jb .LC\n\t"
        "jp .LD\n\t"
        ".LA:\n\t"
            "movl %esi, %eax\n\t"
            "jmp .LE\n\t"
        ".LB:\n\t"
            "movl %edx, %eax\n\t"
            "jmp .LE\n\t"
        ".LC:\n\t"
            "movl %ecx, %eax\n\t"
            "jmp .LE\n\t"
        ".LD:\n\t"
            "movl %r10d, %eax\n\t"
        ".LE:\n\t"
    );
}

void test(){
    bool flag = true;
    int cnt = 0;
    for (short i = SHRT_MIN; i < SHRT_MAX; i++){
        if (find_range_origin(i) != find_range(i)){
            printf("Wrong result for %d!\n", i);
            flag = false;
            break;
        }
    }
    
    if (flag){
        printf("Passed the test!\n");
    }
}

int main(){
    test();

    return 0;
}

3.75

C代码：

#include <complex.h>
double c_imag(double complex x) {
    return cimag(x);
}
double c_real(double complex x) {
    return creal(x) ;
}
double complex c_sub(double complex x, double complex y) {
    return x - y;
}

汇编代码：

double c_imag(double complex x)
c_imag:
	movapd	%xmm1, %xmm0		#r0 = r1
	ret                 		#return r0
	
double c_real (double complex x)
c_real:
	rep; ret             		#return r0
	
double complex c_sub(double complex x, double complex y)
c_sub:
	subsd	%xmm2, %xmm0		#t0 -= t2
	subsd	%xmm3, %xmm1		#t1 -= t3
	ret										

A

%xmm0存储实部，%xmm1存储虚部。

B

返回%xmm0,%xmm1。