Android逆向- ARM除法与取模优化

之前的笔记搬运

除法优化

当除数是变量时, 那么是没有优化的余地, 编译器生成的汇编一定除法汇编, 只有当除数是常量时才有被优化的可能;

编译模式: thumb2

x / 2^n(有符号除以2的幂)

公式: 
     if (x < 0)
        x = (x+2^n-1)
x >> n

实例:    x / 8
//R0  =  (x+2^n-1)
.text:00000BD0                 ADDS            R0, R2, #7

//R2 = ~(R2>>32) & R2  
//如:R2为正R2值不变
//如:R2为负R2 = 0
.text:00000BD2                 BICS.W          R2, R2, R2,ASR#32

//如果R2为0,  R2 = R0
.text:00000BD6                 IT CS
.text:00000BD8                 MOVCS           R2, R0

//R2 >> 3
.text:00000BDA                 ASRS            R0, R2, #3

还原:  O = 2^n

x / -2^n = -(x / 2^n)(有符号除以负2的幂)

公式: 
      if (x < 0)
            x = (x+2^n-1)
        x >> n
        x = -x
实例:    x / -8

.text:00000BD0                 ADDS            R0, R2, #7
.text:00000BD2                 BICS.W          R2, R2, R2,ASR#32
.text:00000BD6                 IT CS
.text:00000BD8                 MOVCS           R2, R0
.text:00000BDA                 ASRS            R0, R2, #3
//前面参考0x1, 这里把结果直接取反就可以了
.text:00000BDC                 NEGS            R0, R0

还原:  O = neg(2^n)

除以负非2^n (有符号)

公式: 
      -(x * c >> 32 >> n)
      if (x < 0) 
         x + 1

实例:    x / -9

//R3 = magicnum
.text:00000BD0                 MOV             R3, #0x38E38E39

//x * r3
.text:00000BD8                 SMULL.W         R1, R3, R3, R2

//正数R2 = 0,  负数R2 = -1
.text:00000BDC                 ASRS            R2, R2, #0x1F

//这里直接用R3再右移1位, 表示移了33位
//R2存放的0或-1
//x正数: 0 - R3 = ~(R3)
//x负数: -1 - R3 = ~(R3 + 1)
.text:00000BDE                 SUB.W           R0, R2, R3,ASR#1

还原:  O = -(2^(32+n) / C)

除以非2^n (有符号)

公式: 
      x * c >> 32 >> n
      if (x < 0) 
         x + 1

实例:    x / 9

.text:00000BD0                 MOV             R3, #0x38E38E39
.text:00000BD8                 SMULL.W         R1, R3, R3, R2
.text:00000BDC                 ASRS            R2, R2, #0x1F

//前面参照0x3
//这里使用了反向减法, R2存放的0或-1
//x正数: R3 - 0 = R3
//x负数: R3 - -1= R3+1
.text:00000BDE                 RSB.W           R0, R2, R3,ASR#1

还原:  O = 2^(32+n) / C

除以2^n (无符号)

公式: 
      x >> n

实例:        unsigned int  x1 = x;
            return x1 / 8;

//直接右移
.text:00000BD0                 LSRS            R0, R2, #3

还原:  O = 2^n

除以非2^n 无溢出(无符号)

公式: 
      (x * MAGIC_NUM) >> 32 >> n

实例:        unsigned int  x1 = x;
            return x1 / 5;

// magicnum
.text:00000BD0                 MOV             R3, #0xCCCCCCCD
//x * magicnum
.text:00000BD8                 UMULL.W         R1, R3, R3, R2
//此时R3是高32位
//R0 = R3 >> 2
.text:00000BDC                 LSRS            R0, R3, #2

还原:  O = 2^(32+n) / C

取模优化

取模2^n

公式: 
  if (x > 0)
         x / c = x & (2^n - 1)
  else
      (x + (2^n - 1) & (2^n - 1)) - (2^n - 1)

实例:   x % 4;


//判断正负数
.text:00000BB8                 MOV             R3, R2,ASR#31
//正数为0, 负数取2^n - 1
.text:00000BBC                 MOV             R3, R3,LSR#30
//x + (2^n - 1)
.text:00000BC0                 ADD             R2, R2, R3
//正数是 x & (2^n - 1)
//负数是 (x + (2^n - 1) & (2^n - 1)) 
.text:00000BC4                 AND             R0, R2, #3
//正数是 (x & (2^n - 1) ) - 0
//负数是 (x + (2^n - 1) & (2^n - 1)) - (2^n - 1)
.text:00000BC8                 RSB             R0, R3, R0

还原:  看最后AND的值是多少+ 1, 就是2^n的值

取模非2^n

公式: 
  x - x / c * c

实例:   x % 7;

//下面五行是除法R3 = x / 7 
.text:00000BB8                 MOV             R3, #0x92492493
.text:00000BC0                 SMULL           R1, R3, R3, R2
.text:00000BC4                 MOV             R1, R2,ASR#31
.text:00000BC8                 ADD             R3, R3, R2
.text:00000BCC                 RSB             R3, R1, R3,ASR#2
//R3 * 8 - R3 = R3 * 7
.text:00000BD0                 RSB             R3, R3, R3,LSL#3
// x- R3
.text:00000BD4                 RSB             R0, R3, R2

赏

感谢大佬

微信