divdi3 division used for long long by gcc on x86

Question

When gcc sees multiplication or division of integer types that isn't supported in hardware, it generates call to special library function.

http://gcc.gnu.org/onlinedocs/gccint/Integer-library-routines.html#Integer-library-routines

According link above, long __divdi3 (long a, long b) used for division of long. However, here http://gcc.gnu.org/onlinedocs/gcc-3.3/gccint/Library-Calls.html divdi explained as "call for division of one signed double-word". When first source has cleary mapping of di suffix -> long arguments, second states divdi for double-word and udivdi for full-word (single, right?)

When I compile simple example

int main(int argc, char *argv[]) {
    long long t1, t2, tr;

    t1 = 1;
    t2 = 1;
    tr = t1 / t2;

    return tr;
}

with gcc -Wall -O0 -m32 -march=i386 (gcc ver. 4.7.2) dissamble shows me

    080483cc <main>:
     80483cc:       55                      push   %ebp
     80483cd:       89 e5                   mov    %esp,%ebp
     80483cf:       83 e4 f0                and    $0xfffffff0,%esp
     80483d2:       83 ec 30                sub    $0x30,%esp
     80483d5:       c7 44 24 28 01 00 00    movl   $0x1,0x28(%esp)
     80483dc:       00
     80483dd:       c7 44 24 2c 00 00 00    movl   $0x0,0x2c(%esp)
     80483e4:       00
     80483e5:       c7 44 24 20 01 00 00    movl   $0x1,0x20(%esp)
     80483ec:       00
     80483ed:       c7 44 24 24 00 00 00    movl   $0x0,0x24(%esp)
     80483f4:       00
     80483f5:       8b 44 24 20             mov    0x20(%esp),%eax
     80483f9:       8b 54 24 24             mov    0x24(%esp),%edx
     80483fd:       89 44 24 08             mov    %eax,0x8(%esp)
     8048401:       89 54 24 0c             mov    %edx,0xc(%esp)
     8048405:       8b 44 24 28             mov    0x28(%esp),%eax
     8048409:       8b 54 24 2c             mov    0x2c(%esp),%edx
     804840d:       89 04 24                mov    %eax,(%esp)
     8048410:       89 54 24 04             mov    %edx,0x4(%esp)
     8048414:       e8 17 00 00 00          call   8048430 <__divdi3>
     8048419:       89 44 24 18             mov    %eax,0x18(%esp)
     804841d:       89 54 24 1c             mov    %edx,0x1c(%esp)
     8048421:       8b 44 24 18             mov    0x18(%esp),%eax
     8048425:       c9                      leave
     8048426:       c3                      ret

Note 8048414: call 8048430 <__divdi3>.

I can't use gcc lib for my project and it's multiplatform. I hoped not to write all __* functions for all platforms (speed is not matter), but now I'm a bit confused.

Can somebody explain, why is there __divdi3 (not __divti3) call generated for long long int (64-bit) division?

Answer 1

On x86 machines, the term "word" usually implies presence of a 16-bit value. More generally in the computer-science world, word can denote values of virtually arbitrary lengths, with words of 10 or 12 bits not being uncommon in the embedded systems.

I believe that the terminology you have hit upon is used for the Linux/Unix systems just for the sake of unification on the level of the operating system and has nothing to do with the target platform of your build. An example of use of the same notation can be found in gdb, which uses w for the 32-bit word and hw for the 16-bit "half-word" (in the x86 sense).

Furthermore, this convention also extends to the standard IEEE-754 floating point numbers with ease, and is summarised in the few bullet points below

• s - single (precision, word) is used for four byte integers (int) / floats (float)
• d - double (precision) for eight byte integers (long or long long) / floats (double)
• t - ten bytes for integers (long long) / floats (long double)

This naming convention is used for all arithmetic built-ins, like __divsi3, __divdi3, __divti3 or __mulsi3, __muldi3, __multi3... (and all u - unsigned - variants). A complete list can be found here.

Division of 64-bit numbers on 32-bit machines uses advanced (and bit difficult) algorithm. However, you can still use algorithm principle you've learned in school. Here's simple pseudo-code for it (have a look on this answer about big-integers):

result = 0;
count = 0;
remainder = numerator;

while(highest_bit_of_divisor_not_set) {
    divisor = divisor << 1;
    count++;
}
while(remainder != 0) {
    if(remainder >= divisor) {
        remainder = remainder - divisor;
        result = result | (1 << count);
    }
    if(count == 0) {
        break;
    }
    divisor = divisor >> 1;
    count--;
}