This removes the improperly named "ln" function and replaces it with a
call to the potentially arch-optimized fls. This also adjusts the
entropy count appropriately taking into consideration the expected
entropy in sections of a scale-invariant distribution. Thanks to Arend
Bayer for additional help with this analysis.
diff -ur a/drivers/char/random.c b/drivers/char/random.c
--- a/drivers/char/random.c 2002-07-20 14:11:07.000000000 -0500
+++ b/drivers/char/random.c 2002-09-07 19:20:20.000000000 -0500
@@ -253,6 +253,8 @@
#include <linux/init.h>
#include <linux/fs.h>
#include <linux/tqueue.h>
+#include <linux/kernel_stat.h>
+#include <linux/bitops.h>
#include <asm/processor.h>
#include <asm/uaccess.h>
@@ -429,43 +431,6 @@
}
#endif
-/*
- * More asm magic....
- *
- * For entropy estimation, we need to do an integral base 2
- * logarithm.
- *
- * Note the "12bits" suffix - this is used for numbers between
- * 0 and 4095 only. This allows a few shortcuts.
- */
-#if 0 /* Slow but clear version */
-static inline __u32 int_ln_12bits(__u32 word)
-{
- __u32 nbits = 0;
-
- while (word >>= 1)
- nbits++;
- return nbits;
-}
-#else /* Faster (more clever) version, courtesy Colin Plumb */
-static inline __u32 int_ln_12bits(__u32 word)
-{
- /* Smear msbit right to make an n-bit mask */
- word |= word >> 8;
- word |= word >> 4;
- word |= word >> 2;
- word |= word >> 1;
- /* Remove one bit to make this a logarithm */
- word >>= 1;
- /* Count the bits set in the word */
- word -= (word >> 1) & 0x555;
- word = (word & 0x333) + ((word >> 2) & 0x333);
- word += (word >> 4);
- word += (word >> 8);
- return word & 15;
-}
-#endif
-
#if 0
#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
#else
@@ -774,15 +739,14 @@
if (delta > delta3)
delta = delta3;
- /*
- * delta is now minimum absolute delta.
- * Round down by 1 bit on general principles,
- * and limit entropy entimate to 12 bits.
+ /* Numerical integration of exponential (scale
+ * invariant) distribution suggests that x-bit numbers
+ * have no more than x-2 bits of entropy across their
+ * range. Throw out 3 bits to be safe and cap at 12
+ * bits.
*/
- delta >>= 1;
- delta &= (1 << 12) - 1;
-
- entropy = int_ln_12bits(delta);
+
+ entropy = fls((delta>>3) & 0xfff);
}
batch_entropy_store(num, time, entropy);
}
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.." - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Sep 15 2002 - 22:00:23 EST