b24413180f560 (Greg Kroah-Hartman 2017-11-01 15:07:57 +0100 1) // SPDX-License-Identifier: GPL-2.0
8bc3bcc93a2b4 (Paul Gortmaker 2011-11-16 21:29:17 -0500 2) #include <linux/export.h>
1977f032722c2 (Jiri Slaby 2007-10-18 23:40:25 -0700 3) #include <linux/bitops.h>
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 4) #include <asm/types.h>
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 5)
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 6) /**
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 7) * hweightN - returns the hamming weight of a N-bit word
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 8) * @x: the word to weigh
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 9) *
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 10) * The Hamming Weight of a number is the total number of bits set in it.
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 11) */
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 12)
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 13) unsigned int __sw_hweight32(unsigned int w)
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 14) {
72d931046030b (Linus Torvalds 2014-09-13 11:14:53 -0700 15) #ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 16) w -= (w >> 1) & 0x55555555;
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 17) w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 18) w = (w + (w >> 4)) & 0x0f0f0f0f;
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 19) return (w * 0x01010101) >> 24;
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 20) #else
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 21) unsigned int res = w - ((w >> 1) & 0x55555555);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 22) res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 23) res = (res + (res >> 4)) & 0x0F0F0F0F;
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 24) res = res + (res >> 8);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 25) return (res + (res >> 16)) & 0x000000FF;
39d997b514e12 (Akinobu Mita 2009-12-21 16:20:16 -0800 26) #endif
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 27) }
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 28) EXPORT_SYMBOL(__sw_hweight32);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 29)
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 30) unsigned int __sw_hweight16(unsigned int w)
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 31) {
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 32) unsigned int res = w - ((w >> 1) & 0x5555);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 33) res = (res & 0x3333) + ((res >> 2) & 0x3333);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 34) res = (res + (res >> 4)) & 0x0F0F;
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 35) return (res + (res >> 8)) & 0x00FF;
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 36) }
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 37) EXPORT_SYMBOL(__sw_hweight16);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 38)
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 39) unsigned int __sw_hweight8(unsigned int w)
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 40) {
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 41) unsigned int res = w - ((w >> 1) & 0x55);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 42) res = (res & 0x33) + ((res >> 2) & 0x33);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 43) return (res + (res >> 4)) & 0x0F;
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 44) }
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 45) EXPORT_SYMBOL(__sw_hweight8);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 46)
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 47) unsigned long __sw_hweight64(__u64 w)
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 48) {
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 49) #if BITS_PER_LONG == 32
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 50) return __sw_hweight32((unsigned int)(w >> 32)) +
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 51) __sw_hweight32((unsigned int)w);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 52) #elif BITS_PER_LONG == 64
72d931046030b (Linus Torvalds 2014-09-13 11:14:53 -0700 53) #ifdef CONFIG_ARCH_HAS_FAST_MULTIPLIER
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 54) w -= (w >> 1) & 0x5555555555555555ul;
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 55) w = (w & 0x3333333333333333ul) + ((w >> 2) & 0x3333333333333333ul);
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 56) w = (w + (w >> 4)) & 0x0f0f0f0f0f0f0f0ful;
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 57) return (w * 0x0101010101010101ul) >> 56;
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 58) #else
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 59) __u64 res = w - ((w >> 1) & 0x5555555555555555ul);
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 60) res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 61) res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 62) res = res + (res >> 8);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 63) res = res + (res >> 16);
f9b4192923fa6 (Akinobu Mita 2006-03-26 01:40:00 -0800 64) return (res + (res >> 32)) & 0x00000000000000FFul;
0136611c62e86 (Andi Kleen 2006-09-26 10:52:38 +0200 65) #endif
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 66) #endif
3b9ed1a5d2d12 (Akinobu Mita 2006-03-26 01:39:13 -0800 67) }
d61931d89be50 (Borislav Petkov 2010-03-05 17:34:46 +0100 68) EXPORT_SYMBOL(__sw_hweight64);