Re: [PATCH 8/12] generic hweight{32,16,8}()

Re: [PATCH 8/12] generic hweight{32,16,8}()

[linux]

This is an extremely well-known technique.  You can see a similar version
that uses a multiply for the last few steps at
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
whch refers to 
"Software Optimization Guide for AMD Athlon 64 and Opteron Processors"
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF

It's section 8.6, "Efficient Implementation of Population-Count Function
in 32-bit Mode", pages 179-180.

It uses the name that I am more familiar with, "popcunt" (population count),
although "Hamming weight" also makes sense.

Anyway, the proof of correctness proceeds as follows:

	b = a - ((a >> 1) & 0x55555555);
	c = (b & 0x33333333) + ((b >> 2) & 0x33333333);
	d = (c + (c >> 4)) & 0x0f0f0f0f;
#if SLOW_MULTIPLY
	e = d + (d >> 8)
	f = e + (e >> 16);
	return f & 63;
#else
	/* Useful if multiply takes at most 4 cycles */
	return (d * 0x01010101) >> 24;
#endif

The input value a can be thought of as 32 1-bit fields each holding
their own hamming weight.  Now look at it as 16 2-bit fields.
Each 2-bit field a1..a0 has the value 2*a1 + a0.  This can be converted
into the hamming weight of the 2-bit field a1+a0 by subtracting a1.

That's what the (a >> 1) & mask subtraction does.  Since there can be no
borrows, you can just do it all at once.

Enumerating the 4 possible cases:

0b00 = 0  ->  0 - 0 = 0
0b01 = 1  ->  1 - 0 = 1
0b10 = 2  ->  2 - 1 = 1
0b11 = 3  ->  3 - 1 = 2


The next step consists of breaking up b (made of 16 2-bir fields) into
even and odd halves and adding them into 4-bit fields.  Since the largest
possible sum is 2+2 = 4, which will not fit into a 4-bit field, the 2-bit
fields have to be masked before they are added.


After this point, the masking can be delayed.  Each 4-bit field holds
a population count from 0..4, taking at most 3 bits.  These numbers can
be added without overflowing a 4-bit field, so we can compute
c + (c >> 4), and only then mask off the unwanted bits.


This produces d, a number of 4 8-bit fields, each in the range 0..8.
>From this point, we can shift and add d multiple times without overflowing
an 8-bit field, and only do a final mask at the end.

The number to mask with has to be at least 63 (so that 32 on't be truncated),
but can also be 128 or 255.  The x86 has a special encoding for signed
immediate byte values -128..127, so the value of 255 is slower.  On
other processors, a special "sign extend byte" instruction might be faster.


On a processor with fast integer multiplies (Athlon but not P4), you can
reduce the final few serially dependent instructions to a single integer
multiply.  Consider d to be 3 8-bit values d3, d2, d1 and d0, each in the
range 0..8.  The multiply forms the partial products:

           d3 d2 d1 d0
        d3 d2 d1 d0
     d3 d2 d1 d0
+ d3 d2 d1 d0
----------------------
           e3 e2 e1 e0

Where e3 = d3 + d2 + d1 + d0.   e2, e1 and e0 obviously cannot generate
any carries.

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Grant Grundler]

On Tue, Jan 31, 2006 at 11:49:49AM -0500, linux@horizon.com wrote:
> This is an extremely well-known technique.  You can see a similar version
> that uses a multiply for the last few steps at
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
> whch refers to 
> "Software Optimization Guide for AMD Athlon 64 and Opteron Processors"
> http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
...

> The next step consists of breaking up b (made of 16 2-bir fields) into
> even and odd halves and adding them into 4-bit fields.  Since the largest
> possible sum is 2+2 = 4, which will not fit into a 4-bit field, the 2-bit
> fields have to be masked before they are added.

Up to here, things were clear.
My guess is you meant "which will not fit into a 2-bit field".

thanks,
grant

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Balbir Singh]

> This is an extremely well-known technique.  You can see a similar version
> that uses a multiply for the last few steps at
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
> whch refers to
> "Software Optimization Guide for AMD Athlon 64 and Opteron Processors"
> http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF
>
> It's section 8.6, "Efficient Implementation of Population-Count Function
> in 32-bit Mode", pages 179-180.

Thanks for doing this. The proof looks good except for what has been
already pointed out by Grant Grundler.

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Balbir Singh]

> > Well, a proof is not difficult. This is a well tested proven piece of
> > code published by Don Knuth. If you need a proof, I can provide one.
>
> Thanks, I want.
>

Please bear with me, I am caught up with other things. I will try and
provide one soon.

Balbir

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Akinobu Mita]

On Fri, Jan 27, 2006 at 11:10:29AM +0530, Balbir Singh wrote:
> On 1/27/06, Akinobu Mita <mita@miraclelinux.com> wrote:
> > On Thu, Jan 26, 2006 at 12:42:09PM +0530, Balbir Singh wrote:
> >
> > > > +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;
> >
> > Probably you are right.
> > Unfortunately, it is difficult for me to prove that sane equivalence.
> >
> 
> Well, a proof is not difficult. This is a well tested proven piece of
> code published by Don Knuth. If you need a proof, I can provide one.

Thanks, I want.

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Balbir Singh]

On 1/27/06, Akinobu Mita <mita@miraclelinux.com> wrote:
> On Thu, Jan 26, 2006 at 12:42:09PM +0530, Balbir Singh wrote:
>
> > > +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;
>
> Probably you are right.
> Unfortunately, it is difficult for me to prove that sane equivalence.
>

Well, a proof is not difficult. This is a well tested proven piece of
code published by Don Knuth. If you need a proof, I can provide one.

> Anyway those hweight*() functions are copied from include/linux/bitops.h:
> generic_hweight*(). So you can optimize these functions.
>

You are right, even those functions can be optimized.

Balbir

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Bryan O'Sullivan]

On Fri, 2006-01-27 at 13:43 +0900, Akinobu Mita wrote:

> I think it's better than adding many HAVE_ARCH_*_BITOPS.
> I will have 14 new headers. So I want to make new directory
> include/asm-generic/bitops/:

While you're thrashing all that stuff, have you thought about adding
generic support for the atomic_*_mask functions?  Only eight of almost
30 arches actually implement them, which makes them worthless for
portable drivers.  The same approach you're using now with other bitops
will work equally well, or be just as broken, depending on the arch in
question :-)

	<b

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Akinobu Mita]

On Thu, Jan 26, 2006 at 12:42:09PM +0530, Balbir Singh wrote:

> > +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;

Probably you are right.
Unfortunately, it is difficult for me to prove that sane equivalence.

Anyway those hweight*() functions are copied from include/linux/bitops.h:
generic_hweight*(). So you can optimize these functions.

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Akinobu Mita]

On Thu, Jan 26, 2006 at 10:57:47AM -0800, Bryan O'Sullivan wrote:

> How about putting each class of bitop into its own header file in
> asm-generic, and getting the arches that need each one to include the
> specific files it needs in its own bitops.h header?
> 

I think it's better than adding many HAVE_ARCH_*_BITOPS.
I will have 14 new headers. So I want to make new directory
include/asm-generic/bitops/:

include/asm-generic/bitops/atomic.h
include/asm-generic/bitops/nonatomic.h
include/asm-generic/bitops/__ffs.h
include/asm-generic/bitops/ffz.h
include/asm-generic/bitops/fls.h
include/asm-generic/bitops/fls64.h
include/asm-generic/bitops/find.h
include/asm-generic/bitops/ffs.h
include/asm-generic/bitops/sched-ffs.h
include/asm-generic/bitops/hweight.h
include/asm-generic/bitops/hweight64.h
include/asm-generic/bitops/ext2-atomic.h
include/asm-generic/bitops/ext2-nonatomic.h
include/asm-generic/bitops/minix.h

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Bryan O'Sullivan]

On Thu, 2006-01-26 at 12:36 +0900, Akinobu Mita wrote:

> HAVE_ARCH_HWEIGHT_BITOPS is defined when the architecture has its own
> version of these functions.

All of this HAVE_ARCH_xxx stuff gave Linus heartburn a few weeks ago,
and you're massively increasing its proliferation.

How about putting each class of bitop into its own header file in
asm-generic, and getting the arches that need each one to include the
specific files it needs in its own bitops.h header?

For example, the hweight stuff would go into
asm-generic/bitops-hweight.h, and then asm-foo/bitops.h would just use

#include <asm-generic/bitops-hweight.h>

or else define its own if it didn't need the generic versions.

	<b

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Rutger Nijlunsing]

[snip]
> >  /*
> >   * 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.

Ah, the joys of bit twiddling!

http://graphics.stanford.edu/~seander/bithacks.html
...has some more.

-- 
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

Re: [PATCH 8/12] generic hweight{32,16,8}()

[Balbir Singh]

On 1/26/06, Akinobu Mita <mita@miraclelinux.com> 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

[PATCH 8/12] generic hweight{32,16,8}()

[Akinobu Mita]

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);
+}
+
+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__ */