lkml.org 
[lkml]   [2006]   [Jan]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 9/12] generic hweight64()
On 1/26/06, Akinobu Mita <mita@miraclelinux.com> 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@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2006-01-26 08:08    [from the cache]
©2003-2014 Jasper Spaans. Advertise on this site