divdi3 division used for long long by gcc on x86

biginteger, c, gcc, integer-division, x86

Solution

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--;
}

Problem

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?

Original source