2017-2018学年下学期期中

2017-2018学年下学期期中试卷（含答案）

一、选择题（20 分）

32 位长的补码表示的 integer 数据的最小值是（）。

A. $-2^{32}$

B. $-2^{32}+1$

C. $-2^{31}$

D. $-2^{31}+1$

答案：
C
mov 和 lea 指令的区别是（）。

A. lea 指令需要解引用（dereferences）地址，mov 指令不需要。

B. mov 指令需要解引用（dereferences）地址，lea 指令不需要。

C. lea 指令可以用于寄存器间数据传递，而 mov 指令不能。

D. mov 指令可以用于寄存器间数据传递，而 lea 指令不能。

答案：
B

下列代码执行后，哪些变量的值为 0？（）

unsigned int a = 0xffffffff;
unsigned int b = 1;
unsigned int c = a + b;
unsigned long d = a + b;
unsigned long e = (unsigned long)a + b;

A. 都不为 0

B. c

C. c and d

D. c, d, and e

答案：

X86-64 机型中关于 %rbx 和 %ebx 寄存器的区别，下列说法正确的是（）。

A. %rbx 和 %ebx 是同一个寄存器。

B. %ebx 引用的是 %rbx 寄存器的低 32 位数据。

C. %rbx 和 %ebx 是完全不同的两个寄存器。

D. %ebx 引用的是 %rbx 寄存器的高 32 位数据。

答案：
B
下列说法不正确的是（）。

A. x86-64 能提供比 x86 更大的虚地址空间。

B. x86 和 x86-64 的栈规则不同。

C. x86 使用 %ebp 存储栈帧的基地址。

D. x86-64 使用 %ebp 存储栈帧的基地址。

答案：
D
执行如下指令：
```
test %eax, %eax
jne 3d<function+0x3d>
```
当 %eax 为（）时，会引起程序跳转。

A. 1

B. 0

C. %eax 任意值

D. %eax 没有合适值能满足指令跳转

答案：
A
下列 C 语言代码中，与汇编指令 lea 0xffffffff(%esi),%eax 功能相对应的是（）。

A. *(esi-1) = eax

B. esi = eax + 0xffffffff

C. eax = esi - 1

D. eax = *(esi -1)

答案：
C

针对下列 C 代码片段，其输出是（）。

unsigned int x = 0xDEADBEEF;
unsigned short y = 0xFFFF;
signed int z = -1;
if (x > (signed short)y) printf("Hello");
if (x > z) printf("World");

A. 没有输出

B. "Hello"

C. "World"

D. "HelloWorld"

答案：

假设一种 8 位浮点数定义为：1 sign，3 exponent，4 fraction。下列哪种表示 NaN？（）

A. 1 000 1111

B. 0 111 1111

C. 0 100 0000

D. 1 111 0000

答案：
B
假设 %rsp 值为 0xdeadbeefdeadd0d0。执行完指令 pushq %rbx 后，%rsp 的值为（）。

A. 0xdeadbeefdeadd0d4

B. 0xdeadbeefdeadd0d8

C. 0xdeadbeefdeadd0cc

D. 0xdeadbeefdeadd0c8

答案：
D

二、（8 分）

假设一种整数为 6 位字长，根据第一列的描述，填写其对应的值。

描述	值
`Umax`
`Tmin`
`(unsigned)((int)4)`
`(unsigned)((int)-7)`
`(((unsigned)0x21) << 1) & 0x3F`
`(int)(20 + 12)`
`12 && 4`
`(!0x15) > 16`

答案：

描述	值
`Umax`	`63`
`Tmin`	`-32`
`(unsigned)((int)4)`	`4`
`(unsigned)((int)-7)`	`57`
`(((unsigned)0x21) << 1) & 0x3F`	`0x02`
`(int)(20 + 12)`	`-32`
`12 && 4`	`1`
`(!0x15) > 16`	`0`

三、（8 分）

考虑基于 IEEE 浮点格式标准的 5 位浮点表示，这种格式没有符号位，只表示非负数（阶码 3 位，尾数 2 位）。

该 5 位浮点数数值为 $V=1.M\times2^E$ ，其中 $E$ 是偏置后的阶码值， $M$ 是尾数值。

下面给出以下十进制值，请写出其对应的浮点数二进制表示，并请给出其舍入值（采用 round-to-even 舍入规则）。

值	浮点数位模式	舍入值
$9/32$
$3$
$9$
$3/16$
$15/2$

答案：

值	浮点数位模式	舍入值
$9/32$	`001 00`	$1/4$
$3$	`100 10`	$3$ ，normalized, exact
$9$	`110 00`	$8$ ，normalized, round down, because `10` is odd
$3/16$	`000 11`	$3/16$ ，exact, denorm
$15/2$	`110 00`	$8$ ，normalized, round up, change exponent

四、（10 分）

在 X86-64 机型上，产生整型变量 x、y、z 的随机数，试判断下列 C 表达式是否恒为真。

/* Create some arbitrary values */
int x = random();
int y = random();
int z = random();

/* Convert to other forms */
unsigned ux = (unsigned)x;
unsigned uy = (unsigned)y;
double dx = (double)x;
double dy = (double)y;
double dz = (double)z;

表达式	是否恒为“真”
`(x<y) == (-x>-y)`
`((x+y)<<4) + y-x == 17y+15x`
`~x+~y+1 == ~(x+y)`
`ux-uy == -(y-x)`
`(x >= 0) \|\| (x < ux)`
`((x >> 1) << 1) <= x`
`(double)(float)x == (double)x`
`dx + dy == (double)(y+x)`
`dx + dy + dz == dz + dy + dx`
`dx * dy * dz == dz * dy * dx`

答案：

(x<y) == (-x>-y)：N。Let x = Tmin, y = 0.
((x+y)<<4) + y-x == 17*y+15*x：Y。Associative, commutative, distributes.
~x+~y+1 == ~(x+y)：Y。(-x-1)+(-y-1)+1 == -(x+y)-1.
ux-uy == -(y-x)：Y。
(x >= 0) || (x < ux)：N。x = -1. Comparison x < ux is never true.
((x >> 1) << 1) <= x：Y。x >> 1 rounds toward minus infinity.
(double)(float)x == (double)x：N。Try x = Tmax.
dx + dy == (double)(y+x)：N。Try x = y = Tmin.
dx + dy + dz == dz + dy + dx：Y。Within range of exact representation by double's.
dx * dy * dz == dz * dy * dx：N。Try dx = Tmax, dy = Tmax - 1, dz = Tmax - 2.

五、（8 分）

考虑如下 C 函数，请根据对应的汇编代码，填写 C 代码中缺失的表达式。

long mystery1(unsigned long x) {
    if (________)
        return ________;
    unsigned long nx = ________;
    long rv = mystery1(nx);
    return ________;
}

其对应的汇编代码如下：

long mystery1(unsigned long x)
x in %rdi
mystery1:
    pushq %rbx
    movq %rdi, %rbx
    movl $0, %eax
    testq %rdi,%rdi
    je .L2
    shrq $2, %rdi
    call mystery1
    addq %rbx,%rax
.L2:
    popq %rbx
    ret

答案：

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

六、（8 分）

考虑如下 C 程序。

#include <stdio.h>

/* Read a string from stdin into buf */
int evil_read_string() {
    int buf[2];
    scanf("%s", buf);
    return buf[1];
}

int main() {
    printf("0x%x\n", evil_read_string());
}

scanf("%s", buf)：从标准输入流（stdin）中读入字符串，并存储在 buf 开始的存储器中（字符串以 '\0' 结束，不检查 buf 存储器的长度）。
printf("0x%x", i)：以 0x 开始打印输出整型变量 i 的十六进制值。
Linux/x86 机器采用小端法。
部分字符的 ASCII 码如下：

字符	ASCII	字符	ASCII	字符	ASCII
`'d'`	`0x64`	`'i'`	`0x69`	`'e'`	`0x65`
`'v'`	`0x76`	`'.'`	`0x2e`	`'s'`	`0x73`
`'r'`	`0x72`	`'l'`	`0x6c`	`'\0'`	`0x00`

A. 上述程序运行在 Linux/x86 机器，输入字符串 dr.evil，针对如下所示的栈结构，请填写 buf[0] 和 buf[1] 中存储的数据（以十六进制表示）。

|<------- buf[0] ------>|<------- buf[1] ------>|
+-----+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |     |     |     |     |     |
+-----+-----+-----+-----+-----+-----+-----+-----+

B. 程序的输出结果是什么？

0x___________

答案：

|<------- buf[0] ------>|<------- buf[1] ------>|
+-----+-----+-----+-----+-----+-----+-----+-----+
| 64  | 72  | 2e  | 65  | 76  | 69  | 6c  | 00  |
+-----+-----+-----+-----+-----+-----+-----+-----+

buf[0] = 0x652e7264，buf[1] = 0x6c6976 或 0x006c6976。

程序的输出结果是：

0x6c6976

七、（18 分）

考虑 x86-64 机型下的如下结构：

struct my_struct {
    char a;
    long long b;
    short c;
    float *d[2];
    unsigned char e[3];
    float f;
};

A. （8 分）请在下面的存储器中完成结构 my_struct 的布局。利用 XX 表示填充的字节，并使用 end 指示结构的结束。

地址	0	1	2	3	4	5	6	7
`0x0`
`0x8`
`0x10`
`0x18`
`0x20`
`0x28`
`0x30`
`0x38`

B. （6 分）考虑如下 C 语言函数，请填写汇编代码中缺失部分。

void foo(struct my_struct *st) {
    st->a = 'e';
    st->d[0] = NULL;
    st->c = 0x213;
    printf("%lld %p %hhu\n", st->b, &st->f, st->e[1]);
}

(gdb) disassemble foo
Dump of assembler code for function foo:
0x00000000004004e4 <+0>:  sub $0x8,%rsp
0x00000000004004e8 <+4>:  movb $0x65,________(%rdi)
0x00000000004004eb <+7>:  movq $0x0,________(%rdi)
0x00000000004004f3 <+15>: movw $0x213,________(%rdi)
0x00000000004004f9 <+21>: movzbl ________(%rdi),%ecx
0x00000000004004fd <+25>: lea ________(%rdi),%rdx
0x0000000000400501 <+29>: mov ________(%rdi),%rsi
0x0000000000400505 <+33>: mov $0x40062c,%edi
0x000000000040050a <+38>: mov $0x0,%eax
0x000000000040050f <+43>: callq 0x4003e0 <printf@plt>
0x0000000000400514 <+48>: add $0x8,%rsp
0x0000000000400518 <+52>: retq
End of assembler dump.

C. （4 分）对 my_struct 结构中元素重新排序，该结构最少应包含多少字节？

A. 48

B. 36

C. 40

D. 以上都不是

答案：

地址	0	1	2	3	4	5	6	7
`0x0`	`a`	`XX`	`XX`	`XX`	`XX`	`XX`	`XX`	`XX`
`0x8`	`b`	`b`	`b`	`b`	`b`	`b`	`b`	`b`
`0x10`	`c`	`c`	`XX`	`XX`	`XX`	`XX`	`XX`	`XX`
`0x18`	`d[0]`	`d[0]`	`d[0]`	`d[0]`	`d[0]`	`d[0]`	`d[0]`	`d[0]`
`0x20`	`d[1]`	`d[1]`	`d[1]`	`d[1]`	`d[1]`	`d[1]`	`d[1]`	`d[1]`
`0x28`	`e[0]`	`e[1]`	`e[2]`	`XX`	`f`	`f`	`f`	`f` / `end`

(gdb) disassemble foo
Dump of assembler code for function foo:
0x00000000004004e4 <+0>:  sub    $0x8,%rsp
0x00000000004004e8 <+4>:  movb   $0x65,(%rdi)
0x00000000004004eb <+7>:  movq   $0x0,0x18(%rdi)
0x00000000004004f3 <+15>: movw   $0x213,0x10(%rdi)
0x00000000004004f9 <+21>: movzbl 0x29(%rdi),%ecx
0x00000000004004fd <+25>: lea    0x2c(%rdi),%rdx
0x0000000000400501 <+29>: mov    0x8(%rdi),%rsi
0x0000000000400505 <+33>: mov    $0x40062c,%edi
0x000000000040050a <+38>: mov    $0x0,%eax
0x000000000040050f <+43>: callq  0x4003e0 <printf@plt>
0x0000000000400514 <+48>: add    $0x8,%rsp
0x0000000000400518 <+52>: retq
End of assembler dump.

C. A

八、（10 points）

某程序中包含 switch 语句，采用跳转表实现。其跳转表如下：

0x4004b7: jmpq *0x400600(,%rax,8)

Using GDB, we extract the 8-entry jump table:

0x400600: 0x00000000004004d1 0x00000000004004c8
0x400610: 0x00000000004004c8 0x00000000004004be
0x400620: 0x00000000004004c1 0x00000000004004d7
0x400630: 0x00000000004004c8 0x00000000004004be

包含 switch 语句的 C 语言程序的反汇编代码如下：

# on entry: %rdi = x, %rsi = y, %rdx = z
0x4004b0: cmp $0x7,%edx
0x4004b3: ja 0x4004c8
0x4004b5: mov %edx,%eax
0x4004b7: jmpq *0x400600(,%rax,8)
0x4004be: mov %edi,%eax
0x4004c0: retq
0x4004c1: mov $0x3,%eax
0x4004c6: jmp 0x4004da
0x4004c8: mov %esi,%eax
0x4004ca: nopw 0x(%rax,%rax,1)
0x4004d0: retq
0x4004d1: mov %edi,%eax
0x4004d3: and $0x19,%eax
0x4004d6: retq
0x4004d7: lea (%rdi,%rdi,1),%eax
0x4004da: add %esi,%eax
0x4004dc: retq

请分析反汇编程序以及跳转表，填写下列 C 程序中的缺失部分：

int test(int x, int y, int z)
{
    int result = 3;
    switch (z)
    {
        case __(1)__:
            _____(2)_____;
        case __(3)__:
        case __(4)__:
            result = _____(5)_____;
            break;
        case __(6)__:
            result = _____(7)_____;
        case __(8)__:
            result = _____(9)_____;
            break;
        default:
            result = _____(10)_____;
    }
    return result;
}

答案：

int test(int x, int y, int z)
{
    int result = 3;
    switch (z)
    {
        case 0:
            x = x & 25;
        case 3:
        case 7:
            result = x;
            break;
        case 5:
            result = 2 * x;
        case 4:
            result = result + y;
            break;
        default:
            result = y;
    }
    return result;
}

九、（10 分）

考虑如下 C 语言代码，其中 M 和 N 是由 #define 声明的常量。

int array1[M][N];
int array2[N][M];

int copy(int i, int j) {
    array1[i][j] = array2[j][i];
}

对应的汇编代码如下：

# on entry: %rdi = i, %rsi = j
copy:
    movl %edi,%ecx
    movl %esi,%ebx
    leal (%ecx,%ecx,8),%edx
    sall $2,%edx
    movl %ebx,%eax
    sall $4,%eax
    subl %ebx,%eax
    sall $2,%eax
    movl array2(%eax,%ecx,4),%eax     // 60*j+4*i
    movl %eax,array1(%edx,%ebx,4)     // 36*i+4*j
    ret

M 和 N 的值是多少？

答案：

M=\frac{36}{4}=9

N=\frac{60}{4}=15