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