1

I'm having a little trouble about understanding how Division and Modulo work in Assembly when compiled from C Code:

Source C Code:

int k1=55,k2=33;
int k3=0,k4=0;
k3=k1/4;
k4=k2/13;

int v1=30,v2=40,v6=50;
int v3=0,v4=0,v5=0;
puts("Modulo v1:");
v3=v1%20;
puts("Modulo v2:");
v4=v2%21;
puts("Modulo v3:");
v6=v3%18;


return 0;

IDA Disassembly :

mov     dword ptr [esp+3Ch], 55
mov     dword ptr [esp+38h], 33
mov     dword ptr [esp+34h], 0
mov     dword ptr [esp+30h], 0
mov     eax, [esp+3Ch] ;    "k3=k1/4"
cdq
and     edx, 3
add     eax, edx
sar     eax, 2
mov     [esp+34h], eax      
mov     ecx, [esp+38h] ;    "k4=k2/13"
mov     edx, 4EC4EC4Fh
mov     eax, ecx
imul    edx             ; Why Imul ?
sar     edx, 2
mov     eax, ecx
sar     eax, 1Fh
sub     edx, eax
mov     eax, edx
mov     [esp+30h], eax
mov     dword ptr [esp+2Ch], 30
mov     dword ptr [esp+28h], 28h
mov     dword ptr [esp+24h], 32h
mov     dword ptr [esp+20h], 0
mov     dword ptr [esp+1Ch], 0
mov     dword ptr [esp+18h], 0
mov     dword ptr [esp], offset aModuloV1 ; "Modulo v1:"
call    _puts
mov     ecx, [esp+2Ch]  ; "v3=v1%20"
mov     edx, 66666667h  ; Weird number ??
mov     eax, ecx
imul    edx             ; Why imul when it's Modulo ?
sar     edx, 3
mov     eax, ecx
sar     eax, 1Fh
sub     edx, eax
mov     eax, edx
shl     eax, 2
add     eax, edx
shl     eax, 2
sub     ecx, eax
mov     eax, ecx
mov     [esp+20h], eax
mov     dword ptr [esp], offset aModuloV2 ; "Modulo v2:"
call    _puts
mov     ecx, [esp+28h]
mov     edx, 30C30C31h ; Weird Number ??
mov     eax, ecx
imul    edx            ; Imul again ?
sar     edx, 2
mov     eax, ecx
sar     eax, 1Fh
sub     edx, eax
mov     eax, edx
shl     eax, 2
add     eax, edx
shl     eax, 2
add     eax, edx
sub     ecx, eax
mov     eax, ecx
mov     [esp+1Ch], eax
mov     dword ptr [esp], offset aModuloV3 ; "Modulo v3:"
call    _puts
mov     ecx, [esp+20h]
mov     edx, 38E38E39h
mov     eax, ecx
imul    edx          ; Why Imul ?
sar     edx, 2
mov     eax, ecx
sar     eax, 1Fh
sub     edx, eax
mov     eax, edx
shl     eax, 3
add     eax, edx
add     eax, eax
sub     ecx, eax
mov     eax, ecx
mov     [esp+24h], eax

My firsh thoughts that there will only be instructions such as DIV and MOD,but when it comes to IDA Disassembly,i see only instructions like

SAR,SHR (what are these 2 instructions doing with DIV and Modulo ?)

IMUL (Why imul when what i want are DIV and Modulo?)

AND (don't know what this is doing )

And some weird Numbers too :

mov     edx, 66666667h  ; Weird "66666667h" number ??

mov     edx, 30C30C31h ; Weird "30C30C31h" number ??

mov     edx, 38E38E39h ; Weird "38E38E39h" number ?

I have searched google many times but still can't find the full explaination which i can clearly unsderstand how these ASM instructions work as DIV and Modulo in C code.

Can someone explain these Assembly instructions step-by-step? Or any keywords for me to do some google search?

Mercy
  • 11
  • 3
  • 4
    `sar` and `shr` are right shifts (`>>`), `and` is of course bitwise and (`&`). These can be used for division and modulo with powers of two. For other cases the compiler may choose a magic number division instead. See this [excellent article](http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html). – Jester Nov 06 '18 at 01:07
  • 1
    Looks like you compiled this with GCC, which uses a multiplicative inverse even when making debug builds (anti-optimized `-O0`). Remainder is calculated as `x%20 = x - (x/20)*20` – Peter Cordes Nov 06 '18 at 03:10
  • *"My firsh thoughts that there will only be instructions such as DIV and MOD"* but why? :) Compilers are lot smarter than that, would you for example switch on optimization, you wouldn't find ANY calculations in the final machine code, it would just output correct results directly. They are trying to produce most performant machine code which is within they reach (the compiler still doesn't have infinite amount of resources to find absolutely optimal machine code for more complex C source, also "optimal" is very difficult to define in ASM, as performance vs size vs runtime matters). – Ped7g Nov 06 '18 at 07:13
  • @PeterCordes Yes indeed! I was trying to solve some Reverse-Engineering CTF Challenges which invoked Modulo and Div instructions.So i tried to compile C Code by GCC to see what is really going on under the hood. – Mercy Nov 07 '18 at 09:58
  • @Jester Your article is really helpful.Tks alot! – Mercy Nov 07 '18 at 09:59

0 Answers0