[PATCH] Fix do_div() for all architectures

This offers a generic do_div64() that actually does the right thing,
unlike some architectures that "optimized" the 64-by-32 divide into
just a 32-bit divide.

Both ppc and sh were already providing an assembly optimized
__div64_32().  I called my function the same, so that their optimized
versions will automatically override mine in lib.a.

I've only tested extensively on m68knommu (uClinux) and made
sure generated code is reasonably short. Should be ok also on
parisc, since it's the same algorithm they were using before.

 - add generic C implementations of the do_div() for 32bit and 64bit
   archs in asm-generic/div64.h;

 - add generic library support function __div64_32() to handle the
   full 64/32 case on 32bit archs;

 - kill multiple copies of generic do_div() in architecture
   specific subdirs. Most copies were either buggy or not doing
   what they were supposed to do;

 - ensure all surviving instances of do_div() have their parameters
   correctly parenthesized to avoid funny side-effects;

2 files changed, 46 insertions, 1 deletions

diff --git a/lib/Makefile b/lib/Makefile
index 9121869155a630..91e7b30d3ca0f9 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o
+	 kobject.o idr.o div64.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff --git a/lib/div64.c b/lib/div64.c
new file mode 100644
index 00000000000000..eab47437f18252
--- /dev/null
+++ b/lib/div64.c
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
+ *
+ * Based on former do_div() implementation from asm-parisc/div64.h:
+ *	Copyright (C) 1999 Hewlett-Packard Co
+ *	Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
+ *
+ *
+ * Generic C version of 64bit/32bit division and modulo, with
+ * 64bit result and 32bit remainder.
+ *
+ * The fast case for (n>>32 == 0) is handled inline by do_div(). 
+ *
+ * Code generated for this function might be very inefficient
+ * for some CPUs. div64_32() can be overridden by linking arch-specific
+ * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
+ */
+
+#include <linux/types.h>
+#include <asm/div64.h>
+
+uint32_t __div64_32(uint64_t *n, uint32_t base)
+{
+	uint32_t low, low2, high, rem;
+
+	low   = *n   & 0xffffffff;
+	high  = *n  >> 32;
+	rem   = high % (uint32_t)base;
+	high  = high / (uint32_t)base;
+	low2  = low >> 16;
+	low2 += rem << 16;
+	rem   = low2 % (uint32_t)base;
+	low2  = low2 / (uint32_t)base;
+	low   = low  & 0xffff;
+	low  += rem << 16;
+	rem   = low  % (uint32_t)base;
+	low   = low  / (uint32_t)base;
+
+	*n = low +
+		((uint64_t)low2 << 16) +
+		((uint64_t)high << 32);
+
+	return rem;
+}
+