Branch data     Line data    Source code

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