Reverse Engineering for Beginners

CHAPTER 41. DIVISION BY 9 CHAPTER 41. DIVISION BY 9

41.4 How it works

That’s how division can be replaced by multiplication and division with 2 nnumbers:

result=

input

divisor

=

input⋅^2

n

divisor

2 n

=

input⋅M

2 n

WhereMis amagiccoefficient.

This is howMcan be computed:

M=

2 n

divisor

So these code snippets usually have this form:

result=

input⋅M

2 n

Division by 2 nis usually done by simply shifting to the right. Ifn< 32 , then the low part of theproductis shifted (inEAXor
RAX). Ifn≥ 32 , then the high part of theproductis shifted (inEDXorRDX).

nis chosen in order to minimize the error.

When doing signed division, the sign of the multiplication result is also added to the output result.

Take a look at the difference:

int f3_32_signed(int a)
{
return a/3;
};

unsigned int f3_32_unsigned(unsigned int a)
{
return a/3;
};

In the unsigned version of the function, themagiccoefficient is0xAAAAAAAB and the multiplication result is divided by
233.

In the signed version of the function, themagic coefficient is0x55555556and the multiplication result is divided by 232.
There are no division instruction though: the result is just taken fromEDX.

The sign is also taken from the multiplication result: the high 32 bits of the result are shifted by 31 (leaving the sign in the
least significant bit ofEAX). 1 is added to the final result if the sign is negative, for result correction.

Listing 41.5: Optimizing MSVC 2012

_f3_32_unsigned PROC
mov eax, -1431655765 ; aaaaaaabH
mul DWORD PTR _a$[esp-4] ; unsigned multiply
; EDX=(input0xaaaaaaab)/2^32
shr edx, 1
; EDX=(input0xaaaaaaab)/2^33
mov eax, edx
ret 0
_f3_32_unsigned ENDP

_f3_32_signed PROC
mov eax, 1431655766 ; 55555556H
imul DWORD PTR _a$[esp-4] ; signed multiply
; take high part of product
; it is just the same as if to shift product by 32 bits right or to divide it by 2^32
mov eax, edx ; EAX=EDX=(input*0x55555556)/2^32
shr eax, 31 ; 0000001fH
add eax, edx ; add 1 if sign is negative
ret 0
_f3_32_signed ENDP