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
Summary of Contents for Athlon Processor x86
Page 1: ...AMD Athlon Processor x86 Code Optimization Guide TM...
Page 12: ...xii List of Figures AMD Athlon Processor x86 Code Optimization 22007E 0 November 1999...
Page 16: ...xvi Revision History AMD Athlon Processor x86 Code Optimization 22007E 0 November 1999...
Page 202: ...186 Page Attribute Table PAT AMD Athlon Processor x86 Code Optimization 22007E 0 November 1999...
Page 252: ...236 VectorPath Instructions AMD Athlon Processor x86 Code Optimization 22007E 0 November 1999...
Page 256: ...240 Index AMD Athlon Processor x86 Code Optimization 22007E 0 November 1999...