linux-kernel - Re: [PATCH] : A better approach to compute int_sqrt in lib/int

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

Message-ID: <20080717180008.GK31126@csclub.uwaterloo.ca>
Date:	Thu, 17 Jul 2008 14:00:09 -0400
From:	lsorense@...lub.uwaterloo.ca (Lennart Sorensen)
To:	Soumyadip Das Mahapatra <soumya.linux@...oo.com>
Cc:	peterz@...radead.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c

On Wed, Jul 16, 2008 at 06:05:56PM -0400, Lennart Sorensen wrote:
> It is also very inaccurate:
> 
> int_sqrt(9380489) returns 3062 with the old code and 146574 with the new
> code.  I wonder which one is closer to right.  It seems as soon as the
> input is 2^22 or higher, the new code goes all to hell and starts
> returning 2^16-1 or similarly silly values rather than 2^11-1 or
> similar.
> 
> Here is how I tested:
> 
> (compiled with gcc -Wall -O2 -std=c99)
> 
> #include <stdio.h>
> #include <unistd.h>
> #include <stdlib.h>
> 
> #define BITS_PER_LONG 32
> 
> unsigned long old_int_sqrt(unsigned long x) {
> 	unsigned long op, res, one;
> 
> 	op = x;
> 	res = 0;
> 
> 	one = 1UL << (BITS_PER_LONG - 2);
> 	while (one > op)
> 		one >>= 2;
> 
> 	while (one != 0) {
> 		if (op >= res + one) {
> 			op = op - (res + one);
> 			res = res +  2 * one;
> 		}
> 		res /= 2;
> 		one /= 4;
> 	}
> 	return res;
> }
> 
> unsigned long new_int_sqrt(unsigned long x) {
> 	unsigned long ub, lb, m;
> 	lb = 1;				/* lower bound */
> 	ub = (x >> 5) + 8;		/* upper bound */
> 	do {
> 		m = (ub + lb) >>  1;	/* middle value */
> 		if((m * m) > x)
This line overflows while the result is good if changed to:
 		if(((unsigned long long)m * (unsigned long long)m) > (unsigned long long)x)

Perhaps there is a better way to do this.

> 			ub = m - 1;
> 		else
> 			lb = m + 1;
> 	} while(ub >= lb);
> 
> 	return lb - 1;
> }
> 

-- 
Len Sorensen
--
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/