Android安全交流群：478084054

0x01 除法優(yōu)化淺析

最近花了點(diǎn)時(shí)間去逆向一些小程序，遇到“(R0 * 0xAAAAAAAB) >> 32”這樣的運(yùn)算時(shí)，一時(shí)看不出何意。后來經(jīng)過搜索，才知道這是編譯器對(duì)除法做的優(yōu)化（因?yàn)槌ㄖ噶畋容^耗時(shí)）。在這里做個(gè)小筆記。

對(duì)于除法操作，如果除數(shù)是2的整數(shù)次方，那直接右移就可以了。比如：R0/4可以用R0>>2代替。如果除數(shù)不是2的整數(shù)次方，那如何優(yōu)化呢？簡單寫一下原理：

結(jié)合示例來看：

void test(unsigned int a) {
  LOG("unsigned int a / 3 = %d", a / 3);
}

test函數(shù)很簡單，看一下反匯編代碼（主要關(guān)心其中的a/3）：

LDR        R2, =0xAAAAAAAB
UMULL.W    R2, R3, R0, R2
LSRS       R1, R3, #1

R0即test函數(shù)的參數(shù)a，最后a/3的計(jì)算結(jié)果保存在R1中。

首先，R0和R2做無符號(hào)數(shù)乘法（UMULL），結(jié)果的高32位保存到R3，低32位保存到R2。R2的值后續(xù)并沒有用到，相當(dāng)于舍棄了，即只保留R0*R2的高32位，也就是相當(dāng)于整個(gè)乘法運(yùn)算的結(jié)果右移了32位。所以前2行代碼即：(R0 * R2) >> 32。

第3行代碼，又把R3邏輯右移了1位，所以這3行代碼合起來就是：(R0 * R2) >> 33。而R2的值是0xAAAAAAAB，所以最終結(jié)果就是：(R0 * 0xAAAAAAAB) >> 33。也就是編譯器將a/3優(yōu)化成了(a * 0xAAAAAAAB) >> 33。那么這個(gè)結(jié)果，與上面提到的除法優(yōu)化原理（a/b = (a*c) >> n，其中c=(2^n)/b）吻合嗎？

從“(a * 0xAAAAAAAB) >> 33”可知，編譯器選擇的n值為33，那么c=(2 ^ 33)/b。這里除數(shù)b為3，所以c=(2^33)/3=2863311530.67，向上取整為2863311531，換成16進(jìn)制，即：0xAAAAAAAB。所以，這里編譯器所做的優(yōu)化與上面提到的優(yōu)化原理正好吻合。

剛才有一個(gè)c從2863311530.67向上取整為2863311531的操作，那么c的值就有一個(gè)0.33的誤差。那為什么這個(gè)誤差不會(huì)影響到最后的計(jì)算結(jié)果呢？這個(gè)是可以進(jìn)行推理證明的，可以參考：https://www.cnblogs.com/shines77/p/4189074.html

0x02 由匯編反推除法

再來看一個(gè)例子，鞏固一下。假設(shè)有以下3行反匯編代碼，現(xiàn)在來反推回高級(jí)代碼。

LDR        R2, =0xCCCCCCCD
UMULL.W    R2, R3, R0, R2
LSRS       R1, R3, #2

3行代碼合起來即：(R0 * 0xCCCCCCCD) >> 34。

除法優(yōu)化原理：a/b = (a*c) >> n，其中c=(2^n)/b。

由(R0 * 0xCCCCCCCD) >> 34，可知n=34，c=0xCCCCCCCD。根據(jù)c=(2^ n)/b，可知b=(2^ n)/c=(2^34)/0xCCCCCCCD=4.99999999971，即b=5（因?yàn)閏值有一個(gè)很小的，不影響除法運(yùn)算結(jié)果的誤差，所以這里得到的值近似5）。所以，上述3行匯編代碼對(duì)應(yīng)的高級(jí)代碼即：R0/5。與實(shí)際的源碼正好對(duì)應(yīng)的上：

void test(int a) {
  LOG("int a / 5 = %d", a / 5);
}

再回頭看一下剛開始提到的“R0 * 0xAAAAAAAB >> 32”，這個(gè)對(duì)應(yīng)的高級(jí)代碼應(yīng)該是什么？

除法優(yōu)化原理：a/b = (a*c) >> n，其中c=(2^n)/b。

由“(R0 * 0xAAAAAAAB) >> 32”，可知n=32，c=0xAAAAAAAB。根據(jù)c=(2^ n)/b，可知b=(2^ n)/c=(2^32)/0xAAAAAAAB=1.49999999983，即b=1.5。所以“(R0 * 0xAAAAAAAB) >> 32”即R0/1.5。不過，這里提到的除法優(yōu)化是針對(duì)整數(shù)常量來說的，所以實(shí)際就是R0/(3/2)，即R0*2/3。

0x03 有符號(hào)數(shù)的除法優(yōu)化

現(xiàn)在把test函數(shù)簡單修改一下：

void test(int a) {
  LOG("int a / 3 = %d", a / 3);
}

原先參數(shù)類型是unsigned int，現(xiàn)在參數(shù)類型是int?？匆幌耡/3對(duì)應(yīng)的反匯編代碼：

LDR        R2, =0x55555556  
MOV        R1, R0           
SMULL.W    R2, R3, R0, R2   
SUB.W      R1, R3, R1,ASR#31

這4行代碼合起來就是：(R0 * 0x55555556) >> 32 – (R0 >> 31)，其中R0 >> 31是算數(shù)右移。先忽略后面的減法，只關(guān)心“(R0*0x55555556)>>32”。

除法優(yōu)化原理：a/b = (a*c) >> n，其中c=(2^n)/b。

由“(R0 * 0x55555556) >> 32”，可知n=32，c=0x55555556。根據(jù)c=(2^ n)/b，可知b=(2^ n)/c=(2^32)/0x55555556=2.9999999986，即b=3。所以“(R0 * 0x55555556) >> 32”即R0/3。這么一看，貌似后面的“– (R0 >> 31)”是多余的。其實(shí)不然，簡單分析一下。

參數(shù)類型是int，“R0 >> 31”就是取符號(hào)位（算數(shù)右移）。那么有兩種情況：

1）R0是正數(shù)，那么R0 >> 31結(jié)果為0，減法相當(dāng)于什么也沒做。
除法優(yōu)化原理還是：a/b = (a*c) >> n，其中c=(2^n)/b。

2）R0是負(fù)數(shù)，那么R0 >> 31結(jié)果為0xFFFFFFFF，即-1，減-1相當(dāng)于加1。
除法優(yōu)化原理變成：a/b =( (a*c) >> n) + 1，其中c=(2^n)/b。

為什么被除數(shù)為負(fù)數(shù)時(shí)，后面要加1呢？因?yàn)椤?a*c) >> n”是向下取整的結(jié)果。加1是為了向0取整，而c/c++語言對(duì)于整數(shù)除法的規(guī)定正是向0取整。

關(guān)于除法優(yōu)化，還有很多更復(fù)雜的情況，以及一系列的理論推導(dǎo)。限于時(shí)間，我就先了解到這。對(duì)于簡單的情況，能根據(jù)反匯編代碼，反推回優(yōu)化之前的除法操作了。

文/十八坰