一丶為什麼要熟悉除法的優化,以及除法原理
是這樣的,在計算機中,除法運算對應的彙編指令分為 DIV(無符号除法指令) 以及 IDIV(有符号除法指令).
但是,除法指令的執行周期較長效率很低.是以編譯器想進辦法的用其它指令去代替除法指令.
比如:
DIV 指令是100個周期
計算 2 / 2
那麼可能在彙編中的表現形式是這樣的
CDQ 符号擴充
DIV EDX,2
好,現在100個周期沒有了
減法和加法指令,指令周期是4個那麼上面的公式可以演化為
mov eax,2
sub eax,2
就算mov 指令是10個指令,那麼總共計算起來才14個指令,而正好完成了一個除法
如果我們把指令周期看做時間的話,那麼100個指令周期是100秒,14個指令周期是14秒
那麼是不是時間變快了,那麼相應的軟體運作速度以及啟動速度也變快了.
二丶丶熟悉數學證明
在講解除法之前,我們要熟悉一下數學公式,以及數學證明,因為在除法的優化中,和這些數學公式息息相關.
當然你不看證明也可以,但是公式一定要明白
這裡我講解的是 <<C++反彙編與逆向分析技術揭秘>> 作者: 錢林松 趙海旭
偉大的錢老師的著作. 第47頁
首先我們要明白計算機中的除法
1.有符号樹和無符号數混除,那麼結果是無符号的
2.兩個無符号整數相除,結果還是無符号的.
3.計算機中面臨如何處理小數,比如 9 / 4 = 2.25
了解數學中的向下取整,以及向上取整
向下取整:
講道理: 比如對x向下取整, x>=0 那麼就是 取得不大于x的最大整數, 相反也就是說, 小于x的遇到的第一個整數
比如 x = 5
那麼向下取整則是4
不大于5,那麼就是小于5, 然後遇到的最大整數,也就是4
向上取整:
同理,向上取整則是 不小于x的最大整數.
除法的擴充知識:
在整數的處罰中,隻有能整除和不能整除的兩種情況(廢話)不能整除,則會産生餘數.
設 a = 被除數 b = 除數 c = 商 r = 餘數
那麼可以得到下面的公式:
除法原型:
a / b = c .... r
6 / 4 = 1 ...2
1. |r| < |b| : 餘數的絕對值,絕對會小于除數的. 比如 6 / 4 = 1 .... 2 那麼 餘數2 不關是正數還是父數,絕對都是絕對會小于除數的,也就是4
2. a = c * b + r : 求被除數,被除數是商*除數+餘數
3.b = (a - r)/c : 求除數,除數等于 被除數-餘數 / 商
4.c = (a - r)/b : 求商: 被除數 - 餘數 / 除數
5. r = a - (c * b) : 求餘數 被除數 - (商 * 除數)
3.計算機中的除法
1.當除數為變量,的時候
計算機中.的彙編指令為 DIV 或者 IDIV,因為除數是不确定的
int n ;
7 / n ===> 彙編指令就用DIV 或者IDIV
沒有優化的餘地,看彙編代碼.
除數為有符号相除
除數為無符号
當除數為變量,且分為有符号和無符号相除
有符号相除: 那麼使用的彙編指令是IDIV
無符号相除: 那麼使用的彙編指令是DIV
2.當除數為2的幂的時候被除數分為有符号和無符号位的時候
比如代碼為:
被除數無符号的情況下,除數是2的幂次方: (也就是n是無符号)
n / 8 那麼8是2^3次方
那麼直接優化為 shr
左移三位
被除數有符号的情況下且大于0,除數是2的幂次方
看到彙編代碼懵逼,那麼上公式,證明,然後則明白
首先公式等于
當B (除數)大于0則使用上面的公式,當b < 0則使用下面的公式
比如計算機中,被除數為正數的時候,可以使用第一個公式的第一個,也可以使用第二個,不過計算機預設向0取整
比如我們計算 17 / 8
正常計算 17 / 8 = 2 .xxxx
有小數
不過計算機計算出來的結果則是2,省略小數了,那麼計算機使用的則是第一個公式.
a / b 向下取整, 然後也可以 a - b + 1 / b 向上取整
我們實驗一下,
代入得到
17 - 8 + 1 / 8 =
10 / 8 = 1.25 轉化為後面的公式,向上取整則是2了.
那麼上面的彙編代碼應該能看明白了.
首先 Cdq 是符号擴充的意思,也就是EDX和EAX一起使用,變成了一個64位寄存器.
然後利用and和edx比較7, 這個7怎麼的出來了,這個7就是上面我們用第一個公式計算出來的
也就是 a - b + 1 這個, 這個7則是b + 1的值.
然後 add eax,edx 被除數 + 上 and過後的值.
最後右邊移動三位.
這裡編譯器巧妙的利用 cdq符号擴充,然後利用了公式,進行了無分支判斷.
如果我們的被除數是正數,那麼 符号擴充之後,edx的值則全部是0,然後and過後,結果還是0
那麼我們的被除數 + 0 右移3位 然後向下取整.
比如我們計算的 n / 8
n取值為17
那麼計算的出 b + 1 的值為 8 + 1
那麼是正數,則edx為0,and 9之後還是0
那麼下面直接 add eax,edx
eax = 原來的被除數 也就是17
edx 結果and後為0
那麼結果還是17
最後 17 右移動三位則是 2.xxx 向下取整就是2了.
如果是負數,那麼b+1的值還是9
那麼此時 add eax,edx = -17 + b - 1 = -10
而後 -10 右移動3位 (-10 / 8) = 1.25 此時向上取整,結果還是-2
公式的話,主要看計算機,一般計算機整數相除,選擇向下取整
負數相除,選擇向上取整.
3.無符号是被除數的情況下, 除數為非2的幂的時候
比如進階語言
unsigned int a;
a / 3 那麼彙編指令有不一樣了
我們看下最後兩個, /3 的,還有/ 0x87654321的
優化成了這樣,還是沒有看到除法
a /c C為常量的時候 a(被除數)
那麼可以得出公式 am >> n位 (具體的推導公式就不寫了,反正都是記公式)
其中m = 2n / c (n的取值範圍看系統,如果是16位,那麼n的起步就是16 ,32位則是32位起步)
那麼現在
mov eax ,xxxxx xxxx是m
mul reg32
shr edx,1fh 1fh是n
那麼根據上面的公式 am >> n
現在已經知道n和m了
而 m = 2n / c
那麼現在可以求C了
按照最後一個求得出 n = 1f ,也就是2^1f + 2^32
為什麼要加上2^32,因為 EDX和eax現在是一個64位寄存器,(看作是)符号擴充了,EDX移動一位,那麼相當于eax 移動33位.
m = 0f2044d73
現在求C的值
反推即可
C = 2^n / m
轉為十進制計算
9223372036854775808 / 4060368243 = 2271560480.4455111112443010011986
結果向上取整得出2271560481
轉為16進制得出
順利還原代碼.
作者：IBinary