Page 1 of 1
64-bit integer division
Posted: Sun Jan 22, 2012 11:44 am
by 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
Re: 64-bit integer division
Posted: Sun Jan 22, 2012 11:57 am
by bluemoon
How about print hex as the stub?
One of the slowest method involve counting MSB bit position, subtraction and rotate, aka long division.
Re: 64-bit integer division
Posted: Sun Jan 22, 2012 1:41 pm
by 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/
Re: 64-bit integer division
Posted: Sun Jan 22, 2012 2:46 pm
by 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!
Re: 64-bit integer division
Posted: Sun Jan 22, 2012 11:45 pm
by 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
Re: 64-bit integer division
Posted: Mon Jan 23, 2012 12:30 am
by 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.
Re: 64-bit integer division
Posted: Mon Jan 23, 2012 10:58 am
by 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...
Re: 64-bit integer division
Posted: Mon Jan 23, 2012 11:49 pm
by 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.
Re: 64-bit integer division
Posted: Tue Jan 24, 2012 3:11 am
by 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() ).
Re: 64-bit integer division
Posted: Tue Jan 24, 2012 5:12 am
by 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.
Re: 64-bit integer division
Posted: Tue Jan 24, 2012 5:54 am
by Brendan
Hi,
Solar wrote: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