Tuesday, 29 August 2017

c - Why does GCC use multiplication by a strange number in implementing integer division?

I've been reading about div and mul assembly operations, and I decided to see them in action by writing a simple program in C:



File division.c



#include 
#include

int main()
{

size_t i = 9;
size_t j = i / 5;
printf("%zu\n",j);
return 0;
}


And then generating assembly language code with:



gcc -S division.c -O0 -masm=intel



But looking at generated division.s file, it doesn't contain any div operations! Instead, it does some kind of black magic with bit shifting and magic numbers. Here's a code snippet that computes i/5:



mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX
movabs rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul rdx ; Multiply 9 by magic number
mov rax, rdx ; Take only the upper 64 bits of the result
shr rax, 2 ; Shift these bits 2 places to the right (?)
mov QWORD PTR [rbp-8], rax ; Magically, RAX contains 9/5=1 now,

; so we can assign it to j


What's going on here? Why doesn't GCC use div at all? How does it generate this magic number and why does everything work?

No comments:

Post a Comment

casting - Why wasn't Tobey Maguire in The Amazing Spider-Man? - Movies & TV

In the Spider-Man franchise, Tobey Maguire is an outstanding performer as a Spider-Man and also reprised his role in the sequels Spider-Man...