第4章 观察各种表达式的求值过程
4.1 算术运算和赋值
算术运算是指加法、减法、乘法、除法这四种数学运算,也称为四则运算。计算机中的四则运算和数学上的四则运算有些不同。本章将揭秘这些运算是如何在C++中完成的。
赋值运算类似于数学中的“等于”,是将一个内存空间中的数据传递到另一个内存空间中。由于内存没有处理器那样的控制能力,各个内存单元之间是无法直接传递数据的,必须通过处理器访问并中转,以实现两个内存单元间的数据传输。
在VC++6.0中,算术运算与其他传递计算结果的代码组合后才能被视为一条有效的语句,如赋值运算或函数的参数传递。单独的算术运算虽然可以编译通过,但是并不会生成代码。因为只进行计算而没有传递结果的运算不会对程序结果有任何影响,此时编译器将其视为无效语句,与空语句等价,不会有任何编译处理,如图4-1所示的代码便是一个很好的例子。
图 4-1 无效语句块
4.1.1 各种算术运算的工作形式
1.加法
加法运算对应的汇编指令为ADD。在执行加法运算时,针对不同的操作数,转换的指令也会不同,编译器会根据优化方式选择最佳的匹配方案。VC++6.0中常用的优化方案有如下两种:
O1方案,生成文件占用空间最小
O2方案,执行效率最快
在VC++6.0中,Release编译选项组的默认选项为O2选项—执行效率优先。在Debug编译选项组中,使用的是Od+ZI选项,此选项使编译器产生的一切代码都以便于调试为最根本的前提,甚至为了便于单步跟踪,以及源码和目标代码块的对应阅读,不惜增加冗余代码。当然也不是完全放弃优化,在不影响调试的前提下,尽可能地进行优化。
本章主要对比和分析Debug编译选项组与Release编译选项组这两个选项对各种计算产生的目标代码方案。在使用Debug编译选项组时,VC++产生的目标汇编代码会和源码是一一对应的。以加法运算为例,分别使用不同类型的操作数来查看在Debug编译选项组下编译后对应的汇编代码,如代码清单4-1所示。
代码清单4-1 使用不同类型的操作数来查看加法运算在Debug编译选项组下编译后的汇编代码
//C++源码说明:加法运算
//无效语句,不参与编译
15+20;
//变量定义
int nVarOne=0;
int nVarTwo=0;
//变量加常量的加法运算
nVarOne=nVarOne+1;
//两个常量相加的加法运算
nVarOne=1+2;
//两个变量相加的加法运算
nVarOne=nVarOne+nVarTwo;
printf("nVarOne=%d\r\n",nVarOne);
//C++源码与对应汇编代码讲解
//C++源码对比,变量赋值
int nVarOne=0;
//将立即数0,传入地址ebp-4中,即变量nVarOne所在的地址
00401028 mov dword ptr[ebp-4],0
//C++源码对比,变量赋值
int nVarTwo=0;
0040102F mov dword ptr[ebp-8],0
//C++源码对比,变量+常量
nVarOne=nVarOne+1;
;取出变量nVarOne数据放入eax中
00401036 mov eax, dword ptr[ebp-4]
;对eax执行加等于1运算
00401039 add eax,1
;将结果放回变量nVarOne中,完成加法运算
0040103C mov dword ptr[ebp-4],eax
//C++源码对比,常量+常量
nVarOne=1+2;
;这里编译器直接计算出了两个常量相加后的结果,放入变量nVarOne中
0040103F mov dword ptr[ebp-4],3
//C++源码对比,变量+变量
nVarOne=nVarOne+nVarTwo;
;使用ecx存放变量nVarOne
00401046 mov ecx, dword ptr[ebp-4]
;使用ecx对变量nVarTwo执行加等于操作
00401049 add ecx, dword ptr[ebp-8]
;将结果存入地址ebp-4处,即变量nVarOne
0040104C mov dword ptr[ebp-4],ecx
代码清单4-1展示了3种操作数的加法运算。在两常量相加的情况下,编译器在编译期间就计算出两常量相加后的结果,将这个结果值作为立即数参与运算,减少了程序在运行期的计算。当有变量参与加法运算时,会先取出内存中的数据,放入通用寄存器中,再通过加法指令来完成计算过程得到结果,最后存回到变量所占用的内存空间中。
开启O2选项后,编译出来的汇编代码将会有较大的变化。由于效率优先,编译器会将无用代码去除,并将可合并代码进行归并处理。例如,在代码清单4-1中,“nVarOne=nVarOne+1;”这样的代码将被删除,因为在其后又重新对变量nVarOne进行了赋值操作,而在此之前没有对变量nVarOne的任何访问,所以编译器判定此句代码是可被删除的。先看看图4-2中的代码,然后再来讨论此代码的其他优化方案。
图 4-2 开启O2选项的Release版加法运算
图4-2中唯一的加法运算是在做参数平衡,而非源码中的加法运算,这是怎么回事?别着急,保持耐心,先给大家介绍两个关于优化的概念。在编译过程中,编译器常常会采用“常量传播”和“常量折叠”这样的方案对代码中的变量与常量进行优化,下面将详细讲解这两种方案。
常量传播
将编译期间可计算出结果的变量转换成常量,这样就减少了变量的使用,请看下面的示例:
void main(){
int nVar=1;
printf("nVarOne=%d\r\n",nVar);
}
变量nVar是一个在编译期间可以计算出结果的变量。因此,在程序中所有引用到nVar的地方都会直接使用常量1来代替,于是代码等价于:
void main(){
printf("nVarOne=%d\r\n",1);
}
常量折叠
当计算公式中出现多个常量进行计算的情况时,且编译器可以在编译期间计算出结果时,这样源码中所有的常量计算都将被计算结果代替,如下面的代码所示:
void main(){
int nVar=1+5-3*6;
printf("nVarOne=%d\r\n",nVar);
}
此时不会生成计算指令,因为“1+5-3*6”的值是可以在编译过程中计算出来的,所以编译器首先会计算出“1+5-3*6”的结果:-12,然后将数值-12替换掉原表达式,其结果依然等价,如下面的代码所示:
void main(){
int nVar=-12;
printf("nVarOne=%d\r\n",nVar);
}
现在变量nVar为一个在编译期间可计算出结果的变量,那么接下来组合使用“常量传播”对其进行常量转换是很合理的,程序中将不会出现变量nVar,直接以常量-12代替,如下面代码所示:
void main(){
printf("nVarOne=%d\r\n",-12);
}
在代码清单4-1中,变量nVarOne和nVarTwo的初始化值是一个常量,VC++编译器在开启O2优化方案后,会尝试使用常量替换掉变量。如果在程序的逻辑中,声明的变量没有被修改过,而且上下文中不存在针对此变量的取地址和间接访问操作,那么这个变量也就等价于常量,编译器就认为可以删除掉这个变量,直接用常量代替。使用常量的好处是可以生成立即数寻址的目标代码,常量作为立即数成为指令的一部分,从而减少了内存的访问次数。(关于内存访问次数的概念,读者可以参考一些计算机组成原理类书籍,了解主频和外频的概念,考察对比处理器的频率和总线的频率。)前面的代码变换后如下所示(以下注释表示被优化剔除的代码):
int nVarOne=0;//常量化以后:int nVarOne=0;nVarOne用0代替了
int nVarTwo=0;//int nVarTwo=0;同上,这句也没有了
//变量加常量的加法运算
nVarOne=nVarOne+1;//nVarOne=0+1;
//两常量相加的加法运算
nVarOne=1+2;//nVarOne=1+2;
nVarOne=nVarOne+nVarTwo;//nVarOne=nVarOne+0;
printf("nVarOne=%d\r\n",nVarOne);
由于转换成了常量,因此在编译期间可以直接计算出结果,而“nVarOne=0+1;”这句赋值代码之后又对nVarOne再次赋值,所以这是一句对程序没有任何影响的代码,被剔除掉(注1)。后面的“nVarOne=1+2;”满足“常量折叠”的条件,所以直接计算出了加法结果3(注2),“nVarOne=1+2”由此转变为“nVarOne=3”,此时满足“常量传播”条件,对nVarOne的引用转变为对常量3的引用,printf的参数引用到nVarOne,于是代码直接成为“printf("nVarOne=%d\r\n",3);”(注3)。
nVarOne=0+1;//优化过程:nVarOne=0+1;删除了(注1)
nVarOne=1+2;//nVarOne=3;常量折叠(注2)
nVarOne=nVarOne+nVarTwo;//nVarOne=3+0;
printf("nVarOne=%d\r\n",nVarOne);//printf("nVarOne=%d\r\n",3);(注3)
进一步研究优化方案,修改代码清单4-1中的源码。将变量的初始值0修改为命令行参数的个数argc。由于argc在编译期间无法确定,所以编译器无法在编译过程中提前计算出结果,程序中的变量就不会被常量替换掉。源码修改后如下所示:
int main(int argc, char*argv[]){
int nVarOne=argc;//修改处
int nVarTwo=argc;//修改处
nVarOne=nVarOne+1;
nVarOne=1+2;
nVarOne=nVarOne+nVarTwo;
printf("nVarOne=%d\r\n",nVarOne);
return 0;
}
将代码再次编译为Release版,如图4-3所示。
图 4-3 另一种优化后的加法运算
与图4-2相比,图4-3中多了arg_0的定义使用。arg_0为IDA分析出的参数偏移,参数偏移的知识将在第6章讲解,这里只需知道[esp+arg_0]是在获取参数即可。
图4-3中只定义了一个参数变量偏移,而在源码中定义的两个局部变量却不见了。为什么呢?我们还是得考察优化过程:
int main(int argc, char*argv[]){
//int nVarOne=argc;在后面的代码中被常量代替
//int nVarTwo=argc;虽然不能用常量代替,但是由于之后没有对nVarTwo进行修改,所以引用
nVarTwo等价于引用argc, nVarTwo则被删除掉,这种方法称为"复写传播"
//nVarOne=nVarOne+1;其后即刻重新对nVarOne赋值,这句被删除了
//nVarOne=1+2;常量折叠,等价于nVarOne=3;
//nVarOne=nVarOne+nVarTwo;常量传播和复写传播,等价于nVarOne=3+argc;
//printf("nVarOne=%d\r\n",nVarOne);
//其后nVarOne没有被访问,可以用3+argc代替
printf("nVarOne=%d\r\n",3+argc);
return 0;
}
编译器在编译期间通过对源码的分析,判定第二个变量nVarTwo可省略,因为它都被赋值为第一个参数argc。在变量nVarOne被赋值为3后,就做了两个变量的加法nVarOne=nVarOne+nVarTwo,这等同于变量nVarOne=3+argc。其后printf引用nVarOne,也就等价于引用3+argc,因此nVarOne也可以被删除掉,于是有了图4-3中的代码。
2.减法
减法运算对应于汇编指令sub,虽然计算机只会做加法,但是可以通过补码转换将减法转变为加法形式来完成。先来复习一下将减法转变为加法的过程。
设有二进制数Y,其反码记为Y(反),假定其二进制长度为8位,有:
Y+Y(反)=1111 1111B
Y+Y(反)+1=0(进位丢失)
根据以上公式,推论之:
Y(反)+1=0-Y<==>Y(反)+1=-Y<==>Y(补)=-Y
这就是为什么负数的补码可以简化为取反加1的原因。
例如,5-2就可对照公式进行转换:
5+(0-2)<==>5+(2(反)+1)<==>5+2(补)
有了这个特性,所有的减法运算就都可以转换成加法运算了。
减法转换的示例如代码清单4-2所示。
代码清单4-2 减法运算示例—Debug版
//C++源码说明:减法运算
//变量定义
int nVarOne=argc;
int nVarTwo=0;
//获取变量nVarTwo的数据,使用scanf防止变量被常量化
scanf("%d",&nVarTwo);
//变量减常量的减法运算
nVarOne=nVarOne-100;
//减法与加法混合运算
nVarOne=nVarOne+5-nVarTwo;
printf("nVarOne=%d\r\n",nVarOne);
//C++源码与对应汇编代码讲解
;变量定义代码略
//C++源码对比,变量-常量
nVarOne=nVarOne-100;
;取变量nVarOne的数据到eax
00401125 mov eax, dword ptr[ebp-4]
;使用减法指令sub,对eax执行减等于100操作
00401128 sub eax,64h
;将结果赋值回nVarOne中
0040112B mov dword ptr[ebp-4],eax
//C++源码对比,减法与加法混合运算
nVarOne=nVarOne+5-nVarTwo;
;按照自左向右顺序依次执行
0040112E mov ecx, dword ptr[ebp-4]
00401131 add ecx,5
00401134 sub ecx, dword ptr[ebp-8]
00401137 mov dword ptr[ebp-4],ecx
;printf函数调用显示结果略
代码清单4-2中的减法运算没有使用加负数的表现形式。那么,在实际的分析中,根据加法操作数的情况,当加数为负数时,执行的并非加法而是减法操作。
在O2选项下,其优化策略和加法一致,故不多言。
3.乘法
乘法运算对应的汇编指令有有符号imul和无符号mul两种。由于乘法指令的执行周期较长,在编译过程中,编译器会先尝试将乘法转换成加法,或使用移位等周期较短的指令。当它们都不可转换时,才会使用乘法指令。具体示例如代码清单4-3所示。
代码清单4-3 各类型乘法转换—Debug版
//C++源码说明:乘法运算
//防止被视为无效代码,将每条运算作为printf参数使用
//printf函数的讲解略
//变量定义
int nVarOne=argc;
int nVarTwo=argc;
//变量乘常量(常量值为非2的幂)
printf("nVarOne*15=%d",nVarOne*15);
//变量乘常量(常量值为2的幂)
printf("nVarOne*16=%d",nVarOne*16);
//两常量相乘
printf("2*2=%d",2*2);
//混合运算
printf("nVarTwo*4+5=%d",nVarTwo*4+5);
//两变量相乘
printf("nVarOne*nVarTwo=%d",nVarOne*nVarTwo);
//C++源码与对应汇编代码讲解
//C++源码对比,变量*常量
printf("nVarOne*15=%d",nVarOne*15);
0040B8A4 mov edx, dword ptr[ebp-4]
;直接使用有符号乘法指令imul
0040B8A7 imul edx, edx,0Fh
;printf函数说明略
//C++源码对比,变量*常量(常量值为2的幂)
printf("nVarOne*16=%d",nVarOne*16);
0040B8B8 mov eax, dword ptr[ebp-4]
;使用左移运算代替乘法运算
0040B8BB shl eax,4
;printf函数说明略
//C++源码对比,常量*常量
printf("2*2=%d",2*2);
;在编译期间计算出2*2的结果,将表达式转换为常量值
0040B8CC push 4
0040B8CE push offset string"2*2=%d"(0041ffac)
0040B8D3 call printf(0040b750)
0040B8D8 add esp,8
//C++源码对比,变量*常量+常量(组合运算)
printf("nVarTwo*4+5=%d",nVarTwo*4+5);
0040B8DB mov ecx, dword ptr[ebp-8]
;利用lea指令完成组合运算
0040B8DE lea edx,[ecx*4+5]
;printf函数说明略
//C++源码对比,变量*变量
printf("nVarOne*nVarTwo=%d",nVarOne*nVarTwo);
0040B90A mov ecx, dword ptr[ebp-4]
;直接使用有符号乘法指令
0040B90D imul ecx, dword ptr[ebp-8]
;printf函数说明略
代码清单4-3为Debug版代码,使用编译选项为Od+ZI。在这种侧重调试的编译方式下,有符号数乘以常量值,且这个常量非2的幂,会直接使用有符号乘法imul指令。当常量值为2的幂时,编译器会采用执行周期短的左移运算来代替执行周期长的乘法指令。
由于任何十进制数都可以转换成二进制数来表示,在二进制数中乘以2就等同于所有位依次向左移动1位。如十进制数3的二进制数为0011,3乘以2后等于6,6转换成二进制数为0110。
当乘数和被乘数同时都是未知变量时,则无法套用优化方案。这时编译器不会优化处理,将直接使用乘法指令完成乘法计算。
在上例中,乘法运算与加法运算的结合编译器采用LEA指令来处理。在代码清单4-3中,lea语句的目的并不是取地址。当这种组合运算中的乘数不等于2、4、8时又该如何处理呢?来看看代码清单4-4中的代码。
代码清单4-4 乘数不等于2、4、8的组合运算
//C++源码对比,变量*常量+常量(乘数超过8)
printf("nVarTwo*9+5=%d",nVarTwo*9+5);
0040B8F3 mov eax, dword ptr[ebp-8]
0040B8F6 imul eax, eax,9
0040B8F9 add eax,5
0040B8FC push eax
0040B8FD push offset string"nVarTwo*9+5=%d"(0041ff7c)
0040B902 call printf(0040b750)
0040B907 add esp,8
由于在Debug版下侧重于调试而非优化,编译器会直接先拆分,然后再进行运算。这些运算在开启O2选项后的Release发布版中经过优化处理后又会被编译成另一种形式。从IDA中提取出的Release版的汇编代码如代码清单4-5所示。
代码清单4-5 各类型乘法转换示例—Release版
;IDA直接将参数作为局部变量使用
arg_0=dword ptr 4
;保存环境
push esi
;取出参数变量数据存入esi中
mov esi,[esp+4+arg_0]
;经过优化后,将nVarOne*15先转化为乘2加自身,可以记作乘以3
;eax=esi*2+esi=3*esi
lea eax,[esi+esi*2]
;将上一步操作结果乘4加自身,等同于乘15
;eax=eax*4+eax=5*eax=5*(3*esi)
lea eax,[eax+eax*4]
push eax
push offset aNvarone15D;"nVarOne*15=%d"
call_printf
;esi中的数据传送到ecx, esi中保存的为参数数据
mov ecx, esi
;将ecx中的数据左移4位,ecx乘以2的4次方
shl ecx,4
push ecx
push offset aNvarone15D;"nVarOne*16=%d"
call_printf
;两常量相乘直接转换常量值
push 4
push offset a22D;"2*2=%d"
call_printf
;这句代码等同于lea edx,[esi*4+5],都是混合运算
lea edx, ds:5[esi*4]
push edx
push offset aNvartwo45D;"nVarTwo*4+5=%d"
call_printf
;此处为乘数不等于2、4、8的情况,编译优化后将乘以9分解为
;(nVarTwo*1+nVarTwo*8),这样就又可以使用lea指令进行运算了
lea eax,[esi+esi*8+5]
push eax
push offset aNvartwo95D;"nVarTwo*9+5=%d"
call_printf
;此处为两个变量相乘,都是未知数,无优化
mov ecx, esi
imul ecx, esi
push ecx
push offset aNvaroneNvartwo;"nVarOne*nVarTwo=%d"
call_printf
add esp,30h
pop esi
在代码清单4-5中,除了两个未知变量的相乘无法优化外,其他形式的乘法运算都可以优化处理。如果运算表达式中有一个常量值,则此时编译器会首先匹配各类优化方案,最后对不符合优化方案的运算进行调整。
通过示例演示,我们前面学习了有符号乘法的各种转换模式以及优化方法,无符号乘法的原理与之相同,读者可以举一反三,自己动手调试,总结经验。
4.除法[1]
(1)除法计算约定
除法运算对应的汇编指令分有符号idiv和无符号div两种。除法指令的执行周期较长,效率也较低,所以编译器想尽办法用其他运算指令代替除法指令。C++中的除法和数学中的除法不同。在C++中,除法运算不保留余数,有专门求取余数的运算(运算符为%),也称之为取模运算。对于整数除法,C++的规则是仅仅保留整数部分,小数部分完全舍弃。
我们先讨论一下除法计算的相关约定。以下讨论的除法是“计算机整数除法”,我们使用C语言中的a/b表示除法关系。在C语言中,两个无符号整数相除,结果依然是无符号的;两个有符号整数相除,结果则是有符号的;如果有符号数和无符号数混除,其结果则是无符号的,有符号数的最高位(符号位)被作为数据位对待,然后作为无符号数参与计算。
对于除法而言,计算机面临着如何处理小数部分的问题。在数学意义上,7/2=3.5,而对于计算机而言,整数除法的结果必须为整数。对于3.5这样的数值,计算机取整数部分的方式有如下几种。
向下取整
根据整数值的取值范围,可以画出以下坐标轴:
所谓对x向下取整,就是取得往-∞方向最接近x的整数值,换而言之也就是取得不大于x的最大整数。
例如,+3.5向下取整得到3;-3.5向下取整得到-4。
在数学描述中,x表示对x向下取整。
在标准C语言的math.h中,定义了floor函数,其作用就是向下取整,也有人称之为“地板取整”。
向下取整的除法,当除数为2的幂时,可以直接用带符号右移指令(sar)来完成。
但是,向下取整存在一个问题:
向上取整
所谓对x向上取整,就是取得往+∞方向最接近x的整数值,换而言之也就是取得不小于x的最小整数。
例如,+3.5向上取整得到4;-3.5向上取整得到-3。
在我们的数学描述中,表示对x向上取整。
在标准C语言的math.h中有定义ceil函数,其作用就是向上取整,也有人称之为“天花板取整”。
向上取整也存在一个问题:
向零取整
所谓对x向零取整,就是取得往0方向最接近x的整数值,换而言之也就是放弃小数部分。
举例说明,+3.5向零取整得到3;-3.5向零取整得到-3。
在我们的数学描述中,[]x表示对x向零取整。
59向零取整的除法满足:
在C语言和其他多数高级语言中,对整数除法规定为向零取整。也有人称这种取整方法为“截断除法”(Truncate)。
(2)除法相关的数学定义和性质
大家先来做道题,阅读下面的C语言代码并写出结果:
//代码1
printf("8%%-3=%d\r\n",8%-3);
//代码2
printf("-8%%-3=%d\r\n",-8%-3);
//代码3
printf("-8%%3=%d\r\n",-8%3);
如果你的答案是:
8%-3=2
-8%-3=-2
-8%3=-2
恭喜你,你答对了,你可以跳过本节继续阅读后面的内容。
如果你得出的答案是错误的,而且不明白为什么错了,那么请和我一起回顾以下数学知识。
定义1:已知两个因数的积与其中一个因数,求另一个因数的运算,叫做除法。
定义2:在整数除法中,只有能整除与不能整除两种情况。当不能整除时,就产生余数。设被除数为a,除数为b,商为q,余数为r,有如下一些重要性质:
性质1:|r|<|b|
性质2:a=b*q+r
性质3:b=(a-r)/q
性质4:q=(a-r)/b
性质5:r=a-q*b
C语言规定整数除法向零取整,那么将前面的“代码1”代入定义和运算性质得:
q=(a-r)/b=(8-r)/(-3)=-2
r=a-q*b=8-(-2*-3)=2
将前面的“代码2”代入定义和运算性质得:
q=(a-r)/b=(-8-r)/(-3)=2
r=a-q*b=-8-(2*-3)=-2
将前面的“代码3”代入定义和运算性质得:
q=(a-r)/b=(-8-r)/3=-2
r=a-q*b=-8-(-2*3)=-2
现在是不是明白自己错在哪里了?
(3)相关定理和推导
对于下面的数学定义和推导,如果你已经掌握或者暂无兴趣,可跳过本节阅读后面的内容。后面内容中涉及的定义和推导将会以编号形式指出,感兴趣的读者可以回到本节考察相关推论和证明。如果实在对数学论证没有兴趣也没关系,重点掌握论证结束后粗体标注的分析要点即可。
定理1 若x为实数,有:
进而可推导:
当x不为整数时:
定理2 若x为整数,则:
定理3 由于上下取整相对于0点是对称的,所以:
进而可推导:
定理4 若x为实数,n为整数,有:
结合(定理1),可推导:(推导5)
推导6 有整数a, b和实数x, a≠b且b≠0,有:
证明:设q为a/b的商,r为余数(0<=|r|<|b|,且q, r均为整数)
推导7 设有a、b两整数,
当b>0时,有:
当b<0时,有:
证明1:设q为a/b的商,r为余数,
根据(定理4),有:
因b>0,|r|<b,有:
证明2:设q为a/b的商,r为余数,
根据(定理4),有:
因b<0,|r|<|b|,有:
因此得:
(4)VC++6.0对整数除法的优化和论证
VC++6.0对除数为整型常量的除法的处理
如果除数是变量,则只能使用除法指令。如果除数为常量,就有了优化的余地。根据除数值的相关特性,编译器有对应的处理方式。
下面将讨论编译器对除数为2的幂、非2的幂、负数等各类情况的处理方式。假定整型为4字节补码的形式,下面来看代码清单4-6中的示例演示。
代码清单4-6 各类型除法转换—Debug版
//C++源码说明:除法运算
//变量定义
int nVarOne=argc;
int nVarTwo=argc;
//两个变量做除法
printf("nVarOne/nVarTwo=%d",nVarOne/nVarTwo);
//变量除以常量,常量2的1次方
printf("nVarOne/2=%d",nVarOne/2);
//变量除以非2的幂
printf("nVarTwo/7=%d",nVarTwo/7);
//变量对非2的幂取模
printf("nVarTwo%7=%d",nVarTwo%7);
//变量除以常量,常量为2的3次方
printf("nVarOne/8=%d",nVarOne/8);
//C++源码与对应汇编代码讲解
//C++源码对比,变量定义
int nVarOne=argc;
0040B7E8 mov eax, dword ptr[ebp+8]
0040B7EB mov dword ptr[ebp-4],eax
//C++源码对比,变量定义
37:int nVarTwo=argc;
0040B7EE mov ecx, dword ptr[ebp+8]
0040B7F1 mov dword ptr[ebp-8],ecx
//除法运算转换特性
//C++源码对比,变量/变量
printf("nVarOne/nVarTwo=%d",nVarOne/nVarTwo);
;取出被除数放入eax中
0040B7F4 mov eax, dword ptr[ebp-4]
;扩展高位
0040B7F7 cdq
;两变量相除,直接使用有符号除法指令idiv
0040B7F8 idiv eax, dword ptr[ebp-8]
;eax保存商值,作为参数压栈,调用函数printf,此函数讲解略
0040B7FB push eax
0040B7FC push offset string"nVarOne/nVarTwo=%d"(00420034)
0040B801 call printf(0040b750)
0040B806 add esp,8
//C++源码对比,变量/常量(常量值为2的1次方)
printf("nVarOne/2=%d",nVarOne/2);
0040B809 mov eax, dword ptr[ebp-4]
0040B80C cdq
;自身减去扩展高位
0040B80D sub eax, edx
;和乘法运算类似,乘法是左移,对应的除法为右移
0040B80F sar eax,1
;printf函数说明略
//C++源码对比,变量/常量(非2的幂)
printf("nVarTwo/7=%d",nVarTwo/7);
0040B81F mov eax, dword ptr[ebp-8]
0040B822 cdq
0040B823 mov ecx,7
;无优化直接使用有符号除法指令idiv
0040B828 idiv eax, ecx
;printf函数说明略
//C++源码对比,变量%常量
printf("nVarTwo%7=%d",nVarTwo%7);
0040B838 mov eax, dword ptr[ebp-8]
0040B83B cdq
0040B83C mov ecx,7
;无优化,直接使用有符号指令idiv
0040B841 idiv eax, ecx
;除法指令过后,余数保存在扩展位edx中
0040B843 push edx
;printf函数说明略
//C++源码对比,变量/常量(常量值为2的3次方)
printf("nVarOne/8=%d",nVarOne/8);
;取出被除数放入eax
0040B851 mov eax, dword ptr[ebp-4]
;扩展eax高位到edx, eax中为负数,则edx为0xFFFFFFFF
0040B854 cdq
;如果eax为负数,则0xFFFFFFFF&0x00000007<==>0x00000007,反之为0
0040B855 and edx,7
;使用eax加edx,若eax为负数则加7,反之加0
0040B858 add eax, edx
;将eax右移3位
0040B85A sar eax,3
;printf函数说明略
代码清单4-6只对除数为2的幂的情况进行了优化处理。下面先对较简单的除数为常量2的优化开始分析。
除数为2的幂
在C语言中,有符号除法的除法规则是向0取整,对有符号数做右移运算,编译后使用的指令为sar,相当于向下取整。
举例说明一下,比如x为4,等价于4 1,结果为2;但是x为5呢?将
处理为5 1,结果还是2。
当x<0,有:
根据(推导7)可得:
明白上面的理论知识后,我们来看看以下的实际运用:
0040B809 mov
eax, dword ptr[ebp-4]
0040B80C cdq
0040B80D sub
eax, edx
0040B80F sar
eax,1
;printf函数说明略
代码清单4-6中0040B80C的cdq是符号扩展到高位edx,如果eax的最高位(符号位)为1,那么edx的值为0xFFFFFFFF,也就是-1,否则为0。0040B80D地址处的sub eax, edx指令执行的操作是将eax减去高位edx,实际上就是被除数为负数的情况下,由于除数为正数(+2的幂),故除法的商为负数。移位运算等价于向下取整,C语言的除法是向零取整,因此需要对商为负的情况做加1调整(见推导7),减去-1等同于加1。eax不为负则减0,等于没处理。最后sar右移完成除法。这样的设计可以避免分支结构的产生。
//C++源码对比,变量/常量(常量值为2的3次方)
printf("nVarOne/8=%d",nVarOne/8);
;取出被除数放入eax
0040B851 mov eax, dword ptr[ebp-4]
;扩展eax高位到edx,若eax为负数,则edx为0xFFFFFFFF
0040B854 cdq
;若eax为负数,则0xFFFFFFFF&0x00000007<==>0x00000007,反之为0
0040B855 and edx,7
;使用eax加edx,如eax为负数则加7,反之加0
0040B858 add eax, edx
;将eax右移3位
0040B85A sar eax,3
;printf函数说明略
代码清单4-6中0040B854的cdq是符号扩展到高位edx,如果eax的最高位(符号位)为1,就是说被除数eax里面保留了负数值,那么edx的值为0xFFFFFFFF,也就是-1,否则为0。在以上代码中,0040B855处对edx做位与运算,当被除数为负数时,edx的值为7,否则为0。在0040B858处的add eax, edx就是被除数为负数时加上2n-1,不为负则加0,等于没处理。最后sar右移完成除法。
除数为非2的幂
Release版中还对除数不为2的幂的情况做了优化(如代码清单4-7所示),其他地方与代码清单4-6相比变化不大。
代码清单4-7 各类型除法转换—Release版
;IDA中的参数标识,经过优化后,省去了局部变量,直接使用参数
arg_0=dword ptr 4
;变量/变量和Debug版相同,此处省略
;……
;变量/常量(常量值为2的幂)和Debug版相同,此处省略
;……
;变量/常量(常量值为非2的幂),这里的汇编代码和Debug版的汇编代码差别很大
;将数值92492493h放入eax中
mov eax,92492493h
;有符号乘法,用esi乘以eax, esi中保存被除数
imul esi
;edx为扩展的高位,可参考代码清单4-6
add edx, esi
;右移2位
sar edx,2
;结果放回eax
mov eax, edx
;将eax右移31次
shr eax,1Fh
;加以右移结果,放入edx中
add edx, eax
push edx
push offset aNvartwo7D;"nVarTwo/7=%d"
call_printf
;其余代码和Debug版类似,此处省略
;……
如代码清单4-7所示,除法的情况处理起来很复杂。在代码起始处出现了一个超大数值:0x92492493。这个数值是从哪里来的呢?由于除法指令的周期比乘法指令周期长很多,因此编译器会用周期较短的乘法和其他指令代替除法。我们先看看数学证明。
设x为被除数变量,o为某一常量,则有:
由于o为常量,且2n的取值由编译器选择,所以的值在编译期间可以计算出来。在VC++中,n的取值都大于等于32,这样就可以直接调整使用乘法结果的高位。
这样,也就是一个编译期间先行计算出来的常量值了,这个值常被称为Magic Number (魔数、幻数)。我们先用c来代替
这个Magic常量,于是又有:
好了,搞明白了这个较为粗糙的数学证明,现在我们可以来看一个实际的例子。先来个简单的,让大家热身一下。请阅读代码清单4-8,最好能够先根据公式反推出高级代码,然后再根据后面的讨论进行印证。
代码清单4-8 小练习1:请将以下汇编代码还原为高级代码
.text:00401000_main proc near;CODE XREF:start+AF p
.text:00401000 arg_0=dword ptr 4
.text:00401000 mov ecx,[esp+arg_0]
.text:00401004 mov eax,38E38E39h
.text:00401009 imul ecx;eax乘以参数
.text:0040100B sar edx,1;有符号移位
.text:0040100D mov eax, edx
.text:0040100F shr eax,1Fh;这里是无符号移位
.text:00401012 add edx, eax
.text:00401014 push edx
.text:00401015 push offset Format;"%d"
.text:0040101A call_printf
.text:0040101F add esp,8
.text:00401022 retn
.text:00401022_main endp
在地址.text:00401004处,我们看到了mov eax,38E38E39h,此后做了乘法和移位操作,最后直接使用edx显示。在乘法指令中,由于edx存放乘积数据的高4字节,因此直接使用edx就等价于乘积右移了32位,再算上.text:0040100B sar edx,1,那就一共移动了33位。在地址.text:0040100D处,eax得到了edx的值,然后对eax右移了1Fh位,对应10进制也就是右移了31位,然后有个很奇怪的加法。其实这里移位的目的是得到有符号数的符号位,如果结果是正数,add edx, eax就是加0,等于什么都没干;如果结果是负数,由于其后面的代码直接使用edx作为计算结果,需要对除法的商调整加1。简单证明如下:
设x、o皆为整数,o为正数,当x≥0时,有:
当x<0时,根据(推导3):
反推过程:
解方程得:(注:此处的约等于将在后面讨论除法优化原则时详细解释)
于是,我们反推出优化前的高级代码为:
printf("%d",argc/9);
总结:
mov eax, MagicNumber
imul……
sar edx,……
mov reg, edx
shr reg,1Fh
add edx, reg
;此后直接使用edx的值,eax弃而不用
当遇到以上指令序列时,基本可判定是除法优化后的代码,其除法原型为a除以常量o, imul可表明是有符号计算,其操作数是优化前的被除数a。接下来统计右移的总次数以确定公式中的n值,然后使用公式将MagicNumber作为c值代入公式求解常量除数o的近似值,四舍五入取整后,即可恢复除法原型。
如果大家理解了上面讨论的问题,那么接下来看一个深入一点的例子,如代码清单4-9所示。
代码清单4-9 小练习2:请将以下汇编代码还原为高级代码
.text:00401080_main proc near;CODE xREF:start+AF p
.text:00401080 arg_0=dword ptr 4
.text:00401080 mov ecx,[esp+arg_0]
.text:00401084 mov eax,24924925h
.text:00401089 mul ecx
.text:0040108B sub ecx, edx
.text:0040108D shr ecx,1
.text:0040108F add ecx, edx
.text:00401091 shr ecx,2;是不是觉得以上代码很诡异
.text:00401094 push ecx
.text:00401095 push offset Format
.text:0040109A call_printf
.text:0040109F add esp,8
.text:004010A2 xor eax, eax
.text:004010A4 retn
.text:004010A4_main endp
遇到这样的代码不要不知所措,我们可以一步步来论证。先看看这段代码都做了些什么:在地址.text:00401084处,疑似为,看后面的代码,不符合上个例子得出的结论,所以不能使用上例中推导公式。接着一边看后面的指令,一边先写出等价于上述步骤的数学表达式。
设c为常量24924925h,以上代码等价于:
.text:0040108B处的sub ecx, edx直接减去了乘法结果的高32位,数学表达式等价于
此后的shr ecx,1相当于除以2:
此后的add ecx, edx再次加上乘法结果的高32位:
此后的shr ecx,2等价于把加法的结果再次除以4
最后直接使用ecx,乘法结果低32位eax弃而不用。
先简化表达式:
进而推导:
没错,这里的高级代码本来就是执行除法。
数数一共移动了几次,ecx一共右移了3位,而且直接与edx运算并作为结果使用,因此还得加上乘法的低32位,共计3 5位,故n的取值为3。已知c值为常量24924925h,根据上述推导,可得:
解方程求得:
于是,我们反推出优化前的高级代码为:
printf("nVarTwo/7=%d\r\n",argc/7);
在计算得出MagicNumber后,如果其值超出4字节整数的表达范围,编译器会对其进行调整。如上例中的argc/7,在计算MagicNumber时,编译器选择,其结果超出了4字节整数的表达范围,所以编译器调整MagicNumber的取值为
,导致整个除法的推导也随之调整。
综合上述证明,可推导出除法等价优化公式如下:
总结:
mov eax, MagicNumber
;这里的reg表示通用寄存器,上例中为ecx,实际分析中还可能是其他寄存器
mul reg
sub reg, edx
shr reg,1
add reg, edx
shr reg, A;这句或许没有,如果没有,则n值为1,否则这里的A就是n-1的值
;此后直接使用reg的值,eax弃而不用
如果遇到以上指令序列,基本可判定是除法优化后的代码,其除法原型为a除以常量o, mul可表明是无符号计算,其操作数是优化前的被除数a,接下来统计右移的总次数以确定公式中的n值,然后使用公式将MagicNumber作为c值代入公式求解常量除数o,即可恢复除法原型。
现在我们可以把难度再提高一点点了,回顾代码清单4-6中的关键部分:
……
;92492493h 疑似
.text:004010AA mov eax,92492493h
;这里是流水线优化,esp和上次调用的call指令相关,和除法计算无关,可暂不理会
;关于流水线优化详见4.4.1小节
.text:004010AF add esp,8
;有符号乘法,用esi乘以eax, esi中保存被除数
.text:004010B2 imul esi
;这里又多出一个诡异的加法
.text:004010B4 add edx, esi
;右移2位,也可看做除4
.text:004010B6 sar edx,2
;结果给eax
.text:004010B9 mov eax, edx
;负数调整加1
.text:004010BB shr eax,1Fh
.text:004010BE add edx, eax
.text:004010C0 push edx
.text:004010C1 push offset aNvartwo7D;"nVarTwo/7=%d"
.text:004010C6 call_printf
……
虽然这个例子中的源码我们都已经了解,但是在.text:004010B4处的加法显得很奇怪,其实这里的代码是上面介绍的除法转乘法公式的变化。在.text:004010B2处的指令是imul esi,这是个有符号数的乘法。请注意,编译器在计算MagicNumber时是作为无符号处理的,而代入除法转换乘法的代码中又是作为有符号乘数处理的。因为有符号数的最高位不是数值,而是符号位,所以,对应的有符号乘法指令是不会让最高位参与数值计算的,这会导致乘数的数学意义和MagicNumber不一致。
于是,在有符号乘法中,如果的取值大于0x80000000(最高位为1,补码形式为负数),实际参与乘法计算的是个负数,其值应等价于
,证明如下:
设有符号整数x、无符号整数y, y≥0x80000000,我们定义y的有符号补码值为y(补),y的无符号值表示为y(无)。如当y=0xffffffff, y(补)的真值=-1,y(无)=232-1。
对x、y进行有符号乘法,根据求补计算规则可推出y(补)=232-y(无),因y≥0x80000000,所以y(补)表达为负数,其真值为-(232-y(无)),简化得到:
y(补)的真值=-(232-y(无))=y(无)-232
例如:neg(5)=0xfffffffb
neg(5)的真值=-5=-(232-0xfffffffb)=0xfffffffb-232
代入有符号乘法:
x*y(补)=x*(y(无)-232)
由此可得,对于有符号整数x、无符号整数y, y>=0x80000000,当对x、y进行有符号乘法计算时,其结果等于x*(y(无)-232),若期望的乘法结果为x*y(无),则需要调整为:
x*y(无)=x*(y(无)-232)+232*x=x*y(补)+232*x
前面例题中的在计算机补码中表示为负数,根据以上推导,
等价于
,故其除法等价优化公式也相应调整为:
完全理解以上证明后,就可以回过头来分析代码清单4-6并将其还原为高级代码了。
先看.text:004010B2处的代码:
;……
.text:004010B2 imul esi
.text:004010B4 add edx, esi
.text:004010B6 sar edx,2
;负数调整略
这里先乘后加,但是参与加法的是edx,由于edx保留了乘法计算的高32位,因此这里的edx等价于,然后加上被除数esi,对edx右移两位,负数调整后直接使用edx中的值了,舍弃了低32位,相当于一共右移了34位,于是可推导出原来的除数。
将以上代码转换为公式:
上式等价于,o为某常量,eax为MagicNumber, esi为被除数。
解方程得:
于是,我们反推出优化前的高级代码为:
printf("%d",argc/7);
注意,这里的argc是有符号整型,因为指令中使用的是imul有符号乘法指令。
总结:
mov eax, MagicNumber(大于7fffffffh)
imul reg
add edx, reg
sar edx,……
mov reg, edx
shr reg,1Fh
add edx, reg
;此后直接使用edx的值
当遇到以上指令序列时,基本可判定是除法优化后的代码,其除法原型为a除以常量o, imul表明是有符号计算,其操作数是优化前的被除数a,接下来统计右移的总次数以确定公式中的n值,然后使用公式,将MagicNumber作为c值代入公式求解常量除数o,即可恢复除法原型。
除数为负的2的幂
.text:00401000_main proc near;CODE XREF:start+AF
.text:00401000
.text:00401000 arg_0=dword ptr 4
.text:00401000
.text:00401000 mov eax,[esp+arg_0]
.text:00401004 cdq
.text:00401005 and edx,7
.text:00401008 add eax, edx
.text:0040100A sar eax,3
.text:0040100D neg eax
.text:0040100F push eax
.text:00401010 push offset Format;"%d"
.text:00401015 call_printf
.text:0040101A add esp,8
.text:0040101D retn
.text:0040101D_main endp
有了前面的基础,现在应该能理解上面的代码了,在0040100A地址处的有符号右移指令存在的原因和前面讨论的道理一致,其后的neg相当于取负。对于除数为负的情况,neg的出现很合理。可能存在的问题在从00401004地址处开始的三行中(粗体表示),cdq将被除数扩展到edx,然后edx与7进行位与操作,最后将结果与被除数相加。相关证明可参考以上除数为正的2的幂的讨论,这里不再赘述。
除数为负的非2的幂(上)
.text:00401000_main proc near;CODE XREF:start+AF
.text:00401000 arg_0=dword ptr 4
.text:00401000 mov ecx,[esp+arg_0]
.text:00401004 mov eax,99999999h
.text:00401009 imul ecx
.text:0040100B sar edx,1
.text:0040100D mov eax, edx
.text:0040100F shr eax,1Fh
.text:00401012 add edx, eax
.text:00401014 push edx
.text:00401015 push offset Format;"%d\n"
.text:0040101A call_printf
.text:0040101F add esp,8
.text:00401022 xor eax, eax
.text:00401024 retn
.text:00401024_main endp
除数为负的求值过程,有什么需要注意的呢?我们先看看除法转乘法的过程:
当o为正数时,设,有:
当o为负数时,有:
现在我们来看看这次编译器产生的代码,eax是MagicNumber, ecx为被除数,代码体现以下表达式:
在讨论的过程中,我们来谈谈分析编译器行为的一个好办法。其实很简单,先写出高级语言,然后看对应的汇编代码,再接着论证其数学模型,最后就可以归纳出还原的办法和依据。在这个例子中,我们出于研究目的,分析自己写的代码,所以对应的运算是已知的:
eax保存了MagicNumber值,据上式可得:
接下来,我们求解|o|:
在分析过程中,以上代码很容易与除数为正的情况相混淆,我们先看看这两者之间的重要差异。关键点在于上述代码中粗体标记的00401004处。在前面讨论的除以7的例子中,我们讲过,当MagicNumber最高位为1时,对于正除数,编译器会在imul和sar之间产生调整作用的add指令,而本例没有,结合上下流程可分析MagicNumber为补码形式,除数为负。这点应作为区分负除数的重要依据。
于是,我们反推出优化前的高级代码为:
printf("%d",argc/-5);
总结:
mov eax, MagicNumber(大于7fffffffh)
imul reg
sar edx,……
mov reg, edx
shr reg,1Fh
add edx, reg
;此后直接使用edx的值
如果遇到以上指令序列,则基本可判定是除法优化后的代码,其除法原型为a除以常量o, imul可表明是有符号计算,其操作数是优化前的被除数a,接下来统计右移的总次数以确定公式中的n值,然后使用公式,将MagicNumber作为c值代入公式求解常量除数o,即可恢复除法原型。
除数为负的非2的幂(下)
上例中我们讨论了MagicNumber大于0x7fffffff的处理方式,接下来讨论在什么情况下MagicNumber会小于等于0x7fffffff,这时候应该怎么处理,请先阅读以下代码:
.text:00401000_main proc near;CODE XREF:start+AF
.text:00401000 arg_0=dword ptr 4
.text:00401000 mov ecx,[esp+arg_0]
.text:00401004 mov eax,6DB6DB6Dh
.text:00401009 imul ecx
.text:0040100B sub edx, ecx
.text:0040100D sar edx,2
.text:00401010 mov eax, edx
.text:00401012 shr eax,1Fh
.text:00401015 add edx, eax
.text:00401017 push edx
.text:00401018 push offset Format;"%d"
.text:0040101D call_printf
.text:00401022 add esp,8
.text:00401025 retn
.text:00401025_main endp
回忆前面除数等于+7的讨论,对于正除数,MagicNumber大于0x7fffffff的处理:
当除数o为负数时,我们直接对上式MagicNumber取负即可,设MagicNumber为c:
对应调整除法转换公式:
明白以上推导,可先将以上代码转换为公式:
据上式可得:
接下来,我们求解o:
于是,我们反推出优化前的高级代码为:
printf("%d",argc/-7);
总结:
mov eax, MagicNumber(小于等于7fffffffh)
imul reg
sub edx, reg
sar edx,……
mov reg, edx
shr reg,1Fh
add edx, reg
;此后直接使用edx的值
当遇到以上指令序列时,基本可判定是除法优化后的代码,其除法原型为a除以常量o, imul可表明是有符号计算,其操作数是优化前的被除数a,由于MagicNumber取值小于等于7fffffffh,而imul和sar之间有sub指令来调整乘积,故可认定除数为负,且MagicNumber为补码形式。接下来统计右移的总次数以确定公式中的n值,然后使用公式将MagicNumber作为c值代入公式求解常量除数|o|,即可恢复除法原型。
除法优化的原则
看到这里,大家应该注意到,在以上的讨论中,还原所得的除数是近似值,说明给出的公式还不够严格。我们接下来好好思考一下还原的除数近似但不等的原因,先看看余数是多少。
回忆一下除法和余数的关系,根据(性质3),有:
b=(a-r)/q
以除以9为例:
解方程求:
r=38E38E39h*9-233=200000001h-200000000h=1
于是找到不等于的原因:
是存在错误的,MagicNumber是整数值,而
是实数值。
于是修改推导公式为:
结果现在又出现了“新问题”,在反汇编代码流程中,还原的公式为:
38E38E39h是的值,代入得到:
—看起来是前功尽弃。
现在我们来解决这个疑问,当x≥0时,根据C语言除法向0取整规则,有:
证明:
在编译器计算MagicNumber时,如果给出一个合适的n值,使下式成立:
则根据(推导6)可得:
举例说明一下,以前面讨论的arg_0/9为例,设arg_0/9商为q:
当arg_0≥0时,有:
当x<0时,有:
证明:
根据(推导3):
根据(推导7):
在编译器计算MagicNumber时,如果给出一个合适的n值,使下式成立:
则根据(推导6)可得:
举例说明一下,以前面讨论的arg_0/9为例,设arg_0/9商为q:
当arg_0<0时,有:
根据(推导7):
显然,根据(推导6)可以得到:
由以上讨论可以看出,关键点在于,编译器计算MagicNumber的值,使运算结果满足(推导6)中的等式,其中计算确定MagicNumber表达式中2n的取值尤为重要。读者可以自行尝试分析其他案例。
笔者曾经分析过VC++6.0中计算MagicNumber的过程,现在将分析的要点和还原的代码提供出来,供有兴趣的读者研究。找到VC++6.0安装目录下的\VC98\Bin文件夹中的c2.dll(版本12.0.9782.0),先用OD载入这个目录下的CL.EXE,加入命令行后开始调试(如cl/c/O2 test.cpp),然后在LoadLibrary这个函数下断点,等待c2文件加载,其有符号整数除法MagicNumber的计算过程在c2的文件偏移OX5FACE处。加载后的虚拟地址请自行计算(参考PE格式相关资料),断点设置在此处可以看到有符号整数除法MagicNumber的推算过程,其汇编代码过长,读者可以自己使用IDA查看,本书不再列出,笔者直接提供使用hexray插件后修改的C代码见随书文件中的SignedDivision.cpp。
理解了整数除法后,我们顺便也谈谈取模。
在VC++6.0中,对两个变量取模或者对非2的幂取模,可直接使用div或idiv指令完成,余数在dx或者是edx中。对2的k次方取余,余数的值只需取得被除数二进制数值中的最后k位的值即可,负数则还需在k位之前补1,设k为5,可以得到以下代码:
mov reg,被除数
and reg,8000001Fh
jns LAB1
or reg,0FFFFFFE0h
LAB1:
如果余数的值非0,以上代码是没有问题的;如果余数的值为0,则根据以上代码计算出的结果(FFFFFFE0h)是错误的。因此应该加以调整,调整的方法为在or运算之前减1,在or运算之后加1。对于余数不为0的情况,此调整不影响计算结果;对于余数为0的情况,末尾k位全部为0值,此时减1得到末尾k位为1,or运算得到-1,最后加1得到余数值为0。调整后的代码如下:
mov reg,被除数
and reg,8000001F;这里的立即数是去掉高位保留低位的掩码,其值由2k决定
jns LAB1
dec reg
or reg, FFFFFFE0
inc reg
LAB1:
当遇到以上指令序列时,基本可判定是取模代码,其取模原型为被除数(变量)对2k(常量)执行取模运算,jns可表明是有符号计算,考察“and reg,8000001F”这类去掉高位保留低位的代码,统计出一共保留了多少低位,即可得到k的值,代入求得2k的值后,可恢复取模代码原型。
最后强调一点,对于x%2k这样的运算,有的编译器会利用性质5得到以下代码(x%25):
;先求x/25的商
mov eax,被除数
cdq
and edx,1F
add eax, edx
sar eax,5;这时eax已经得到了商
;余数=被除数-商*25
shl eax,5
sub被除数,eax;此时可以得到余数
通过以上方法可以实现无分支取模。
关于负数取模问题,下面来论证一下。
r=a%b(b<0),根据性质5:r=a-q*b,当r为非0值,可得r的符号和a相同,可以推导:当a>0,b<0时,r=a%b=a%|b|;当a<0,b<0时,r=a%b=-(|a|%|b|)。取绝对值的C语言程序对应的代码如下所示:
int main(int argc, char*argv[])
{
printf("%d\r\n",abs(argc));
return 0;
}
对应的反汇编代码如下所示:
.text:00401000_main proc near
.text:00401000
.text:00401000 arg_0=dword ptr 4
.text:00401000
.text:00401000 mov eax,[esp+arg_0]
.text:00401004 cdq
.text:00401005 xor eax, edx
.text:00401007 sub eax, edx;无分支求eax的绝对值
.text:00401009 push eax
.text:0040100A push offset aD;"%d\r\n"
.text:0040100F call sub_401020
.text:00401014 add esp,8
.text:00401017 xor eax, eax
.text:00401019 retn
.text:00401019_main endp
上面是一个无分支求绝对值的例子。在上例中,eax得到arg_0的值,然后cdq的高位扩展到edx,当eax≥0时,edx的值为0;否则edx为0xFFFFFFFF,也就是-1。接着执行xor eax, edx,对于异或运算,与0异或时,其值不变;与1异或时,相当于求反。因此,这里代码的含义是:当eax≥0时,edx为0,异或后其值不变;否则edx为0xFFFFFFFF,异或后等价于取反。最后执行sub eax, edx,也就是说,当eax≥0时,edx为0,“sub eax, edx”的结果相当于eax减去0,其值不变;否则edx为-1,“sub eax, edx”相当于eax自加1,结合前面的求反也就等价于求补。综上所述,当eax≥0时,其值不变,否则eax求补,相当于求绝对值。
请读者按以上推导,自己研究对-2k取模的实现原理。
[1]本节参考资料:1.《Concrete Mathematics》(Ronald L.Graham著)。2.《The Art of Computer Programming》(Donald E.Knuth著)。