1 /* SPDX-License-Identifier: GPL-2.0-only */
2
3 #include <xen/bitops.h>
4 #include <xen/init.h>
5 #include <xen/self-tests.h>
6
7 /* Value @b broadcast to every byte in a long */
8 #if BITS_PER_LONG == 32
9 # define BCST(b) ((b) * 0x01010101UL)
10 #elif BITS_PER_LONG == 64
11 # define BCST(b) ((b) * 0x0101010101010101UL)
12 #else
13 # error Extend me please
14 #endif
15
generic_hweightl(unsigned long x)16 unsigned int generic_hweightl(unsigned long x)
17 {
18 x -= (x >> 1) & BCST(0x55);
19 x = (x & BCST(0x33)) + ((x >> 2) & BCST(0x33));
20 x = (x + (x >> 4)) & BCST(0x0f);
21
22 if ( IS_ENABLED(CONFIG_HAS_FAST_MULTIPLY) )
23 return (x * BCST(0x01)) >> (BITS_PER_LONG - 8);
24
25 x += x >> 8;
26 x += x >> 16;
27 #if BITS_PER_LONG > 32
28 x += x >> 32;
29 #endif
30
31 return x & 0xff;
32 }
33
34 #ifdef CONFIG_SELF_TESTS
test_generic_hweightl(void)35 static void __init __constructor test_generic_hweightl(void)
36 {
37 RUNTIME_CHECK(generic_hweightl, 0, 0);
38 RUNTIME_CHECK(generic_hweightl, 1, 1);
39 RUNTIME_CHECK(generic_hweightl, 3, 2);
40 RUNTIME_CHECK(generic_hweightl, 7, 3);
41 RUNTIME_CHECK(generic_hweightl, 0xff, 8);
42
43 RUNTIME_CHECK(generic_hweightl, BCST(0x55), BITS_PER_LONG / 2);
44 RUNTIME_CHECK(generic_hweightl, BCST(0xaa), BITS_PER_LONG / 2);
45
46 RUNTIME_CHECK(generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2);
47 RUNTIME_CHECK(generic_hweightl, -1UL, BITS_PER_LONG);
48 }
49 #endif /* CONFIG_SELF_TESTS */
50