Take 2 of my entropy patches. Includes minor cleanups and should
address concerns about headless systems.
Patch 1:
This simplifies and properly names the log function.
Note that this is effectively a branchless generic_{fls,ffs,flz,ffz}.
I'll experiment with using this approach there later.
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-08-23 12:43: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>
@@ -430,41 +432,19 @@
#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)
+static inline __u32 int_log2_16bits(__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;
+
+ return hweight16(word)-1;
}
-#endif
#if 0
#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
@@ -782,7 +762,7 @@
delta >>= 1;
delta &= (1 << 12) - 1;
- entropy = int_ln_12bits(delta);
+ entropy = int_log2_16bits(delta);
}
batch_entropy_store(num, time, entropy);
}
--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
Oliver Xymoron wrote:
>
>> +static inline __u32 int_log2_16bits(__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;
> +
> + return hweight16(word)-1;
> }
> -#endif
I suggest you to use a more efficient version like that below:
static inline int ld2_16(__u16 v)
{
unsigned r = 0;
if (v >= 0x100) {
v >>= 8;
r += 8;
}
if (v >= 0x10) {
v >>= 4;
r += 4;
}
if (v >= 4) {
v >>= 2;
r += 2;
}
if (v >= 2)
r++;
return r;
}
--
Abramo Bagnara mailto:[email protected]
Opera Unica Phone: +39.546.656023
Via Emilia Interna, 140
48014 Castel Bolognese (RA) - Italy
On Sat, Aug 24, 2002 at 11:22:10AM +0200, Abramo Bagnara wrote:
> Oliver Xymoron wrote:
> >
> >> +static inline __u32 int_log2_16bits(__u32 word)
> > {
> > /* Smear msbit right to make an n-bit mask */
> > word |= word >> 8;
> > word |= word >> 4;
> > word |= word >> 2;
> > word |= word >> 1;
...
> > + return hweight16(word)-1;
> > }
> > -#endif
>
> I suggest you to use a more efficient version like that below:
>
> static inline int ld2_16(__u16 v)
> {
> unsigned r = 0;
>
> if (v >= 0x100) {
> v >>= 8;
> r += 8;
> }
> if (v >= 0x10) {
> v >>= 4;
> r += 4;
> }
> if (v >= 4) {
> v >>= 2;
> r += 2;
> }
> if (v >= 2)
> r++;
> return r;
Four branches are almost certainly less efficient. In any case, the
intent above is not to optimize the code, but to replace it with a
call to identical code that exists in bitops so that optimizations can
be made globally, and arch-specific if necessary.
--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."