[PATCH] (1/7) entropy, take 2 - log2

[PATCH] (1/7) entropy, take 2 - log2

[Oliver Xymoron]

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.." 

Re: [PATCH] (1/7) entropy, take 2 - log2

[Abramo Bagnara]

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:abramo.bagnara@libero.it

Opera Unica                          Phone: +39.546.656023
Via Emilia Interna, 140
48014 Castel Bolognese (RA) - Italy

Re: [PATCH] (1/7) entropy, take 2 - log2

[Oliver Xymoron]

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.."