]>
Commit | Line | Data |
---|---|---|
3b9ed1a5 AM |
1 | #include <linux/module.h> |
2 | #include <asm/types.h> | |
3 | ||
4 | /** | |
5 | * hweightN - returns the hamming weight of a N-bit word | |
6 | * @x: the word to weigh | |
7 | * | |
8 | * The Hamming Weight of a number is the total number of bits set in it. | |
9 | */ | |
10 | ||
11 | unsigned int hweight32(unsigned int w) | |
12 | { | |
13 | unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555); | |
14 | res = (res & 0x33333333) + ((res >> 2) & 0x33333333); | |
15 | res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F); | |
16 | res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF); | |
17 | return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF); | |
18 | } | |
19 | EXPORT_SYMBOL(hweight32); | |
20 | ||
21 | unsigned int hweight16(unsigned int w) | |
22 | { | |
23 | unsigned int res = (w & 0x5555) + ((w >> 1) & 0x5555); | |
24 | res = (res & 0x3333) + ((res >> 2) & 0x3333); | |
25 | res = (res & 0x0F0F) + ((res >> 4) & 0x0F0F); | |
26 | return (res & 0x00FF) + ((res >> 8) & 0x00FF); | |
27 | } | |
28 | EXPORT_SYMBOL(hweight16); | |
29 | ||
30 | unsigned int hweight8(unsigned int w) | |
31 | { | |
32 | unsigned int res = (w & 0x55) + ((w >> 1) & 0x55); | |
33 | res = (res & 0x33) + ((res >> 2) & 0x33); | |
34 | return (res & 0x0F) + ((res >> 4) & 0x0F); | |
35 | } | |
36 | EXPORT_SYMBOL(hweight8); | |
37 | ||
38 | unsigned long hweight64(__u64 w) | |
39 | { | |
40 | #if BITS_PER_LONG == 32 | |
41 | return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w); | |
42 | #elif BITS_PER_LONG == 64 | |
43 | u64 res; | |
44 | res = (w & 0x5555555555555555ul) + ((w >> 1) & 0x5555555555555555ul); | |
45 | res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul); | |
46 | res = (res & 0x0F0F0F0F0F0F0F0Ful) + ((res >> 4) & 0x0F0F0F0F0F0F0F0Ful); | |
47 | res = (res & 0x00FF00FF00FF00FFul) + ((res >> 8) & 0x00FF00FF00FF00FFul); | |
48 | res = (res & 0x0000FFFF0000FFFFul) + ((res >> 16) & 0x0000FFFF0000FFFFul); | |
49 | return (res & 0x00000000FFFFFFFFul) + ((res >> 32) & 0x00000000FFFFFFFFul); | |
50 | #else | |
51 | #error BITS_PER_LONG not defined | |
52 | #endif | |
53 | } | |
54 | EXPORT_SYMBOL(hweight64); |