VC6 Release下的除法优化技术(1)

Snow

源代码:
#include <stdio.h>

void main(int argc)
{
        printf("%d\n",argc/9);        
}

汇编代码:
00401000    8B4C24 04       mov ecx,dword ptr ss:[esp+4]
00401004    B8 398EE338     mov eax,38E38E39
00401009    F7E9            imul ecx
0040100B    D1FA            sar edx,1
0040100D    8BC2            mov eax,edx
0040100F    C1E8 1F         shr eax,1F
00401012    03D0            add edx,eax
00401014    52              push edx
00401015    68 30604000     push Test_CPP.00406030                   ; %d\n
0040101A    E8 11000000     call Test_CPP.00401030
0040101F    83C4 08         add esp,8
00401022    C3              retn


取模和除法的优化之后的汇编代码通常都会有一个很大的数出现,就像本例中的38E38E39h,由于我现在还没搞明白这个数的真正作用是什么，且将它叫做幻数吧。
下面来解析代码

00401000    8B4C24 04       mov ecx,dword ptr ss:[esp+4]
将被除数放到ecx寄存器

00401004    B8 398EE338     mov eax,38E38E39
将幻数放到ecx

00401009    F7E9            imul ecx
0040100B    D1FA            sar edx,1
0040100D    8BC2            mov eax,edx
0040100F    C1E8 1F         shr eax,1F
00401012    03D0            add edx,eax
这段代码看起来莫名其妙,那就先来看一些数学的东西吧
假设x=被除数
    o=除数
    c=幻数
    式①
其中,o的值我们已经在源代码中给出,是个常量.
的实际值则由编译器给出，也是个常量
就是说 的值是可以事先计算出来的,编译器就是把这个值作为幻数c
于是我们将c带入式&#129;,得到:
  式②
那么最后总结一下，就是说:
   式③
那么到此为止,我们就将占用CPU时间20个周期的除法指令,转换为一个乘法指令和一个移位指令了（乘法指令和移位指令占的周期加起来都不够一个除法指令多）

现在让我们再回顾一下代码,不用翻页了,我再贴一次：
00401009    F7E9            imul ecx
0040100B    D1FA            sar edx,1
0040100D    8BC2            mov eax,edx
0040100F    C1E8 1F         shr eax,1F
00401012    03D0            add edx,eax

下面一句一句的分析
00401009    F7E9            imul ecx
此汇编代码得出我们数学公式中的xc,然后放到edx:eax里面去
(edx放数据的高位 eax放数据的低位)

0040100B    D1FA            sar edx,1
数据存放的位置是edx:eax 我们知道有公式

指令imul ecx已经计算出xc了,那么这一条指令恐怕与"右移n位"有些关系
edx:eax存放的是数据,那么我们如果弃eax不用,直接将edx参与右移n位的相关计算的话,那么edx的值相当于把原数据右移了32位，而此处的指令又将edx向右移动了一位,那么就一共向右移动了33位了。
就是说我们已经知道了式&#402;中的n了，即n=33.
此时edx= ，似乎已经大功告成了。但是下面却还有这样一段代码
0040100D    8BC2            mov eax,edx
0040100F    C1E8 1F         shr eax,1F
00401012    03D0            add edx,eax
这段代码的意思如下
eax=edx
然后将eax向右移动1F位(31位)，那么此时eax只剩下一个原来的符号位的值了
然后将这个原符号位的值加上edx，就是说：
如果edx的值为正数的话，那么符号位为0，add edx,0之后 edx的值不变
如果edx的值为负数的话，那么符号位为1，add edx,-1之后 edx的值 +1

为什么edx的值是负数就要-1呢？？？
因为有这样一些数学的公式：
当a≥0：

当a≤0：

其中 ，分别是向零取整, 向上取整， 向下取整

例如0.5向上取整是1， 向下取整是0，向零取整也是0
又如 -1.5向上取整是-1，向下取整是-2，向0取整是-1
（C语言除法一律是向零取整,而右移运算是向下取整）

现在回到我们的 edx是负数时为什么要加1的问题上，根据上面数学公式可以得出原因
  即

好了分析完毕，最后再总结下反推出来的结果
因为 ,所以
我们已经知道 中n=33，即，而幻数c也在反汇编中看到是38E38E39
可得 ，o=8.999999……，即o≈9
最终反推出C语言代码为printf("%d\n",argc/7);

温馨提示~~~~：此推导方法仅在编译器计算幻数得出的结果可用4字节表示的情况下适用。
其他情况下一篇文章再说吧

gaoyueh0ng

"零取整=下取整+1" 解释上是不是遗漏了什么?  比如 -5/4=-5>>2=-2 再+1为-1 这个结果是正确的. 但是对于-8/4=-8>>2=-2 再+1为-1 明显结果就不对了.. 我在想是不是跟右移32+n位有关.但是又不知道怎么证明.

Snow

因为图片要一副一副的上传再插入，可能有图片放错的地方，看到的提醒下 谢谢

cu629944

膜拜了，期待下一篇分析~

willJ

不错，最近在看C++反汇编？

Snow

willJ 发表于 2012-6-22 15:33
不错，最近在看C++反汇编？

是啊。。这篇东西也是按书用自己的语言写出来而已。。

Snow

willJ 发表于 2012-6-22 15:33
不错，最近在看C++反汇编？

为什么你的评分能评15CB那么多额。。

willJ

Snow 发表于 2012-6-22 16:40
为什么你的评分能评15CB那么多额。。

因为俺是独步武林

zhimingcom

中n=33，即，而幻数c也在反汇编中看到是38E38E39
可得  ，o=8.999999……，即o≈9
最终反推出C语言代码为printf("%d\n",argc/9);

Chenxs110

那本书上也讲了 有符号无符号的  跟数学联系很紧密

O_o

对形如 x/y = z 的简单除法，有以下的转换：

x/y = z

x* (1/y) = z 

x* M = z

M = 1/y = 1^32 / ((1^32)*y) = (1^32/y) >> 32