What does this magic number do? [duplicate]

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?

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.

• Somehow 0xE38E38E38E38E38Fui64 >> 64) >> 5 is equivalent with divided by 36. May you explain that in your answer? Aug 24 '18 at 21:23
• Ah. Yes. I didn't notice the arithmetic shift in your code is 5 instead of the expected shift by 3. The additional shift by two bits means you're actually dividing by 9*2^2 = 9*4 = 36 Aug 24 '18 at 21:25
• But, diving by 9 and multiplying by 0xE38... will not be same as the second one 1/9 isn't finite. Aug 24 '18 at 21:41
• Those are close approximations that work for integers. You're correct it will not work when you assign the result into a floating point variable. Aug 24 '18 at 21:48