user manual

96 Derivation of Multiplier Used for Integer Division by
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;