1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 28bc3bcc9SPaul Gortmaker #include <linux/export.h> 31977f032SJiri Slaby #include <linux/bitops.h> 43b9ed1a5SAkinobu Mita #include <asm/types.h> 53b9ed1a5SAkinobu Mita 63b9ed1a5SAkinobu Mita /** 73b9ed1a5SAkinobu Mita * hweightN - returns the hamming weight of a N-bit word 83b9ed1a5SAkinobu Mita * @x: the word to weigh 93b9ed1a5SAkinobu Mita * 103b9ed1a5SAkinobu Mita * The Hamming Weight of a number is the total number of bits set in it. 113b9ed1a5SAkinobu Mita */ 123b9ed1a5SAkinobu Mita __sw_hweight32(unsigned int w)13d61931d8SBorislav Petkovunsigned int __sw_hweight32(unsigned int w) 143b9ed1a5SAkinobu Mita { 1572d93104SLinus Torvalds #ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER 1639d997b5SAkinobu Mita w -= (w >> 1) & 0x55555555; 1739d997b5SAkinobu Mita w = (w & 0x33333333) + ((w >> 2) & 0x33333333); 1839d997b5SAkinobu Mita w = (w + (w >> 4)) & 0x0f0f0f0f; 1939d997b5SAkinobu Mita return (w * 0x01010101) >> 24; 2039d997b5SAkinobu Mita #else 21f9b41929SAkinobu Mita unsigned int res = w - ((w >> 1) & 0x55555555); 223b9ed1a5SAkinobu Mita res = (res & 0x33333333) + ((res >> 2) & 0x33333333); 23f9b41929SAkinobu Mita res = (res + (res >> 4)) & 0x0F0F0F0F; 24f9b41929SAkinobu Mita res = res + (res >> 8); 25f9b41929SAkinobu Mita return (res + (res >> 16)) & 0x000000FF; 2639d997b5SAkinobu Mita #endif 273b9ed1a5SAkinobu Mita } 28d61931d8SBorislav Petkov EXPORT_SYMBOL(__sw_hweight32); 293b9ed1a5SAkinobu Mita __sw_hweight16(unsigned int w)30d61931d8SBorislav Petkovunsigned int __sw_hweight16(unsigned int w) 313b9ed1a5SAkinobu Mita { 32f9b41929SAkinobu Mita unsigned int res = w - ((w >> 1) & 0x5555); 333b9ed1a5SAkinobu Mita res = (res & 0x3333) + ((res >> 2) & 0x3333); 34f9b41929SAkinobu Mita res = (res + (res >> 4)) & 0x0F0F; 35f9b41929SAkinobu Mita return (res + (res >> 8)) & 0x00FF; 363b9ed1a5SAkinobu Mita } 37d61931d8SBorislav Petkov EXPORT_SYMBOL(__sw_hweight16); 383b9ed1a5SAkinobu Mita __sw_hweight8(unsigned int w)39d61931d8SBorislav Petkovunsigned int __sw_hweight8(unsigned int w) 403b9ed1a5SAkinobu Mita { 41f9b41929SAkinobu Mita unsigned int res = w - ((w >> 1) & 0x55); 423b9ed1a5SAkinobu Mita res = (res & 0x33) + ((res >> 2) & 0x33); 43f9b41929SAkinobu Mita return (res + (res >> 4)) & 0x0F; 443b9ed1a5SAkinobu Mita } 45d61931d8SBorislav Petkov EXPORT_SYMBOL(__sw_hweight8); 463b9ed1a5SAkinobu Mita __sw_hweight64(__u64 w)47d61931d8SBorislav Petkovunsigned long __sw_hweight64(__u64 w) 483b9ed1a5SAkinobu Mita { 493b9ed1a5SAkinobu Mita #if BITS_PER_LONG == 32 50d61931d8SBorislav Petkov return __sw_hweight32((unsigned int)(w >> 32)) + 51d61931d8SBorislav Petkov __sw_hweight32((unsigned int)w); 523b9ed1a5SAkinobu Mita #elif BITS_PER_LONG == 64 5372d93104SLinus Torvalds #ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER 540136611cSAndi Kleen w -= (w >> 1) & 0x5555555555555555ul; 550136611cSAndi Kleen w = (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul); 560136611cSAndi Kleen w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful; 570136611cSAndi Kleen return (w * 0x0101010101010101ul) >> 56; 580136611cSAndi Kleen #else 59f9b41929SAkinobu Mita __u64 res = w - ((w >> 1) & 0x5555555555555555ul); 603b9ed1a5SAkinobu Mita res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul); 61f9b41929SAkinobu Mita res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful; 62f9b41929SAkinobu Mita res = res + (res >> 8); 63f9b41929SAkinobu Mita res = res + (res >> 16); 64f9b41929SAkinobu Mita return (res + (res >> 32)) & 0x00000000000000FFul; 650136611cSAndi Kleen #endif 663b9ed1a5SAkinobu Mita #endif 673b9ed1a5SAkinobu Mita } 68d61931d8SBorislav Petkov EXPORT_SYMBOL(__sw_hweight64); 69