AMD 250 Unsigned Division by Multiplication of Constant, Algorithm Divisors 1 = d 231, Odd d, 161

25112 Rev. 3.06 September 2005 Software Optimization Guide for AMD64 Processors

Unsigned Division by Multiplication of Constant

Algorithm: Divisors 1 <= d < 231, Odd d

The following code shows an unsigned division using a constant value multiplier.

;a = algorithm

;m = multiplier

;s = shift factor

;a == 0

mov eax, m mul dividend

shr edx, s ; EDX = quotient

;a == 1

mov eax, m mul dividend add eax, m adc edx, 0

shr edx, s ; EDX = quotient

Code for determining the algorithm (a), multiplier (m), and shift factor (s) from the divisor (d) is found in the section “Derivation of Algorithm, Multiplier, and Shift Factor for Integer Division by Constants” on page 186.

Algorithm: Divisors 231 <= d < 232

For divisors 231 <= d < 232, the possible quotient values are either 0 or 1. For this reason, it is easy to establish the quotient by simple comparison of the dividend and divisor.When the dividend needs to be preserved, consider using code like the following:

;In: EAX = dividend

;Out: EDX = quotient

xor edx, edx			; 0
cmp	eax,	d	;	CF = (dividend < divisor) ? 1 : 0
sbb	edx,	-1	;	quotient = 0 + 1 - CF = (dividend < divisor) ? 0 : 1

When the dividend does not need to be preserved, the division can be accomplished without the use of an additional register, thus reducing register pressure, as shown here:

;In: EAX = dividend

;Out: EDX = quotient

cmp edx, d			; CF = (dividend < divisor) ? 1 : 0
mov	eax,	0	;	0
sbb	eax,	-1	;	quotient = 0 + 1 - CF = (dividend < divisor) ? 0 : 1

Chapter 8 Integer Optimizations 161