diff options
author | Akinobu Mita <mita@miraclelinux.com> | 2006-03-26 04:39:13 -0500 |
---|---|---|
committer | Linus Torvalds <torvalds@g5.osdl.org> | 2006-03-26 11:57:11 -0500 |
commit | 3b9ed1a5d2d121f32d2cb4f2b05f1fc57c99c946 (patch) | |
tree | d8ea52d6b490c0e3b3851e1887c01700cc0115c6 /lib/hweight.c | |
parent | 09020adb61416c4307de35941a9725a5e33d9beb (diff) |
[PATCH] bitops: generic hweight{64,32,16,8}()
This patch introduces the C-language equivalents of the functions below:
unsigned int hweight32(unsigned int w);
unsigned int hweight16(unsigned int w);
unsigned int hweight8(unsigned int w);
unsigned long hweight64(__u64 w);
In include/asm-generic/bitops/hweight.h
This code largely copied from: include/linux/bitops.h
Signed-off-by: Akinobu Mita <mita@miraclelinux.com>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib/hweight.c')
-rw-r--r-- | lib/hweight.c | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/lib/hweight.c b/lib/hweight.c new file mode 100644 index 000000000000..721a4b8b4fb8 --- /dev/null +++ b/lib/hweight.c | |||
@@ -0,0 +1,54 @@ | |||
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); | ||