AMD Athlon™ Processor x86 Code Optimization

22007E/0 — November 1999

;algorithm

1

 

MOV

EAX,

m

 

MOV

EDX,

dividend

 

MOV

ECX,

EDX

 

IMUL

EDX

 

 

ADD

EDX,

ECX

 

SHR

ECX,

31

 

SAR

EDX,

s

 

ADD

EDX,

ECX

; quotient in EDX

*/

 

 

 

typedef

unsigned __int64

U64;

typedef

unsigned long

U32;

U32

log2 (U32 i)

 

{

 

 

 

U32 t

= 0;

 

i

= i

>> 1;

 

while

(i) {

 

 

i =

i >> 1;

 

 

t++;

 

 

}

 

 

 

return (t);

 

}

 

 

 

U32

d, l, s, m, a;

 

U64

m_low, m_high, j, k;

 

/* Determine algorithm (a), multiplier (m), and shift count

(s)for 32-bit signed integer division. Based on: Granlund, T.; Montgomery, P.L.: “Division by Invariant Integers using Multiplication”. SIGPLAN Notices, Vol. 29, June 1994, page 61. */

l= log2(d);

j= (((U64)(0x80000000)) % ((U64)(d)));

k= (((U64)(1)) << (32+l)) / ((U64)(0x80000000–j));

m_low

=

(((U64)(1)) << (32+l)) / d;

m_high

=

((((U64)(1)) << (32+l)) + k) / d;

while (((m_low >> 1) < (m_high >> 1)) && (l > 0)) { m_low = m_low >> 1;

m_high = m_high >> 1;

l = l – 1;

}

m= ((U32)(m_high)); s = l;

a = (m_high >> 31) ? 1 : 0;

96

Derivation of Multiplier Used for Integer Division by

Page 112
Image 112
AMD x86 manual MOV ECX EDX Imul ADD SHR SAR