Reverse Engineering for Beginners

CHAPTER 77. HAND DECOMPILING + Z3 SMT SOLVER CHAPTER 77. HAND DECOMPILING + Z3 SMT SOLVER

rdx=0x388D76AEE8CB1500;

rax=_lrotr(rax, rax&0xF); // rotate right

rax^=rdx;

rdx=0xD2E9EE7E83C4285B;

rax=_lrotl(rax, rax&0xF); // rotate left

r8=rax+rdx;

rdx=0x8888888888888889;

rax=r8;

rax*=rdx;

// RDX here is a high part of multiplication result

rdx=rdx>>5;

// RDX here is division result!

rax=rdx;

rcx=(r8+rdx*4)-(rax<<6);
rax=r8
rax=_lrotl (rax, rcx&0xFF); // rotate left
return rax;
};

We can spot the division using multiplication (41 on page 468). Indeed, let’s calculate the divider in Wolfram Mathematica:

Listing 77.1: Wolfram Mathematica

In[1]:=N[2^(64 + 5)/16^^8888888888888889]
Out[1]:=60.

We get this:

uint64_t f(uint64_t input)
{
uint64_t rax, rbx, rcx, rdx, r8;

ecx=input;

rdx=0x5D7E0D1F2E0F1F84;

rax=rcx;

rax*=rdx;

rdx=0x388D76AEE8CB1500;

rax=_lrotr(rax, rax&0xF); // rotate right

rax^=rdx;

rdx=0xD2E9EE7E83C4285B;

rax=_lrotl(rax, rax&0xF); // rotate left

r8=rax+rdx;

rax=rdx=r8/60;

rcx=(r8+rax4)-(rax64);
rax=r8
rax=_lrotl (rax, rcx&0xFF); // rotate left
return rax;
};

One more step:

uint64_t f(uint64_t input)
{
uint64_t rax, rbx, rcx, rdx, r8;

rax=input;

rax*=0x5D7E0D1F2E0F1F84;

rax=_lrotr(rax, rax&0xF); // rotate right

rax^=0x388D76AEE8CB1500;

rax=_lrotl(rax, rax&0xF); // rotate left

r8=rax+0xD2E9EE7E83C4285B;

rcx=r8-(r8/60)*60;

rax=r8

rax=_lrotl (rax, rcx&0xFF); // rotate left

return rax;