控制语句除了条件分支就是循环, 今天看循环的操作, 以及比较特殊的分支语句, 就是switch.
汇编指令并没有直接的指令对应循环, 而是用条件测试和跳转组合起来实现循环的效果. 汇编代码主要基于两种基本的循环模式. 先来看两种基本循环模式的第一种:
do-while循环
do-while循环的基本模式是:
do {
body-statement
} while(test-expr);
这个循环的效果是执行一次body之后, 测试test-expr条件表达式的值, 为真则继续循环.
靠近汇编的角度, 这种语句会被翻译成如下结构的语句:
loop:
body-statement;
t = test-expr;
if(t)
goto loop;
这种语句就很接近汇编了, 其中的关键点在于更新条件表达式的语句.
练习 3.22 阶乘的大小
- 32位 int 能表示的最大的n的阶乘, n 是多少? 32位int最大的正数是2147483647 , 直接运行程序列出来部分结果就可以知道 n = 12 还没溢出, 而13就溢出了, 因为最后两位不是00
1 : 1 2 : 2 3 : 6 4 : 24 5 : 120 6 : 720 7 : 5040 8 : 40320 9 : 362880 10 : 3628800 11 : 39916800 12 : 479001600 13 : 1932053504 14 : 1278945280 15 : 2004310016 16 : 2004189184 - 64位的long也类似的列出来:
1 : 1 2 : 2 3 : 6 4 : 24 5 : 120 6 : 720 7 : 5040 8 : 40320 9 : 362880 10 : 3628800 11 : 39916800 12 : 479001600 13 : 6227020800 14 : 87178291200 15 : 1307674368000 16 : 20922789888000 17 : 355687428096000 18 : 6402373705728000 19 : 121645100408832000 20 : 2432902008176640000 21 : -4249290049419214848可见最大n = 20.
练习 3.23 已知C和汇编, 代码, x 一开始存放在%rdi中:
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;
}
long dw_loop(long x)
dw_loop:
movq %rdi, %rax 把x复制到%rax中, 由于x是局部变量, 其实这句就相当于*p = &x, 操作x就是操作%rax寄存器
movq %rdi, %rcx 把x复制到%rcx中
imulq %rdi, %rcx 设置%rcx的值为 x * x, 所以%rcx中存放的是局部变量y = x * x
leaq (%rdi, %rdi), %rdx %rdx的值为 x+x, 则n存放在%rdx中
.L2:
leaq 1(%rcx, %rax), %rax 让x = x + y + 1 ? 这是一条指令把两条活都干了, 先是 x = x + y , 然后 x = x + 1.
subq $1, %rdx n = n - 1
testq %rdx, %rdx 测试%rdx 也就是 n
jg .L2 n>0 则跳转到 .L2
rep;ret 返回%rax中的值
通过分析可以知道, y 存放在 %rcx 中, n 存放在%rdx中.
编译器通过将x复制到 %rax中 来直接操作, 然后使用leaq 指令合并了两行代码的计算, 相比解引用指针效率要高很多.
普通while循环
do-while循环其实和汇编代码的对应非常直接.while循环就没有那么直接, while循环的一般模式是:
while(test-expr){
body-statement
}
这个有两种翻译方法. 第一种与do-while很像, 但直接跳到测试条件的部分:
//直接跳到测试语句
goto test;
//循环体, 执行完之后又到测试条件语句处
loop:
body-statement
//测试条件, 满足就跳到循环体
test:
t = test-expr;
if(t)
goto loop;
这个本质上就是一个直接跳到测试条件的do-while循环.
练习3.24 根据汇编填写C程序
long loop_while(long a, long b)
a in %rdi, b in %rsi
loop_while:
movl $1, %eax 向%rax里放入1 long result = 1
jmp .L2 跳转到L2
.L3:
leaq (%rdi, %rsi), %rdx long temp = x + y
imulq %rdx, %rax result = result * temp
addq $1, %rdi a++
.L2:
cmpq %rsi, %rdi 比较a : b
jl .L3 如果a < b, 跳转到 L3
rep; ret 返回%rax
根据汇编来补充C代码:
long loop_while(long a, long b){
// 一开始设置result = 1
long result = 1;
//这个条件就是L2中测试条件, 只要符合就跳转到L3
while(a < b){
//循环体是L3做的事情
result = result * (a + b);
a = a + 1;
}
return result;
}
第二种翻译方法叫做 guarded-do 模式, 其实就是先进行判断条件分支, 不成立就跳过循环, 成立就进入循环. 这个模式是:
t = test-expr;
if(!t)
goto done:
loop:
body-statment
if(t)
goto loop:
done:
可以看到, 就相当于在do-while之前先判断一次, 就成了普通的while循环. 毕竟do-while和普通while就差了要不要先执行一次, 如果在do-while之前先执行一次, 那么就相当于是一个普通的while了.
练习 3.25 已知汇编命令, 补全C代码
参数 a 在 %rdi, b 在 %rsi 中.
loop_while2:
testq %rsi, %rsi 测试b
jle .L8 b<=0的时候跳转 L8
movq %rsi, %rax long result = b
.L7:
imulq %rdi, %rax result = result * a
subq %rdi, %rsi b = b - a
testq %rsi, %rsi 测试 b 后的值
jg .L7 如果大于0, 跳回L7, 即一直循环
rep; ret 当 b-a<=0 的时候, 就返回%rax中的值
.L8:
movq %rsi, %rax result = b
ret
这个逻辑实际上第一次测试B的时候, b<=0就直接 结束了, 所以第一次测试必须 b>0 才能进入循环. 在循环内部, 则是每次测试 b-=a之后的值,直到b-a<=0就结束循环:
long loop_while2(long a, long b){
//无论直接跳到L8还是进入循环, %rax都要用到b的值
long result = b;
// 循环条件就是 L7中的测试条件, 即 %rsi 的值大于0
while (b > 0) {
//循环体的内容
result = result * a;
b = b - a;
}
return result;
}
练习 3.26 根据汇编写出C代码
// x in %rdi
long fun_a(unsigned long x)
fun_a:
movl $0, eax 这句相当于long val = 0
jmp .L5 无条件跳转, 而没有先测试条件, 说明编译器采用的是跳转到中间的方式
.L6:
xorq %rdi, %rax val = val ^ x
shrq %rdi 逻辑右移1位, 最高位补0
.L5:
testq %rdi, %rdi 测试x
jne .L6 x 不是 0 的时候, 跳转L6, 所以L6是循环体
andl $1, %eax 此时%eax的值与1做与运算, 结果存在%eax中, 实际上的结果就是%eax的最低位
ret 返回%rax的值
根据分析写出的代码是:
long funa(unsigned long x){
long val = 0;
while( x!=0 ){
val = val ^ x;
x >>= 1;
}
val = val & 0x1;
return val;
}
代码是写出来了, 但是半天没看明白意思. 看了答案才明白是计算奇偶性….
for循环
普通的for循环如下:
for(init-expr; test-expr; update-expr)
实际上可以翻译成如下的while循环:
init-expr:
while(test-expr){
......
update-expr
}
可以看的其实就是一个初始化表达式, 之后加上一个while循环, 因此翻译成汇编的话, 就是在while循环之前设置一个初始化循环表达式. 其后就是while语句的翻译, 有着上边的两种不同翻译方法.
练习 3.27 把例子转换成guarded-do模式
long fact_for_while(long n){
long i = 2;
long result = 1;
while (i <= n) {
result *= i;
i++;
}
return result;
}
这一段翻译成guarded-do的时候,首先就要测试条件表达式, 如果成功的话进入循环 ,然后在循环体执行完毕之后, 再测试表达式.
long fact_for_while_guarded_do(long n){
long i = 2;
long result = 1;
if(i>n)
goto done;
loop:
result *= i;
i++;
if(i<=n)
goto loop;
done:
return result;
}
练习 3.28 根据汇编写出C代码
long fun_b(unsigned long x)
x in %rdi
fun_b:
movl $64, %edx %edx寄存器中存入64, 就是0x40
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位, x>>=1
subq $1, %rdx 装入64的寄存器 减去 1
jne .L10 %rdx 不是 0 的情况下 继续循环, 是0的情况下终止循环
rep; ret
根据汇编代码补齐得到的结果是:
long fun_b(unsigned long x){
long val = 0;
long i;
for(i=64; i>0; i--){
long temp = x;
temp = temp ^ 0x1;
val = val * 2;
val = val | temp;
x >>= 1;
}
}
由于在之前的表达式, i 的初始值是确定的常数即64, 所以没有使用初始表达式.
手工演算了一下, 这个函数实际上是把x按位给反向排列了一下, 比如10011, 会变成11001. 函数的逻辑是最低一位拿过来, 然后乘以2, 再去加上移位后的最低一位,不断重复直到全部位移完.
练习3.29 带有continue语句的for
首先考虑一下continue语句的左右. continue语句的作用是直接跳到下一次循环的开头. 然而要注意的是, 对于汇编代码, 并不能使用continue直接跳过循环开始处的标号, 因为更新条件的语句也在汇编体内.
因此应当考虑将更新条件的语句放在循环体最后, 如果遇到continue语句就直接跳转到更新条件语句.
用goto语句来模拟题目中的循环, 应该写成如下:
long sum = 0;
long i;
i=0;
goto test;
loop-normal:
sum +=i;
loop-continue:
i++;
test:
if(i < 10) {
if(i&1){
goto loop-continue;
}
goto loop-normal:
}
done:
可见改写的方式, 就是把loop-normal的部分单独分离出去, 如果启动了continue, 就只进行更新i的操作, 如果未启动continue, 则执行不含continue的完整的循环体.
CSAPP的答案其实是一样的,就是在循环体里单独分出一部分是update, 在循环体的最下边, 翻译成汇编基本和我的一样.
switch
swtich 语句可以用一连串if-else 语句实现, 但是这么做的话效率很低. 通常编译器是采取创建一个数组的方式, 其中每个元素是要跳转的地址, 然后根据测试条件直接按照索引找到地址进行跳转.
这样的好处是所用时间基本一致, 而不会进行大量的分支判断.
有意思的是, GCC扩展了C语言, 加入了&&运算符用来取得指向标号的指针, 然后组成一个指针数组. 这样就可以用测试的值运算后得到的值直接进行索引来跳转.
扩展后的C语句与汇编的对应关系就非常容易看出来了.先会创造一个标号指针数组:
static void *jt[7] = {&&loc_A, &&loc_def, &&loc_B, &&loc_C, &&loc_D, &&loc_def, &&loc_D};
然后将测试条件进行一定的转换, 使其结果能够当做数组指针, 不满足这些条件则跳转至default对应的标号:
if (index > 6){
goto loc_def;
}
goto *jt[index]
每一个swtich语句的末尾的break对应的其实是一个goto done的语句. 当然也可以故意不写break或者将多种情况对应一个跳转地址.
跳转指定标号的指令 jmp *.L4(, %rsi, 8)的写法目前看上去有点奇怪, 要把%rsi乘以8, %rsi中保存着index的值. 看一下跳转表的结构:
//按照8的倍数进行分配地址
.L4:
.quad .L3
.quad .L8
.quad .L5
.quad .L6
.quad .L7
...
所以可以知道, index等于几, 就从L4的开头找几倍8的倍数的地址, 就相当于使用数组索引了. 其实就是再度跳转到对应的汇编代码位置向下执行.
练习题 3.30
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, 进入跳转表
然后按顺序往下看, 对应关系如下:
.L4
quad: .L9 -1
quad: .L5 0
quad: .L6 1
quad: .L7 2
quad: .L2 3 注意, L2为default, 所以不存在此情况
quad: .L7 4
quad: .L8 5
quad: .L2 6 注意, 无此标号, 因为L2对应default
quad: .L5 7
练习题 3.31
根据汇编代码补全C 函数:
void switcher(long a, long b, long c, long *dest)
a in %rdi, b in %rsi, c in %rdx, dest in %rcx
switcher:
cmpq $7, %rdi 比较x和7 , 可见 a 最小 为 0, 最大为7
ja .L2 如果超过,就转到L2也就是default.
jmp *.L4(, $rdi, 8) 进入跳转表
然后就要仔细观察跳转表和语句的结构:
首先看到对应索引 1, 3, 6的L2是default, 所以case 中不会有1, 3, 6 三个值, 只剩下 0,2,4,5,7.然后查看L7的代码发现没有jmp, 说明是fallthrough ,则L7对应的case 5
就是第一个case.
之后标号剩下 0,2,4,7, 可以看到2和7都跳到L5, 所以中间的连续两个case是 2 和 7.
现在只剩下0和4.仔细观察可以发现 索引4的时候直接跳到结束, 只有可能是最后一个Case E的情况, 而看L3对应的0, 还在继续处理C, 因此是CASE B的对应.
void swticher(long a, long b, long c, long *dest){
long val;
switch(a){
case 5:
c = b ^ 0xF;
case 0:
val = c + 112;
case 2:
case 7:
val = (b + c) << 2;
break;
case 4:
val = a;
break;
default:
val = b;
}
*dest = val;
}
感觉这题目不仅是考代码, 连逻辑推理也一并考了….
循环和Switch搞定了, 后边是通过栈来传递数据, 感觉又要掉头发了…..
