首页
论坛
课程
招聘
雪    币: 270
活跃值: 活跃值 (18)
能力值: ( LV9,RANK:610 )
在线值:
发帖
回帖
粉丝

[原创]浅谈sar指令在整数除法中的优化

2010-2-9 10:42 11814

[原创]浅谈sar指令在整数除法中的优化

2010-2-9 10:42
11814
初学《加密与解密3》看到第四章里的编译器的算法优化时的一点困惑,然后动手实践了一下得到一点心得体会,拿来跟大家分享!
   ps.本人汇编基础非常差,sar指令也是刚刚学会的,另外脑袋转的慢,别人用5分钟能解决的问题,我得用10分钟,因此这篇文章我花了6个多小时才完成。
如果有错误欢迎指出,以免误导他人!

浅谈Sar指令在整数除法中的优化

还不懂sar指令的同学马上去baidu啊,Google啊查去,我刚查完!
首先来看一段vc代码
int get()
{
  return -8;
}

int main()
{
  int a = get()/2;
  printf("%d",a);
  return 0;
}

汇编代码(本文里反汇编码都是指Release版本下的OD返回编码)如下
00401000  /$  B8 F8FFFFFF   mov     eax, -8   ; get子程序 总是返回-8
00401005  \.  C3            retn
00401006      90            nop
00401010  /$  E8 EBFFFFFF   call    00401000  ;得到返回值 eax = -8
00401015  |.  99            cdq                ;将eax的值符合扩展到edx
00401016  |.  2BC2          sub     eax, edx   ;等价于 eax = eax + 符号位(eax为正数或者0时符号位为0,负数时为1)
00401018  |.  D1F8          sar     eax, 1      ;带符合右移一位
0040101A  |.  50            push    eax
0040101B  |.  68 30704000   push    00407030      ;  ASCII "%d"
00401020  |.  E8 0B000000   call    00401030       ;printf函数
00401025  |.  83C4 08       add     esp, 8
00401028  |.  33C0          xor     eax, eax
0040102A  \.  C3            retn
0040102B      90            nop


简单的伪代码表示如下
Mov eax, idata              ;idata表示一个整数
Add eax, eax的符号位
Sar eax, 1

上面是一个整数/2的情况 
如果一个整数/2^n(这里2^n表示2的n次方) 应该如何表示呢
我们将上面的VC代码修改这么一句
int a = get()/2; =>   int a = get()/16;
通过反汇编自己翻译成伪代码就是这样的
Mov eax, idata              ;idata表示一个整数
Add eax, (eax的符号位)*(2^n - 1) ;这里n=4
Sar eax, n

上面这个就是一般的除数是2^n一般的公式了,正负整数都管用

粗略的用这样一个数学公式来表示:
Idata/(2^n) = YWn(idata+2^n - 1)
注意 YWn表示将其后面的数以sar方式移动n位 即 sar (数),n

再变换一下,将idata换成(idata – 2^n + 1)
(Idata – 2^n+1)/(2^n) = YWn(idata)             -----------最终公式

Ps.上面的公式是我OD反汇编总结出来的,缺少数学的严格推理证明。我不会证,谁来证明下啊?感激不尽!

下面来解释一个难点,也是写本文的初衷
看一段VC代码:
int get()
{
  int i=rand()%2;
   if(i)
  return rand();
   else
   return rand()*(-1);
}

int main()
{
  int a = get()/9;
  printf("%d",a);
  return 0;
}

反汇编码:
00401010  /$  E8 EBFFFFFF   call    00401000   ;调用get函数 eax=随即数
00401015  |.  8BC8          mov     ecx, eax  ; ecx = eax
00401017  |.  B8 398EE338   mov     eax, 38E38E39 ;这是一个编译器预先设定好的MagicNumber
0040101C  |.  F7E9          imul    ecx ;带符合的乘法,不多说
0040101E  |.  D1FA          sar     edx, 1 ;将乘法的高32位结果算数右移一位
00401020  |.  8BC2          mov     eax, edx ;eax = edx
00401022  |.  C1E8 1F       shr     eax, 1F   ;逻辑右移31位
00401025  |.  03D0          add     edx, eax ;以上这3句的意思就是  edx = edx+edx的符号位,本文最重要的目的就是解释他为什么加1
00401027  |.  52            push    edx
00401028  |.  68 30704000   push    00407030              ;  ASCII "%d"
0040102D  |.  E8 0E000000   call    00401040  ;printf edx
00401032  |.  83C4 08       add     esp, 8
00401035  |.  33C0          xor     eax, eax
00401037  \.  C3            retn

关于MagicNumber这里给你几个连接自己看,不多介绍
http://bbs.pediy.com/showthread.php?t=68849
http://bbs.pediy.com/showthread.php?t=81456
我们把上面的反汇编代码写成伪代码,如下
idata 表示一个32位有符号数,这里一定是有符号的,否则逻辑错误
magic 表示立即数0x38E38E39  他是一个正数
FH(idata) 表示idata的最高位,即 FH(idtat) = (idata & 0x80000000)? 1:0
[edx,eax]表示 edx和eax组成的64位的寄存器

Mov [edx,eax], magic*idata
Sar [edx,eax],33      ;由于移位的操作此时eax里面的值已经没有意义了
Add edx + idata的符号位  ;因为magic是个正数,所以等价于magic*idata的符号位


而我们的本意是 idata/9
因此得到如下数学公式,我们就是要证明他的正确性
YW33(magic*idata) + FH(idata) = idata/9          -------------- (黄金公式)
①.  当FH(idata) == 0时
上述黄金公式即
Magic*idata/2^33 = idata/9

Magic*9 = 2^33
我们将magic = 0x0x38E38E39带入  然后用科学计算器验证了下结果如下
Magic*9 = 0x200000001 
2^33 = 0x200000000
这种优化的除法本身就是一种近似,这里不多讨论为什么存在一个1的差异
证毕。
②.  当FH(idata) == 1时
由 最终公式(Idata – 2^n+1)/(2^n) = YWn(idata)
得到
YW33(magic*idata) = (magic*idata – 2^33 + 1)/(2^33)
将右边带入黄金公式即:
(magic*idata – 2^33 + 1)/(2^33) + 1 = idata/9

Magic*idata/2^33 – 1 + 1 = idata/9          (;1/2^33 ≈ 0因此忽略掉)

Magic*idata/2^33 = idata/9

Magic*9 = 2^33
证毕。

HWS计划·2020安全精英夏令营来了!我们在华为松山湖欧洲小镇等你

上传的附件:
最新回复 (13)
雪    币: 270
活跃值: 活跃值 (18)
能力值: ( LV9,RANK:610 )
在线值:
发帖
回帖
粉丝
blueapplez 活跃值 14 2010-2-9 10:57
2
0
遗漏说明一下 :最终公式只对负数有效
正数是这个样子:Idata/(2^n) = YWn(idata)
雪    币: 2025
活跃值: 活跃值 (15)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2010-2-9 10:57
3
0
6个多小时 不顶说不过去
雪    币: 270
活跃值: 活跃值 (18)
能力值: ( LV9,RANK:610 )
在线值:
发帖
回帖
粉丝
blueapplez 活跃值 14 2010-2-9 11:06
4
0
还不是脑袋转不过弯来  要是脑袋转的快   估计一会就能想明白了  呵呵
S大  帮看看有没有什么错误啊    万一错了  误导别人就不好了
雪    币: 310
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
stalker 活跃值 8 2010-2-9 13:01
5
0
支持blueapplez
一堆公式看得有点晕
雪    币: 65
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
langker 活跃值 2010-2-10 16:39
6
0
看过类似的,没看过这么透彻的
雪    币: 205
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
fonilye 活跃值 2010-2-19 09:12
7
0
对于公式Idata/(2^n)=YWn(idata+2^n-1)
有一点需要说明,即intel使用的有符号除法的商是采取向零圆整的方式(如:(-5)/2=-2……-1,5/2=2……1),所以对于不能整除的数,移位的结果与商差1。这就是移位前加上(2^n-1)的原因。
由于不会使用论坛功能,把解释的内容粘贴到这里就走样了,所以放入附件。
对于这个公式理解后面加(2^n-1)的原因不是太难,难的是当初如何想到加(2^n-1)而不是别的数,向先驱们致敬!
向lz的专研精神致敬!
上传的附件:
雪    币: 578
活跃值: 活跃值 (25)
能力值: ( LV9,RANK:140 )
在线值:
发帖
回帖
粉丝
monsterok 活跃值 3 2010-2-19 21:13
8
0
牛b啊,偶像啊
雪    币: 270
活跃值: 活跃值 (18)
能力值: ( LV9,RANK:610 )
在线值:
发帖
回帖
粉丝
blueapplez 活跃值 14 2010-2-20 09:13
9
0
to:fonilye
对于公式Idata/(2^n)=YWn(idata+2^n-1)
有一点需要说明,即intel使用的有符号除法的商是采取向零圆整的方式(如:(-5)/2=-2……-1,5/2=2……1),所以对于不能整除的数,移位的结果与商差1。这就是移位前加上(2^n-1)的原因。

这里是不是要分正数负数呢?
雪    币: 205
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
fonilye 活跃值 2010-2-20 10:29
10
0
对,正数的补码是其本身,除法和移位的结果是相同的,不需要修正(就是你第二帖中提出的那个正数公式)。
但对负数的补码,除法和直接移位的结果并不相同,如果用移位代替除法的话,可能需要修正(视移出部分是否为零而定)。我前一帖的解释只是对你提出的负数那个公式。
呵呵,是我的表述有问题
雪    币: 77
活跃值: 活跃值 (42)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
网络游侠 活跃值 2010-4-20 11:02
11
0
我的理解就是整数 /2 ....余数 随他怎么变。 公式不变!
雪    币: 154
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
leeonegor 活跃值 2010-12-3 16:35
12
0
雪    币: 353
活跃值: 活跃值 (12)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
晓欣 活跃值 3 2010-12-3 21:11
13
0
不错,对看反汇编代码很有帮助!
雪    币: 40
活跃值: 活跃值 (10)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
moasm 活跃值 2011-9-16 12:20
14
0
<code>
Mov eax, idata              ;idata表示一个整数
Add eax, (eax的符号位)*(2^n - 1) ;这里n=4
Sar eax, n
</code>

你的这一段代码写得非常好. 但是似乎应该是反过来的:

<code>
Mov eax, idata              ;idata表示一个整数
Add eax, -(eax的符号位)*(2^n - 1) ;这里n=4
Sar eax, n
</code>
或者
<code>
Mov eax, idata              ;idata表示一个整数
SUB eax, (eax的符号位)*(2^n - 1) ;这里n=4
Sar eax, n
</code>

----------------------------------------------------------
即最后的结果是
1>如果 被除数 为 非负数 时候, 直接为
<code>
Sar eax, n    ; eax为被除数, 除数为 2^n
</code>

2>如果被除数 是负数时候, 为:
<code>
Mov eax, idata            
ADD eax, (2^n - 1)
Sar eax, n
</code>
游客
登录 | 注册 方可回帖
返回