大理寺少卿 发表于 前天 22:21

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**

xxxxbzn1 发表于 昨天 10:03

楼主,不论什么情况你一定要hold住!hold住就是胜利!
页: [1]
查看完整版本: X86C++反汇编03.除法的优化