Reversing : The Hacker's Guide to Reverse Engineering

Table B.1 Examples of Reciprocal Multiplications in Division

RECIPROCAL

DIVISOR IN 32-BIT VALUE (AS A COMBINED

SOURCE CODE RECIPROCAL FRACTION) WITH DIVISOR

3 0xAAAAAAAB 2/3 2

5 0xCCCCCCCD 4/5 4

6 0xAAAAAAAB 2/3 4

Notice that the last digit in each reciprocal is incremented by one. This is

because the fractional values can never be accurately represented, so the com-

piler is rounding the fraction upward to obtain an accurate integer result

(within the given bits).

Of course, keep in mind that multiplication is also not a trivial operation,

and multiplication instructions in IA-32 processors can be quite slow (though

significantly faster than division). Because of this, compilers only use recipro-

cal when the divisor is not a power of 2. When it is, compilers simply shift

operands to the right as many times as needed.

Deciphering Reciprocal-Multiplications

Reciprocal multiplications are quite easy to detect when you know what to

look for. The following is a typical reciprocal multiplication sequence:

mov ecx, eax

mov eax, 0xaaaaaaab

mul ecx

shr edx, 2

mov eax, edx

526 Appendix B

DIVIDING VARIABLE DIVIDENDS USING RECIPROCAL MULTIPLICATION?

There are also optimized division algorithms that can be used for variable

dividends, where the reciprocal is computed in runtime, but modern IA-32

implementations provide a relatively high-performance implementation of the

DIVand IDIVinstructions. Because of this, compilers rarely use reciprocal

multiplication for variable dividends when generating IA-32 code—they simply

use the DIVor IDIVinstructions. The time it would take to compute the

reciprocal in runtime plus the actual reciprocal multiplication time would be

longer than simply using a straightforward division.

22_574817 appb.qxd 3/16/05 8:45 PM Page 526