On 1/26/06, Akinobu Mita <[email protected]> wrote:
> This patch introduces the C-language equivalents of the functions below:
> unsigned int hweight32(unsigned int w);
> unsigned int hweight16(unsigned int w);
> unsigned int hweight8(unsigned int w);
>
> HAVE_ARCH_HWEIGHT_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:10.000000000 +0900
> +++ 2.6-git/include/asm-generic/bitops.h 2006-01-25 19:14:11.000000000 +0900
> @@ -458,14 +458,38 @@
> #endif /* HAVE_ARCH_FFS_BITOPS */
>
>
> +#ifndef HAVE_ARCH_HWEIGHT_BITOPS
> +
> /*
> * hweightN: returns the hamming weight (i.e. the number
> * of bits set) of a N-bit word
> */
>
> -#define hweight32(x) generic_hweight32(x)
> -#define hweight16(x) generic_hweight16(x)
> -#define hweight8(x) generic_hweight8(x)
> +static inline unsigned int hweight32(unsigned int w)
> +{
> + unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
> + res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
> + res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
> + res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
> + return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
> +}
> +
This can be replaced with
register int res=w;
res=res-((res>>1)&0x55555555);
res=(res&0x33333333)+((res>>2)&0x33333333);
res=(res+(res>>4))&0x0f0f0f0f;
res=res+(res>>8);
return (res+(res>>16)) & 0xff;
Similar optimizations can be applied to the routines below. Please see
http://www-cs-faculty.stanford.edu/~knuth/mmixware.html errata and the code
in mmix-arith.w for the complete set of optimizations and credits.
http://www.jjj.de/fxt/fxtbook.pdf is another inspirational source for
such algorithms.
> +static inline unsigned int hweight16(unsigned int w)
> +{
> + unsigned int res = (w & 0x5555) + ((w >> 1) & 0x5555);
> + res = (res & 0x3333) + ((res >> 2) & 0x3333);
> + res = (res & 0x0F0F) + ((res >> 4) & 0x0F0F);
> + return (res & 0x00FF) + ((res >> 8) & 0x00FF);
> +}
> +
> +static inline unsigned int hweight8(unsigned int w)
> +{
> + unsigned int res = (w & 0x55) + ((w >> 1) & 0x55);
> + res = (res & 0x33) + ((res >> 2) & 0x33);
> + return (res & 0x0F) + ((res >> 4) & 0x0F);
> +}
> +
> +#endif /* HAVE_ARCH_HWEIGHT_BITOPS */
>
> #endif /* __KERNEL__ */
Regards,
Balbir
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
