linux-kernel - [PATCH 1/1] GCD: add binary GCD algorithm

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <1408106956-12986-1-git-send-email-zhaoxiu.zeng@gmail.com>
Date:	Fri, 15 Aug 2014 20:49:16 +0800
From:	Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
To:	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...nel.org>,
	George Spelvin <linux@...izon.com>,
	David Howells <dhowells@...hat.com>,
	Peter Zijlstra <peterz@...radead.org>,
	AKASHI Takahiro <takahiro.akashi@...aro.org>,
	Josh Boyer <jwboyer@...hat.com>
Cc:	linux-kernel@...r.kernel.org, Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
Subject: [PATCH 1/1] GCD: add binary GCD algorithm

Because some architectures (alpha, armv6, etc.) don't provide hardware division,
the mod operation is slow! Binary GCD algorithm uses simple arithmetic operations,
it replaces division with arithmetic shifts, comparisons, and subtraction.

Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
---
 lib/Kconfig | 15 +++++++++++++++
 lib/gcd.c   | 31 ++++++++++++++++++++++++++++++-
 2 files changed, 45 insertions(+), 1 deletion(-)

diff --git a/lib/Kconfig b/lib/Kconfig
index a5ce0c7..80e8e54 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -177,6 +177,21 @@ config CRC8
 	  when they need to do cyclic redundancy check according CRC8
 	  algorithm. Module will be called crc8.
 
+#
+# GCD
+#
+choice
+	prompt "GCD implementation"
+	default GCD_ALGO_EUCLIDEAN
+
+config GCD_ALGO_EUCLIDEAN
+	bool "Euclidean algorithm"
+
+config GCD_ALGO_BINARY
+	bool "Binary GCD algorithm (Stein's algorithm)"
+
+endchoice
+
 config AUDIT_GENERIC
 	bool
 	depends on AUDIT && !AUDIT_ARCH
diff --git a/lib/gcd.c b/lib/gcd.c
index 3657f12..911ec7f 100644
--- a/lib/gcd.c
+++ b/lib/gcd.c
@@ -6,7 +6,7 @@
 unsigned long gcd(unsigned long a, unsigned long b)
 {
 	unsigned long r;
-
+#ifdef CONFIG_GCD_ALGO_EUCLIDEAN
 	if (a < b)
 		swap(a, b);
 
@@ -16,6 +16,35 @@ unsigned long gcd(unsigned long a, unsigned long b)
 		a = b;
 		b = r;
 	}
+#else
+	r = a | b;
+
+	if (!a || !b)
+		return r;
+
+	r = r ^ (r - 1);
+	if (!(a & r))
+		goto even_odd; /* a/c even, b/c odd */
+	if (!(b & r))
+		goto odd_even; /* a/c odd, b/c even */
+
+	/* a/c and b/c both odd */
+	while (a != b) {
+		if (a > b) {
+			a -= b;
+even_odd:
+			do
+				a >>= 1;
+			while (!(a & r));
+		} else {
+			b -= a;
+odd_even:
+			do
+				b >>= 1;
+			while (!(b & r));
+		}
+	}
+#endif
 	return b;
 }
 EXPORT_SYMBOL_GPL(gcd);
-- 
1.9.3

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/