Reversing : The Hacker's Guide to Reverse Engineering

This code multiplies ECXby 0xAAAAAAAB, which is equivalent to 0.6666667

(or two-thirds). It then shifts the number by two positions to the right. This

effectively divides the number by 4. The combination of multiplying by two-

thirds and dividing is equivalent to dividing by 6. Notice that the result from

the multiplication is taken from EDX and not from EAX. This is because the

MUL instruction produces a 64-bit result—the most-significant 32-bits are

stored in EDXand the least-significant 32-bits are stored in EAX. You are inter-

ested in the upper 32 bits because that’s the integral value in the fixed-point

representation.

Here is a slightly more involved example, which adds several new steps to

the sequence:

mov ecx, eax

mov eax, 0x24924925

mul ecx

mov eax, ecx

sub eax, edx

shr eax, 1

add eax, edx

shr eax, 2

This sequence is quite similar to the previous example, except that the result

of the multiplication is processed a bit more here. Mathematically, the preced-

ing sequence performs the following:

y = ((x - x _ sr) ÷ 2 + x _ sr) ÷ 4

Where x= dividendand sr= 1 ÷ 7 (scaled).

Upon looking at the formula it becomes quickly evident that this is a divi-

sion by 7. But at first glance, it may seem as if the code following the MUL

instruction is redundant. It would appear that in order to divide by 7 all that

would be needed is to multiply the dividend by the reciprocal. The problem is

that the reciprocal has limited precision. The compiler rounds the reciprocal

upward to the nearest number in order to minimize the magnitude of error

produced by the multiplications. With larger dividends, this accumulated

error actually produces incorrect results. To understand this problem you

must remember that quotients are supposed to be truncated (rounded down-

ward). With upward-rounded reciprocals, quotients will be rounded upward

for some dividends. Therefore, compilers add the reciprocal once and subtract

it once—to eliminate the errors it introduces into the result.

Modulo

Fundamentally, modulo is the same operation as division, except that you take

a different part of the result. The following is the most common and intuitive

method for calculating the modulo of a signed 32-bit integer:

Understanding Compiled Arithmetic 527

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