-
-
[原创]release版本下除法优化过后还原除数的方法
-
2017-11-10 04:52
-
Release版本优化除法需要条件:
1)除数不为零
2)除数为立即数
如不需看例子可直接查看文章总结(请往下拉)
由于例子进程为32位,所以最低移位数是32(如果是64位进程,那么最低移位数是64)
无符号被除数 除 2的幂
例子:
UINT uNum;
uNum = uNum /8;
release优化汇编如下
mov eax, [ebp+uNum]
shr eax, 3
除数为:2^3
无符号被除数 除 非2的幂
例子:UINT uNum;
uNum =uNum /11;
release优化汇编如下
mov eax, 0BA2E8BA3hmul [ebp+uNum]shr edx, 3MagicNumber== 0BA2E8BA3h;移位数N=32+3=35
因为使用的是 mul 指令,还原方法:
2^N/M的商向上取整
2^35/0BA2E8BA3h-->34359738368/3123612579=10.9999999996
10.9999999996向上取整为:11
除数为:11
特例:
UINT uNum;
uNum =uNum /7;
release优化汇编如下
mov ecx, [ebp+uNum]
mov eax, 24924925h
mul ecx
sub ecx, edx
. shr ecx, 1
add ecx, edx
shr ecx, 2
魔法数M=24924925h;
移位数N=32+1+2=35;
因为使用的是 mul 指令,还原方法:
2^N/(2^32+M)的商向上取整
详细还原如下:
2^35/24924925h-->34359738368/(4294967296+613566757)=6.999999999
6.99999999向上取整为:7
除数为:7
无符号被除数 除 非2的幂负数
例子:
UINT uNum;
uNum =uNum /-9;
release优化汇编如下
mov eax, 80000005h
mul [ebp+uNum]
shr edx, 1Fh
魔法数M=80000005h;
移位数N=32+1FH=63;
因为使用的是 mul 指令,(由于混除,当做无符号除法),还原方法:
2^N/M的商向上取整
详细还原如下:
2^63/80000005h-->9223372036854775808/2147483643=4294967286.00000002
4294967286.00000002向上取整为:4294967287
因为商值较大,转为十六进制:0FFFFFFF7h,当有符号解释为十进制:-9
除数为:-9
有符号被除数 除 2的幂
例子:
int nNum;
nNum = nNum /16;
release优化汇编如下
mov eax, [ebp+nNum]
cdq
and edx, 0Fh
add eax, edx
sar eax, 4
有符号除2的幂为 定式:
Mov eax,mem
Cdq
And edx,immA
Add eax,edx
Sar eax,immB
还原方法:
当2^immB - 1 == immA
除数为2^immB
有符号被除数 除 非2的幂
例子1: 1)当除数为正例子2:1)当除数为负int nNum;
nNum =nNum /19;
release优化汇编如下
mov eax, 6BCA1AF3h
imul [ebp+nNum]
sar edx, 3
mov eax, edx
shr eax, 1Fh
add eax, edx
相比无符号被除数除非2的幂多了后三行汇编(还原无需在意)
魔法数M=6BCA1AF3h;
移位数N=32+3=35;
因为使用的imul 指令,所以需要知道除数为正还是负,
由于6BCA1AF3h<0x80000000,而另imul与sar之间edx并未做减法(nNum)调整,固判定除数为正数还原方法:
2^N/M的商向上取整
详细还原如下:
2^35/0BA2E8BA3h-->34359738368/1808407283=18.999999995
18.999999995向上取整为:19
除数为:19
例子1: 2)当除数为正
int nNum;
nNum =nNum /7;
release优化汇编如下
mov eax, 92492493h
imul [ebp+nNum]
add edx, [ebp+nNum]
sar edx, 2
mov eax, edx
shr eax, 1Fh
add eax, edx
相比无符号被除数除非2的幂多了后三行汇编(还原无需在意)
魔法数M=6BCA1AF3h;
移位数N=32+2;
因为使用的imul 指令,所以需要知道除数为正还是负,
由于M>=0x80000000,而另imul与sar之间edx有做加法(nNum)调整
固判定除数为正数.还原方式为:
2^N/M的商向上取整
2^34/92492493h-->17179869184/2454267027=6.99999999
6.99999999向上取整为:7
除数为:7
int nNum;
nNum =nNum /-33;
release优化汇编如下
mov eax, 0C1F07C1Fh
imul [ebp+nNum]
sar edx, 3
mov eax, edx
shr eax, 1Fh
add eax, edx
相比无符号被除数除非2的幂多了后三行汇编(还原无需在意)魔法数M=0C1F07C1Fh;
移位数N=32+3;
因为使用的imul 指令,所以需要知道除数为正还是负,
由于0C1F07C1Fh>=0x80000000,另imul与sar之间edx并未做加法(nNum)调整,固判定除数为负数,还原方式为:
2^N/neg(M)的商向上取整转为负数
neg(0C1F07C1Fh)=1041204193;
2^35/neg(0C1F07C1Fh)-->34359738368/1041204193=32.99999999
32.99999999向上取整为:33,加上负数符号-->-33
除数为:-33
例子2:2)当除数为负
int nNum;
nNum =nNum /-7
release优化汇编如下
mov eax, 6DB6DB6Dh
imul [ebp+nNum]
sub edx, [ebp+nNum]
sar edx, 2
mov eax, edx
shr eax, 1Fh
add eax, edx
相比无符号被除数除非2的幂多了后三行汇编(还原无需在意)魔法数M=6DB6DB6Dh;
移位数N=32+2;
因为使用的imul 指令,所以需要知道除数为正还是负,
由于M<0x80000000,而imul与sar之间edx有做减法(nNum)调整,固判定除数为负数还原方式为:
2^N/neg(M)的商向上取整转为负数
neg(6DB6DB6Dh)=2454267027;
2^34/neg(6DB6DB6Dh)-->17179869184/2454267027=6.999999996.99999999向上取整为:7 ,加上负数符号-->-7
除数为:-7
总结:
设B为进程位数
设N为移位数
设M为魔法数
设 C为除数
查看乘法指令为mul 或 imul
Mul指令还原
如果是 mul,则查看是否满足指令有”mul sub shr add shr”定式,如果满足,则使用 C=2^(N+B)/(2^B+M)
如果不满足,则使用 C=2^(N+B)/M
如果是imul 则需要查看M来判断除数为正负
M<0X80000000 并且在imul 与sar指令中并未出现sub调整,则除数为正
否则除数为负,则使用 C=2^(N+B)/neg(M)
M>=0X80000000 并且在imul 与sar指令中并未出现add调整,则除数为负
否则除数为正,则使用 C=2^(N+B)/M
详细还原推到方式请查看钱林松老师写的DRE
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
