linux-ext4 - [patch] small fix for e2p

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: <20060920085608.GA18351@openx1.frec.bull.fr>
Date:	Wed, 20 Sep 2006 10:56:08 +0200
From:	Alexandre Ratchov <alexandre.ratchov@...l.net>
To:	linux-ext4@...r.kernel.org
Cc:	Jean-Pierre Dion <jean-pierre.dion@...l.net>
Subject: [patch] small fix for e2p_percent()

hello,

e2p_percent() doesn't work for zero percent (``mke2fs -m0'' gets killed with
SIGFPE).

is there a reason for not simply using 64 bit arithmetic? perhaps to avoid
overflows for 7e+9TB file-systems :-), or just for correctness...

So, here is the patch that fixes this. In order to avoid integer overflows,
we pick 16 more bits to store ``base'' and do the exact division on 48 bits.
Since ``100 * base'' always fits in 48 bits, there's never overflow. This
still work if we remplace 'unsigned int' by 'unsigned long long'.

cheers,

-- Alexandre

Signed-off-by: Alexandre Ratchov <alexandre.ratchov@...l.net>

Index: e2fsprogs-1.39/lib/e2p/percent.c
===================================================================
--- e2fsprogs-1.39.orig/lib/e2p/percent.c	2006-09-20 12:07:05.000000000 +0200
+++ e2fsprogs-1.39/lib/e2p/percent.c	2006-09-20 12:33:20.000000000 +0200
@@ -14,18 +14,41 @@
 /*
  * We work really hard to calculate this accurately, while avoiding
  * an overflow.  "Is there a hyphen in anal-retentive?"  :-)
+ *
+ * -- "Yes there is, as in hair-splitting and nit-picking"
  */
 unsigned int e2p_percent(int percent, unsigned int base)
 {
-	unsigned int mask = ~((1 << (sizeof(unsigned int) - 1) * 8) - 1);
+	unsigned hi, lo, q, r;
 
-	if (100 % percent == 0)
-		return base / (100 / percent);
-	if (mask & base) 
-		return (base / 100) * percent;
-	return base * percent / 100;
+	/* 
+	 * in order to avoid overflow we write 'base' as:
+	 *
+	 *	base = hi * 2^16 + lo 
+	 * 
+	 * then we do all computations separately on 'hi' and 'lo'.
+	 * By using the definition of division:
+	 *
+	 *	precent * base = result * 100 + reminder
+	 *
+	 * (reminder < 100), we obtain the exact value of 'result' 
+	 * as follows:
+	 */
+#define BITS	16
+#define MASK	((1 << BITS) - 1)
+
+	hi = percent * (base >> BITS);
+	lo = percent * (base & MASK);
+
+	q = ((hi / 100) << BITS) + lo / 100;
+	r = ((hi % 100) << BITS) + lo % 100;
+		
+	return q + r / 100;
+#undef BITS
+#undef MASK
 }
 
+
 #ifdef DEBUG
 #include <unistd.h>
 #include <stdio.h>

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