linux-kernel - [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 for Android: free password hash cracker in your pocket

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

Date:	Wed, 16 Jul 2008 13:19:31 -0700 (PDT)
From:	Soumyadip Das Mahapatra <soumya.linux@...oo.com>
To:	linux-kernel@...r.kernel.org
Subject: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c

Hello everybody !!
      The patch below is what i think is a better approach to
compute int_sqrt().

What about it ?

Thanks !!

---
--- a/lib/int_sqrt.c    2008-04-17 08:19:44.000000000 +0530
+++ b/lib/int_sqrt.c    2008-07-02 11:37:01.000000000 +0530
@@ -1,4 +1,3 @@
-
 #include <linux/kernel.h>
 #include <linux/module.h>
 
@@ -7,26 +6,21 @@
  * @x: integer of which to calculate the sqrt
  *
  * A very rough approximation to the sqrt() function.
+ * Improved version from the previous one.
  */
 unsigned long 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 ub, lb, m;
+    lb = 1;                /* lower bound */
+    ub = (x >> 5) + 8;        /* upper bound */
+    do {
+        m = (ub + lb) >>  1;    /* middle value */
+        if((m * m) > x)
+            ub = m - 1;
+        else
+            lb = m + 1;
+    } while(ub >= lb);
+    
+    return lb - 1;
 }
 EXPORT_SYMBOL(int_sqrt);



      

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