user manual

94 Derivation of Multiplier Used for Integer Division by
AMD Athlon™ Processor x86 Code Optimization
22007E/0—November 1999
;algorithm 1
MOV EDX, dividend
MOV EAX, m
MUL EDX
ADD EAX, m
ADC EDX, 0
SHR EDX, s ;EDX=quotient
*/
typedef unsigned __int64 U64;
typedef unsigned long U32;
U32 d, l, s, m, a, r;
U64 m_low, m_high, j, k;
U32 log2 (U32 i)
{
U32 t = 0;
i = i >> 1;
while (i) {
i = i >> 1;
t++;
}
return (t);
}
/* Generate m, s for algorithm 0. Based on: Granlund, T.;
Montgomery, P.L.:"Division by Invariant Integers using
Multiplication”. SIGPLAN Notices, Vol. 29, June 1994, page
61. */
l = log2(d) + 1;
j = (((U64)(0xffffffff)) % ((U64)(d)));
k = (((U64)(1)) << (32+l)) / ((U64)(0xffffffff–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;
}
if ((m_high >> 32) == 0) {
m = ((U32)(m_high));
s = l;
a = 0;
}