初学《加密与解密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;
}
代码:
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^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
粗略的用这样一个数学公式来表示：
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
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的符号位
因此得到如下数学公式，我们就是要证明他的正确性
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
证毕。