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