<-- Home

编译器中的整型除法优化

最近在逆向时,经常遇见这一类x86汇编代码。

...
movsx ecx,word ptr ds:[0x474C48]
mov eax,0x66666667
imul ecx
sar edx,0x3
mov ecx,edx
shr ecx,0x1F
add ecx,edx
...

熟悉逆向或者编译器底层设计的大佬对0x66666667这个数肯定不陌生,这个数是一个用于除5操作的Magic Number,那么就可以猜测这段代码是一段除法操作的代码。

我们并没有看见DIV指令,那么这段代码是如何实现除法运算的呢?DIV操作在intel x86指令中是比较慢的,为了提高程序运行的速度,我们可以用乘法代替除法运算。这就是该代码中没有DIV指令,而有IMUL指令的原因。

来详细分析一下这段代码。

首先将内存地址为0x474C48中的数据送至ecx并拓展成32位符号数,然后将其与0x66666667相乘,将存储结果高32位的edx算术右移3位,再获取edx算术右移后的值,将该值逻辑左移31位,即获取符号位(该位当被除数为正数时为0,被除数为负数时为1),将符号位与edx的值相加,获得新的高32位。

整个操作相当于 (x * 0x66666667) >> (32 + 3)

那么我们现在可能还是不明白,这个操作是怎么实现除法的?除数是多少?我们可以推导一下:

为被除数变量, 为某一常量,则有:

因为 为常量,且 的取值由编译器选择,所以 可以在编译期间计算出来。当 的取值大于等于32时,可以直接调整乘法结果的高位。

那么 就是一个先行计算出来的已知常量值了,这类值被称为Magic Number。

我们设 ,则有:

时,有:

时,有:

反推过程:

根据整数除法向0取整的规则,可得:

解方程得:

这就计算出了除数的值,该操作为一个除20的整数除法运算。

然后我们来写一个程序验证一下结论

#include<cstdio>

int main() {
    int a = 20;
    printf("%d\n", a / 20);
    return 0;
}

对应的汇编代码如下:

00401349    E8 F2050000     call test.00401940
0040134E    C74424 1C 14000>mov dword ptr ss:[esp+0x1C],0x14
00401356    8B4C24 1C       mov ecx,dword ptr ss:[esp+0x1C]
0040135A    BA 67666666     mov edx,0x66666667
0040135F    89C8            mov eax,ecx                              ; test.004013E0
00401361    F7EA            imul edx                                 ; test.00400000
00401363    C1FA 03         sar edx,0x3
00401366    89C8            mov eax,ecx                              ; test.004013E0
00401368    C1F8 1F         sar eax,0x1F
0040136B    29C2            sub edx,eax
0040136D    89D0            mov eax,edx                              ; test.00400000
0040136F    894424 04       mov dword ptr ss:[esp+0x4],eax
00401373    C70424 24804000 mov dword ptr ss:[esp],test.00408024     ; ASCII "%d\n"
0040137A    E8 BD560000     call test.00406A3C

分析上面的汇编代码,虽然有些地方和开头不太一样,但是其思路是一致的。

那么编译器是如何计算出Magic Number的呢,不同编译器的实现方法不同。这里贴一下《C++反汇编与逆向分析》随书代码。

#include <iostream.h>
#include <malloc.h>
#include <string.h>
#include <windows.h>
#include <math.h>
#include <stdlib.h>   

#define for if(0){}else for

// 对于除数在3到13之间,直接查表,表结构如下
struct SignedMagicNumber
{
  int nMagic; 
  int nExpInc;
};

// 对于除数为2的幂,有其他处理,故表内无对应值
struct SignedMagicNumber MagicTable[] = {
  {1, 1},           // 0 
  {1, 1},           // 1
  {1, 1},           // 2
  {0x55555556, 0},
  {0, 0},           // 4
  {0x66666667, 1},
  {0x2AAAAAAB, 0},
  {0x92492493, 2},
  {0, 0},           // 8
  {0x38E38E39, 1},
  {0x66666667, 2},
  {0x2E8BA2E9, 1},
  {0x2AAAAAAB, 1}
};


#define EXP31 0x80000000

// 以下代码还原修改自VC++6.0 bin目录下c2.dll(版本12.0.9782.0),文件偏移5FACE,
// 原程序的返回值定义为结构体,这里修改为参数返回
int GetMagic(unsigned int nDivC, int *nOutExpInc)
{
//   if ((int)nDivC >= 3 && nDivC < 13)
//   {
//     *nOutExpInc = MagicTable[nDivC].nExpInc;
//     return MagicTable[nDivC].nMagic;
//   }

  unsigned int nAbsDivC = abs(nDivC);
  int nExcBase = 31;

  // t = 2^31 if nDivC > 0
  // or t = 2^31 + 1 if nDivC < 0
  unsigned int t = (nDivC >> 31) + EXP31;

  // |nc| = t - 1 - rem(t, |nDivC|)
  unsigned int nLargestMultiple  = t - t % nAbsDivC - 1;
  unsigned int q1 = EXP31 / nLargestMultiple;
  unsigned int r1 = EXP31 - nLargestMultiple * q1;
  unsigned int nMagicNumber = EXP31 / nAbsDivC;
  unsigned int r2 = EXP31 - nAbsDivC * nMagicNumber;

  do
  {
    r1 *= 2;
    q1 *= 2;
    ++nExcBase;
    if ( r1 >= nLargestMultiple )
    {
      ++q1;
      r1 -= nLargestMultiple;
    }
    r2 *= 2;
    nMagicNumber *= 2;
    if ( r2 >= nAbsDivC )
    {
      ++nMagicNumber;
      r2 -= nAbsDivC;
    }
  }
  while ( q1 < nAbsDivC - r2 || q1 == nAbsDivC - r2 && !r1 );

  nMagicNumber++;

  if ( (int)nDivC < 0 )
    nMagicNumber = -(int)nMagicNumber;

  *nOutExpInc = nExcBase - 32;

  return nMagicNumber;
}

int main(int argc)
{
  int nExpInc;
  int nMagicNumber;


  int nDividend = argc-201; // 这是被除数
  int nDivisor = -100;      // 这是除数
  int nQuotient;            // 这里存放商

  // GetMagic用来计算magic number,
  // 第一个参数指定除数,第二个参数OUT指数相对32的增量
  // 这个例子用来模拟计算70 / -7的结果
  do 
  {
    nMagicNumber = GetMagic(nDivisor, &nExpInc);
    printf("nMagicNumber = 0x%08x, ExpInc = %d\r\n", nMagicNumber, nExpInc);

    if (nDivisor >= 0)
    {
      __asm
      {
        mov eax, nMagicNumber // 编译器会做成imm寻址,nMagicNumber早已在编译期间算出
        mov esi, nDividend
        imul esi

        // 编译器不会产生这里的跳转,
        // 因为编译阶段就计算出nMagicNumber的取值了,
        // 所以编译期间就可以决定是否产生其后的add指令,
        // nMagicNumber小于0x80000000(负数)则不需增加add
        test nMagicNumber, 80000000h
        jz NEXT1
        add edx, esi
NEXT1:
        mov ecx, nExpInc
        sar edx, cl
        shr esi, 31
        add edx, esi
        mov nQuotient, edx
      }
    }
    else
    {
      __asm
      {
        mov eax, nMagicNumber
        mov esi, nDividend
        imul esi

        test nMagicNumber, 80000000h
        jnz NEXT2
        sub edx, esi
NEXT2:
        mov ecx, nExpInc
        sar edx, cl
        mov ecx, edx
        shr ecx, 31
        add edx, ecx
        mov nQuotient, edx
      }
    }
    
    printf("%d / %d = %d\r\n", nDividend, nDivisor, nQuotient);
    printf("%d / %d = %d\r\n", nDividend, nDivisor, nDividend / nDivisor);
    if (nQuotient != nDividend / nDivisor)
    {
      puts("Error");
      break;
    }
    
    nDivisor++;
    if (nDivisor == 0 || nDivisor == -1 || nDivisor == 1)
    {
      nDivisor = 2;
    }
    nDividend += 10;
  }
  while(nDivisor <= 100);
  
  return 0;
}

0x66666667是怎么得到的?(2 ^ 33) / 5 + 1 = 0x66666667

_(:з」∠)_