AMD 250 manual Unsigned Integer Division, 186

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

8.8Derivation of Algorithm, Multiplier, and Shift Factor for Integer Division by Constants

The following examples illustrate the derivation of algorithm, multiplier and shift factor for signed and unsigned integer division.

Unsigned Integer Division

The utility udiv.exe was compiled from the code shown in this section. The utilities provided in this document are for reference only and are not supported by AMD.

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 231 – 1, inclusive. For divisors of the form d = d' * 2n, the multiplier is the same as for d' and the shift factor is s + n.

Example

/* This program determines the algorithm (a), multiplier (m), and shift factor (s) to be used to accomplish *unsigned* division by a constant divisor. Compile with MSVC.

*/

#include <stdio.h>

typedef	unsigned	__int64	U64;
typedef	unsigned	long	U32;

U32 log2(U32 i)

{

U32 t = 0; i = i >> 1; while (i) {

i = i >> 1; t++;

}

return(t);

}

U32 res1, res2;

U32 d, l, s, m, a, r, n, t;

U64 m_low, m_high, j, k;

int main (void)

{

fprintf(stderr, "\n");

fprintf(stderr, "Unsigned division by constant\n"); fprintf(stderr, "=============================\n\n");

186 Integer Optimizations Chapter 8