i/c整型除法的汇编优化

一、前言

整型除法是逆向学习当中的一大难点，Vs2019 时代硬件功能上去了,很多优化就不再需要。因此逻辑比低版本简单点,很多优化逻辑在硬件层实现了。

但除法指令周期很长，还是很依赖编译优化。当然利用IDA可以方便的还原除法，但对于想知其所以然的同学，还是需要深入学习，以应对各种可能变化。

推荐学习顺序：

->本文

->阅读《C++反汇编与逆向分析技术揭秘（第2版）》(文中简称书)

->逆向编译器

本文将略去数论结论的证明，从汇编算法层面介绍除法的各种汇编实现。

至于除法的硬件实现，见《计算机组成原理》不在本文讨论范围。

二、除法定式

定式证明见后续

定式一：常量折叠

printf(“%d”,10/8);

伪汇编：

push 1

push “%d”

call printf

定式二：除数为变量

有符号数

int x;

cin>>x;

printf("%d",10/x);

伪汇编：

cdq或xor edx,edx

idiv 10,x

无符号数

unsigned y;

cin>>y;

printf("%d",10/y);

伪汇编：

cdq或xor edx,edx

div 10,x

定式三：除数为常量±2^n

有符号数±2

int i;

cin>>i;

printf("%d",i/2);

printf("%d",i/-2);

伪汇编：

  mov eax,i

  cdq  ;上整转下整

  sub eax,edx

sar eax,1

neg eax    ; i/-2则多该行汇编

有符号数±2^n  

int i;

cin>>i;

printf("%d",i/2^n);

printf("%d",i/-2^n);

伪汇编：

    mov eax,i

      cdq  ;上整转下整

      and edx,2^n-1

      add eax,edx  或 lea edi,[eax+edx]

      sar eax,n        sar edi,n

      neg eax    ;  -2^n则多该行汇编

无符号数2^n

unsigned int i;  

cin>>i;

printf("%d",i/2^n);

伪汇编：

shr eax,n

定式四：除数为普通常量

有符号数    

  int i;

        cin>>i;

        printf("%d",i/c);

伪汇编:

形式1：Debug

             mov eax,i

    mov ecx,c

    cdq  或xor edx,edx       

            idiv  eax,ecx

形式2：Release

         mov eax, M     

imul i

空  或add edx,i   或 sub edx,i   ; 调整i*M用

//上整转下整，加符号位

         sar  edx,SarNum   ;SarNum=0,则没有该行

        mov eax,edx               mov eax,edx

        shr eax,1F          或     cdq

        add edx,eax                sub eax,edx

无符号数

unsigned int i;

cin>>i;

printf("%d",i/c);

伪汇编:

形式1：Debug

            mov eax,i

   mov ecx,c

   cdq  或xor edx,edx

            div  eax,ecx

形式2：Release

         mov eax,M

         mul i

  shr edx,ShrNum    ;ShrNum=0,则没有该行

形式3：Release

         mov ecx,i

mov eax,M

         mul ecx

         sub ecx,edx

  shr ecx,1

  add ecx,edx

  shr ecx,ShrNum

三、数论结论（见附件）

四、定式证明（见附件）

附：M和n的编译计算（见附件）

编译源码剖析（见附件）

介于证明推导公式较多，不便编辑，全文见附件pdf。

下一篇，将介绍  利用  正则表达式 实现 除法反编译 的 工具，及 逆向还原 整数除法 的 方法。