What does this magic number do? [duplicate]

Question

This question already has an answer here:

• How can I reverse optimized integer division/modulo by constant operations? 3 answers

I've opened a 64 bit DLL file in IDA. One function has this pseudocode:

unsigned __int64 output;
ULONG input;
output = (unsigned __int64)(input * (unsigned __int128)0xE38E38E38E38E38Fui64 >> 64) >> 5;

Here is the equivalent assembly view:

mov     rcx, r13
mov     [rsp+56], rcx
mov     edx, [rsp+152]
mov     rax, 0E38E38E38E38E38Fh
mul     rdx
mov     r8, rdx
shr     r8, 5
mov     [r15], r8d
cmp     r8d, esi
cmova   r8d, ebx

When I want to compile that same code in MSVC++, it shows:

warning C4293: '>>': shift count negative or too big, undefined behavior

My question is, what does that long constant value do? Is there anything cryptic with that bit shifting?

Answer 1

although I flagged this question should be closed as duplicate, keeping it has some additional value because of the multiple different magic number values used, redirecting users encountering different magic values to the same resource.

On modern processors, integer division is one of the slowest arithmetic operations you can have a processor perform. Often orders of magnitude slower than other arithmetic operations.

It turns out that if divisor is constant you can avoid the expensive division operation using clever arithmetic tricks to a set of considerably faster operations (multiplications, additions and shifts), thus reaching overall faster performance at the expense of slightly larger code.

This is often called "division by magic numbers" because those numbers indeed often look like randomly selected numbers, that is not, however, the case. Compilers (and sometimes humans, too) use those tricks often nowadays, since size of code is less of an issue thanks to the exponential growth of storage capacity.

The general approach is that we can develop an equation like the following:

X / Y == X * (1/Y) == sqrt((X * 2^n) * (1/Y)), 2^n) == ((x << n) * 1/Y)>>n

In your case, 0xE38E38E38E38E38Fui64 with a shift of 3 bits is the hardcoded magic number used for division by 9 for unsigned 64 bit integers. Since your code actually shifts by 5, the actual divisor equals 9 * 2^2 = 36.