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