Branch data     Line data    Source code

       1                 :            : #include <linux/export.h>
       2                 :            : #include <linux/bitops.h>
       3                 :            : #include <asm/types.h>
       4                 :            : 
       5                 :            : /**
       6                 :            :  * hweightN - returns the hamming weight of a N-bit word
       7                 :            :  * @x: the word to weigh
       8                 :            :  *
       9                 :            :  * The Hamming Weight of a number is the total number of bits set in it.
      10                 :            :  */
      11                 :            : 
      12                 :          0 : unsigned int __sw_hweight32(unsigned int w)
      13                 :            : {
      14                 :            : #ifdef ARCH_HAS_FAST_MULTIPLIER
      15                 :            :         w -= (w >> 1) & 0x55555555;
      16                 :            :         w =  (w & 0x33333333) + ((w >> 2) & 0x33333333);
      17                 :            :         w =  (w + (w >> 4)) & 0x0f0f0f0f;
      18                 :            :         return (w * 0x01010101) >> 24;
      19                 :            : #else
      20                 :     888335 :         unsigned int res = w - ((w >> 1) & 0x55555555);
      21                 :     888335 :         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
      22                 :     888335 :         res = (res + (res >> 4)) & 0x0F0F0F0F;
      23                 :     888335 :         res = res + (res >> 8);
      24                 :     888335 :         return (res + (res >> 16)) & 0x000000FF;
      25                 :            : #endif
      26                 :            : }
      27                 :            : EXPORT_SYMBOL(__sw_hweight32);
      28                 :            : 
      29                 :          0 : unsigned int __sw_hweight16(unsigned int w)
      30                 :            : {
      31                 :          0 :         unsigned int res = w - ((w >> 1) & 0x5555);
      32                 :          0 :         res = (res & 0x3333) + ((res >> 2) & 0x3333);
      33                 :          0 :         res = (res + (res >> 4)) & 0x0F0F;
      34                 :          0 :         return (res + (res >> 8)) & 0x00FF;
      35                 :            : }
      36                 :            : EXPORT_SYMBOL(__sw_hweight16);
      37                 :            : 
      38                 :          0 : unsigned int __sw_hweight8(unsigned int w)
      39                 :            : {
      40                 :          0 :         unsigned int res = w - ((w >> 1) & 0x55);
      41                 :          0 :         res = (res & 0x33) + ((res >> 2) & 0x33);
      42                 :          0 :         return (res + (res >> 4)) & 0x0F;
      43                 :            : }
      44                 :            : EXPORT_SYMBOL(__sw_hweight8);
      45                 :            : 
      46                 :          0 : unsigned long __sw_hweight64(__u64 w)
      47                 :            : {
      48                 :            : #if BITS_PER_LONG == 32
      49                 :          0 :         return __sw_hweight32((unsigned int)(w >> 32)) +
      50                 :          0 :                __sw_hweight32((unsigned int)w);
      51                 :            : #elif BITS_PER_LONG == 64
      52                 :            : #ifdef ARCH_HAS_FAST_MULTIPLIER
      53                 :            :         w -= (w >> 1) & 0x5555555555555555ul;
      54                 :            :         w =  (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
      55                 :            :         w =  (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
      56                 :            :         return (w * 0x0101010101010101ul) >> 56;
      57                 :            : #else
      58                 :            :         __u64 res = w - ((w >> 1) & 0x5555555555555555ul);
      59                 :            :         res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
      60                 :            :         res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
      61                 :            :         res = res + (res >> 8);
      62                 :            :         res = res + (res >> 16);
      63                 :            :         return (res + (res >> 32)) & 0x00000000000000FFul;
      64                 :            : #endif
      65                 :            : #endif
      66                 :            : }
      67                 :            : EXPORT_SYMBOL(__sw_hweight64);