14.4 得到除数

14.4.1 变形＃1

通常，代码具有这样一种形式

  1. mov     eax, MAGICAL CONSTANT
  2. imul    input value
  3. sar     edx, SHIFTING COEFFICIENT ; signed division by 2^x using arithmetic shift right
  4. mov     eax, edx
  5. shr     eax, 31
  6. add     eax, edx

我们将32位的magic系数表示为M，移位表示为C，除数表示为D

我们得到的除法是

14.4 得到除数 - 图1

举个例子

清单14.5：优化模式 MSVC2012

  1. mov     eax, 2021161081     ; 78787879H
  2. imul    DWORD PTR _a$[esp-4]
  3. sar     edx, 3
  4. mov     eax, edx
  5. shr     eax, 31             ; 0000001fH
  6. add     eax, edx

即

14.4 得到除数 - 图2

比32位的数字大，为了方便，于是我们使用用Wolfram Mathematica软件。

  1. In[1]:=N[2^(32+3)/2021161081]
  2. Out[1]:=17.

因此例子中的代码得到结果是17。

对于64位除法来说，原理是一样的，但是应该使用264来代替232。

  1. uint64_t f1234(uint64_t a)
  2. {
  3.     return a/1234;
  4. };

清单14.7：MSVC2012/Ox

  1. f1234   PROC
  2.         mov     rax, 7653754429286296943 ; 6a37991a23aead6fH
  3.         mul     rcx
  4.         shr     rdx, 9
  5.         mov     rax, rdx
  6.         ret     0
  7. f1234   ENDP

清单14.8：Wolfram Mathematica

  1. In[1]:=N[2^(64+9)/16^^6a37991a23aead6f]
  2. Out[1]:=1234.

14.4.2 变形＃2

忽略算数移位的变形也是存在的

  1. mov     eax, 55555556h ; 1431655766
  2. imul    ecx
  3. mov     eax, edx
  4. shr     eax, 1Fh

更加简洁

14.4 得到除数 - 图3

在这个例子中

14.4 得到除数 - 图4

再用一次Wolfram Mathematica

  1. In[1]:=N[2^32/16^^55555556]
  2. Out[1]:=3.

得到的除数是3