Reverse Engineering for Beginners

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

41.4.1 More theory

It works, because that is how it’s possible to replace division by multiplication:

x

c

=x

1

c

1

cis calledmultiplicative inverseand can be precomputed by compiler.

But this is for real numbers What about integers? It’s possible to findmultiplicative inversefor integer in the environment
of modulo arithmetics^3 .CPUregisters fits nicely: each is limited by 32 or 64 bits, so almost any arithmetic operation on
registers are in fact opeartions on modulo 232 or 264.

Read more about it in [War02, pp. 10-3].

41.5 Getting the divisor.

41.5.1 Variant #1

Often, the code looks like this:

mov eax, MAGICAL CONSTANT

imul input value

sar edx, SHIFTING COEFFICIENT ; signed division by 2 x using arithmetic shift right

mov eax, edx

shr eax, 31

add eax, edx

Let’s denote the 32-bitmagiccoefficient asM, the shifting coefficient asCand the divisor asD.

The divisor we need to get is:

D=

2 32+C

M

For example:

Listing 41.6: Optimizing MSVC 2012

mov eax, 2021161081 ; 78787879H

imul DWORD PTR _a$[esp-4]

sar edx, 3

mov eax, edx

shr eax, 31 ; 0000001fH

add eax, edx

This is:

D=

2 32+3

2021161081

The numbers are larger than 32-bit, so we can use Wolfram Mathematica for convenience:

Listing 41.7: Wolfram Mathematica

In[1]:=N[2^(32+3)/2021161081]
Out[1]:=17.

So the divisor from the code we used as example is 17.

For x64 division, things are the same, but 264 has to be used instead of 232 :

uint64_t f1234(uint64_t a)
{
return a/1234;
};

(^3) Wikipedia