bugCat's Blog

毛的感情的程序猿

0%

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

发表于 更新于 分类于
本文字数： 27k 阅读时长 ≈ 24 分钟

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

练习题3.1假设下面的值存放在指明的内存地址和寄存器中:

image-20221025203611818

操作数 值
%rax 0x100
0x104 0xAB
$0x108 0x108
(%rax) 0xFF
4(%rax) 0xAB
9(%rax,%rdx) 0x11
260(%rcx,%rdx) 0x13
0xFC(,%rcx,4) 0xFF
(%rax,%rdx,4) 0x11

练习题3.2对于下面汇编代码的每一行，根据操作数，确定适当的指令后缀。(例如，mov 可以被重写成movb、movw、movl或者movq。）

image-20221025222250940

1
2
3
4
5
6
movl %eax, (%rsp)		;%eax是2个字的，传输2字，所以是movl
movw (%rax), %dx		;%dx是1个字的，传输1字，所以是movw
movb $0xFF, %b1			;%b1是1个字节的，传输1字，所以是movb
movb (%rsp,%rdx,4), %dl ;%dl是1个字的，传输1字，所以是movb
movq (%rdx), %rax		;%rax是4个字的，传输1字，所以是movq
movbw %dx, (%rax)		;%dx是1个字的，传输1字，所以是movw

练习题3.3当我们调用汇编器的时候，下面代码的每一行都会产生一个错误消息。解释每一行都是哪里出了错。

image-20221026110728710

1
2
3
4
5
6
7
movb $0xF, (%ebx) 		;内存引用的寄存器必须是四个字的，改成movb $0xF, (%rbx)
movl %rax, (%rsp) 		;%rax是四个字而l代表两个字，改成movl %eax, (%rsp) 或者 movq %rax, (%rsp)
movw (%rax), 4(%rsp)	;两个操作数不能都是内存引用
movb %al, %sl			;没有寄存器名字叫%sl
movq %rax,$0x123		;立即数不能作为des操作数
movl %eax, %rdx			;答案上说目标操作数大小不正确（destination operand incorrect size），这个有点不太理解
movb %si, 8(%rbp)		;%si是一个字而b代表一个字节，改成movb %sil, 8(%rbp) 或者 movw %si, 8(%rbp)

练习题3.4假设变量sp和dp被声明为类型

1
2
src_t *sp;
dest_t *dp;

这里src_t和dest_t是用typedef声明的数据类型。我们想使用适当的数据传送指令来实现下面的操作;

1
*dp = (dest_t) *sp;

假设 sp 和 dp 的值分别存储在寄存器 %rdi 和 %rsi 中。对于表中的每个表项，给出实现指定数据传送的两条指令。其中第一条指令应该从内存中读数，做适当的转换，并设置寄存器 %rax 的适当部分。然后，第二条指令要把 %rax 的适当部分写到内存。在这两种情况中，寄存器的部分可以是 %rax、%eax、%ax 或 %al，两者可以互不相同。

记住，当执行强制类型转换既涉及大小变化又涉及 C 语言中符号变化时，操作应该先改变大小。

src_t dest_t 指令 解释
long long movq (%rdi), %rax
movq %rax, (%rsi)		 long 为 8 字节，目标字节数也为 8，所以都用 movq 。
char int movsbl (%rdi), %eax
movl %eax, (%rsi)		 因为源有符号，所以用 movs 。又因为是 char 到 int ，所以使用 bl 。
char unsigned movsbl (%rdi), %eax
movl %eax, (%rsi)		 同上。
unsigned char long movzbl (%rdi), %eax
movq %rax, (%rsi)		 需要把字节扩展成四字，由于是 unsigned，所以用零扩展。
int char movl (%rdi), %edx
movb %al, (%rsi)		 原始字节还是要读出来的，但是只传送低位字节，即按目标大小进行截断。源有无符号无所谓。
unsigned unsigned char movl (%rdi), %al
movb %al, (%rsi)		 本质同上。
char short movsbw (%rdi), %ax
movw %ax, (%rsi)		 需要进行符号拓展。

练习题3.5已知信息如下。将一个原型为

1
void decode1(long *p, long *yp, long *zp);

的函数编译成汇编代码，得到如下代码:

1
2
3
4
5
6
7
8
9
10
  void decode1(1ong *xp, long *yp, long *zp);
  xp in %rdi, yp in %rsi, zp in %rdx
decode1:
  movq  (%rdi), %r8
  movq  (%rsi), %rcx
  movq  (%rdx), %rax
  movq  %r8, (%rsi)
  movq  (%rcx), (%rdx)
  movq  (%rax), (%rdi)
  ret

参数 xp、yp 和 zp 分别存储在对应的寄存器 %rdi、%rsi 和 %rdx 中。

请写出等效于上面汇编代码的 decode1 的 C 代码。

1
2
3
4
5
6
7
8
9
10
void decode1(long *p, long *yp, long *zp)
{
	long x = *xp;
	long y = *yp;
	long z = *zp;
	
    *yp = x;
    *zp = y;
    *xp = z;
}

练习题3.6 假设寄存器 %rax 的值为 x，%rcx 的值为 y。填写下表，指明下面每条汇编代码指令存储在寄存器 %rdx 中的值：

表达式 结果
leaq 6 (%rax), %rdx x + 6
leaq (%rax, %rcx), %rdx x + y
leaq (%rax, %rcx, 4), %rdx x + 4y
leaq 7 (%rax, %rax, 8), %rdx 9x + 7
leaq 0xA (, %rcx, 4), %rdx 4y + 10
leaq 9 (%rax, %rcx, 2), %rdx x + 2y + 9

练习题3.7考虑下面的代码，我们省略了被计算的表达式：

1
2
3
4
long scale2(long x, long y, long z) {
    long t = ____________________;
    return t;
}

用 GCC 编译实际的函数得到如下的汇编代码：

1
2
3
4
5
6
7
  long scale2(long x, long y, long z)
  x in %rdi, y in %rsi, z in %rdx
scale2:
  leaq  (%rdi, %rdi, 4), %rax
  leaq  (%rax, %rsi, 2), %rax
  leaq  (%rax, %rdx, 8), %rax
  ret

填写出 C 代码中缺失的表达式。

1
long t = 5*x + 2*y + 8*z

练习题 3.8 假设下面的值存放指定的内存地址和寄存器中：

image-20221027211920652

image-20221027211934019

填写下表，给出下面指令的效果，说明将被更新的寄存器或内存位置，以及得到的值：

指令 目的 值
addq %rcx, (%rax) 0x100 0xFF + 0x1 = 0x100
subq %rdx, 8 (%rax) 0x108 0xAB - 0x3 = 0xA8
imulq $16, (%rax, %rdx, 8) 0x100 + 0x3 * 8 = 0x118 0x11 * 16 = 0x110
incq 16 (%rax) 0x110 0x14
decq %rcx %rcx 0x0
subq %rdx, %rax %rax 0x0FD

练习题 3.9设我们想生成以下 C 函数的汇编代码：

1
2
3
4
5
6
long shift_left4_rightn(long x, long n)
{
    x <<= 4;
    x >>= n;
    return x;
}

下面这段汇编代码执行实际的移位，并将最后的结果放在寄存器 %rax 中。此处省略了两条关键的指令。参数 x 和 n 分别存放在寄存器 %rdi 和 %rsi 中。

1
2
3
4
5
6
7
8
  long shift_left4_rightn(long x, long n)
  x in %rdi, n in %rsi
shift_left4_rightn:
  movq  %rdi, %rax    Get x
  ________________    x <<= 4
  movl  %esi, %ecx    Get n (4 bytes)
  ________________    x >>= n

根据右边的注释，填出缺失的指令。请使用算术右移操作。

1
2
salq  $4, %rax      x <<= 4
sarq  %cl, %rax     x >>= n

练习题 3.10 下面的函数是图3-11a中函数一个变种，其中有些表达式用空格替代:

1
2
3
4
5
6
7
8
long arith2(long x, long y, long z)
{
    long t1 = _____;
    long t2 = _____;
    long t3 = _____;
    long t4 = _____;
    return t4;
}

实现这些表达式的汇编代码如下：

1
2
3
4
5
6
7
8
9
10
  long arith2(long x, long y, long z)
  x in %rdi, y in %rsi, z in %rdx
arith2:
  orq   %rsi, %rdi
  sarq  $3, %rdi
  notq  %rdi
  movq  %rdx, %rax
  subq  %rdi, %rax
  ret

基于这些汇编代码，填写 C 语言代码中缺失的部分

1
2
3
4
long t1 = x | y;
long t2 = t1 >> 3;
long t3 = ~ t2;
long t4 = z - t3;

练习题 3.11常常可以看见以下形式的汇编代码行：

1
xorq %rdx, %rdx

但是在产生这段汇编代码的 C 代码中，并没有出现 EXCLUSIVE-OR 操作。

A. 解释这条特殊的 EXCLUSIVE-OR 指令的效果，它实现了什么有用的操作。

B. 更直接地表达这个操作的汇编代码是什么？

C. 比较同样一个操作的两种不同实现的编码字节长度。

A. 这个指令用来将寄存器 %rdx 设置为 0，运用了对任意 x，x^x=0 这一属性。它对应于 C 语句 x=0 。

B. 将寄存器 %rdx 设置为 0 的更直接的方法是用指令 movq $0, %rdx 。

C. 汇编和反汇编这段代码，我们发现使用 xorq 的版本只需要 3 个字节，而使用 movq 的版本需要 7 个字节。其他将 %rdx 设置为 0 的方法都依赖于这样一个属性，即任何更新低位 4 字节的指令都会把高位字节设置为 0 。因此，我们可以使用 xorl %edx, %edx（2 字节）或 movl $0, %edx（5 字节）。

练习题 3.12 考虑如下函数，它计算两个无符号 64 位数的商和余数：

1
2
3
4
5
6
7
8

void uremdiv(unsigned long x, unsigned long y, unsigned long *qp, unsigned long *rp) 
{
    unsigned long q = x / y;
    unsigned long r = x % y;
    *qp = q;
    *rp = r;
}

修改有符号除法的汇编代码来实现这个函数。

1
2
3
4
5
6
7
8
9
10
11
  void uremdiv(unsigned long x, unsigned long y, unsigned long *qp, unsigned long *rp)
  x in %rdi, y in %rsi, qp in %rdx, rp in %rcx
uremdiv:
  movq  %rdx, %r8      Copy qp
  movq  %rdi, %rax     Move x to lower 8 bytes of dividend
  movl  $0, %edx       Set upper 8 bytes of divended to 0
  divq  %rsi           Divide by y
  movq  %rax, (%r8)    Store quotient at qp
  movq  %rdx, (%rcx)   Store remainder at rp
  ret

练习题 3.13 虑下列的 C 语言代码：

1
2
3
int comp(data_t a, data_t b) {
    return a COMP b;
}

它给出了参数 a 和 b 之间比较的一般形式，这里，参数的数据类型 data_t（通过 typedef）被声明为表 3-1 中列出的某种整数类型，可以是有符号的也可以是无符号的。 COMP 通过 #define 来定义。

假设 a 在 %rdi 中某个部分，b 在 %rsi 中某个部分。对于下面每个指令序列，确定哪种数据类型 data_t 和比较 COMP 会导致编译器产生这样的代码。（可能有多个正确答案，请列出所有的正确答案。

image-20221030184524281

A.后缀 ‘l’ 和寄存器指示符表明是 32 位操作数，而且调用的是有符号的小于比较。所以 data_t 一定是 int 。

B.后缀 ‘w’ 和寄存器指示符表明是 16 位操作数，而且调用的是有符号的大于等于。所以 data_t 一定是 short。

C.后缀 ‘b’ 和寄存器指示符表明是 8 位操作数，而且调用的是无符号小于等于。所以 data_t 一定是 unsigned char 。

D.后缀 ‘q’ 和寄存器指示符表明是 64 位操作数，同时比较符号是 != ，有符号、无符号和指针参数都是一样的。所以 data_t 可以是 long、unsigned long 或 char * 。

练习题 3.14 考虑下面的 C 语言代码：

1
2
3
int test(data_t a) {
    return a TEST 0;
}

它给出了参数 a 和 0 之间比较的一般形式，这里，我们可以用 typedef 来声明 data_t ，从而设置参数的数据类型，用 #define 来声明 TEST，从而设置比较的类型。对于下面每个指令序列，确定哪种数据类型 data_t 和比较 TEST 会导致编译器产生这样的代码。（可能有多个正确答案，请列出所有的正确答案。）

image-20221030192217880

A.后缀 ‘q’ 和寄存器指示符表明是 64 位操作数，而且调用有符号大于等于，所以 data_t 一定是 long 。

B.后缀 ‘w’ 和寄存器指示符表明是 16 位操作数，比较符 == 对于有无符号都是一样的。所以 data_t 可以是 short 或者 unsigned short 。

C.后缀 ‘b’ 和寄存器指示符表明是 8 位操作数，使用的是无符号大于，所以 data_t 一定是 unsigned char 。

D.后缀 ‘l’ 和寄存器指示符表明是 32 位操作数，使用的是带符号的小于等于，所以 data_t 一定是 int 。

练习题 3.15在下面这些反汇编二进制代码节选中，有些信息被 X 代替了。回答下列关于这些指令的问题。

A. 下面 je 指令的目标是什么？（在此，你不需要知道任何有关 callq 指令的信息。）

1
2
4003fa: 74 02    je    XXXXXX
4003fc: ff do    callq *%rax

je 指令的目标为 0x4003fc + 0x02 = 0x4003fe 。

B. 下面 je 指令的目标是什么？

1
2
40042f: 74 f4    je   XXXXXX
400431: 5d       pop  %rbp

je 指令的目标为 0x400431 - 12（由于 0xf4 是 -12 的一个字节的补码表示）= 0x400425 。

C. ja 和 pop 指令的地址是多少？

1
2
XXXXXX: 77 02    ja   400547
XXXXXX: 5d       pop  %rbp

跳转目标是绝对地址 0x400547 。根据字节编码，一定在距离 pop 指令 0x2 的地址处。所以，pop 指令地址为 0x400547 - 0x2 = 0x400545 。注意，ja 指令的编码需要 2 个字节。所以 ja 指令的地址为 0x400543 处。

D. 在下面的代码中，跳转目标的编码是 PC 相对的，且是一个 4 字节补码数。字节按照从最低位到最高位的顺序列出，反映出 x86-64 的小端法字节顺序。跳转目标的地址是什么？

1
2
4005e8: e9 73 ff ff ff     jmp  XXXXXX
4005ed: 90                 nop

以相反的顺序来读这些字节，我们看到目标偏移量是 0xffffff73 ，或者十进制数 -141 。所以跳转目标为 0x4005ed - 141 = 0x400560 。

练习题 3.16已知下列 C 代码：

1
2
3
4
5
void cond(long a, long *p)
{
    if (p && a > *p)
        *p = a;
}

GCC 会产生下面的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
# void cond(long a, long *p)
# a in %rdi, p in %rsi
cond:
  testq  %rsi, %rsi   # 测试 p
  je     .L1          # 如果是 0 就跳转到 L1 
  comq   %rdi, (%rsi) # 比较 *p 和 a
  jge    .L1          # 如果 *p >= a，跳转到 L1
  movq   %rdi, (%rsi) # *p = a
.L1:
  rep; ret

A. 按照图 3-16b 中所示的风格，用 C 语言写一个 goto 版本，执行同样的计算，并模拟汇编代码的控制流。像示例中那样给汇编代码加上注解可能会有所帮助。

1
2
3
4
5
6
7
8
9
10
void goto_cond(long a, long *p) {
    if (p == 0)
      goto done;
    if (*p >= a)
      goto done;
    *p = a;
  done:
    return;
}

B. 请说明为什么 C 语言代码中只有一个 if 语句，而汇编代码包含两个条件分支。

第一个条件分支是 && 表达式实现的一部分。如果对 p 为非空的测试失败，代码会跳过对 a > *p 的测试。

练习题 3.17将 if 语句翻译成 goto 代码的另一种可行的规则如下：

1
2
3
4
5
6
7
8
9
    t = test-expr;
    if (t)
        goto true;
    else-statement
    goto done;
true:
    then-statement
done:

A. 基于这种规则，重写 absdiff_se 的 goto 版本。

1
2
3
4
5
6
7
8
9
10
11
12
long gotodiff_se_alt(long x, long y) {
    long result;
    if (x < y)
        goto x_lt_y;
    go_cnt++
    result = x - y;
    return result;
x_lt_y:
    lt_cnt++;
    result = y - x;
    return result;
}

B. 你能想出选用一种规则而不选用另一种规则的理由吗？

大多数情况下，可以在这两种方式中任意选择。但是原来的方法对常见的没有 else 语句的情况更好一些。对于这种情况，我们只用简单地将翻译规则修改如下：

1
2
3
4
5
6
    t = test-expr;
    if (!t)
        goto done;
    then-statement
done:

练习题 3.18从如下形式的 C 语言代码开始：

1
2
3
4
5
6
7
8
9
10
11
long test(long x, long y, long z) {
    long val = ___________;
    if (______) {
        if (______)
            val = ______;
        else
            val = ______;
    } else if (______)
        val = ______;
    return val;
}

GCC 产生如下的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# long test(long x, long y, long z)
# x in %rdi, y in %rsi, z in %rdx
test:
  leaq  (%rdi, %rsi), %rax  # long temp1 = x + y
  addq  %rdx, %rax          # temp1 = temp1 + z
  cmpq  $-3, %rdi           # 比较 x 和 -3
  jge   .L2                 # x >= -3 时跳转到 L2
  cmpq  %rdx, %rsi          # 比较 y 和 z
  jge   .L3                 # y >= z 时跳转到 L3
  movq  %rdi, %rax          # temp1 = x
  imulq %rsi, %rax          # temp1 = temp1 * y
  ret                       # return
.L3:
  movq  %rsi, %rax          # 此时 x < -3，y >= z；temp1 = y
  imulq %rdx, %rax          # temp1 = temp1 * z
  ret                       # return
.L2:
  cmpq  $2, %rdi            # 此时 x >= -3；比较 x 和 2
  jle   .L4                 # x <= 2 时跳转到 L4
  movq  %rdi, %rax          # temp1 = x
  imulq %rdx, %rax          # temp1 = temp1 * z
.L4:
  rep; ret

填写 C 代码中缺失的表达式。

1
2
3
4
5
6
7
8
9
10
11
12
long test(long x, long y, longz) {
    long val = x + y + z;
    if (x < -3) {
        if (y < z)
            val = x * y;
        else
            val = y * z;
    } else if (x > 2) 
        val = x * z;
   return val;
}

练习题 3.20 下面的 C 函数中，我们对 OP 操作的定义是不完整的：下面的 C 函数中，我们对 OP 操作的定义是不完整的：下面的 C 函数中，我们对 OP 操作的定义是不完整的：

1
2
3
4
5
# define OP _________ /* Unknown operator */

long arith(long x){
    return x OP 8;
}

当编译时，GCC 会产生如下汇编代码：

1
2
3
4
5
6
7
8
9
# long arith(long x)
# x in %rdi
arith:
  leaq  7(%rdi), %rax   # temp = x + 7
  testq %rdi, %rdi      # Test x
  cmovns %rdi, %rax     # if x >= 0, temp = x
  sarq   $3, %rax       # result = temp >> 3 (= x / 8)
  ret

A. OP 进行的是什么操作？

运算符是 ‘/’ 。可以看到这是一个通过右移实现除以 2 的 3 次幂的例子。在移位 k = 3 之前，如果被除数是负数的话，必须加上偏移量 2k−1=7 （向上舍入）。

B. 给代码添加注释，解释它是如何工作的。

练习题 3.21 C 代码开始的形式如下：

1
2
3
4
5
6
7
8
9
10
11
long test(long x, long y) {
    long val = _____;
    if (_____) {
        if (_____)
            val = ______;
        else
            val = ______;
    } else if (______)
        val = ________;
    return val;
}

GCC 会产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# long test(long x, long y)
# x in %rdi, y in %rsi
test:
  leaq  0(, %rdi, 8), %rax  # long temp = 8 * x
  testq %rsi, %rsi          # test y
  jle   .L2                 # y <= 0
  movq  %rsi, %rax          # temp = y
  subq  %rdi, %rax          # temp = temp - x
  movq  %rdi, %rdx          # long temp2 = x
  andq  %rsi, %rdx          # temp2 = temp2 & y
  cmpq  %rsi, %rdi          # 比较 x 和 y
  cmovge %rdx, %rax         # x >= y, temp = temp2
  ret
.L2:
  addq  %rsi, %rdi          # x = x + y
  cmpq  $-2, $rsi           # 比较 y 和 -2
  cmovle %rdi, %rax         # y <= -2, temp = x + y
  ret

填补 C 代码中缺失的表达式。

1
2
3
4
5
6
7
8
9
10
11
long test(long x, long y) {
    long val = 8 * x;
    if (y > 0) {
        if (x < y)
            val = y - x;
        else
            val = x & y;
    } else if (y <= -2)
        val = x + y;
    return val;
}

练习题 3.22

A. 用一个 32 位 int 表示 n! ，最大的 n 的值是多少？

如果构建一张使用数据类型 int 来计算的阶乘表，得到下面这样的结果：

n n! OK?
1 1 Y
2 2 Y
3 6 Y
4 24 Y
5 120 Y
6 720 Y
7 5040 Y
8 40320 Y
9 362880 Y
10 3628800 Y
11 39916800 Y
12 479001600 Y
13 1932053504 N

当 n = 13 时发生溢出，可以通过$x/n$看它是否等于$(n-1)!$进行判断。

B. 如果用一个 64 位 long 表示，最大的 n 的值是多少？

用long表示的话，最大的 n 值为 20，才溢出，也就是知道20！long类型才溢出。

练习题 3.23 已知 C 代码如下：

1
2
3
4
5
6
7
8
9
10
11
long dw_loop(long x){
    long y = x * x;
    long *p = &x;
    long n = 2 * x;
    do {
        x += y;
        (*p)++;
        n--;
    } while (n > 0);
    return x;
}

GCC 产生的汇编代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# long dw_loop(long x)
# x initially in %rdi

long dw_loop(long x)
dw_loop:
    movq   %rdi, %rax            # Copy x to %rax   
    movq   %rdi, %rcx               
    imulq  %rdi, %rcx            # Compute y = x*x   
    leaq   (%rdi, %rdi), %rdx    # Compute n = x+x   

  .L2:                           # loop:
    leaq   1(%rcx, %rax), %rax   # Compute x += y + 1   
    subq   $1, %rdx              # Decrement n   
    testq  %rdx, %rdx            # Test n   
    jg     .L2                   # If > 0, goto loop   
    rep;ret                      # Return

A. 哪些寄存器用来存放程序值 x、y 和 n ？

%rax 存放 x ，%rcx 存放 y ，%rdx 存放 n 。

B. 编译器如何消除对指针变量 p 和表达式 (*p)++ 隐含的指针间接引用的需求？

编译器认为指针 p 总是指向 x ，因此表达式 (*p)++ 就能够实现 x 加一。代码通过 leaq 指令，把这个加一和加 y 组合起来。

C. 对汇编代码添加一些注释，描述程序操作。

练习题 3.24对于如下 C 代码：

1
2
3
4
5
6
7
8
9
long loop_while(long a, long b)
{
    long result = ____;
    while (____) {
        result = ____;
        a = ____ ;
    }
    return result;
}

以命令行选项 -Og 运行 GCC 产生如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# long loop_while(long a, long b)
# a in %rdi, b in %rsi
loop_while:
    movl   $1, %eax            
    jmp    .L2                 

  .L3:
    leaq   (%rdi, %rsi), %rdx  
    imulq  %rdx, %rax          
    addq   $1, %rdi            

  .L2:
    cmpq   %rsi, %rdi          
    jl     .L3                 
    rep; ret

可以看到编译器使用了跳转到中间的翻译方法，在用 jmp 跳转到标号 .L2 开始测试。填写 C 代码中缺失的部分。

1
2
3
4
5
6
7
8
9
long loop_while(long a, long b)
{
    long result = 1;
    while (a < b) {
        result = result * (a + b);
        a = a + 1;
    }
    return result;
}

练习题 3.25对于如下 C 代码：

1
2
3
4
5
6
7
8
9
long loop_while2(long a, long b)
{
    long result = ____;
    while (____) {
        result = ____;
        b = ____ ;
    }
    return result;
}

以命令行选项 -ol 运行 GCC ，产生如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# a in %rdi, b in %rsi
loop_while2:
    testq   %rsi, %rsi      
    jle     .L8             
    movq    %rsi, %rax      
  .L7:
    imulq   %rdi, %rax      
    subq    %rdi, %rsi      
    testq   %rsi, %rsi      
    jg      .L7             
    rep; ret                
  .L8:
    movq    %rsi, %rax      
    ret

可以看到编译器使用了 guarded-do 的翻译方法，使用了 jle 指令使得当初始测试不成立时，忽略循环代码。填写缺失的 C 代码。

1
2
3
4
5
6
7
8
9
long loop_while2(long a, long b)
{
    long result = b;
    while (b>0) {
        result = result * a;
        b = b - a;
    }
    return result;
}

练习题 3.26 函数 fun_a 有如下整体结构：

1
2
3
4
5
6
7
8
9
long fun_a(unsigned long x) {
    long val = 0;
    while (...) {
        .
        .
        .
    }
    return ...;
}

GCC C 编译器产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# long fun_a(unsigned long x)
# x in %rdi
long fun_a(unsigned long x)

fun_a:
    movl   $0, eax      
    jmp    .L5          

  .L6:
    xorq   %rdi, %rax   
    shrq   %rdi         # Shift right by 1

  .L5:
    testq  %rdi, %rdi   
    jne    .L6          
    andl   $1, %eax     
    ret

逆向工程这段代码的操作，然后完成下面作业：

A. 确定这段代码使用的循环翻译方法。

使用的是跳转到中间翻译方法。汇编中使用了 jmp 指令。

B. 根据汇编代码版本填写完 C 代码中缺失的部分。

1
2
3
4
5
6
7
8
9
long fun_a(unsigned long x) {
    long val = 0;
    while (x != 0) {
        val ^= x ;
        x >>= 1 ;
    }
    
    return val & 0x1;
}

C. 用自然语言描述这个函数是计算什么的。

这个代码计算参数 x 的奇偶性。也就是，如果 x 中有奇数个 1，就返回 1，如果有偶数个 1，就返回 0。

练习题 3.27

先把 fact_for 转换成 while 循环，再进行 guarded-do 变化，写出 fact_for 的 goto 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long fact_for_gd_goto(long n)
{
    long i = 2;
    long result = 1;
    if (n <= 1)
        goto done;
    loop:
        result *= i;
        i++;
        if (i <= n)
            goto loop;
    done:
        return result;
}

练习题 3.28函数 fun_b 有如下整体结构：

1
2
3
4
5
6
7
8
9
10
11
long fun_b(unsigned long x) {
    long val = 0;
    long i;
    for ( ... ; ... ; ... ) {
        .
        .
        .
    }
    return val;
}

GCC 编译器产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# long fun_b(unsigned long x)
# x in %rdi

fun_b:
    movl   $64, %edx        # %edx 寄存器中存入 64
    movl   $0, %eax         # 对应 long val = 0

  .L10:
    movq   %rdi, %rcx       # long temp = x
    andl   $1, %ecx         # temp = temp ^ 0x1  x 的最低位
    addq   %rax, %rax       # val = val * 2
    orq    %rcx, %rax       # val = val | temp 最低位如果是 1，就是真
    shrq   %rdi             # 逻辑右移 1 位
    subq   $1, %rdx         # 装入寄存器，减去 1
    jne    .L10             # %rdx 不是 0 的情况下继续循环
    rep; ret

逆向工程这段代码的操作，然后完成下面的工作：

A. 根据汇编代码版本填写 C 代码中缺失的部分。

1
2
3
4
5
6
7
8
9
10
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;
}

B. 解释循环前为什么没有初识测试也没有初始跳转到循环内部的测试部分。

这段代码使用 guarded-do 变换生成的，但是编译器发现因为 i 初始化成了 64，所以一定会满足测试 i != 0 ，因此初始的测试是没必要的。

C. 用自然语言描述这个函数是计算什么的。

这段代码把 x 中的位反过来，创造一个镜像。实现的方法是：将 x 的位从左往右移，然后再填入这些位，就像是把 val 从右往左移。

练习题 3.29

在 C 语言中执行 continue 语句会导致程序跳到当前循环迭代的结尾。当处理 continue 语句时，将 for 循环翻译成 while 循环的描述规则需要一些改进。例如，当考虑下面的代码：

1
2
3
4
5
6
7
8
9
10
/* Example of for loop containing a continue statement */
/* Sum even numbers between 0 and 9 */
long sum = 0;
long i;
for (i = 0; i < 10; i++) {
    if (i & 1)
        continue;
    sum += i;
}

A. 如果我们简单地直接应用将 for 循环翻译到 while 循环的规则，会得到什么呢？产生的代码会有什么错误呢？

1
2
3
4
5
6
7
8
9
10
11
12
/* Naive translation of for loop into while loop */
/* WARNING: This is buggy code */
long sum = 0;
long i = 0;
while (i < 10) {
    if (i & 1)
        /* This will cause an infinite loop */
        continue;
    sum += i;
    i++;
}

因为 continue 语句会阻止索引变量 i 被修改，所以这段代码是无限循环。

B. 如何用 goto 语句来替代 continue 语句，保证 while 循环的行为同 for 循环的行为完全一样？

通用的解决方法是用 goto 语句替代 continue 语句，它会跳过循环体中余下的部分，直接跳到 update 部分

1
2
3
4
5
6
7
8
9
10
/* Correct translation of for loop into while loop */
long sum = 0;
long i = 0;
while (i < 10) {
    if (i & 1)
        goto update;
    sum += i;
    update:
        i++;
}

练习题 3.30下面的 C 函数省略了 switch 语句的主体。在 C 代码中，情况标号是不连续的，而有些情况有多个标号。

1
2
3
4
5
6
7
8
9
10
void switch2(long x, long *dest) {
    long val = 0;
    switch (x) {
        .
        .  // Body of switch statement omitted
        .
    }
    *dest = val;
}

在编译该函数时，GCC 为程序的初始部分生成了以下汇编代码，变量 x 在寄存器 %rdi 中：

1
2
3
4
5
6
7
8
# void switch2(long x, long *dest)
# x in %rdi
switch2:
    addq    $1, %rdi    # x = x + 1 ，由于将索引控制在 0 开始，所以 x 的最小值是 -1      
    cmpq    $8, %rdi    # 比较 x - 8，其实就是 x + 1 - 8 > 0 ，则原始的 x 最大标号是 7       
    ja      .L2         # 超过 8 就跳转到 L2，L2 相当于 default   
    jmp     *.L4(, %rdi, 8)    # 没有超过 8 就进入跳转表

为跳转表生成以下代码：

1
2
3
4
5
6
7
8
9
10
11
.L4
    quad:   .L9    # -1
    quad:   .L5    # 0
    quad:   .L6    # 1
    quad:   .L7    # 2
    quad:   .L2    # default
    quad:   .L7    # 4
    quad:   .L8    # 5
    quad:   .L2    # default 
    quad:   .L5    # 7

A. switch 语句内情况标号的值分别是多少？

-1、0、1、2、4、5 和 7

B. C 代码中哪些情况有多个标号？

.L5 的情况为 0 和 7，.L7 的情况标号为 2 和 4。

练习题 3.31

对于一个通用结构的 C 函数 switcher:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void switcher(long a, long b, long c, long *dest)
{
    long val;
    switch(a) {
    case ____:     /* Case A */
        c = ____;
        /* Fall through */
    case ____:     /* Case B */
        val = ____;
        break;
    case ____:     /* Case C */
    case ____:     /* Case D */
        val = ____;
        break;
    case ____:     /* Case E */
        val = ____;
        break;
    default:
        val = ____;
    }
    *dest = val;
}

GCC 产生如下所示的汇编代码和跳转表：

image-20221108153523592

填写 C 代码中缺失的部分。除了情况标号 C 和 D 的顺序之外，将不同情况填入这个模板的方式是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void switcher(long a, long b, long c, long *dest)
{
    long val;
    switch(a) {
    case 5:     /* Case A */
        c = b ^ 15;
        /* Fall through */
    case 0:     /* Case B */
        val = c + 112;
        break;
    case :     /* Case C */
    case :     /* Case D */
        val =  (c + b) << 2 ;
        break;
    case :     /* Case E */
        val = a;
        break;
    default:
        val = b;
    }
    *dest = val;
}

练习题 3.32

下面列出的是两个函数 first 和 last 的反汇编代码，以及 main 函数调用 first 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Disassembly of last(long u, long v)
# u in %rdi, v in %rsi
0000000000400540 <last>:
  400540:  48 89 f8          mov   %rdi, %rax     # L1: u
  400543:  48 0f af c6       imul  %rsi, %rax     # L2: u*v
  400547:  c3                req                  # L3: Return
  
# Disassembly of first(long x)
# x in %rdi
0000000000400548 <first>:
   400548: 48 8d 77 01       lea   0x1(%rdi), %rsi  # F1: x+1
   40054c: 48 83 ef 01       sub   $0x1, %rdi       # F2: x-1
   400500: e8 eb ff ff ff    callq 400540 <last>    # F3: Call last(x-1, x+1)
   400555: f3 c3             repz  retq             # F4: Return
   .
   .
   .
   400560: e8 e3 ff ff ff    callq 400548 <first>   # M1: Call first(10)
   400565: 48 89 c2          mov   %rax, %rdx       # M2: Resume

从 main 调用 first(10) 开始，到程序返回 main 时为止，填写下表记录指令执行的过程。

指令 状态值 (指令执行前)
标号 PC 指令 %rdi %rsi %rax %rsp %rsp 描述
M1 0x400560 callq 10 - - 0x7fffffffe820 - 调用 first(10)
F1 0x400548 leq 10 - - 0x7fffffffe818 0x400565 first 的入口
F2 0x40054c sub 10 11 - 0x7fffffffe818 0x400565
F3 0x400550 callq 9 11 - 0x7fffffffe810 0x400565 调用 last(9, 11)
L1 0x400540 mov 9 11 - 0x7fffffffe810 0x400555 last 的入口
L2 0x400543 imul 9 11 9 0x7fffffffe810 0x400555
L3 0x400547 retq 9 11 99 0x7fffffffe810 0x400555 从 last 返回 99
F4 0x400555 repz repq 9 11 99 0x7fffffffe818 0x400565 从 first 返回 99
M2 0x400565 mov 9 11 99 0x7fffffffe820 - 继续执行 main

练习题 3.33

C 函数 procprob 有 4 个参数 u、a、v 和 b，每个参数要么是一个有符号数，要么是一个指向有符号数的指针，这里的数大小不同。该函数的函数体如下：

1
2
3
*u += a;
*v += b;
return sizeof(a) + sizeof(b);

编译得到如下 x86-64 代码：

1
2
3
4
5
6
procprob:
  movslq  %edi, %rdi
  addq    %rdi, (%rdx)
  addb    %sil, (%rcx)
  movl    $6, %eax
  ret

确定 4 个参数的合法顺序和类型。

因为代码的 return 里返回的是 6，所以可以知道 a 和 b 两个数一个是 4 位长，一个是 2 位长。

假如 a 是 4 位长度， 则一开始扩展 %edi 符号实际上操作的是 a， 那么之后把 a 加到 (%rdx) 上边，说明 %rdx 中是 u。对应的，%sil 中是 b，%rcx 中是 v。

a 通过 %edi 作为第一个参数传递，把它从 4 个字节转换成 8 个字节，再加到 %rdx 指向的 8 个字节上。这就意味着 a 必定是 int 类型，u 一定是 long 类型。还可以看到 b 的低位字节被加到了 %rcx 指向的字节。这就意味着 v 一定是 char 。

假如 b 是 4 位长度,，则一开始扩展 %edi 符号实际上操作的是 b ，那么之后把 b 加到 (%rdx) 上边，说明 %rdx 中是 v。对应的，%sil 中是 a，%rcx 中是 u 。

所以两种情况是：

1
2
int procprob(int a, short b, long *u, char *v)`
int procprob(int b, short a, long *v, char *u)

练习题 3.34

一个函数 P 生成名为 a0 ~ a7 的局部变量，然后调用函数 Q ，没有参数。GCC 为 P 的第一部分产生如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# long P(long x)
# x in %rdi
P:
    pushq   %r15
    pushq   %r14
    pushq   %r13
    pushq   %r12
    pushq   %rbp
    pushq   %rbx    

    subq    $24, %rsp      

    movq    %rdi, %rbx     
    leaq    1(%rdi), %r15  
    leaq    2(%rdi), %r14  
    leaq    3(%rdi), %r13  
    leaq    4(%rdi), %r12  
    leaq    5(%rdi), %rbp  

    leaq    6(%rdi), %rax  
    mov     %rax, (%rsp)   
    leaq    7(%rdi), %rdx  
    movq    %rdx, 8(%rsp)  
    movl    $0, %eax       
    call    Q

A. 确定哪些局部值存储在被调用者保存寄存器中。

局部值 a0 ~ a5 分别保存被调用者保存寄存器 %rbx、%r15、%r14、%13、%12 和 %rbp。

B. 确定哪些局部变量存储在栈上。

局部值 a6 和 a7 存放在栈中相对于栈指针偏移量为 0 和 8 的地方。

C. 解释为什么不能把所有的局部值都存储在被调用者保存寄存器中。

存储完 6 个局部变量后，程序用完了所有的被调用者保存寄存器，所以剩下的两个值保存在栈上。

练习题 3.35 一个具有通用结构的 C 函数如下：

1
2
3
4
5
6
7
8
9
long rfun(unsigned long x){
    if(______){
        return ______;
    }
    unsigned long nx = ______;
    long rv = rfun(nx);
    return ______;
}

GCC 产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# long rfun(unsigned long x)
# x in %rdi

rfun:
    pushq   %rbx           
    movq    %rdi, %rbx     
    movl    %0, %eax       
    testq   %rdi, %rdi     
    je      .L2            
    shrq    $2, %rdi       
    callq   rfun           
    addq    %rbx, %rax     

  .L2
    popq    %rbx           
    ret

A. rfun 存储在被调用者保存器 %rbx 中的值是什么？

寄存器 %rbx 保存参数 x 的值

B. 填写上述 C 代码中缺失的表达式。

1
2
3
4
5
6
7
8
9
long rfun(unsigned long x){
    if(x == 0){
        return 0;
    }
    unsigned long nx = x >> 2;
	long rv = rfun(nx);
    return x + rv ;
}

练习题 3.36

考虑下面的声明：

1
2
3
4
5
short S[7];
short *T[3];
short **U[6];
int   V[8];
double *W[4];

填写下表，描述每个数组的元素大小、整个数组的大小以及元素 i 的地址：

数组 元素大小 整个数组的大小 起始地址 元素 i
S 2 14 $x_S$ $x_S+2i$
T 8 24 $x_T$ $x_T+8i$
U 8 48 $x_U$ $x_U+8i$
V 4 32 $x_V$ $x_V+4i$
W 8 32 $x_W$ $x_W+8i$

练习题 3.37

假设短整形数组 S 的地址 $x_S$ 和整数索引 i 分别存放在寄存器 %rdx 和 %rcx 中。对下面每个表达式，给出它的类型、值的表达式和汇编代码实现。如果结果是指针的话，要保存在寄存器 %rax 中，如果数据类型为 short，就保存在寄存器元素 %ax 中。

表达式 类型 值 汇编代码
S + 1 short* $x_S+2$ leaq 2(%rdx), %rax
S[3] short $M[x_S+6]$ movw 6(%rdx), %ax
&S[i] short* $x_S+2i$ leaq (%rdx, %rcx, 2), %rax
S[4*i+1] short $M[x_S+8_i+2]$ movw 2(%rdx, %rcx, 8), %ax
S + i - 5 short* $x_S+2i−10$ leaq -10(%rdx, %rcx, 2), %rax

练习题 3.38

考虑下面的源码，其中 M 和 N 是用 #define 声明的常数：

1
2
3
4
5
6
long P[M][N];
long Q[N][M];

long sum_element(long i, long j) {
    return P[i][j] + Q[j][i];
}

在编译这个程序中，GCC 产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# long sum_element(long i, long j)
# i in %rdi, j in %rsi

sum_element:
    leaq   0(,%rdi, 8),  %rdx       # %rdx = 8i
    subq   %rdi, %rdx               # %rdx - i = 7i
    addq   %rsi, %rdx               # %rdx = 7i + j
    leaq   (%rsi, %rsi, 4), %rax    # %rax = 5j
    addq   %rax, %rdi               # %rdi = i + 5j
    movq   Q(, %rdi, 8), %rax       # M[xQ + 8(5j + i)]
    movq   P(, %rdx, 8), %rax       # M[xP + 8(7i + j)]
    ret

运用逆向工程技能，根据这段汇编代码，确定 M 和 N 的值。

P 有 7 列，Q 有 5 列，得到 M=5 和 M=7 。

练习题3.39

利用等式3.1来解释图3-37b的C代码中Aptr、Bptr和 Bend的初始值计算(第3~5行)是如何正确反映fix_prod_ele的汇编代码中它们的计算(第3~5行)的。

对于L=4，C=16和j=0，指针Aptr等于$x_A＋4×(16i＋0)=x_A+64i$。

对于L=4，C=16，i=0和j=k，指针 Bptr等于$x_B+4×(16×0+k)=x_B+4k$。

对于L=4，C=16，i=16和j=k，Bend等于$x_B+4×(16×16+k)=x_B+1024+4k$。

练习题 3.41考虑下面的结构声明：

1
2
3
4
5
6
7
8
9
struct prob {
    int *p;
    struct {
        int x;
        int y;
    } s;
    struct prob *next;
};

这个声明说明一个结构可以嵌套在另一个结构中，就像数组可以嵌套在结构中、数组可以嵌套在数组中一样。

下面的过程（省略了某些表达式）对这个结构进行操作：

1
2
3
4
5
void sp_init(struct prob *sp) {
    sp->s.x = _____;
    sp->p   = _____;
    sp->next= _____;
}

A. 下列字段的偏移量是多少（以字节为单位）？

p: 指针 p 是第一个元素，偏移量为 0
s.x: 是紧接在 p 之后的结构内第一个元素，偏移量为 8
s.y: x 的长度为 4，所以偏移量为 12
next: y 的长度为 4，所以偏移量为 16

B. 这个结构总共需要多少字节？
指针长度为 8，int为4，总共24字节。

C. 编译器为 sp_init 的主体产生的汇编代码如下：

1
2
3
4
5
6
7
8
9
10
# void sp_init(struct prob *sp)
# sp in %rdi
sp_init:
movl 12(%rdi), %eax     # Get sp->s.y
movl %eax, 8(%rdi)      # Save in sp->s.x
leaq 8(%rdi), %rax      # Compute &(sp->s.x)
movq %rax, (%rdi)       # Store in sp->p
movq %rdi, 16(%rdi)     # Store sp in sp->next
ret

根据这些信息，填写 sp_init 代码中缺失的表达式。

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

练习题 3.42下面的代码给出了类型 ELE 的结构声明以及函数 fun 的原型：

1
2
3
4
5
6
7
struct ELE {
    long v;
    struct ELE *p;
}

long fun(struct ELE *ptr);

当编译 fun 的代码时，GCC 会产生如下汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# long fun(struct ELE *ptr)
# ptr in %rdi

fun:
    movl   $0, %eax          # result = 0
    jmp    .L2               # Goto middle
  .L3:                       # loop:
    addq   (%rdi), %rax      # result += ptr->v
    movq   8(%rdi), %rdi     # ptr = ptr->p
  .L2:                       # middle:
    testq  %rdi, %rdi        # Test ptr
    jne    .L3               # If != NULL, goto loop
    rep; ret

A. 利用逆向工程技巧写出 fun 的 C 代码。

1
2
3
4
5
6
7
8
long fun(struct ELE *ptr) {
	long val = 0;
    while(ptr){
        val += ptr->v;
        ptr = ptr->p;
    }
	return val;
}

B. 描述这个结构实现的数据结构以及 fun 执行的操作。

每个结构都是一个单链表中的元素，字段 v 是元素的值，字段 p 是指向下一个元素的指针。函数 fun 计算列表中元素值的和。

习题 3.43

假设给你个任务，检查一下 C 编译器为结构和联合的访问产生正确的代码。你写了下面的结构声明：

1
2
3
4
5
6
7
8
9
10
11
typedef union {
    struct {
        long u;
        short v;
        char w;
    } t1;
    struct {
        int a[2];
        char *p;
    } t2;
} u_type;

你写了一组具有下面这种形式的函数：

1
2
3
void get(u_type *up, type *dest) {
    *dest = expr;
}

这组函数有不一样的访问表达式 expr，而且根据 expr 的类型来设置目的数据类型 type 。然后再检查编译这些函数时产生的代码，看看它们是否与你预期的一样。

假设在这些函数中，up 和 dest 分别被加载到寄存器 %rdi 和 %rsi 中。填写下表中的数据类型 type，并用 1 ~ 3 条指令序列来计算表达式，并将结果存储到 dest 中。

expr type 代码
up->t1.u long movq (%rdi), %rax movq %rax, (%rsi)
up->t1.v short movw 8(%rdi), %ax movw %ax, (%rsi)
&up->t1.w char* addq $10, %rdi movq %rdi, (%rsi)
up->t2.a int* movq %rdi, (%rsi)
up->t2.a[up->t1.u] int movq (%rdi), %rax movl (%rdi, %rax, 4), %eax movl %eax, (%rsi)
*up->t2.p char movq 8(%rdi), %rax movb (%rax), %al movb %al, (%rsi)

练习题 3.44 对下面每个结构声明，确定每个字段的偏移量，结构总的大小，以及在 x86-64 下它的对齐要求：

A. struct P1 {int i; char c; int j; char d};

i c j d 总共 对齐
0 4 8 12 16 4

B. struct P2 {int i; char c; char d; long j};

i c d j 总共 对齐
0 4 5 8 16 8

​ C. struct P3 {short w[3]; char c[3]};

w c 总共 对齐
0 6 10 2

D. struct P4 {short w[5]; char *c[3]};

w c 总共 对齐
0 16 40 8

E. struct P5 {struct P3 a[2]; struct P2 t};

a t 总共 对齐
0 24 40 8

练习题 3.45

对于下列结构声明回答后续问题：

1
2
3
4
5
6
7
8
9
10
struct {
    char  *a;    
    short  b;    
    double c;   
    char   d;     
    float  e;    
    char   f;     
    long   g;     
    int    h;      
} rec;

A. 这个结构中所以的字段的字节偏移量是多少？

字段 a b c d e f g h
大小 8 2 8 1 4 1 8 4
偏移量 0 8 16 24 28 32 40 48

B. 这个结构总的大小是多少？

总共 56 个字节长。

C. 重新排列这个结构中的字段，以最小化浪费的空间，然后再给出重排过的结构的字节偏移量和总的大小。

当所有的数据元素的长度都是 2 的幂时，一种行之有效的策略是按照大小的降序排列结构的元素。

1
2
3
4
5
6
7
8
9
10
11
struct {
    char   *a;
    double  c; 
    long    g;
    float   e;
    int     h;
    short   b;
    char    d;
    char    f;
} rec;

得到的偏离量如下：

字段 a c g e h b d f
大小 8 8 8 4 4 2 1 1
偏移量 0 8 16 24 28 32 34 35

这个结构要填充 4 个字节以满足 8 字节对齐的要求，所以总共是 40 个字节。

练习题 3.47

在运行 Linux 版本 2.6.16 的机器上运行栈检查代码 10 000 次，我们获得地址的范围从最小的 0xffffb754 到最大的 0xffffd754 。

A. 地址的大概范围是多大？

0xffffd754 - 0xffffd754 = 0x00002000 大约 $2^{13}$ 个地址的范围。

B. 如果我们尝试一个有 128 字节 nop sled 的缓冲区溢出，要想穷尽所有的起始地址，需要尝试多少次？

$2^7$ 为 128，$2^{13}÷2^7=2^6$ ，需要 64 次尝试。

练习题3.49

在这道题中，我们要探究图3-43b第5～11行代码背后的逻辑，它分配了变长大小的数组p。正如代码的注释表明的，$s_1$表示执行第4行的 subq指令之后栈指针的地址。这条指令为局部变量i分配空间。$s_2$表示执行第4行的subq 指令之后栈指针的值。这条指令为局部数组p 分配存储。最后，p表示第10～11行的指令赋给寄存器%r8和%rcx的值。这两个寄存器都用来引用数组p。

图3-44的右边画出了$s_1$、$s_2$和p指示的位置。图中还画出了$s_2$和p的值之间可能有一个偏移量为$e_2$字节的位置，该空间是未被使用的。数组p的结尾和s指示的位置之间还可能有一个偏移量为$e_1$字节的地方。

image-20221110194157270

3-43b

image-20221110194231170

A.用数学语言解释第5～7行中计算s2的逻辑。提示:想想—16的位级表示以及它在第6行andq指令中的作用。

第5行的leaq指令计算值8n＋22，然后第6行的andq指令把它向下舍入到最接近的16的倍数。当n是奇数时，结果值会是8n+8，当n是偶数时，结果值会是8n+16，这个值减去$s_1$就得到$s_2$。

解释：

第5行汇编得到8n+22。

第6行8n+22与立即数-16进行与运算。按照最高位为符号位来说，-16的二进制为1 0000，因为符号拓展值不变，所以-16的8字节表示为.... 1111 0000，省略号全为1。所以第6行是要将8n+22与.... 1111 0000进行与运算，这会导致8n+22的低4位如果谁有1都会被舍弃掉，原文描述为：“把它向下舍入到最接近的16的倍数”，因为是舍弃低4位所以是“向下舍入”。按照本人描述为：舍弃掉权值为8,4,2,1的二进制位，只留下权值大于等于8的二进制位。

所以，与$-16进行与运算后，结果将会是16的倍数。倍数可能是0,1…

当n为偶数时，将8n+22拆分为8n和22。既然n为偶数，则8n为16的倍数，那么8n and $-16 = 8n。22 and $-16 = 16。将两个结果加起来就是8n + 16。
当n为奇数时，将8n+22拆分为8(n-1)和30。既然n-1为偶数，则8(n-1)为16的倍数，那么8(n-1) and $-16 = 8(n-1)。30 and $-16 = 16。将两个结果加起来就是8n + 8.

还有就是这个22，其实可以替换为16-23中一个数都可以，把这个数称为m，那么要求m或者m+8在和与$-16进行与运算后，结果必须为16，从这个要求就可以得出这个范围。

B.用数学语言解释第8～10行中计算p的逻辑。提示:可以参考2.3.7节中有关除以2的幂的讨论。

该序列中的三条指令将s2舍入到最近的8的倍数。它们利用了2.3.7节中实现除以⒉的幂用到的偏移和移位的组合。

解释：

在第8行，将%rsp加上7即$2^3-1$，假设%rsp栈指针为x，在第9行右移3位，这里将产生$⌈x/2^3⌉$即$⌈x/8⌉$。
第10行乘以8，相当于左移3位。可以想象，当%rsp刚好是8的倍数时，执行完8-10行，不变，因为向上取整时为本身。当%rsp不是8的倍数时，执行完8-10行，为%rsp+8，因为向上取整时加1了。

换个角度，7的二进制为111，当%rsp的低三位是000时，加上111不会使得第4位加1；当%rsp的低三位不是000而是其他情况时，加上111肯定使得第4位加1。然后第9,10行的操作是先右移3位，再左移3位，这就相当于把低3位的二进制值清0。

总结一下：要么%rsp不变，要么%rsp向上舍入到最接近8的倍数。

C.对于下面n和$s_1$的值，跟踪代码的执行，确定$s_2$、$p$、$e_1$和$e_2$的结果值。

n $s_1$ $s_2$ $p$ $e_1$ $e_2$
5 2065 2017 2024 1 7
6 2064 2000 2000 16 0

解释：

在第7行汇编分配栈空间时，是将$e_1$和$e_2$和数组的空间一起考虑的了。

当第10行汇编执行，才会确定了$e_1$和$e_2$的大小。因为只有这个时候才知道了数组空间的开始地址和结束地址。注意这个图里面，$e_1$和$e_2$不一定都是8个字节。

当$s_1$为刚好为8的倍数时,$e_1$和$e_2$就没什么用了，起码不需要它俩来8K对齐了，因为本来就是8K对齐的。

当$s_1$不是8的倍数时，$e_1$和$e_2$可以用来保证数组每个元素8K对齐。

D.这段代码为$s_2$和p的值提供了什么样的对齐属性?

可以看到$s_2$的计算方式会保留$s_1$的偏移量为最接近的16的倍数。还可以看到p会以8的倍数对齐，正是对8字节元素数组建议使用的。

练习题 3.50

对于下面的 C 代码，表达式 val1 ~ val4 分别对应程序值 i、f、d 和 l：

1
2
3
4
5
6
7
8
9
double fcvt2(int *ip, float *fp, double *dp, long l) {
    int i = *ip;
    float f = *fp;
    double d = *dp;
    *ip = (int)     val1;
    *fp = (float)   val2;
    *dp = (double)  val3;
    return (double) val4;
}

根据该函数如下的 x86-64 代码，确定这个映射关系：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# double fcvt2(int *ip, float *fp, double *dp, long l)
# ip in %rdi, fp in %rsi, dp in %rdx, l in %rcx
# Result returned in %xmm0

fcvt2:
    movl        (%rdi), %eax        # 把 ip 的值放入 %eax
    vmovss      (%rsi), %xmm0       # 传送单精度数, 把 fp 放入 %xmm0
    vcvttsd2si  (%rdx), %r8d        # 双精度转 32 位整数，dp 放入 %r8d
    movl        %r8d, (%rdi)        # 转换后写入 ip 对应的内存位置
    vcvtsi2ss   %eax, %xmm1, %xmm1  # 32 位整数转单精度浮点数
    vmovss      %xmm1, (%rsi)       # 转换后写入 fp 对应的地址
    vcvtsi2sdq  %rcx, %xmm1, %xmm1  # 64 位整数转为双精度浮点
    vmovsd      %xmm1, (%rdx)       # 转换后写入到 dp 对应的地址
    vunpcklps   %xmm0, %xmm0, %xmm0 # 单精度转换为双精度
    vcvtps2pd   %xmm0, %xmm0        
    ret

  • 取出位于 dp 的值，转换成 int，再存储到 ip。因此推断出 val1 是 d。
  • 取出位于 ip 的值，转换成 float，再存储到 fp。因此推断出 val2 是 i。
  • l 的值转换成 double，并存储在 dp。因此推断出 val3 是 l。
  • fp 的值被转换成双精度，值通过寄存器 %xmm0 返回。因此推断出 val4 是 f。

练习题 3.51

下面的 C 函数将类型为 src_t 的参数转换为类型为 dst_t 的返回值，这里两种参数类型都用 typedef 定义：

1
2
3
4
dest_t cvt(src_t x){
    dest_t y = (dest_t) x;
    return y;
}

在 x86-64 上执行这段代码，假设参数 x 在 %xmm0 中，或者在寄存器 %rdi 的某个适当的命名中（即 %rdi 或 %edi）。用一条或两条指令来完成类型转换，并把结果值复制到寄存器 %rax 的某个适当命令部分中（整数结果），或 %xmm0 中（浮点结果）。给出这条或这些指令，包括源和目的寄存器。

Tx Ty 指令
long double vcvtsi2sdq %rdi, %xmm0
double int vcvvttsd2si %xmm0, %eax
double float vunpcklpd %xmm0, %xmm0, %xmm0 vcvtpd2ps %xmm0, %xmm0
long float vcvtsi2ssq %rdi, %xmm0, %xmm0
float long vcvttss2siq %xmm0, %rax

练习题 3.52

对于下面每个函数声明，确定参数的寄存器分配：

A. double g1(double a, long b, float c, int d);

a 在 %xmm0 ，b 在 %rdi 中，c 在 %xmm1 中，d 在 %esi 中。

B. double g2(int a, double *b, float *c, long d);

a 在 %edi 中，b 在 %rsi 中，c 在 %rdx 中，d 在 %rcx 中。

C. double g3(double *a, double b, int c, float d);

a 在 %rdi 中，b 在 %xmm0 中，c 在 %esi 中，d 在 %xmm1 中。

D. double g4(float a, int *b, float c, double d);

a 在 %xmm0 中，b 在 %rdi 中，c 在 %xmm1 中，d 在 %xmm2 中。

练习题 3.53

对于下面的 C 函数，4 个参数的类型由 typedef 定义：

1
2
3
double funct1(art1_t p, arg2_t q, arg3_t r, arg4_t s){
    return p/(q+r) - s;
}

编译时，GCC 产生如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
Assembly
# double funct1(art1_t p, arg2_t q, arg3_t r, arg4_t s)
# Refer to arguments as i1(%rdi), i2(%esi), f1(%xmm0), and f2(%xmm1)

funct1:
    vcvtsi2ssq      %rsi, %xmm2, %xmm2      # Get i2 and convert from long to float
    vaddss          %xmm0, %xmm2, %xmm0     # Add f1 (type float)
    vcvtsi2ss       %edi, %xmm2, %xmm2      # Get i1 and convert from int to float
    vdivss          %xmm0, %xmm2, %xmm0     # Compute i1 / (i2 + f1)
    vunpcklps       %xmm0, %xmm0, %xmm0
    vcvtps2pd       %xmm0, %xmm0            # Convert to double
    vsubsd          %xmm1, %xmm0, %xmm0     # Compute i1 / (i2 + f1) - f2(double)
    ret

确定 4 个参数类型的可能组合。

1
2
double funct1a(int p, float q, long r, double s);
double funct1b(int p, long q, float r, double s);

练习题 3.54 函数 func2 具有如下原型：

1
double funct2(double w, int x, float y, long z);

GCC 为该函数产生如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
Assembly
# double funct2(double w, int x, float y,long z)
# w in %xmm0, x in %edi, y in %xmm1, z in %rsi

funct2:
    vcvtsi2ss       %edi, %xmm2, %xmm2      # Convert x to float
    vmulss          %xmm1, %xmm2, %xmm1     # Multiply by y
    vunpcklps       %xmm1, %xmm1, %xmm1
    vcvtps2pd       %xmm1, %xmm2            # Convert x*y to double
    vcvtsi2sdq      %rsi, %xmm1, %xmm1      # Convert z to double
    vdivsd          %xmm1, %xmm0, %xmm0     # Compute w/z
    vsudsd          %xmm0, %xmm2, %xmm0     # Subtract from x*y
    ret

写出 funct2 的 C 语言版本。

1
2
3
4
5
6
7
8
9
10
11
double funct2(double w, int x, float y,long z){
    float temp = (float) x;
    y = y * temp;
    double temp2 = (double) y;
    double temp3 = (double) z;
    w = w / temp3;
    return y - w;
}
double funct2(double w, int x, float y,long z){
    return y * x - w / z;
}