流水线乱序与除法定式

流水线乱序

为了提示效率,打乱原有的指令顺序,例如:

  1. cdq
  2. lea esi, [ecx + 445]
  3. idiv esi

本来cdqidiv相关性更高,但是cdqidiv都会用到 edx,所以插入与edx无关的lea指令,可以小幅提高效率。

除法定式

除法的优化原则,就是将除法指令转为等效的乘法和移位。
简化版推导过程如下:
设 a 为被除数,c 为除数,q 为商,r 为余数:

ac=q...r


除以 c 等于乘以 c 的倒数可得:

a1c


c 的倒数,分子分母同时乘以2的n次幂,可得:

a12nc2n


等于

a2nc12n


其中

2nc

是在编译期间就能计算好的,称为 MagicNumber。对于 VC 系列编译器,对 n 的取值都是大于等于32,所以除法最后变成:

(aMagicNumber)>>n


x86汇编中的乘法指令imul或者mul,都是用 eax存放低32位数据,edx 存放高32位数据,编译器生成除法指令时可能产生如下指令:

  1. sar edx, K

相当于乘法结果右移32位后再右移K位,带入到公式中:

(aMagicNumber)>>(32+K)


又因为:

MagicNumber=2nc


所以,还原除数 c 的公式为:

c=2nMagicNumber


最终:

c=232+KMagicNumber

总结,遇到除法,首先要想到公式

c=232+KMagicNumber


K 会出现在sar edx, K中。下面的各种情况,都是对 MagicNumber 做一些调整,例如检查符号位等等,但是思路是一样的,优先使用这个公式还原。

除数为正数,且为2的幂

  1. mov eax, dword ptr [ebp-4]
  2. cdq
  3. sub eax, edx ;或者 add edx, 7 add eax, edx
  4. sar eax, K

cdq将符号扩展到 edx,sub eax, edx执行的操作是将 eax 减去高位 edx,是为了调整移位取整的问题,被除数为正数,edx 为0,等于没处理;被除数为负数,相当于加1;add edx, 7 add eax, edx这两句同理,目的都为解决被除数的符号问题,最后右移完成除法。
所以,最后还原为eax / (2^K)

除数为正数,且为非2的幂

情况1:

  1. mov eax, MagicNumber
  2. imul A
  3. sar edx, K
  4. mov reg, edx
  5. shr reg, 1Fh
  6. add edx, reg
  7. ; 此后直接使用 edx 的值,eax 弃而不用

还原为edx = A / { (2^ k+32 / MagicNumber) }

情况2:

  1. mov eax, MagicNumber (大于0x7FFFFFFFh)
  2. imul A
  3. add edx, reg
  4. sar edx, K
  5. mov reg, edx
  6. shr reg, 1Fh
  7. add edx, reg
  8. ; 此后直接使用 edx 的值

还原为edx = A / {2^(K + 32) / MagicNumber }

无符号除数,且为非2的幂:

  1. mov eax, MagicNumber
  2. mul A
  3. sub reg, edx
  4. shr reg, 1
  5. add reg, edx
  6. shr reg, K ;这句可能没有,如果没有,则 K 值为0,如果有就是 K + 1
  7. ; 此后直接使用 reg 的值,eax 弃而不用

还原为reg = (unsigned)A / { (2^(k + 1 +32) / (2^32 + MagicNumber) }

除数为负数,且为2的幂

  1. mov eax, dword ptr [ebp-4]
  2. cdq
  3. sub eax, edx ;或者 add edx, 7 add eax, edx
  4. sar eax, K
  5. neg eax

还原为eax / { -(2^K) },参考“除数为正数,且为2的幂”的情况,将结果neg取反,表示除数为负。

除数为负数,且为非2的幂

两种情况,但是还原方式是一样的。

情况1:

  1. mov eax, MagicNumber (大于0x7FFFFFFFh)
  2. imul A
  3. sar edx, K
  4. mov reg, edx
  5. shr reg, 1Fh
  6. add edx, reg
  7. ; 此后直接使用 edx 的值

还原为edx = A / { - (2^(k+32) / (2^32 - MagicNumber) ) }

情况2:

  1. mov eax, MagicNumber (小于0x7FFFFFFFh)
  2. imul A
  3. sub edx, reg
  4. sar, edx, K
  5. mov reg, edx
  6. shr reg, 1Fh
  7. add edx, reg
  8. ; 此后直接使用 edx 的值

还原为edx = A / { - (2^(k+32) / (2^32 - MagicNumber) ) }

分享到:

0 条评论

昵称

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

沙发空缺中,还不快抢~