datapath: compat: Downstream the reciprocal_div.{c,h}.

[sliver-openvswitch.git] / datapath / linux / compat / reciprocal_div.c

diff --git a/datapath/linux/compat/reciprocal_div.c b/datapath/linux/compat/reciprocal_div.c
index 7ec7528..90ce7b1 100644 (file)
--- a/datapath/linux/compat/reciprocal_div.c
+++ b/datapath/linux/compat/reciprocal_div.c
@@ -1,13 +1,25 @@
+#include <linux/kernel.h>
 #include <asm/div64.h>
 #include <linux/reciprocal_div.h>
 
-#include <linux/version.h>
-#if LINUX_VERSION_CODE < KERNEL_VERSION(3,3,0)
-/* definition is required since reciprocal_value() is not exported */
-u32 reciprocal_value(u32 k)
+/*
+ * For a description of the algorithm please have a look at
+ * include/linux/reciprocal_div.h
+ */
+
+struct reciprocal_value reciprocal_value(u32 d)
 {
-       u64 val = (1LL << 32) + (k - 1);
-       do_div(val, k);
-       return (u32)val;
+       struct reciprocal_value R;
+       u64 m;
+       int l;
+
+       l = fls(d - 1);
+       m = ((1ULL << 32) * ((1ULL << l) - d));
+       do_div(m, d);
+       ++m;
+       R.m = (u32)m;
+       R.sh1 = min(l, 1);
+       R.sh2 = max(l - 1, 0);
+
+       return R;
 }
-#endif