linux-kernel - [PATCH 1/1] div64: Speedup generic version

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>] [day] [month] [year] [list]

Message-Id: <1408291309-5941-1-git-send-email-zhaoxiu.zeng@gmail.com>
Date:	Mon, 18 Aug 2014 00:01:49 +0800
From:	Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
To:	Alasdair G Kergon <agk@...hat.com>,
	Mike Snitzer <snitzer@...hat.com>
Cc:	linux-kernel@...r.kernel.org, Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
Subject: [PATCH 1/1] div64: Speedup generic version

The new version do few 64 bits operations.
When high 32 bits of dividend becomes 0, use 32 bits division directly.

Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@...il.com>
---
 lib/div64.c | 63 +++++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 43 insertions(+), 20 deletions(-)

diff --git a/lib/div64.c b/lib/div64.c
index 4382ad7..89b9ed4 100644
--- a/lib/div64.c
+++ b/lib/div64.c
@@ -23,37 +23,60 @@
 /* Not needed on 64bit architectures */
 #if BITS_PER_LONG == 32
 
+typedef union {
+	struct {
+#if defined(__LITTLE_ENDIAN)
+		uint32_t vl;
+		uint32_t vh;
+#else
+		uint32_t vh;
+		uint32_t vl;
+#endif
+	} u;
+	uint64_t v;
+} UINT64;
+
 uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
 {
-	uint64_t rem = *n;
-	uint64_t b = base;
-	uint64_t res, d = 1;
-	uint32_t high = rem >> 32;
+	UINT64 rem = { .v = *n, };
+	UINT64 res, b;
+	int shift;
+	uint32_t d;
 
 	/* Reduce the thing a bit first */
-	res = 0;
-	if (high >= base) {
-		high /= base;
-		res = (uint64_t) high << 32;
-		rem -= (uint64_t) (high*base) << 32;
+	res.v = 0;
+	if (rem.u.vh >= base) {
+		res.u.vh = rem.u.vh / base;
+		rem.u.vh = rem.u.vh % base;
+		if (!rem.u.vh)
+			goto end;
 	}
 
-	while ((int64_t)b > 0 && b < rem) {
-		b = b+b;
-		d = d+d;
-	}
+	/*
+	 * Here rem.u.vh < base, so "fls(rem.u.vh) <= fls(base)".
+	 * If "fls(rem.u.vh) == fls(base)", shift equals 31.
+	 * else, shift equals "32 + fls(rem.u.vh) - fls(base)"
+	 */
+	shift = 32 + fls(rem.u.vh) - fls(base) - (fls(rem.u.vh) == fls(base));
+	b.u.vl = base << shift;
+	b.u.vh = base >> (32 - shift);
+	d = 1UL << shift;
 
 	do {
-		if (rem >= b) {
-			rem -= b;
-			res += d;
+		if (rem.v >= b.v) {
+			rem.v -= b.v;
+			res.u.vl |= d;
 		}
-		b >>= 1;
+		b.v >>= 1;
 		d >>= 1;
-	} while (d);
+	} while (rem.u.vh);
+
+end:
+	res.u.vl |= rem.u.vl / base;
+	rem.u.vl = rem.u.vl % base;
 
-	*n = res;
-	return rem;
+	*n = res.v;
+	return rem.u.vl;
 }
 
 EXPORT_SYMBOL(__div64_32);
-- 
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/