Re: [PATCH 9/12] generic hweight64()
From: Balbir Singh
Date: Thu Jan 26 2006 - 02:04:31 EST
On 1/26/06, Akinobu Mita <mita@xxxxxxxxxxxxxxxx> wrote:
> This patch introduces the C-language equivalent of the function:
> unsigned long hweight64(__u64 w);
>
> HAVE_ARCH_HWEIGHT64_BITOPS is defined when the architecture has its own
> version of these functions.
>
> This code largely copied from:
> include/linux/bitops.h
>
> Index: 2.6-git/include/asm-generic/bitops.h
> ===================================================================
> --- 2.6-git.orig/include/asm-generic/bitops.h 2006-01-25 19:14:11.000000000 +0900
> +++ 2.6-git/include/asm-generic/bitops.h 2006-01-25 19:14:11.000000000 +0900
> @@ -491,6 +491,25 @@
>
> #endif /* HAVE_ARCH_HWEIGHT_BITOPS */
>
> +#ifndef HAVE_ARCH_HWEIGHT64_BITOPS
> +
> +static inline unsigned long hweight64(__u64 w)
> +{
> +#if BITS_PER_LONG < 64
> + return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
> +#else
> + u64 res;
> + res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul);
This can be replaced with
res = (w-((w >> 1) & 0x5555555555555555ul));
> + res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
> + res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful);
res = (res+(res>>4))&0x0F0F0F0F0F0F0F0Ful;
> + res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul);
> + res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul);
> + return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul);
> +#endif
> +}
> +
> +#endif /* HAVE_ARCH_HWEIGHT64_BITOPS */
> +
> #endif /* __KERNEL__ */
>
> #endif /* _ASM_GENERIC_BITOPS_H */
> -
Please see Don Knuth's MMIXWare for more credits and improvements to this
algorithm
Balbir
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/