AMD Typewriter x86 사용자 설명서
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)
; 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
IMUL EAX, 001010101h ;y * 0x01010101
SHR EAX, 24
;population count = (y *
; 0x01010101) >> 24
; 0x01010101) >> 24
MOV
retVal, EAX
;store result
}
return (retVal);
}
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.
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
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. */
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:
In:
d = divisor, 1 <= d < 2^31, d odd
Out:
a = algorithm
m = multiplier
s = shift factor
m = multiplier
s = shift factor
;algorithm 0
MOV
MOV
EDX, dividend
MOV
EAX, m
MUL
EDX
SHR
EDX, s ;EDX=quotient