反汇编代码还原之除数为非2的幂
本文为看雪论坛精华文章
看雪论坛作者ID:TkBinary
目录
系列文章
一. 数学知识补充
1.1 简介
1.2 分数
1.2.1分数加法
1.2.1分数乘法
二. 除法优化之有符号非2的幂优化
2.1高级代码与反汇编
2.2 除法非2的幂还原
2.3 除数为非2的幂的优化与原理
2.4 总结除法还原公式
三. 除法优化之无符号非2的幂优化
3.1 无符号非2的幂除数为正代码反汇编还原
3.2 无符号非2的幂除数为负数反汇编代码还原
3.3 特殊汇编
四. 为什么学习除法优化
4.1 为什么学习除法优化
五. 高级Vs编译器与linux下的gcc优化
5.1 vs2019 x86 有符号非2的幂优化
5.2 vs2019 x64有符号非2的幂优化
5.3 linux gcc x86 有符号非2的幂
5.4 其它同理自己建立项目研究
系列文章
* 点击文字即可跳转文章
一. 数学知识补充
1.1 简介
1.2 分数
1.2.1分数加法
1.2.1分数乘法
分数乘法
**分数*分数 是分子 * 分子 分母 * 分母**
如下:
口诀: 乘分数,没难度,上乘上,下乘下,再约分。
整数相乘
如果一个整数 * 一个分数,那么这个分数就可以看做是分子,而分母就是1。
例子:
至于约分,可以寻找最小公因数,跟公倍数相反。
公倍数是找出相乘,公因数就是找出可以分子/分母的数,都去除同一个数。
二. 除法优化之有符号非2的幂优化
2.1 高级代码与反汇编
int main(int argc, char* argv[])
{
/*
除法
*/
int NumberOne = 0;
int NumberTwo = 0;
scanf("%d",&NumberOne);
scanf("%d",&NumberTwo);
int Count1 = NumberOne / 3;
int Count2 = NumberTwo / 5;
int Count3 = NumberTwo / 6;
int Count4 = NumberTwo / 9;
printf("%d%d%d%d%d",Count4,Count3,Count2,Count1);
system("pause");
return 0;
}
汇编对应代码:
.text:00401000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:00401000 _main proc near ; CODE XREF: start+AF↓p
.text:00401000
.text:00401000 var_8 = dword ptr -8
.text:00401000 var_4 = dword ptr -4
.text:00401000 argc = dword ptr 4
.text:00401000 argv = dword ptr 8
.text:00401000 envp = dword ptr 0Ch
.text:00401000
.text:00401000 sub esp, 8
.text:00401003 xor eax, eax
.text:00401005 mov [esp+8+var_8], eax
.text:00401009 mov [esp+8+var_4], eax
.text:0040100D lea eax, [esp+8+var_8]
.text:00401011 push eax
.text:00401012 push offset aD ; "%d"
.text:00401017 call _scanf
.text:0040101C lea ecx, [esp+10h+var_4]
.text:00401020 push ecx
.text:00401021 push offset aD ; "%d"
.text:00401026 call _scanf
//第一段
.text:0040102B mov ecx, [esp+18h+var_8]
.text:0040102F mov eax, 55555556h
.text:00401034 imul ecx
.text:0040103A mov eax, edx
.text:0040103C shr eax, 1Fh
.text:0040103F add edx, eax
//第二段
.text:00401036 mov ecx, [esp+18h+var_4]
.text:00401041 mov eax, 66666667h
.text:00401047 imul ecx
.text:00401049 sar edx, 1
.text:0040104B mov eax, edx
.text:0040104D shr eax, 1Fh
.text:00401050 add edx, eax
.text:00401057 push edx //这里原先是流水线优化给提到上边来了
//第三段
.text:00401052 mov eax, 2AAAAAABh
.text:00401058 imul ecx
.text:0040105A mov eax, edx
.text:0040105C shr eax, 1Fh
.text:0040105F add edx, eax
.text:00401066 push edx //同上流水线优化
//第四段
.text:00401061 mov eax, 38E38E39h
.text:00401067 imul ecx
.text:00401069 sar edx, 1
.text:0040106B mov ecx, edx
.text:0040106D shr ecx, 1Fh
.text:00401070 add edx, ecx
.text:00401072 push edx
.text:00401073 push offset aDDDDD ; "%d%d%d%d%d"
.text:00401078 call _printf
.text:0040107D push offset aPause ; "pause"
.text:00401082 call _system
.text:00401087 xor eax, eax
.text:00401089 add esp, 30h
.text:0040108C retn
.text:0040108C _main endp
2.2 除法非2的幂还原
乍一看上面汇编代码,除法怎么变为了这样,为什么又有乘法又有除法,还有调整等,那么这里就着重讲解一下。
如果想要直接还原,那么我们把代码定式提取出来,直接进行还原。
代码定式:
mov ecx, 被除数
mov eax, M值
imul ecx
sar edx, n
mov eax, edx
shr eax, 1Fh
add edx, eax
push edx
根据汇编我们只需要看三个点即可,并且得出三个点的公式得原理:
其中M是编译器计算出来了, ecx是被除数,这里sar n值,直接操作的是edx。这里其实是除法转变为了乘法,而如果除法转变为乘法,那么在32位年代下,两个数相乘32的值是不会放下的。所以我们这里其实使用的是 edx,eax 来代表乘法的结果,然后我们直接操作了乘积的高位,这里右移1,等价于是除以2^n+1。
那么我们还原的时候直接记住死公式就可以,2^32+1/M 。
直接统计n的取值,然后用 2的32次方 + n即可。因为乘积的低位时代表2^32次方,这里直接是对乘积高位做操作,所以我们需要加上低位的32次方的值。
例子还原:
.text:0040102B mov ecx, [esp+18h+var_8]
.text:0040102F mov eax, 55555556h
.text:00401034 imul ecx
.text:0040103A mov eax, edx //这里直接使用的是edx.而没有对edx做修改.所以我们的n值就是0
.text:0040103C shr eax, 1Fh
.text:0040103F add edx, eax
我们套用公式:
2.3 除数为非2的幂的优化与原理
.text:00401061 mov eax, 38E38E39h
.text:00401067 imul ecx
.text:00401069 sar edx, 1
.text:0040106B mov ecx, edx
.text:0040106D shr ecx, 1Fh
.text:00401070 add edx, ecx
.text:00401072 push edx
.text:00401061 mov eax, 38E38E39h
.text:00401067 imul ecx
.text:00401069 sar edx, 1
2.4 总结除法还原公式
三. 除法优化之无符号非2的幂优化
int main(int argc, char* argv[])
{
/*
除法
*/
unsigned int NumberOne = 0;
unsigned int NumberTwo = 0;
scanf("%u",&NumberOne);
scanf("%u",&NumberTwo);
unsigned int Count1 = NumberOne / 3;
unsigned int Count2 = NumberTwo / 5;
unsigned int Count3 = NumberTwo / 6;
unsigned int Count4 = NumberTwo / 9;
printf("%d%d%d%d%d",Count4,Count3,Count2,Count1);
system("pause");
return 0;
}
.text:00401005 mov [esp+8+var_8], eax
.text:00401009 mov [esp+8+var_4], eax
.text:0040102B mov eax, 2863311531
.text:00401030 mov ecx, [esp+18h+var_4]
.text:00401034 mul [esp+18h+var_8]
.text:00401038 shr edx, 1
.text:0040103A mov eax, 3435973837
.text:0040103F push edx
.text:00401040 mul ecx
.text:00401042 shr edx, 2
.text:00401045 mov eax, 0AAAAAAABh
.text:0040104A push edx
.text:0040104B mul ecx
.text:0040104D shr edx, 2
.text:00401050 mov eax, 38E38E39h
.text:00401055 push edx
.text:00401056 mul ecx
.text:00401058 shr edx, 1
.text:0040105A push edx
3.1 无符号非2的幂除数为正代码反汇编还原
.text:0040102B mov eax, 2863311531
.text:00401030 mov ecx, [esp+18h+var_4]
.text:00401034 mul [esp+18h+var_8]
.text:00401038 shr edx, 1
被除数 = 2^33
除数 = M
求除数公式 = 2^n/M = b
代入公式
2^33 / 2863311531 = 2.999999999 向上取整 = 3 所以得出这里的除数为3. ecx = var4
所以这里反汇编为高级代码为 var_4 / 3
3.2 无符号非2的幂除数为负数反汇编代码还原
int main(int argc, char* argv[])
{
/*
除法
*/
unsigned int NumberOne = 0;
unsigned int NumberTwo = 0;
scanf("%u",&NumberOne);
scanf("%u",&NumberTwo);
unsigned int Count1 = NumberOne / -3;
unsigned int Count2 = NumberTwo / -5;
unsigned int Count3 = NumberTwo / -6;
unsigned int Count4 = NumberTwo / -9;
printf("%d%d%d%d%d",Count4,Count3,Count2,Count1);
system("pause");
return 0;
}
.text:00401005 mov [esp+8+var_8], eax
.text:00401009 mov [esp+8+var_4], eax
/-3
.text:0040102B mov eax, 40000001h
.text:00401030 mov ecx, [esp+18h+var_4]
.text:00401034 mul [esp+18h+var_8]
.text:00401038 shr edx, 1Eh
.text:00401040 push edx
/-5
.text:0040103B mov eax, 80000003h
.text:00401041 mul ecx
.text:00401043 shr edx, 1Fh
.text:0040104B push edx
/-6
.text:00401046 mov eax, 7
.text:0040104C mul ecx
.text:0040104E mov eax, ecx
.text:00401050 sub eax, edx
.text:00401052 shr eax, 1
.text:00401054 add eax, edx
.text:00401056 shr eax, 1Fh
.text:00401059 push eax
/-9
.text:0040105A mov eax, 80000005h
.text:0040105F mul ecx
.text:00401061 shr edx, 1Fh
.text:00401064 push edx
3.3 特殊汇编
mov regA,[ebp - xxx]
mov reg,M
mul regA
sub regA,edx
shr regA,n
add regA,edx
shr regA,(n-1)
这里取出两个n值。1+31= 32,所以n值为32。
代入公式得:
2^64 / 4,294,967,303 = 0XFFFFFFF9
关于特殊汇编在下一篇应该会详细讲解。
四. 为什么学习除法优化
4.1 为什么学习除法优化
还是那句话为什么学习除法优化,好就以我们上面的例子为例,那么使用IDA F5查看。
请问看到这种代码你怕了吗?直接反汇编可以得出这一段代码我是干啥,用IDA反汇编就会得出右移等等,在我们看来就是硬汇编。
也就是硬着头皮还原的,所以说这就是我们学习的意义所在。当然F5还是很强大的,但是我们学会了能更好的帮助我们进行反汇编,更好的通过反汇编从而还原为高级代码。
五. 高级Vs编译器
与linux下的gcc优化
其实还是老生常谈,拿高版本与低版本做个对比,看看优化方式是否发生了改变。
5.1 vs2019 x86 有符号非2的幂优化
高级代码:
int main(int argc, char* argv[])
{
/*
除法
*/
int NumberOne = 0;
int NumberTwo = 0;
scanf("%d",&NumberOne);
scanf("%d",&NumberTwo);
int Count1 = NumberOne / 3;
int Count2 = NumberTwo / 5;
int Count3 = NumberTwo / 6;
int Count4 = NumberTwo / 9;
printf("%d%d%d%d%d",Count4,Count3,Count2,Count1);
system("pause");
return 0;
}
汇编:
.text:00401080 push ebp
.text:00401081 mov ebp, esp
.text:00401083 sub esp, 8
.text:00401086 lea eax, [ebp+var_4]
.text:00401089 mov [ebp+var_4], 0
.text:00401090 push eax
.text:00401091 push offset unk_41ECDC
.text:00401096 mov [ebp+var_8], 0
.text:0040109D call sub_401050
.text:004010A2 lea eax, [ebp+var_8]
.text:004010A5 push eax
.text:004010A6 push offset unk_41ECDC
.text:004010AB call sub_401050
.text:004010B0 mov ecx, [ebp+var_8]
.text:004010B3 mov eax, 55555556h
.text:004010B8 imul [ebp+var_4]
.text:004010BB mov eax, edx
.text:004010BD shr eax, 1Fh
.text:004010C0 add eax, edx
.text:004010C2 push eax
.text:004010C3 mov eax, 66666667h
.text:004010C8 imul ecx
.text:004010CA sar edx, 1
.text:004010CC mov eax, edx
.text:004010CE shr eax, 1Fh
.text:004010D1 add eax, edx
.text:004010D3 push eax
.text:004010D4 mov eax, 2AAAAAABh
.text:004010D9 imul ecx
.text:004010DB mov eax, edx
.text:004010DD shr eax, 1Fh
.text:004010E0 add eax, edx
.text:004010E2 push eax
.text:004010E3 mov eax, 38E38E39h
.text:004010E8 imul ecx
.text:004010EA sar edx, 1
.text:004010EC mov eax, edx
.text:004010EE shr eax, 1Fh
.text:004010F1 add eax, edx
.text:004010F3 push eax
.text:004010F4 push offset aDDDDD ; "%d%d%d%d%d"
.text:004010F9 call sub_401020
.text:004010FE push offset aPause ; "pause"
.text:00401103 call sub_4048E7
.text:00401108 add esp, 28h
.text:0040110B xor eax, eax
.text:0040110D mov esp, ebp
.text:0040110F pop ebp
这里流水线优化等也不去掉了,可以发现跟VC6.0无任何区别。
5.2 vs2019 x64有符号非2的幂优化
高级代码:
int main(int argc, char* argv[])
{
/*
除法
*/
__int64 NumberOne = 0;
__int64 NumberTwo = 0;
scanf("%I64d", &NumberOne);
scanf("%I64d", &NumberTwo);
__int64 Count1 = NumberOne / 3;
__int64 Count2 = NumberTwo / 5;
__int64 Count3 = NumberTwo / 6;
__int64 Count4 = NumberTwo / 9;
printf("%I64d%I64d%lld%lld", Count4, Count3, Count2, Count1);
system("pause");
return 0;
}
反汇编:
text:00000001400010D0 sub rsp, 38h
.text:00000001400010D4 xor eax, eax
.text:00000001400010D6 lea rdx, [rsp+38h+arg_10]
.text:00000001400010DB lea rcx, aI64d ; "%I64d"
.text:00000001400010E2 mov [rsp+38h+arg_10], rax
.text:00000001400010E7 mov [rsp+38h+arg_18], rax
.text:00000001400010EC call sub_140001080
.text:00000001400010F1 lea rdx, [rsp+38h+arg_18]
.text:00000001400010F6 lea rcx, aI64d ; "%I64d"
.text:00000001400010FD call sub_140001080
.text:0000000140001102 mov rcx, [rsp+38h+arg_18]
.text:0000000140001107 mov rax, 5555555555555556h
.text:0000000140001111 imul [rsp+38h+arg_10]
.text:0000000140001116 mov rax, 6666666666666667h
.text:0000000140001120 mov r10, rdx
.text:0000000140001123 shr r10, 3Fh
.text:0000000140001127 add r10, rdx
.text:000000014000112A imul rcx
.text:000000014000112D mov [rsp+38h+var_18], r10
.text:0000000140001132 mov r9, rdx
.text:0000000140001135 sar r9, 1
.text:0000000140001138 mov rax, r9
.text:000000014000113B shr rax, 3Fh
.text:000000014000113F add r9, rax
.text:0000000140001142 mov rax, 2AAAAAAAAAAAAAABh
.text:000000014000114C imul rcx
.text:000000014000114F mov rax, 1C71C71C71C71C72h
.text:0000000140001159 mov r8, rdx
.text:000000014000115C shr r8, 3Fh
.text:0000000140001160 add r8, rdx
.text:0000000140001163 imul rcx
.text:0000000140001166 lea rcx, aI64dI64dLldLld ; "%I64d%I64d%lld%lld"
.text:000000014000116D mov rax, rdx
.text:0000000140001170 shr rax, 3Fh
.text:0000000140001174 add rdx, rax
.text:0000000140001177 call sub_140001020
.text:000000014000117C lea rcx, aPause ; "pause"
.text:0000000140001183 call sub_1400045C4
.text:0000000140001188 xor eax, eax
.text:000000014000118A add rsp, 38h
.text:000000014000118E retn
观看反汇编其实跟x86一致。
这里还是去掉流水线优化,提取核心代码位置进行反汇编。
M数值变大,还是代入公式即可。这里使用的mov r10,rdx,说明直接使用的rdx, rdx是一个64位数,所以 2^64 / M = 2.9999999 向上取整 = 3。
5.3 linux gcc x86 有符号非2的幂
高级代码:
#include<stdio.h>
int main()
{
int NumberOne = 0;
int NumberTwo = 0;
scanf("%d", &NumberOne);
scanf("%d", &NumberTwo);
int Count1 = NumberOne / 3;
int Count2 = NumberTwo / 5;
int Count3 = NumberTwo / 6;
int Count4 = NumberTwo / 9;
printf("%d%d%d%d", Count4, Count3, Count2, Count1);
scanf("%d", &Count4);
scanf("%d", &Count3);
scanf("%d", &Count2);
scanf("%d", &Count1);
printf("%d%d%d%d", Count4, Count3, Count2, Count1);
return 0;
}
如果你是64位系统,那么你使用gcc命令如下:
gcc xxx.c -o2 -m32
编译出来即可,其实下面反汇编跟x86 vc++6.0 vs2019 一样,可以不用看了。
反汇编:
.text:080484BB ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:080484BB public main
.text:080484BB main proc near ; DATA XREF: _start+17↑o
.text:080484BB
.text:080484BB var_24 = dword ptr -24h
.text:080484BB var_20 = dword ptr -20h
.text:080484BB var_1C = dword ptr -1Ch
.text:080484BB var_18 = dword ptr -18h
.text:080484BB var_14 = dword ptr -14h
.text:080484BB var_10 = dword ptr -10h
.text:080484BB var_C = dword ptr -0Ch
.text:080484BB argc = dword ptr 8
.text:080484BB argv = dword ptr 0Ch
.text:080484BB envp = dword ptr 10h
.text:080484BB
.text:080484BB ; __unwind {
.text:080484BB lea ecx, [esp+4]
.text:080484BF and esp, 0FFFFFFF0h
.text:080484C2 push dword ptr [ecx-4]
.text:080484C5 push ebp
.text:080484C6 mov ebp, esp
.text:080484C8 push ebx
.text:080484C9 push ecx
.text:080484CA sub esp, 20h
.text:080484CD mov eax, large gs:14h
.text:080484D3 mov [ebp+var_C], eax
.text:080484D6 xor eax, eax
.text:080484D8 mov [ebp+var_24], 0
.text:080484DF mov [ebp+var_20], 0
.text:080484E6 sub esp, 8
.text:080484E9 lea eax, [ebp+var_24]
.text:080484EC push eax
.text:080484ED push offset unk_80486B0
.text:080484F2 call ___isoc99_scanf
.text:080484F7 add esp, 10h
.text:080484FA sub esp, 8
.text:080484FD lea eax, [ebp+var_20]
.text:08048500 push eax
.text:08048501 push offset unk_80486B0
.text:08048506 call ___isoc99_scanf
.text:0804850B add esp, 10h
.text:0804850E mov ecx, [ebp+var_24]
.text:08048511 mov edx, 55555556h
.text:08048516 mov eax, ecx
.text:08048518 imul edx
.text:0804851A mov eax, ecx
.text:0804851C sar eax, 1Fh
.text:0804851F sub edx, eax
.text:08048521 mov eax, edx
.text:08048523 mov [ebp+var_1C], eax
.text:08048526 mov ecx, [ebp+var_20]
.text:08048529 mov edx, 66666667h
.text:0804852E mov eax, ecx
.text:08048530 imul edx
.text:08048532 sar edx, 1
.text:08048534 mov eax, ecx
.text:08048536 sar eax, 1Fh
.text:08048539 sub edx, eax
.text:0804853B mov eax, edx
.text:0804853D mov [ebp+var_18], eax
.text:08048540 mov ecx, [ebp+var_20]
.text:08048543 mov edx, 2AAAAAABh
.text:08048548 mov eax, ecx
.text:0804854A imul edx
.text:0804854C mov eax, ecx
.text:0804854E sar eax, 1Fh
.text:08048551 sub edx, eax
.text:08048553 mov eax, edx
.text:08048555 mov [ebp+var_14], eax
.text:08048558 mov ecx, [ebp+var_20]
.text:0804855B mov edx, 38E38E39h
.text:08048560 mov eax, ecx
.text:08048562 imul edx
.text:08048564 sar edx, 1
.text:08048566 mov eax, ecx
.text:08048568 sar eax, 1Fh
.text:0804856B sub edx, eax
.text:0804856D mov eax, edx
5.4 其它同理自己建立项目研究
自己建立项目研究,高手复习,新手学习,谢谢观看。
看雪ID:TkBinary
https://bbs.pediy.com/user-home-723188.htm
*本文由看雪论坛 TkBinary 原创,转载请注明来自看雪社区。
推荐文章++++
求分享
求点赞
求在看