5.7 汇编语言:汇编高效乘法运算
汇编语言是一种面向机器的低级语言,用于编写计算机程序。汇编语言与计算机机器语言非常接近,汇编语言程序可以使用符号、助记符等来代替机器语言的二进制码,但最终会被汇编器编译成计算机可执行的机器码。
乘法指令是一种在CPU中实现的基本算术操作,用于计算两个数的乘积。在汇编语言中,乘法指令通常是通过mul(无符号乘法)
和imul(有符号乘法)
这两个指令实现的。由于乘法指令在执行时所消耗的时钟周期较多,所以编译器在优化代码时通常会尝试将乘法操作转换为更高效的加法、和移位操作。
对于较小的数,编译器可能会选择将乘法操作直接转换为加法操作。例如,将表达式
a * b
转换为a + a + ... + a
(b次相加)的形式。这种方式可以通过循环展开、代码向量化等技术来优化。对于较大的数,编译器可能会使用位移和移位操作来代替乘法。例如,将表达式
a * b
转换为a << n + a << m
的形式,其中n
和m
为符合条件的位数。这种方式可以通过位移指令的高效性来加速运算。
当以上方式均无法进行优化时,编译器才会使用mul/imul
指令来执行乘法操作。这两条指令可以对无符号数和有符号数进行乘法运算,即便这两条指令会使用更多的时钟周期,但乘法指令的计算效率相对于其他指令DIV
来说仍然较低,因此在编写高效代码时,应尽可能地避免使用乘法操作,并结合使用上面提到的技巧进行优化。
7.1 使用IMUL指令完成乘法
要计算乘法在不考虑执行效率的情况下编译器通常会直接使用imul
指令完成计算,imul指令在一些情况下可以比其他乘法指令(如mul指令)更快地执行乘法运算,但性能较低的原因主要是由于imul指令通常用于有符号数的乘法运算,并且在执行时需要处理符号位的扩展和溢出问题,这转换成了额外的指令和时钟周期的消耗。如果对于无符号整数或需要使用寄存器的低位或者高位结果的情况,使用imul指令可以提供一定的优势。
计算乘法时应遵循:
- 如果乘数与被乘数都是
8位
则把AL
做乘数,结果放在AX
中 - 如果乘数与被乘数都是
16位
将把AX
做乘数,结果放在EAX
中 - 如果乘数与被乘数都是
32位
将把EAX
做乘数,结果放在EDX:EAX
中
乘法指令计算很简单,只需要累加乘数即可,如下所示则是一个简单的计算三个数相乘的汇编实现;
.data |
7.2 使用LEA指令替换乘法
在实际编程中,我们可以使用LEA指令来替代乘法操作,从而提高代码的执行效率。但读者需要注意,在使用LEA计算乘法时必须要保证乘数是2
的次幂,并且乘数的范围必须是2/4/8
这三个区间才可使用该指令,我们使用汇编来实现计算eax*8+2
其汇编指令如下。
- 假设
eax=5
计算eax * 8 + 2
的结果,拆分过程如下: - 1.计算
lea ebx,dword ptr ds:[eax * 8 + 2]
这就相当于计算ebx = (eax * 8) +2
直接可得到结果。
第一个案例比较简单,可直接使用一条lea指令即可完成计算过程,只要保证被乘数是2的次幂即可。
.data |
7.3 使用LEA指令拆分计算
如果我们计算的乘法超出了2/4/8
次幂范围,则需要对乘法进行拆分,拆分时也应遵循2的次幂原则,拆分后在分开来计算。
- 假设
eax=3
计算15 * eax
的结果,拆分过程如下: - 1.计算
lea edx,[eax * 4 + eax]
这就相当于计算edx = (4 * eax) + eax = 5eax
其中的每个edx
就相当于5个eax
- 2.计算
lea edx,[edx * 2 + edx]
这就相当于计算edx = (5 * eax) * 2 + (5 * eax)
- 3.计算
(5eax * 2) = 10eax
接着计算(5 * eax) = 5eax
最后得出10eax + 5eax
- 4.经过该过程可得出
eax * 15 = 45
最终计算3*15=45
得到最终结果.
这个计算过程看似复杂,但如果将其转化为汇编指令那么只需要两条即可实现快速乘法运算。
.data |
7.4 使用LEA指令递减计算
如果计算乘法时乘数非2的次幂,这种情况下需要减去特定的值,例如当我们计算eax * 7
时,由于7非二的次幂,我们无法通过lea
指令进行计算,但我们可以计算eax * 8
计算出的结果减去一个eax
同样可以得到正确的值。
- 假设
eax=3
计算eax * 7 + 10
的结果,拆分过程如下: - 1.计算
lea edx,dword ptr ds:[eax * 8]
这就相当于计算edx = (8 * eax)
- 2.计算
sub edx,eax
这就相当于计算edx = (8 * eax) - eax
- 3.计算
add edx,10
这就相当于计算edx = ( (8 * eax) - eax ) + 10
- 4.经过如上计算,我们就可以计算出
eax * 7 + 10
的最终结果
这个计算过程看似复杂,但其实在汇编层面并不难构建,如下分别实现计算两个表达式求值过程。
.data |
7.5 使用SHL计算无符号乘法
通过使用逻辑左移同样可以实现2的次幂的高速乘法运算,但逻辑左移只能用于计算无符号乘法,且只能计算被乘数是2的次方的算式。
计算时我们需要参考次方表,这里我列举出几个常用的次方数值:
次方表: 1=>2 2=>4 3=>8 4=>16 5=>32 6=>64 7=>128
次方表: 8=>256 9=>512 10=>1024 11=>2048 12=>4096 13=>8192 14=>16384
假设
eax=3
计算eax * 8 + 10
的结果,拆分过程如下:1.计算
shl eax,3
这就相当于计算eax = eax * 2 ^(次方) 3
其公式相当于计算eax = eax * 8
2.计算
add eax,10
这就相当于计算eax = (eax * 8) + 10
3.最终即可得到计算结果也就是
3*8+10
得到34
通过使用逻辑左移,我们可以实现快速无符号乘法运算,如下代码是效率最高的一种。
.data |
7.6 使用SAL计算有符号乘法
通过使用算数左移同样可以实现2的次幂的高速乘法运算,与逻辑左移不同,算术左移只能计算有符号乘法,且只能计算被乘数是2的次方的算式。
计算时我们需要参考次方表,这里我列举出几个常用的次方数值:
次方表: 1=>2 2=>4 3=>8 4=>16 5=>32 6=>64 7=>128
次方表: 8=>256 9=>512 10=>1024 11=>2048 12=>4096 13=>8192 14=>16384
假设
eax=-5,ebx=3
计算(eax * 8) + (ebx * 4)
的结果,拆分过程如下:1.计算
sal eax,3
这就相当于计算eax = (eax * 2 ^ 3 )
其公式相当于计算eax = eax * 8
结果是一个有符号数2.计算
shl ebx,2
这就相当于计算ebx = (ebx * 2 ^2)
其公式相当于计算ebx = ebx * 4
结果是一个无符号数3.最终将有符号与无符号数通过
add eax,ebx
相加,即可得到(eax * 8) + (ebx * 4)
的最终结果-28
如下是通过算数左移,实现2的次幂的高速乘法运算,我们可以将算数运算与逻辑运算相加通过此方式提高运算效率。
.data |
乘法优化的知识点基本就这些,除了两个未知变量的相乘无法优化外,其他形式的乘法运算均可以进行优化,如果表达式中存在一个常量值,那编译器则会匹配各种优化策略,最后对不符合优化策略的运算进行调整,如果真的无法优化,则会使用原始乘法指令计算。