lkml.org 
[lkml]   [2006]   [Feb]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRe: [patch 14/44] generic hweight{64,32,16,8}()
    On Wed, Feb 01, 2006 at 06:02:38PM +0900, Akinobu Mita 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);
    > unsigned long hweight64(__u64 w);
    >
    > In include/asm-generic/bitops/hweight.h
    >
    > This code largely copied from:
    > include/linux/bitops.h
    >
    > Signed-off-by: Akinobu Mita <mita@miraclelinux.com>
    > include/asm-generic/bitops/hweight.h | 54 +++++++++++++++++++++++++++++++++++
    > 1 files changed, 54 insertions(+)
    >
    > Index: 2.6-git/include/asm-generic/bitops/hweight.h
    > ===================================================================
    > --- /dev/null
    > +++ 2.6-git/include/asm-generic/bitops/hweight.h
    > @@ -0,0 +1,54 @@
    > +#ifndef _ASM_GENERIC_BITOPS_HWEIGHT_H_
    > +#define _ASM_GENERIC_BITOPS_HWEIGHT_H_
    > +
    > +#include <asm/types.h>
    > +
    > +/**
    > + * hweightN - returns the hamming weight of a N-bit word
    > + * @x: the word to weigh
    > + *
    > + * The Hamming Weight of a number is the total number of bits set in it.
    > + */
    > +
    > +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);
    > +}


    The first step can be implemented slightly better:

    unsigned int res = w-((w>>1)&0x55555555);

    as I found once on the web[1].

    Several of the following steps can also be simplified
    by omitting the masking when the result can't possibly
    cause a carry to propagate too far.

    This might also have a non negligible impact
    on code size.


    > +
    > +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);
    > +}
    > +
    > +static inline unsigned long hweight64(__u64 w)
    > +{
    > +#if BITS_PER_LONG == 32
    > + return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
    > +#elif BITS_PER_LONG == 64
    > + u64 res;
    > + res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul);
    > + res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
    > + res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful);
    > + res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul);
    > + res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul);
    > + return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul);
    > +#else
    > +#error BITS_PER_LONG not defined
    > +#endif
    > +}
    > +
    > +#endif /* _ASM_GENERIC_BITOPS_HWEIGHT_H_ */
    >


    Regards,
    Gabriel

    [1] It might be better to write the first line

    unsigned res = w - ((w&0xaaaaaaaa)>>1);

    but I can never remember what the C standard guarantess about
    right shifts values (very little IIRC). I believe that it will
    work properly on all architectures that GCC supports, however,
    and that it will help on many.
    -
    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-02-02 15:13    [W:0.032 / U:148.868 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site