linux-kernel - [PATCH] lib/int_sqrt.c: optimize for small argument values

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: <20171019203137.131042-1-md@google.com>
Date:   Thu, 19 Oct 2017 13:31:37 -0700
From:   Michael Davidson <md@...gle.com>
To:     Andrew Morton <akpm@...ux-foundation.org>,
        Ingo Molnar <mingo@...nel.org>,
        David Miller <davem@...emloft.net>,
        Matthew Wilcox <mawilcox@...rosoft.com>,
        Kees Cook <keescook@...omium.org>
Cc:     linux-kernel@...r.kernel.org, Michael Davidson <md@...gle.com>
Subject: [PATCH] lib/int_sqrt.c: optimize for small argument values

int_sqrt() currently takes approximately constant time
regardless of the value of the argument. By using the
magnitude of the operand to set the initial conditions
for the calculation the cost becomes proportional to
log2 of the argument with the worst case behavior not
being measurably slower than it currently is.

Signed-off-by: Michael Davidson <md@...gle.com>
---
 lib/int_sqrt.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
index 1ef4cc344977..8394b0dcecd4 100644
--- a/lib/int_sqrt.c
+++ b/lib/int_sqrt.c
@@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)
 	if (x <= 1)
 		return x;
 
-	m = 1UL << (BITS_PER_LONG - 2);
+	m = 1UL << (__fls(x) & ~1UL);
 	while (m != 0) {
 		b = y + m;
 		y >>= 1;
-- 
2.15.0.rc1.287.g2b38de12cc-goog