X86C++反汇编03.除法的优化
1. **理解并掌握数学模型,这样换个编译器优化,数学模型是不变的**2. **同一模型,描述的代码序列可能会有变化**
### **无符号数除法,且除数非2的整数次幂 的正数**
**令 M =2^n / C **
**A / C => A *1 / C =>A *2^n /C *1 / 2^n=>A * 2^n /C>> n=>AM >> n**
**M =2^n / C **
**C=2^n / M**
**C是常量n的值由编译器给那么还是常量**
**当M值越大,即 n值越大 数值越精确**
**因为我们是 32位除法,n值起步32 ,随着C的值越大,n的值越大**
**计算机会自动生成 满足条件的最小 M 值**
**因此可用定式 表达**
**moveax, M ; MagicNumber**
**mul A ; AM **
**shr edx , n ; >>n**
**int main(unsigned int argc, char* argv[])**
**{**
** printf("%d\r\n",******argc / 3****** );**
** return 0;**
**}**
**对应的反汇编代码**
**mov eax, 0AAAAAAABh ;M值 2863311531**
**mul ; A * M**
** shr edx, 1 ; n = 32+1 = 33 ,乘积 结果表达式为edx(高32位) eax(低32位) ,右移32位**
** ; 就到了edx, edx又右移了1位 就是 33,即 直接右移edx,默认已经右移了32位**
** push edx**
** push offset aD **
** call sub_401020**
**add esp, 8**
**xor eax, eax**
**retn**
**验证: **
**移位是下整,还原就需要上整**
** 2^33/ 2863311531 = 8589934592/2863311531 = 3 即 C (被除数是3)**
!(./notesimg/1657186527071-78275737-4482-47af-a1ca-038b0c44aa6b.png)
**int main(unsigned int argc, char* argv[])**
**{**
** printf("%d\r\n",******argc / 7****** );**
** return 0;**
**}**
**对应的反汇编代码**
**mov ecx, **
**mov eax, 24924925h ;M有进位, 所以真正值为: 124924925h 4908534053**
**mul ecx**
**sub ecx, edx**
**shr ecx, 1 ;右移了 1 位**
**add ecx, edx**
**shr ecx, 2 ;右移了 2 位**
**验证: 当遇到 * - 移 +移代表M 产生了进位 高位为1 右移32位 + 3位总共移了 35 位**
**2^35 / 4908534053=34359738368 /4908534053 =7**
**上面优化的原因就是图片倒过来转化,从终点推导到起点**
** 是为了解决 M值是 大数问题把 2^35拆分成2^32 * 2 * 2^2**
**练习: 还原代码**
**.text:00401001 mov esi, ****
****.text:00401005 mov eax, 0CCCCCCCDh 3435973837****
****.text:0040100A mul esi****
****.text:0040100C shr edx, 2 2^34 17179869184****
****.text:0040100F push edx****
****.text:00401010 push offset aD ; "%d\r\n"****
****.text:00401015 call printf**
**17179869184 /3435973837= 5**
**还原代码为: argc/5**
**.text:0040101A mov eax, 20000003h 536870915****
****.text:0040101F mul esi****
****.text:00401021 shr edx, 1Dh 2^61 ********
****.text:00401024 push edx****
****.text:00401025 push offset aD ; "%d\r\n"****
****.text:0040102A call printf****
****.text:0040102F add esp, 10h**
**argc / -23**
** 2^61 /536870915 = 4294967273(FFFF FFE9) =-0x17 =-23**
**无符号数 / 有符号数 结果是无符号数**
**无符号数 * 有符号数 结果是有符号数**
### **有符号数除法,且除数非2的整数次幂 的正数 **
**有符号就要面对 负数向上取值,正数向下取整问题**
**当 x 不为整数时 x 下整 +1 = x 上整 **
**M =2^n/C 因为 C 不是的整数次幂 ,因此 M 也不可能是,而且M是个小数 **
```
int main(unsigned int argc, char* argv[])
{
printf("%d\r\n",argc / 5);
return 0;
}
对应的反汇编代码
mov ecx,
mov eax, 66666667h ; 1717986919
imul ecx ;imul 代表有符号运算
sar edx, 1 ; 2^33 8589934592
;下面代码是想实现无分支实现 下整转上整还原代码时不需要还原
mov eax, edx
shr eax, 1Fh
add edx, eax
下整转上整还可以用下面序列
mov eax,edx
cdq
sub eax,edx
验证: 8589934592/ 1717986919 = 5
int main(unsigned int argc, char* argv[])
{
printf("%d\r\n",argc / 3);
return 0;
}
对应的反汇编代码
mov ecx,
mov eax, 55555556h ;1431655766
imul ecx
;无分支实现 下整转上整
mov eax, edx
shr eax, 1Fh
add edx, eax
上面没有 sar edx ,n ,代表右移了32位
所以:
2^32/1431655766=3
int main(int argc, char* argv[])
{
printf("%d\r\n",argc / 7 );
return 0;
}
对应的反汇编代码
mov ecx,
mov eax, 92492493h ;2454267027
imul ecx ;这里把M变成了有符号负数
add edx, ecx ;调整结果
sar edx, 2
;无分支实现 下整转上整
mov eax, edx
shr eax, 1Fh
add edx, eax
结论:当 M 值 为有符号负数时 ,需要对结果进行调整有增加一条 调整指令
调整方式为: add edx , 乘数指令操作数
练习:
.text:00401001 mov esi,
.text:00401005 mov eax, 38E38E39h 954437177
.text:0040100A mul esi ;无符号数
.text:0040100C shr edx, 1 2^33 8589934592
858934592/ 954437177= 9
.text:00401019 mov eax, 86186187h ; 186186187h 6544712071
.text:0040101E mul esi ;无符号数
.text:00401020 mov eax, esi
.text:00401022 sub eax, edx
.text:00401024 shr eax, 1
.text:00401026 add eax, edx
.text:00401028 shr eax, 4 2^(32+1+4) = 2^37 137438953472
出现了*-移+移指令 M产生了进位
2 ^37 / 6544712071=21
.text:00401036 mov eax, 2AAAAAABh 715827883
.text:0040103B imul esi ;有符号
.text:0040103D sar edx, 1 2^33 8589934592
.text:0040103F mov ecx, edx ;无分之实现下整转上整
.text:00401041 shr ecx, 1Fh
.text:00401044 add edx, ecx
2^33 / 715827883 =8589934592 /715827883=12
.text:00401051 mov eax, 0EA0EA0EBh 3926827243
.text:00401056 imul esi ;有符号
.text:00401058 add edx, esi ;M时有符号负数 调整指令
.text:0040105A sar edx, 5 2^37 137438953472
.text:0040105D mov eax, edx ;无分之实现下整转上整
.text:0040105F shr eax, 1Fh
.text:00401062 add edx, eax
137438953472/ 3926827243= 35
```
**有符号除法定式**
**mov eax, M**
**imul r32/m32**
**sar edx , n**
**mov r32 , edx**
**shr r32, 31**
**add edx, r32**
** 实现用一个有符号数A * 无符号数8086h ,要求结果为 有符号数 **
```
mov ax, 8086h
imulA
add dx,A
使用imul 是因为 8086h是常量,而 A 是变量,使用muld的话结果不可控
使用imulA即 把 A * 8086h 的时候 实际运算的值的真值是(8086h 被视为有符号负数,最高位为1,他是取反+1后的值);
add dx,A 是因为要的结果是 8086hA ,但他运算的结果 为8086hA-10000hA ,因此要加上 10000hA
```
**补码变形**
**a + ~a = ffff**
**a + ~a +1 = 10000h**
**~a+1 = 10000h - a**
** A *-(10000h-8086h) **
**= A * ( 8086h - 10000h )**
**=8086hA-10000hA**
**在dx,ax 中存一个只32位的值**
**ax*10000h =ax.0000 =dx +ax ,ax**
楼主,不论什么情况你一定要hold住!hold住就是胜利!
页:
[1]