526互联

5.7 汇编语言：汇编高效乘法运算

发布时间 2023-08-23 09:17:23作者: lyshark

汇编语言是一种面向机器的低级语言，用于编写计算机程序。汇编语言与计算机机器语言非常接近，汇编语言程序可以使用符号、助记符等来代替机器语言的二进制码，但最终会被汇编器编译成计算机可执行的机器码。

乘法指令是一种在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
    x DWORD ?
    y DWORD ?
    z DWORD ?
    szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
    main PROC
      mov dword ptr ds:[x],10
      mov dword ptr ds:[y],24
      mov dword ptr ds:[z],18
      
      ; 计算 x * y * z
      mov eax,dword ptr ds:[x]
      imul eax,dword ptr ds:[y]
      imul eax,dword ptr ds:[z]
      invoke crt_printf,addr szFmt,eax
    main ENDP
END main

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
  x DWORD ?
  szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
  main PROC
    ; 针对乘法的lea指令优化
    mov dword ptr ds:[x],5
    
    mov eax,dword ptr ds:[x]               ; eax = x
    xor ebx,ebx                            ; ebx = 0
    lea ebx,dword ptr ds:[eax * 8 + 2]     ; ebx = eax * 8 + 2
    invoke crt_printf,addr szFmt,ebx
    
    invoke ExitProcess,0
  main ENDP
END main

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
  x DWORD ?
  szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
  main PROC
    ; 针对乘法的lea指令优化
    mov dword ptr ds:[x],3
    
    ; 如果使用lea计算乘法,则乘数必须是2/4/8
    mov eax,dword ptr ds:[x]               ; eax = 3
    lea edx,dword ptr ds:[eax * 4 + eax]   ; edx = 4eax + eax 得出 5eax,也就是说每一个edx就代表5个eax
    lea edx,dword ptr ds:[edx * 2 + edx]   ; edx = (5eax * 2) + 5eax 最终得出 15eax
    invoke crt_printf,addr szFmt,edx       ; edx = eax * 15 计算后得出 45
    
    invoke ExitProcess,0
  main ENDP
END main

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
  x DWORD ?
  szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
  main PROC
    ; 针对乘法的lea指令优化
    mov dword ptr ds:[x],3
    
    ; 如果计算乘法时乘数非2的次幂,则此时需要减

    ; 计算 edx = eax * 7 + 10
    mov eax,dword ptr ds:[x]               ; eax = 3 => 计算 eax * 7 + 10
    lea edx,dword ptr ds:[eax * 8]         ; edx = eax * 8
    sub edx,eax                            ; edx = edx - eax
    add edx,10                             ; edx = edx + 10
    invoke crt_printf,addr szFmt,edx       ; edx = eax * 7 + 10
    
    ; 计算 edx = eax * 3 - 7
    mov eax,dword ptr ds:[x]               ; eax = 3 => 计算 eax * 3 - 7
    lea edx,dword ptr ds:[eax * 2]         ; edx = eax * 2
    add edx,eax                            ; edx = edx + eax
    sub edx,7                              ; edx = edx - 7
    invoke crt_printf,addr szFmt,edx       ; edx = eax * 3 - 7
    
    invoke ExitProcess,0
  main ENDP
END main

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
  x DWORD ?
  szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
  main PROC
    mov dword ptr ds:[x],3
    
    ; 计算 eax = eax * 2 ^ 1 相当于计算 eax * 2
    mov eax,dword ptr ds:[x]
    shl eax,1
    invoke crt_printf,addr szFmt,eax
    
    ; 计算 eax = eax * 2 ^ 2 相当于计算 eax * 4
    mov eax,dword ptr ds:[x]
    shl eax,2
    invoke crt_printf,addr szFmt,eax
    
    ; 计算 eax = eax * 2 ^ 3 相当于计算 eax * 8
    mov eax,dword ptr ds:[x]
    shl eax,3
    add eax,10
    invoke crt_printf,addr szFmt,eax

    invoke ExitProcess,0
  main ENDP
END main

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
  x DWORD ?
  y DWORD ?
  szFmt BYTE '计算结果: %d',0dh,0ah,0
.code
  main PROC
    mov dword ptr ds:[x],-5
    mov dword ptr ds:[y],3
    
    ; 计算 eax = eax * 2 ^ 1 相当于计算 eax * 2
    mov eax,dword ptr ds:[x]
    sal eax,1
    invoke crt_printf,addr szFmt,eax
    
    ; 计算 eax = eax * 2 ^ 2 相当于计算 eax * 4
    mov eax,dword ptr ds:[x]
    sal eax,2
    invoke crt_printf,addr szFmt,eax

    ; 计算 eax = (eax * 2 ^ 3 ) + (ebx * 2 ^2) 相当于计算 (eax * 8) + (ebx * 4)
    mov eax,dword ptr ds:[x]
    mov ebx,dword ptr ds:[y]
    sal eax,3                  ; eax * 8 (有符号乘法)
    shl ebx,2                  ; ebx * 4 (无符号乘法)
    add eax,ebx                ; eax + ebx
    invoke crt_printf,addr szFmt,eax

    invoke ExitProcess,0
  main ENDP
END main

乘法优化的知识点基本就这些，除了两个未知变量的相乘无法优化外，其他形式的乘法运算均可以进行优化，如果表达式中存在一个常量值，那编译器则会匹配各种优化策略，最后对不符合优化策略的运算进行调整，如果真的无法优化，则会使用原始乘法指令计算。

本文作者： 王瑞
本文链接： https://www.lyshark.com/post/ade8241c.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！