代码逆向(八)——除法与取模运算的识别与优化原理

2019-04-14 08:19发布

站内文章 / 模拟电子
12576 0 1107
转自:http://blog.csdn.net/yangbostar/article/details/58682791.9.1、除法与倒数相乘
    何为倒数相乘？很简单，编译器世界中倒数相乘的中心思想其实就是用乘法来代替除法运算。它的原理很简单，就是将被除数乘以除数的倒数，其公式为x/y = x*(1/y)，我们拿10/2作为例子，我可以得出以下推论：

由 公式x/y = x*(1/y) 可得 10/2 = 10*(1/2) = 10*0.5

    编译器也正是由这个公式才得以将除法转换为除法，但是编译器为什么要这样做呢？原因同样很简单，因为乘法的运算速度会比除法快4倍左右，在现有的Intel指令集中，就属除法指令最慢，因此将其优化为乘法的理由显得很充分，但是这么做似乎有不妥之处，让我们看看这是为什么……

int _tmain(int argc, _TCHAR* argv[])
{
    int   a = 5/2;
    float b = 5.0/2.0;

  printf("    5/2 = %d/r/n5.0/2.0 = %1.1f",a,b);
  return 0;
}
-Export--------------------------------
    5/2 = 2
5.0/2.0 = 2.5

    很明显，我们没能充分考虑到浮点类型，一般情况下，在C语言中1除以任何数其结果皆为0，这个问题显得比较严重，我们要怎样才能解决它呢？


1.9.2、倒数相乘与定点运算的配合

    为了使除法的倒数相乘优化成为可能，编译器使用了定点运算方案来表示小数。

    那么何为定点运算，定点运算有什么特点呢？

    我们都知道一般情况下我们的小数都是用浮点类型来表示的，有一位会记录当前的小数点位于那里，当然还有其他的一些转换规则，这些都不是本文所关心的，我们只需知道浮点类型的小数可以位于任意一位，也就是说“小数点是浮动的”。

    而定点运算根据字面意思来理解就是“小数点是固定的”，这种小数的定点表示法有很多优点，首当其冲的就是效率上的提高。当然，作为代价，同样也必须承受随之而来的精度上的丢失。

    那么，这个定点表示法又是怎样运作的呢？它怎么就能保存小数信息呢？这部分内容很难寻找，经过大量近似资料的启示与笔者的试验，最终才证实其原理其实很简单，这首先还要从定点表示法的小数点位置与精度说起。

    首先，编译器一般都将小数点定位在第一位，因为要表示一个数的倒数，那么用小数表示的话必然是一个小于1的数，例如8的倒数与12345678的倒数分别为0.125与~0.000000081，因此其整数部分恒为0。

    其次，就是精度问题，例如我们用一个4bit大小的数来表述小数的话，那么它的精度就是0.0625，其表示的整数每加1或减1，其表示的小数就随之增加或减少0.0625，如下所示：

确定精度：
┏━━┳━━━━━┳━━━━━━┳━━━━━━┳━━━━━━━┓
┃Bit ┃1         ┃2           ┃3           ┃4             ┃
┣━━╋━━━━━╋━━━━━━╋━━━━━━╋━━━━━━━┫
┃精度┃2^-1 [0.5]┃2^-2 [0.25] ┃2^-3 [0.125]┃2^-4 [0.0625] ┃
┗━━┻━━━━━┻━━━━━━┻━━━━━━┻━━━━━━━┛

例子：
 0001 = 1 = 1*0.0625 = 0.0625
 0010 = 2 = 2*0.0625 = 0.125
 0101 = 5 = 5*0.0625 = 0.3125

    而对于32位的编译器来说，只不过是将上面的例子的位数扩充了一下，因此精度也就随之提高，我们直接看例子：

精度：2^-32 = 0.00000000023283064365386962890625

例子：
┏━━┳━━━━━━┳━━━━━━━━━━┳━━━━━━━━━┓
┃除数┃倒数(小数)  ┃定点运算 : 小数/精度┃舍去小数点的16进制┃
┣━━╋━━━━━━╋━━━━━━━━━━╋━━━━━━━━━┫
┃3   ┃0.3333333333┃1431655765.190167756┃0x55555555        ┃
┣━━╋━━━━━━╋━━━━━━━━━━╋━━━━━━━━━┫
┃5   ┃0.2         ┃858993459.2000000000┃0x33333333        ┃
┣━━╋━━━━━━╋━━━━━━━━━━╋━━━━━━━━━┫
┃11  ┃0.0909090909┃390451572.3245912064┃0x1745D174        ┃
┣━━╋━━━━━━╋━━━━━━━━━━╋━━━━━━━━━┫
┃59  ┃0.0169491525┃72796055.68241664000┃0x0456C797        ┃
┣━━╋━━━━━━╋━━━━━━━━━━╋━━━━━━━━━┫
┃99  ┃0.0101010101┃43383508.03606568960┃0x0295FAD4        ┃
┗━━┻━━━━━━┻━━━━━━━━━━┻━━━━━━━━━┛

    有了上面的基础，我们就可正式进入除法优化的神秘领地了……


1.9.3、除法运算的识别与优化原理

    大多数情况下除法是最好识别的，因为其特征很明显。另外，在上一节《乘法的识别与优化原理》笔者详细的讲解了编译器利用位移指令(sar、shr)的优化情况，很明显的，除法必然也会存在这种优化，但是鉴于其基础知识已经讲解且原理比较简单，因此除法的位移优化在本小节中将一带而过，我们将重点放在倒数相乘相关的优化上。

    按照惯例，请读者阅读以下源代码，并猜测编译器会将其进行怎样的优化：

int _tmain(int argc, _TCHAR* argv[])
{
    printf("03=%d",argc/3);  //-*
    printf("05=%d",argc/5);  // |-> 注意，这些除数的倒数在上一段“1.9.2节”中有提及
    printf("11=%d",argc/11); // |
    printf("59=%d",argc/59); //-*
    printf("04=%d",argc/4);
    printf("64=%d",argc/64);
    return 0;
}

    下面我们先看看它的Debug版部分反汇编代码：
    (再次提醒一下，Debug的反汇编代码并不是完整的，与逻辑无关的部分代码都已经被笔者删除了，如有疑问请查看第1.3节)

.text:004113A0     push ebp
.text:004113A1     mov ebp, esp
.text:004113A3     sub esp, 0C0h
......             ......
.text:004113BE     mov eax, [ebp+argc]
.text:004113C1     cdq                                 ; 此指令的意思是将edx扩展为eax的高位，将其扩展为64位
.text:004113C2     mov ecx, 3                          ; ecx = 3(除数)
.text:004113C7     idiv ecx                            ; edx:eax = eax/ecx = argc/3
.text:004113CB     push eax
.text:004113CC     push offset Format                  ; "03=%d"
.text:004113D1     call ds:__imp__printf
.text:004113D7     add esp, 8
......             ......
.text:004113E1     mov eax, [ebp+argc]
.text:004113E4     cdq
.text:004113E5     mov ecx, 5
.text:004113EA     idiv ecx

热门文章