64-bit integer division

[evoex]

Hello everyone,

I need to implement 64-bit integer division (unsigned for now, but I'll need the signed version later as well) for printf. As my kernel is 32 bits, gcc doesn't natively support it. I could include the gcc library but I'd rather not... So, I need to implement this myself.

What is a good algorithm for this? I don't need it to be extremely optimized for now, I'd rather have a stub version that works but I can improve later.
Modulo should be part of it as well, but I think one algorithm will lead to the other easily.

Thanks in advance,
evoex

[bluemoon]

How about print hex as the stub?

One of the slowest method involve counting MSB bit position, subtraction and rotate, aka long division.

[Brynet-Inc]

OpenBSD's libc and libkern have GCC-compatible "quadword" functions, you can port them instead of using libgcc.

http://www.openbsd.org/cgi-bin/cvsweb/s ... libc/quad/

[evoex]

Daaamn, that does NOT look like an easy algorithm. I guess I'm just going to ignore "%lld" support for my kernel, and only implement "%llx"... Although I think there should be a relatively easy algorithm if the number divided by is always only 32 bits...

Thanks guys!

[Brendan]

Hi,

All you need to convert a 64-bit integer into an decimal value as an ASCII string is division by 10, or, dividing a 64-bit value by a 32-bit value is enough.

For 32-bit 80x86 assembly, the DIV instruction divides a 64-bit integer by a 32-bit value and gives you a 32-bit result (with a 32-bit remainder). The problem is overflow (e.g. if the result doesn't fit in 32-bits).

To get around that, you do it as a pair of divisions:

Code: Select all

    xor edx,edx
    mov eax,[dividend + 4]      ;edx:eax = high dword of dividend
    div dword [divisor]         ;eax = high dword of dividend / divisor; edx = high dword of dividend % divisor
    mov [result + 4],eax        ;result high dword = high dword of dividend / divisor
    mov eax,[dividend]          ;edx:eax = low dword of dividend + high dword of dividend % divisor
    div dword [divisor]         ;eax = (low dword of dividend + high dword of dividend % divisor) / divisor; edx = remainder
    mov [result],eax            ;result low dword = (low dword of dividend + high dword of dividend % divisor) / divisor
    mov [remainder],edx         ;remainder = (low dword of dividend + high dword of dividend % divisor) % divisor

For an example, imagine you're dividing 0x123456789ABCDEF0 by 10:

Code: Select all

    xor edx,edx
    mov eax,[dividend + 4]      ;edx:eax = 0x0000000012345678
    div dword [divisor]         ;eax = 0x01D208A5; edx = 0x00000006
    mov [result + 4],eax        ;result high dword = 0x01D208A5
    mov eax,[dividend]          ;edx:eax = 0x000000069ABCDEF0
    div dword [divisor]         ;eax = 0xA912E318; edx = 0
    mov [result],eax            ;result low dword = 0xA912E318
    mov [remainder],edx         ;remainder = 0

Result = 0x01D208A5A912E318, remainder = 0.

Note: This is only for unsigned 64-bit integers. For signed 64-bit integers, if the highest bit is set display a "-" character and negate the integer, then treat it as unsigned. Negating a 64-bit signed integer goes like this:

Code: Select all

    not dword [value]
    not dword [value + 4]
    add dword [value],1
    adc dword [value + 4],0

Cheers,

Brendan

[Love4Boobies]

On the subject of division, I plan to add a series of operation optimization flags to my JIT compiler. However, to a lesser extent, they might be useful in a C library as well:

• Adjustable caches and look-up tables
• Multiplication and division as a series of shifts and additions/substractions; remainders using modulo.
• Given the fact that division is much slower than multiplication, division using multiplication (i.e., by multiplying by the reciprocal since we can exploit the fact that multiplication is performed using register pairs on the x86(-64)), which should be performed in the following two scenarios (provided the small memory footprint is not a problem):
  • The divident is a constant
  • The same (variable) divident is used enough times to compensate for the overhead of computing the reciprocal

However, I can't help but wonder why you have a printf implementation in your kernel.

[evoex]

@Brendan:
Amazing, thanks!

@Love4Boobies:
I've got a printf implementation for my debug_printf function, to display debug information (obviously), which will be optimized to nothing when NDEBUG is defined. I'll probably use it to deal with kernel panics as well, to print the messages nice and easily.
Nothing that needs to be fast...

[Love4Boobies]

If it's for (hopefully early) debugging purposes, why do you need to simulate printf (format specifiers, anything but hex, etc.)? You will get nowhere if you just write code obliviously. Any software project, esp. something as complex as an OS, should be properly eningeered. I don't know much about your project so I could be judging it prematurely; but just to be safe, you should click here.

[Solar]

I don't quite see where the problem is with having a fully qualified printf() implementation in kernel space. It's not as if you'd be calling it often. Personally, I like to clamp down on code duplication, and would happily accept my kernel-space print-whatever function and my user-space printf() implementation to be identical (instead of, say, having a dumbed-down kprintf() ).

[Combuster]

One consideration though, you'd probably want to strategically place some #if defined(FLOAT_SUPPORTED) if you are going to share code between kernel and userland in that fashion. You don't want to trip over FPU opcodes even if your format argument doesn't strictly need it.

[Brendan]

Hi,

I don't quite see where the problem is with having a fully qualified printf() implementation in kernel space. It's not as if you'd be calling it often.

Mostly something like that would only exist for early debugging, and would be ripped out later (once you've got a sane video driver interface, or a sane "kernel log" service). There's no point caring much about the features and quality of code you will throw away.

Personally, I wouldn't even bother with a reasonably complete "sprintf()" (even though that's something you're likely to keep, to add characters to the end of your kernel's log). You only really need to handle ASCII strings, hex and decimal, so things like floating point and octal aren't needed.

Finally, I wouldn't bother with a partial/incomplete "sprintf()" either. Given the amount of things you'll use it for, it's probably easier to just use lower level functions (strcpy(), itoa(), etc) directly, and avoid the insanity of searching a "const char[]" each time. As a bonus you'll probably find you don't need to bother with "varargs.h" at all either (and could dump the C calling conventions and use something more efficient like "fastcall" for everything in the kernel).

Of course I'm much more used to micro-kernels - the above opinion may not be too suitable for monolithic kernels...


Cheers,

Brendan