Entropy fixes - fls
PATCH 1/11 Entropy fixes - fls
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.
drivers/char/random.c +9 -45
@@ -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); }
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."