AMD x86 manual Unsigned Division by Multiplication of Constant

AMD Athlon™ Processor x86 Code Optimization 22007E/0 — November 1999

Signed Division	In the opt_utilities directory of the AMD documentation
Utility	CDROM, run sdiv.exe in a DOS window to find the fastest code
	for signed division by a constant. The utility displays the code
	after the user enters a signed constant divisor. Type “sdiv >
	example.out” to output the code to a file.
Unsigned Division	In the opt_utilities directory of the AMD documentation
Utility	CDROM, run udiv.exe in a DOS window to find the fastest code
	for unsigned division by a constant. The utility displays the code
	after the user enters an unsigned constant divisor. Type “udiv >
	example.out” to output the code to a file.

Unsigned Division by Multiplication of Constant

Algorithm: Divisors	The following code shows an unsigned division using a constant
1 <= d < 231, Odd d	value multiplier.

;In: d = divisor, 1 <= d < 2^31, odd d

;Out: a = algorithm

;m = multiplier

;s = shift factor

;algorithm		0
MOV	EDX,	dividend
MOV	EAX,	m
MUL	EDX
SHR	EDX,	s	;EDX=quotient
;algorithm		1
MOV	EDX,	dividend
MOV	EAX,	m
MUL	EDX
ADD	EAX,	m
ADC	EDX,	0
SHR	EDX,	s	;EDX=quotient

Derivation of a, m, s The derivation for the algorithm (a), multiplier (m), and shift count (s), is found in the section “Unsigned Derivation for Algorithm, Multiplier, and Shift Factor” on page 93.

Algorithm: Divisors For divisors 231 <= d < 232, the possible quotient values are

231 <= d < 232either 0 or 1. This makes it easy to establish the quotient by simple comparison of the dividend and divisor. In cases where the dividend needs to be preserved, example 1 below is recommended.

78 Replace Divides with Multiplies