64 bit division on linux kernel
I'm looking for a 64 bit division algorithm but not depends on GPL licence.
I found the following code in Hacker Delight book (Figure 9-5):
unsigned long long udivdi3(unsigned long long u,
unsigned long long v)
if (v >> 32 == 0) {
if (u >> 32 < v)
return DIVU(u, v) & 0xFFFFFFFF;
else {
.....
}
}
The problem is that 'return DIVU' calculate a division of 64/32 so it is no what I looking for. What to do?
Eli Avraham2 Answers
This is the reason that compiler-rt exists. Here is the C implementation of what __udivdi3 ultimately calls, but note that platform-specific assembly versions are also used, e.g. on x86.
But really, there's no point in avoiding libgcc for this - it is much more mature, supports many more platforms, and with the Runtime Library Exception the GPL is largely defanged - and you definitely shouldn't be modifying the upstream source for this so there's no modified source code that you have to make available.
o11cIt seems to be tricky to do 64-bit division in Linux kernel code. I'm not sure you're having the same problem I've had, but here's what I know.
It looks like the instruction sets don't fully handle 64-bit arithmetic. It looks like gcc emits calls to helper functions. For example, on ARM, if I write
t /= 86400;
where t is a 64-bit variable, my kernel build fails with "undefined reference to '__aeabi_ldivmod'". Evidently the kernel doesn't link against the full C library where functions like __aeabi_ldivmod exist.
The solution seems to be to call do_div instead. do_div isn't actually a function; it's a macro declared in an architecture-specific header file. (For ARM, it's in arch/arm/include/asm/div64.h. There's a similar file for x86.)
The solution is to replace t /= 86400 with
(void)do_div(t, 86400);
do_div divides its first argument by its second, in-place, and returns the remainder (which I'm ignoring in this example).
There's a big comment in div64.h telling you more about do_div and how to use it.
Steve SummitUser contributions licensed under CC BY-SA 3.0