Re: Linux 2.1 kernel patch --- update /dev/random driver.
Alexander Kjeldaas (astor@guardian.no)
Mon, 25 May 1998 11:49:23 +0200
On Mon, May 25, 1998 at 12:31:16AM -0400, tytso@mit.edu wrote:
> * More asm magic....
> *
> * For entropy estimation, we need to do an integral base 2
> - * logarithm. By default, use an open-coded C version, although we do
> - * have a version which takes advantage of the Intel's x86's "bsr"
> - * instruction.
> + * logarithm.
> + *
> + * Note the "12bits" suffix - this is used for numbers between
> + * 0 and 4095 only. This allows a few shortcuts.
> */
> -#if (!defined (__i386__))
> -static inline __u32 int_ln(__u32 word)
> +#if 0 /* Slow but clear version */
> +static inline __u32 int_ln_12bits(__u32 word)
> {
> __u32 nbits = 0;
>
> - while (1) {
> - word >>= 1;
> - if (!word)
> - break;
> + while (word >>= 1)
> nbits++;
> - }
> return nbits;
> }
> -#else
> -static inline __u32 int_ln(__u32 word)
> +#else /* Faster (more clever) version, courtesy Colin Plumb */
> +static inline __u32 int_ln_12bits(__u32 word)
> {
> - __asm__("bsrl %1,%0\n\t"
> - "jnz 1f\n\t"
> - "movl $0,%0\n"
> - "1:"
> - :"=r" (word)
> - :"r" (word));
> - return 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
Isn't this the same as the ffs() function?
This seems to be needed several places in the kernel and there is
native support for this operation on many architectures. Someone has
already provided a patch to implement ffs in bitops.h but it hasn't
been included yet. Maybe it's a good idea to do so now?
astor
--
Alexander Kjeldaas, Guardian Networks AS, Trondheim, Norway
http://www.guardian.no/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu