From 01308c2bb5d7970c59ea3a61554ce58736dcc2a9 Mon Sep 17 00:00:00 2001
From: Jesse Gross <jesse@nicira.com>
Date: Fri, 15 Jul 2011 09:59:05 -0700
Subject: [PATCH] datapath: Backport reciprocal division.

The reciprocal division library did not exist until 2.6.20 and is
not currently exported in any version, so this backports it.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>
---
 datapath/linux/.gitignore                     |  1 +
 datapath/linux/Modules.mk                     |  2 +
 .../compat/include/linux/reciprocal_div.h     | 40 +++++++++++++++++++
 datapath/linux/compat/reciprocal_div.c        |  9 +++++
 4 files changed, 52 insertions(+)
 create mode 100644 datapath/linux/compat/include/linux/reciprocal_div.h
 create mode 100644 datapath/linux/compat/reciprocal_div.c

diff --git a/datapath/linux/.gitignore b/datapath/linux/.gitignore
index b99cbd34..d4341759 100644
--- a/datapath/linux/.gitignore
+++ b/datapath/linux/.gitignore
@@ -24,6 +24,7 @@
 /modules.order
 /netdevice.c
 /random32.c
+/reciprocal_div.c
 /skbuff-openvswitch.c
 /table.c
 /time.c
diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk
index 217f12d4..a3fdc782 100644
--- a/datapath/linux/Modules.mk
+++ b/datapath/linux/Modules.mk
@@ -5,6 +5,7 @@ openvswitch_sources += \
 	linux/compat/ip_output-openvswitch.c \
 	linux/compat/kmemdup.c \
 	linux/compat/netdevice.c \
+	linux/compat/reciprocal_div.c \
 	linux/compat/skbuff-openvswitch.c \
 	linux/compat/time.c
 openvswitch_headers += \
@@ -38,6 +39,7 @@ openvswitch_headers += \
 	linux/compat/include/linux/netlink.h \
 	linux/compat/include/linux/rculist.h \
 	linux/compat/include/linux/rcupdate.h \
+	linux/compat/include/linux/reciprocal_div.h \
 	linux/compat/include/linux/rtnetlink.h \
 	linux/compat/include/linux/skbuff.h \
 	linux/compat/include/linux/slab.h \
diff --git a/datapath/linux/compat/include/linux/reciprocal_div.h b/datapath/linux/compat/include/linux/reciprocal_div.h
new file mode 100644
index 00000000..f618bddc
--- /dev/null
+++ b/datapath/linux/compat/include/linux/reciprocal_div.h
@@ -0,0 +1,40 @@
+#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 /* Linux kernel < 2.6.20 */
+#endif /* __LINUX_RECIPROCAL_DIV_WRAPPER_H */
diff --git a/datapath/linux/compat/reciprocal_div.c b/datapath/linux/compat/reciprocal_div.c
new file mode 100644
index 00000000..6a3bd48f
--- /dev/null
+++ b/datapath/linux/compat/reciprocal_div.c
@@ -0,0 +1,9 @@
+#include <asm/div64.h>
+#include <linux/reciprocal_div.h>
+
+u32 reciprocal_value(u32 k)
+{
+	u64 val = (1LL << 32) + (k - 1);
+	do_div(val, k);
+	return (u32)val;
+}
-- 
2.30.2