[ovs-dev] [PATCH 1/3] datapath: Backport reciprocal divide functions.

[Jesse Gross]

This backports reciprocal_divide() to kernels before 2.6.20.  Note that
reciprocal_value() isn't exported in any kernel version, so it isn't possible
to use it.  The declaration is kept for consistency.  It's not actually needed
for any current use anyways.

Signed-off-by: Jesse Gross <jesse at nicira.com>
---
 datapath/linux-2.6/Modules.mk                      |    1 +
 .../compat-2.6/include/linux/reciprocal_div.h      |   39 ++++++++++++++++++++
 2 files changed, 40 insertions(+), 0 deletions(-)
 create mode 100644 datapath/linux-2.6/compat-2.6/include/linux/reciprocal_div.h

diff --git a/datapath/linux-2.6/Modules.mk b/datapath/linux-2.6/Modules.mk
index b7b9524..fbb5b54 100644
--- a/datapath/linux-2.6/Modules.mk
+++ b/datapath/linux-2.6/Modules.mk
@@ -35,6 +35,7 @@ openvswitch_headers += \
 	linux-2.6/compat-2.6/include/linux/netfilter_bridge.h \
 	linux-2.6/compat-2.6/include/linux/netfilter_ipv4.h \
 	linux-2.6/compat-2.6/include/linux/netlink.h \
+	linux-2.6/compat-2.6/include/linux/reciprocal_div.h \
 	linux-2.6/compat-2.6/include/linux/rculist.h \
 	linux-2.6/compat-2.6/include/linux/rcupdate.h \
 	linux-2.6/compat-2.6/include/linux/rtnetlink.h \
diff --git a/datapath/linux-2.6/compat-2.6/include/linux/reciprocal_div.h b/datapath/linux-2.6/compat-2.6/include/linux/reciprocal_div.h
new file mode 100644
index 0000000..dfa1d9e
--- /dev/null
+++ b/datapath/linux-2.6/compat-2.6/include/linux/reciprocal_div.h
@@ -0,0 +1,39 @@
+#ifndef _LINUX_RECIPROCAL_DIV_WRAPPER_H
+#define _LINUX_RECIPROCAL_DIV_WRAPPER_H
+
+#include <linux/version.h>
+#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,20)
+#include_next <linux/reciprocal_div.h>
+#else
+
+#include <linux/types.h>
+
+/*
+ * This file describes reciprocical division.
+ *
+ * This optimizes the (A/B) problem, when A and B are two u32
+ * and B is a known value (but not known at compile time)
+ *
+ * The math principle used is :
+ *   Let RECIPROCAL_VALUE(B) be (((1LL << 32) + (B - 1))/ B)
+ *   Then A / B = (u32)(((u64)(A) * (R)) >> 32)
+ *
+ * This replaces a divide by a multiply (and a shift), and
+ * is generally less expensive in CPU cycles.
+ */
+
+/*
+ * Computes the reciprocal value (R) for the value B of the divisor.
+ * Should not be called before each reciprocal_divide(),
+ * or else the performance is slower than a normal divide.
+ */
+extern u32 reciprocal_value(u32 B);
+
+
+static inline u32 reciprocal_divide(u32 A, u32 R)
+{
+	return (u32)(((u64)A * R) >> 32);
+}
+
+#endif
+#endif
-- 
1.7.1