user manual

Derivation of Multiplier Used for Integer Division by Constants 93
22007E/0—November 1999 AMD Athlon™ Processor x86 Code Optimization
ADD EAX, EDX ;x = (w & 0x33333333) + ((w >> 2) &
; 0x33333333)
MOV EDX, EDX ;x
SHR EAX, 4 ;x >> 4
ADD EAX, EDX ;x + (x >> 4)
AND EAX, 00F0F0F0Fh ;y = (x + (x >> 4) & 0x0F0F0F0F)
IMUL EAX, 001010101h ;y * 0x01010101
SHR EAX, 24 ;population count = (y *
; 0x01010101) >> 24
MOV retVal, EAX ;store result
}
return (retVal);
}
Derivation of Multiplier Used for Integer Division by
Constants
Unsigned Derivation for Algorithm, Multiplier, and Shift Factor
The utility udiv.exe was compiled using the code shown in this
section.
The following code derives the multiplier value used when
performing integer division by constants. The code works for
unsigned integer division and for odd divisors between 1 and
2
31
–1, inclusive. For divisors of the form d = d’*2
n
, the multiplier
is the same as for d’ and the shift factor is s + n.
/* Code snippet to determine algorithm (a), multiplier (m),
and shift factor (s) to perform division on unsigned
32-bit
integers by constant divisor. Code is written for the
Microsoft Visual C compiler. */
/*
In: d = divisor, 1 <= d < 2^31, d odd
Out: a = algorithm
m = multiplier
s = shift factor
;algorithm 0
MOV EDX, dividend
MOV EAX, m
MUL EDX
SHR EDX, s ;EDX=quotient