(1/7) entropy, take 2 - log2
PATCH 1/1 (1/7) entropy, take 2 - log2
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.
drivers/char/random.c +6 -26
@@ -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); }
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
Quoted 10 lines · Oliver Xymoron
Quoted 2 lines
+static inline
__u32int_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;drivers/char/random.c +0
-2-/* Remove one bit to make this a logarithm */ - word >>=1 ;
drivers/char/random.c line 467
Quoted 10 lines
drivers/char/random.c +2
-7-/* 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;
}Signature · 5 lines
Abramo Bagnara mailto:[email protected] Opera Unica Phone: +39.546.656023 Via Emilia Interna, 140 48014 Castel Bolognese (RA) - Italy
Quoted 9 lines · Abramo Bagnara
Quoted 8 lines · Oliver Xymoron
Quoted 2 lines
+static inline
__u32int_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;
...
Quoted 17 lines
drivers/char/random.c line 467
Quoted 3 lines
drivers/char/random.c +1
-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;
Quoted 8 lines
}
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.
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."