狗儿

热爱的话就坚持吧~

0%

【转】除法与取模运算的识别与优化原理

我是很少转载文章的,可是这篇写得实在是太棒了。虽然写于12年,但是依然具有学习的意义。

我会在此文基础上,在下一篇博文对模运算做一些总结。

本文转自zeroevent,我对文章排版做了一定的修改。

1.9.1、除法与倒数相乘

何为倒数相乘?很简单,编译器世界中倒数相乘的中心思想其实就是用乘法来代替除法运算。它的原理很简单,就是将被除数乘以除数的倒数,其公式为x/y = x*(1/y),我们拿10/2作为例子,我可以得出以下推论:

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

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

1
2
3
4
5
6
7
8
9
10
11
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]

例子:

1
2
3
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)的优化情况,很明显的,除法必然也会存在这种优化,但是鉴于其基础知识已经讲解且原理比较简单,因此除法的位移优化在本小节中将一带而过,我们将重点放在倒数相乘相关的优化上。

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

1
2
3
4
5
6
7
8
9
10
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节)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
.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
.text:004113EE push eax
.text:004113EF push offset a05D ; "05=%d"
.text:004113F4 call ds:__imp__printf
.text:004113FA add esp, 8
...... ......
...... ......
.text:0041144A mov eax, [ebp+argc]
.text:0041144D cdq ; 扩展为64位 edx:eax
.text:0041144E and edx, 3 ; 选取edx的低2位(0x3 = 00000011)
.text:00411451 add eax, edx ; 当被除数小于除数时,将结果清零【注1】
.text:00411451 ;
.text:00411451 ; -= 注1 =-
.text:00411451 ; (以下为扩展知识,非必须掌握)
.text:00411451 ; 这个操作其实其最终目的就是控制特殊情况下的计算结果,
.text:00411451 ; 《黑客反汇编揭秘》对edx的解释是“数值符号位”,这是错误
.text:00411451 ; 的!在此提醒各位读者注意……
.text:00411451 ; 我们知道,其实这种除数为正的除法计算无非就四种情况:
.text:00411451 ; 1、被除数>除数
.text:00411451 ; 2、被除数<除数
.text:00411451 ; 3、负的被除数>除数
.text:00411451 ; 4、负的被除数<除数
.text:00411451 ; 根据整型除法的规则,任何被除数如果除以比自己大的除数
.text:00411451 ; 其结果皆为0(例如1/2=0或1/9999=0)。
.text:00411451 ; 但是作为编译器来讲,必须要考虑到以上所有情况,按照我
.text:00411451 ; 们正常人的思路,既然后面必须使用sar指令,那么我们只需要保
.text:00411451 ; 证这种特殊情况下的除法计算在右移后为0即可。
.text:00411451 ; 这其实很简单,只需要给被除数加上一个比出书小一的数即
.text:00411451 ; 可,原理如下所示:
.text:00411451 ; -16/4 = (-16+3)>>2 = -13>>2 = -4
.text:00411451 ; -5/4 = (-5+3) >>2 = -2 >>2 = -1
.text:00411451 ; -4/4 = (-4+3) >>2 = -1 >>2 = -1
.text:00411451 ; -3/4 = (-3+3) >>2 = 0 >>2 = 0
.text:00411451 ; -2/4 = (-2+3) >>2 = 1 >>2 = 0
.text:00411451 ; 通过上面的几个例子相信各位都能明白之中的原理了,但是
.text:00411451 ; 我们并没有将被除数为正数的情况考虑进去。而通过编译器生成
.text:00411451 ; 的汇编代码则给了我们很好的提示,就是利用and指令在高位取
.text:00411451 ; 值,这也就是为什么要将被除数扩展为64位的根本原因。
.text:00411451 ; 通过cdq将eax扩展为64位后,cpu将以edx:eax的方式来表示
.text:00411451 ; 数据,那么edx肯定就是高位了,而我们的编译器编译出来的代码
.text:00411451 ; 始终都是32位的,因此edx寄存器理论上是根本用不上的。
.text:00411451 ; 但是有一种情况下例外,就是被除数为负数时,edx寄存器里
.text:00411451 ; 面的值是0xFFFFFFFF(二进制全1),反之则二进制全0。
.text:00411451 ; 利用这个特性编译器使用了与(and)运算来巧妙地达到了目的,
.text:00411451 ; 这样一来如果被除数为负数,那么将任何数与edx进行and运算都得
.text:00411451 ; 那个数本身,反之则恒为0。
.text:00411451 ; 总结起来原理虽非常简单,但也不得不感叹人类智慧的伟大…
.text:00411451
.text:00411451
.text:00411453 sar eax, 2 ; 带符号右移2位,相当于除以4
.text:00411458 push eax
.text:00411459 push offset a04D ; "04=%d"
.text:0041145E call ds:__imp__printf
.text:00411464 add esp, 8
...... ......
.text:0041146E mov eax, [ebp+argc]
.text:00411471 cdq
.text:00411472 and edx, 0Fh
.text:00411475 add eax, edx
.text:00411477 sar eax, 4
.text:0041147C push eax
.text:0041147D push offset a16D ; "16=%d"
.text:00411482 call ds:__imp__printf
.text:00411488 add esp, 8
...... ......
...... ......
.text:004114B6 xor eax, eax
...... ......
.text:004114C8 mov esp, ebp
.text:004114CA pop ebp
.text:004114CB retn

通过上面例子可知,虽然Debug模式下未开启任何优化,不过在除数为2的次方的情况下,编译器仍对其做了不小的优化,那么Release版就更是可想而知了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
.text:00401000   push esi
.text:00401001 mov esi, [esp+4+argc]
.text:00401005 mov eax, 55555556h ; 注意这里,比我们在“1.9.2节”中算出来的值大1
.text:0040100A imul esi ; argc*(1/3),结果保存在edx:eax组成的64位寄存器里
.text:0040100C mov eax, edx ; 去掉小数部分【注2】
.text:0040100C ;
.text:0040100C ; -= 注2 =-
.text:0040100C ; 记得我们在上面学习定点计算时讲过一句话“编译器一
.text:0040100C ; 般都将小数点定位在第一位,因为要表示一个数的倒数,那
.text:0040100C ; 么用小数表示的话必然是一个小于1的数”。
.text:0040100C ; 因此,当imul指令变向将其扩展为64位后,其小数点的
.text:0040100C ; 位置是不会变得,所以始终保证小数点都在一个固定的位置,
.text:0040100C ; 在这里也就是eax里的最高位上。
.text:0040100C ; 由此可知,如果想舍去小数,那么只需要清除eax里的值
.text:0040100C ; 即可。
.text:0040100C ; 当然,纵观汇编指令的上下文可知,这一步操作还有另
.text:0040100C ; 外的一个目的--备份,将edx中的值备份一份,以便于简单高
.text:0040100C ; 效的取出其符号位。
.text:0040100C ;
.text:0040100C
.text:0040100E shr eax, 1Fh ; 取符号位
.text:00401011 push edi
.text:00401012 mov edi, ds:__imp__printf
.text:00401018 add eax, edx ; 将符号位加到结果上【注3】
.text:00401018 ;
.text:00401018 ; -= 注3 =-
.text:00401018 ; 对于这步操作应该会让很多读者感到困惑,为什么要加
.text:00401018 ; 上符号位呢?其实很简单,就是为了遵守整数除法的规则。
.text:00401018 ; 让我们先看看下面几个小例子:
.text:00401018 ; ┏━━┳━━━━━━━━━━━━┳━━━━━━━━━┓
.text:00401018 ; ┃算式┃浮点结果[16进制值(64位)]┃整型结果[16进制值]┃
.text:00401018 ; ┣━━╋━━━━━━━━━━━━╋━━━━━━━━━┫
.text:00401018 ; ┃ 8/3┃ 2.67[00000002 AAAAAAB0]┃ 2[0000 0002] ┃
.text:00401018 ; ┣━━╋━━━━━━━━━━━━╋━━━━━━━━━┫
.text:00401018 ; ┃-8/3┃-2.67[FFFFFFFD 55555550]┃-2[FFFF FFFE] ┃
.text:00401018 ; ┗━━┻━━━━━━━━━━━━┻━━━━━━━━━┛
.text:00401018 ; 通过上面的例子我们不难发现,其实这个加法只是为了兼
.text:00401018 ; 容负数,因为负数的编码规则与正数不同,仅此而已。
.text:00401018 ;
.text:00401018
.text:0040101A push eax
.text:0040101B push offset Format ; "03=%d"
.text:00401020 call edi ; __imp__printf
.text:00401022 mov eax, 66666667h ; 注意这里,比我们在“1.9.2节”中算出来的值大了1倍多
.text:00401027 imul esi
.text:00401029 sar edx, 1 ; 将整数部分右移1位(既除2),恢复到原来的数值。
.text:0040102B mov ecx, edx
.text:0040102D shr ecx, 1Fh
.text:00401030 add ecx, edx
.text:00401032 push ecx
.text:00401033 push offset a05D ; "05=%d"
.text:00401038 call edi ; __imp__printf
.text:0040103A mov eax, 2E8BA2E9h
.text:0040103F imul esi
.text:00401041 sar edx, 1
.text:00401043 mov eax, edx
.text:00401045 shr eax, 1Fh
.text:00401048 add eax, edx
.text:0040104A push eax
.text:0040104B push offset a11D ; "11=%d"
.text:00401050 call edi ; __imp__printf
.text:00401052 mov eax, 22B63CBFh ; 比我们在“1.9.2节”中算出来的值大了8倍多
.text:00401057 imul esi
.text:00401059 sar edx, 3 ; 将整数部分右移3位(既除8),恢复到原来的数值。
.text:0040105C mov ecx, edx
.text:0040105E shr ecx, 1Fh
.text:00401061 add ecx, edx
.text:00401063 push ecx
.text:00401064 push offset a59D ; "59=%d"
.text:00401069 call edi ; __imp__printf
.text:0040106B mov eax, esi
.text:0040106D cdq ;-*
.text:0040106E and edx, 3 ; |
.text:00401071 add eax, edx ; |-> 与在Debug版中的优化一模一样,为了节省篇幅后面就省略掉了
.text:00401073 sar eax, 2 ; |
.text:00401076 push eax ;-*
.text:00401077 push offset a04D ; "04=%d"
.text:0040107C call edi ; __imp__printf
...... ......
.text:0040108A push offset a16D ; "16=%d"
...... ......
.text:0040109D push offset a64D ; "64=%d"
...... ......
.text:004010A4 add esp, 38h
.text:004010A7 pop edi
.text:004010A8 xor eax, eax
.text:004010AA pop esi
.text:004010AB retn

后面除数为2的次方的优化没什么可说的,与Debug版里一模一样,但是上面的除法优化可能是有些读者很困惑,这究竟是为什么呢?我们先看看下面这张表:

除数 倒数(小数) 定点运算 : 小数/精度 舍去小数点的16进制 反汇编中对应的值 (1/除数)×2 (1/除数)×8
3 0.3333333333 1431655765.190167756 0x55555555 0x55555556 - -
5 0.2 858993459.2000000000 0x33333333 0x66666667 0x66666666 -
11 0.0909090909 390451572.3245912064 0x1745D174 0x2E8BA2E9 0x2E8BA2E8 -
59 0.0169491525 72796055.68241664000 0x0456C797 0x22B63CBF - 0x22B63CBE

由上表可知,不管我们反汇编中体现出来的值最终比实际计算出来的值大几倍,而且都是2的次方,例如11的倒数对应的是大2倍,而59对应的是大8倍。

其次反汇编中体现出来的值不管比原值大几倍或是大致没变,都要比原值大1。

着看起来似乎有些怪异,我们先想想后面这种情况,想想为什么非要大个1呢?它为什么不大2或100呢?这其实不难理解,很明显的与精度有关,我们拿除数为59的定点运算结果72796055.68241664000来说,在将其转为16进制后,它的小数会直接被舍去,而按照四舍五
入的原则其实是应该加1的,但是实际并没有这样做。

编译器在进行优化时考虑到了这点,为了弥补后面丢失的小数精度,所以在最终生成代码时就统一都给加了一个1。

第二种加1的问题解决了,思维活跃的读者这时应该可以猜到第一种情况也是精度问题了。事实也正像读者们所想象的那样,将原定点表示法计算出来的值乘以一个2的倍数,就是出于精度的考虑。

让我们共同回忆一下定点表示法的特点:

(1) 计算更加简便快速
(2) 有精度问题

很明显的,当我们试图用定点表示法表示越小的小数时,其精度问题就越明显,就拿一个4位的定点小数来讲,其最小精度为0.0625,也就是说如果我们想表示0.05的话是不行的,那么除了增加位数以外,还有没有什么其他方法呢?答案是肯定的!

做法很简单,我们只需将0.05乘以5,那么我们就可以用0x4来表示它了,而且精度一丁点也没丢失,再次使用的时候只需再将其除以5即可。

不过令人沮丧的,上面的思路虽然原理是对的,但是实际情况要复杂一些,因为编译器最终是要将除法优化掉的,所以我们必须保证在数据还原时不能出现除法,这很明显要用到位移了,而位移的特点是只能转换除数为2的次方的除法,因此这就需要我们保证我们在变幻小数时将其增加的倍数也必须是2的次方。

我们拿1876523938/876523938这个例子来讲,这次我们要将其乘以4以期减少误差,其运算逻辑如下:

参考数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 此算式的浮点结果  = 2.140870
此算式的整除结果 = 2
1876523938 = 0x6FD97BA2
1/876523938定点表示 = 0x00000004
4/876523938定点表示 = 0x00000013

以普通方式计算:

1876523938/876523938 = 1876523938 * (1/876523938) = 0x6FD97BA2 * 0x00000004 = 0x00000001 BF65EE88
0x00000001 E0C00000 取整 = 0x00000001 = 1
结果为1

以编译器优化后方式计算:

1876523938/876523938 = 1876523938 * (4/876523938) = 0x6FD97BA2 * 0x00000013 = 0x00000008 4D242D06
0x00000008 4D242D06 取整 = 0x00000008
0x00000008 >> 2 = 0x00000002 = 2
结果为2

由此可见,这种计算前增加倒数值(称之为‘倒数向上圆整’)后,在将结果减去对应倍数的值(称之为‘商向下圆整’)的方法可以比较完美的解决精度问题。

到此,我们有关于除法逆向的学习就可以告一段落了,下面我们就趁热打铁,再看看另一个与除法相关的知识点。

1.9.4、取模运算的识别与优化原理

事实上当我们明白了除非运算的优化原理后,在理解取模运算就非常简单了,取模运算只不过是在除法运算的基础上再加一步而已。

那么即便是如此,我们还是有必要说一说,先看源码:

1
2
3
4
5
6
int _tmain(int argc, _TCHAR* argv[])
{
argc = argc-65;
printf("64=%d",argc);
return 0;
}

简单至极的源码呀!想必编译出来的机器码也是如此,Debug版的肯定更加友好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
.text:004113A0   push ebp
.text:004113A1 mov ebp, esp
...... ......
.text:004113BE mov eax, [ebp+argc]
.text:004113C1 sub eax, 41h
.text:004113C4 mov [ebp+argc], eax
.text:004113C7 mov eax, [ebp+argc]
.text:004113CA cdq
.text:004113CB mov ecx, 0Ah
.text:004113D0 idiv ecx ; 直到这步为止,都与除法运算一模一样
...... ......
.text:004113D4 push edx ; 看看,这就是唯一的不同之处,将高位当做参数直接压栈即可,
.text:004113D4 ; 为什么会这样?如果你这样问的话,那就证明你该读读Intel的
.text:004113D4 ; 文档了……
.text:004113D4 ;
.text:004113D4
.text:004113D5 push offset Format ; "64=%d"
.text:004113DA call ds:__imp__printf
.text:004113E0 add esp, 8
...... ......
.text:004113EA xor eax, eax
...... ......
.text:004113FC mov esp, ebp
.text:004113FE pop ebp
.text:004113FF retn

既然Debug版简单的让人窒息,那么Release版势必也不会太难了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
.text:00401000   mov ecx, [esp+argc]
.text:00401004 sub ecx, 41h
.text:00401007 mov eax, 66666667h
.text:0040100C imul ecx
.text:0040100E sar edx, 2
.text:00401011 mov eax, edx
.text:00401013 shr eax, 1Fh
.text:00401016 add eax, edx ; 到这里为止,与普通除法一样
.text:00401018 lea eax, [eax+eax*4] ; eax*5
.text:0040101B add eax, eax ; eax*2 (这两条指令的意思其实就是减商乘以10)
.text:0040101D sub ecx, eax ; ecx里保存的是被除数,eax里保存的是乘以10之后的商,
.text:0040101D ; 推算成公式就是:
.text:0040101D ; x%y = x-(x/y)*y [注:(x/y)为整除]
.text:0040101D ;
.text:0040101D ; 我们根据以上公式演算一下:
.text:0040101D ; 64 = 64-(64/10)*10 = 64-6*10 = 64-60 = 4
.text:0040101D ;
.text:0040101D ; 多么简单清晰明了……
.text:0040101D ;
.text:0040101D
.text:0040101F push ecx
.text:00401020 push offset Format ; "64=%d"
.text:00401025 call ds:__imp__printf
.text:0040102B add esp, 8
.text:0040102E xor eax, eax
.text:00401030 retn

非常顺利的完成了取模运算的学习,最后在总结一下特点:

普通除法:

1
2
3
4
5
6
mov Reg32_1, XXXXXXXXh
imul Reg32_2(被除数)
...
mov Reg32_1, edx
shr Reg32_1, 1Fh
add Reg32_1, edx

应用计算结果
(除数=XXXXXXXXh*2^-32 如果倒数被向上圆整了,那么根据sar指令后的数值向下圆整即可)

除数为2的次方:

1
2
3
4
5
mov eax, (被除数)
cdq
and edx, XXh
add eax, edx
sar eax, YYh

应用计算结果
(除数 = XXh+1 或 2^YYh)

取模运算:
除法特征
乘法计算
应用计算结果

到这里,有关于本小节的所有内容就全部结束了,虽然本小节洋洋洒洒的写了近2万字,但是这已经是笔者精简了近40多小时的结果了,虽不敢说字字珠玑,但也应该算得上是华秩之章了。