How to divide two 64-bit numbers in Linux Kernel?

Question

Some code that rounds up the division to demonstrate (C-syntax):

#define SINT64 long long int
#define SINT32 long int

SINT64 divRound(SINT64 dividend, SINT64 divisor)
{
  SINT32 quotient1 = dividend / divisor;

  SINT32 modResult = dividend % divisor;
  SINT32 multResult = modResult * 2;
  SINT32 quotient2 = multResult / divisor;

  SINT64 result = quotient1 + quotient2;

  return ( result );
}

Now, if this were User-space we probably wouldn't even notice that our compiler is generating code for those operators (e.g. divdi3() for division). Chances are we link with libgcc without even knowing it. The problem is that Kernel-space is different (e.g. no libgcc). What to do?

Crawl Google for a while, notice that pretty much everyone addresses the unsigned variant:

#define UINT64 long long int
#define UINT32 long int

UINT64 divRound(UINT64 dividend, UINT64 divisor)
{
  UINT32 quotient1 = dividend / divisor;

  UINT32 modResult = dividend % divisor;
  UINT32 multResult = modResult * 2;
  UINT32 quotient2 = multResult / divisor;

  UINT64 result = quotient1 + quotient2;

  return ( result );
}

I know how to fix this one: Override udivdi3() and umoddi3() with do_div() from asm/div64.h. Done right? Wrong. Signed is not the same as unsigned, sdivdi3() does not simply call udivdi3(), they are separate functions for a reason.

Have you solved this problem? Do you know of a library that will help me do this? I'm really stuck so whatever you might see here that I just don't right now would be really helpful.

Thanks, Chad

Answer 1

I don't think (at least can't find a way to make) Chris' answer work in this case because do_div() actually changes the dividend in-place. Getting the absolute value implies a temporary variable whose value will change the way I require but can't be passed out of my __divdi3() override.

I don't see a way around the parameter-by-value signature of __divdi3() at this point except to mimic the technique used by do_div().

It might seem like I'm bending over backwards here and should just come up with an algorithm to do the 64-bit/32-bit division I actually need. The added complication here though is that I have a bunch of numerical code using the '/' operator and would need to go through that code and replace every '/' with my function calls.

I'm getting desperate enough to do just that though.

Thanks for any follow-up, Chad

Answer 2

Here's my really naive solution. Your mileage may vary.

Keep a sign bit, which is sign(dividend) ^ sign(divisor). (Or *, or /, if you're storing your sign as 1 and -1, as opposed to false and true. Basically, negative if either one is negative, positive if none or both are negative.)

Then, call the unsigned division function on the absolute values of both. Then tack the sign back onto the result.

P.S. That is actually how __divdi3 is implemented in libgcc2.c (from GCC 4.2.3, the version that's installed on my Ubuntu system). I just checked. :-)

Answer 3

ldiv ?

Edit: reread title, so you might want to ignore this. Or not, depending on if it has an appropriate non-library version.

Answer 4

This functionality is introduced in /linux/lib/div64.c as early as kernel v2.6.22.