基于ARM的除法運(yùn)算優(yōu)化策略

ARM在硬件上不支持除法指令，編譯器是通過(guò)調(diào)用C庫(kù)函數(shù)來(lái)實(shí)現(xiàn)除法運(yùn)算的，有許多不同類型的除法程序來(lái)適應(yīng)不同的除數(shù)和被除數(shù)。但直接利用C庫(kù)函數(shù)中的標(biāo)準(zhǔn)整數(shù)除法程序，根據(jù)執(zhí)行情況和輸入操作數(shù)的范圍，要花費(fèi)20～100個(gè)周期，消耗較多的軟件運(yùn)行時(shí)間。在實(shí)時(shí)嵌入式應(yīng)用中，對(duì)時(shí)間參數(shù)較為敏感，故可以考慮如何優(yōu)化避免除法消耗過(guò)多的CPU運(yùn)行時(shí)間。

除法和模運(yùn)算(／和％)執(zhí)行起來(lái)比較慢，所以應(yīng)盡量避免使用。但是，除數(shù)是常數(shù)的除法運(yùn)算和用同一個(gè)除數(shù)的重復(fù)除法，執(zhí)行效率會(huì)比較高。在ARM中，可以利用單條MUL指令實(shí)現(xiàn)乘法操作。本文將闡述如何用乘法運(yùn)算代替除法運(yùn)算，以及如何使除法的次數(shù)最少化。

1 避免除法運(yùn)算

在非嵌入式領(lǐng)域，因?yàn)?/SPAN>CPU運(yùn)算速度快、存儲(chǔ)器容量大，除法操作通常都是不加考慮直接使用的。但在嵌入式領(lǐng)域，首先需要考慮的是這些除法操作是否是必須的。以對(duì)環(huán)形緩沖區(qū)操作為例，經(jīng)常要用到除法，其實(shí)完全可以避免這些除法運(yùn)算。

假定有一個(gè)buffer_size大小的環(huán)形緩沖區(qū)，如圖1所示，0ffset指定目前所在的位置。通過(guò)increment字節(jié)來(lái)增加offset的值，一般是這樣寫的：

0ffset=(Offset+increment)％buffer_size；

效率更高的寫法是：

offset+=increment；

if(offset>=buffer_size){

offset一=buffer_size；

}

第一種寫法要花費(fèi)50個(gè)周期，而第二種因?yàn)闆]有除法運(yùn)算，只須花費(fèi)3個(gè)周期。這里假定incrementbuff_er_size，在實(shí)際應(yīng)用中這點(diǎn)應(yīng)該是保證的。

如果不能避免除法運(yùn)算，那么就應(yīng)盡量使除數(shù)和被除數(shù)是無(wú)符號(hào)的整數(shù)。有符號(hào)的除法程序執(zhí)行起來(lái)更加慢，因?yàn)樗鼈兿纫〉贸龜?shù)和被除數(shù)的絕對(duì)值，再調(diào)用無(wú)符號(hào)除法運(yùn)算，最后再確定結(jié)果的符號(hào)。

2 充分利用商和余數(shù)

許多C語(yǔ)言庫(kù)中的除法函數(shù)返回商和余數(shù)。換句話說(shuō)，每一個(gè)除法運(yùn)算，余數(shù)是可以無(wú)償?shù)玫降模粗嗳?。例如，要在屏幕緩沖區(qū)找到偏移量為offset的屏幕位置(x，y)，可以這樣寫：

typeclef struct{

int x；

int y；

}point；

point getxy_v1(unsigned int offset，unslgned int bytes_per_line){

point p；

p．y=offset／lt)ytes_per_line；

p．x=offset - p．y* bytcs_per_line；

return p；

}

這里，似乎對(duì)p．x使用減法和乘法，少了一次除法運(yùn)算；但是，實(shí)際上使用模運(yùn)算或者取余操作效率更高，對(duì)

getxy_vl改進(jìn)如下：

point getxy_v2(unsigned int offset，unsigned int bytes_per_line){

point P；

P．x=offset％bytes_per_1ine；

P．y=offset／bytes_per_line；

return P;

從下面編譯器的輸出結(jié)果可以看到，只有一次除法調(diào)用。實(shí)際上，這個(gè)程序要比前面的getxy_vl少4條指令(注意，并不是對(duì)所有的編譯器和C庫(kù)都有這樣的結(jié)果)。getxy_v2

STMFD r13!，{r4，r14}；保存r4，lr人堆棧

MOV r4，rO ；賦值后r4保存的為點(diǎn)P基址

MOV rO，r2 ；rO=bytes_per_line

BL rt_udiv ；調(diào)用無(wú)符號(hào)除法例程

(r0．；r1)=(rl／rO，rl％rO)

STR r0，[r4，#4] ；P．y=offset／bytes_per_line

STR rl，[r4，#o] ；P．x=offset%bytes_per_line

LDMFD r13!，(r4，pc)；恢復(fù)上下文，返回

3 把除法轉(zhuǎn)換為乘法

在程序中，同一個(gè)除數(shù)的除法經(jīng)常會(huì)出現(xiàn)很多次。在前面的例子中，bytes_per_line的值在整個(gè)程序中都是固定不變的。又如3到2笛卡爾坐標(biāo)變換，其中就使用了同一個(gè)除數(shù)兩次：

(x,Y，x)→(x／z，y／z)

這種情況下，使用cache指令中的值1／z，并使用1／z的乘法來(lái)代替除法運(yùn)算，效率會(huì)更高。另外，要盡可能使用int類型的運(yùn)算，避免使用浮點(diǎn)運(yùn)算。

下面將更加偏重于從數(shù)學(xué)和理論的角度分析，把重復(fù)除法轉(zhuǎn)換成乘法運(yùn)算。

下面來(lái)區(qū)分精確數(shù)學(xué)意義上的除法和整型除法運(yùn)算：

◇n／d，即整數(shù)n被分成整數(shù)d份，結(jié)果趨向于O(與C語(yǔ)言相同)；

◇n％d，即n被d除之后的余數(shù)，就是n--d(n／d)；

◇n/d=nd-1，即真正數(shù)學(xué)意義上的n被d除。

當(dāng)使用整型除法時(shí)，最容易估算d-1值的方法是計(jì)算232／d。然后，就可以估算n／d為：

(n(232／d))／232 (1)

在執(zhí)行n的乘法時(shí)，需要精確到64位。對(duì)于這種方法，會(huì)出現(xiàn)如下問(wèn)題：

◇為了計(jì)算232／d，由于一個(gè)unsigned int類型的數(shù)據(jù)放不下232，編譯器要使用64位long long類型的數(shù)，而且必須指定除法為(1 ull32)／d。這種64位的除法比32位的除法執(zhí)行起來(lái)要慢得多。

◇如果d碰巧是1，那么232／d就不再適合于un―signed int數(shù)據(jù)類型。

上面的做法似乎很好，而且解決了這兩個(gè)問(wèn)題。那么，再來(lái)看一下用(232一1)／d代替232／d。

令

s=0xffffffff ul／d (2)

以上n／d-2，q，n／d+1為整數(shù)值，所以可得q=n／d或q=(n／d)一1，即初步估計(jì)的結(jié)果q與正確值n／d有可能存在偏差1?？梢园l(fā)現(xiàn)，通過(guò)計(jì)算余數(shù)r=n―qd(O≤r2d)是比較容易的。下面的代碼糾正了這個(gè)結(jié)果：

r=n--q*d;／*初步估計(jì)結(jié)果余數(shù)r的范圍為O≤r2d*／

if(r>=d){／*若需要校正*／

r-=d；／*校正r，使O≤rd為正確余數(shù)范圍*／

n++;／*相應(yīng)商加1進(jìn)行校正*／

} ／*得正確結(jié)果q=n／d和r=n％d*／

下面給出一個(gè)實(shí)例，用上面的算法完成了N個(gè)元素的數(shù)組被d除。首先，計(jì)算上面所說(shuō)的s值，然后用乘以5來(lái)代替每個(gè)被d除的除法。64位的乘是很容易實(shí)現(xiàn)的，因?yàn)?/SPAN>ARM中有一條指令UMULL，可以進(jìn)行2個(gè)32位數(shù)相乘，給出一個(gè)64位的結(jié)果。

void scale(

unsigned int*dest； ／*目的數(shù)據(jù)*／

unsigned int*src； ／*源數(shù)據(jù)*／

unsignedInt d； ／*分母d*／

urlslglaedInt N；) ／*數(shù)據(jù)長(zhǎng)度*／

{

unsigned int s=0xFFFFFFFFu／d；

do{

unsigned int n，q，r；

n=*(src++)；

q=(urtslgrted int)(((unsined tong long)n*s)>>32)；

r=n*d；

if(r>=d){ ／*若需要對(duì)商進(jìn)行校正*／

q++；

}

*(dest++)=q;

}while(一一N)；

}

這里假定除數(shù)和被除數(shù)都是32位的無(wú)符號(hào)整數(shù)。當(dāng)然，使用32位乘法進(jìn)行16位的無(wú)符號(hào)數(shù)計(jì)算，或者使用1 28位乘法進(jìn)行64位數(shù)計(jì)算，運(yùn)算規(guī)則是一樣的。可以為特定的數(shù)據(jù)選擇最窄的運(yùn)算寬度。如果數(shù)據(jù)是16位的，那么就設(shè)置s=(216一1)/d，然后用標(biāo)準(zhǔn)的整型乘法來(lái)求值q。

4 結(jié) 論

在嵌入式軟件編程中，為了節(jié)省CPU運(yùn)行時(shí)間，應(yīng)盡可能避免使用除法。對(duì)環(huán)形緩沖區(qū)的處理可以不用除法。如果不能避免除法運(yùn)算，那么應(yīng)盡可能使用除法程序同時(shí)產(chǎn)生商n／d和余數(shù)n％d的好處。對(duì)于重復(fù)對(duì)一除數(shù)d的除法．預(yù)先計(jì)算好s=(2k一1)／d，用乘以s的2k位乘法來(lái)代替除以d的k位無(wú)符號(hào)整數(shù)除法，可大大減少由于直接使用除法操作引入的指令周期數(shù)。