|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [xen master] xen/bitops: Introduce generic_hweightl() and hweightl()
commit 6bb2a4ff2df5b39a560beae4b6186e8061a38d66
Author: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
AuthorDate: Thu Aug 22 19:04:44 2024 +0100
Commit: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CommitDate: Tue Sep 3 20:22:18 2024 +0100
xen/bitops: Introduce generic_hweightl() and hweightl()
There are 6 remaining callers in Xen:
* The two hweight32() calls, _domain_struct_bits() and
efi_find_gop_mode(),
are __init only.
* The two hweight_long() calls are both in bitmap_weight().
* The two hweight64() calls are hv_vpset_nr_banks() and x86_emulate().
Only bitmap_weight() and possibly hv_vpset_nr_banks() can be considered fast
paths, and they're all of GPR-width form.
Furthermore, the differences between a generic int and generic long form is
only an ADD and SHIFT, and only in !CONFIG_HAS_FAST_MULTIPLY builds.
Therefore, it is definitely not worth having both generic implemenations.
Implement generic_hweightl() based on the current generic_hweight64(),
adjusted to be compatible with ARM32, along with standard SELF_TESTS.
Implement hweightl() with usual constant-folding and arch opt-in support.
PPC
is the only architecture that devates from generic, and it simply uses the
builtin.
No functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
Reviewed-by: Jan Beulich <jbeulich@xxxxxxxx>
---
xen/arch/ppc/include/asm/bitops.h | 2 ++
xen/common/bitops.c | 14 +++++++++++
xen/include/xen/bitops.h | 18 ++++++++++++++
xen/lib/Makefile | 1 +
xen/lib/generic-hweightl.c | 49 +++++++++++++++++++++++++++++++++++++++
5 files changed, 84 insertions(+)
diff --git a/xen/arch/ppc/include/asm/bitops.h
b/xen/arch/ppc/include/asm/bitops.h
index eb3355812e..6e4e112b8b 100644
--- a/xen/arch/ppc/include/asm/bitops.h
+++ b/xen/arch/ppc/include/asm/bitops.h
@@ -124,6 +124,8 @@ static inline int test_and_set_bit(unsigned int nr,
volatile void *addr)
#define arch_fls(x) ((x) ? 32 - __builtin_clz(x) : 0)
#define arch_flsl(x) ((x) ? BITS_PER_LONG - __builtin_clzl(x) : 0)
+#define arch_hweightl(x) __builtin_popcountl(x)
+
/**
* hweightN - returns the hamming weight of a N-bit word
* @x: the word to weigh
diff --git a/xen/common/bitops.c b/xen/common/bitops.c
index b504dd1308..5e5d20d225 100644
--- a/xen/common/bitops.c
+++ b/xen/common/bitops.c
@@ -133,6 +133,19 @@ static void __init test_multiple_bits_set(void)
CHECK(multiple_bits_set, 0xc000000000000000ULL, true);
}
+static void __init test_hweight(void)
+{
+ /* unsigned int hweightl(unsigned long) */
+ CHECK(hweightl, 0, 0);
+ CHECK(hweightl, 1, 1);
+ CHECK(hweightl, 3, 2);
+ CHECK(hweightl, 7, 3);
+ CHECK(hweightl, 0xff, 8);
+
+ CHECK(hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2);
+ CHECK(hweightl, -1UL, BITS_PER_LONG);
+}
+
static void __init __constructor test_bitops(void)
{
test_ffs();
@@ -140,4 +153,5 @@ static void __init __constructor test_bitops(void)
test_for_each_set_bit();
test_multiple_bits_set();
+ test_hweight();
}
diff --git a/xen/include/xen/bitops.h b/xen/include/xen/bitops.h
index 4d51708c4a..dde84443a9 100644
--- a/xen/include/xen/bitops.h
+++ b/xen/include/xen/bitops.h
@@ -35,6 +35,12 @@ extern void __bitop_bad_size(void);
unsigned int attr_const generic_ffsl(unsigned long x);
unsigned int attr_const generic_flsl(unsigned long x);
+/*
+ * Hamming Weight, also called Population Count. Returns the number of set
+ * bits in @x.
+ */
+unsigned int attr_const generic_hweightl(unsigned long x);
+
/**
* generic__test_and_set_bit - Set a bit and return its old value
* @nr: Bit to set
@@ -306,6 +312,18 @@ static always_inline attr_const unsigned int
fls64(uint64_t x)
(_v & (_v - 1)) != 0; \
})
+static always_inline attr_const unsigned int hweightl(unsigned long x)
+{
+ if ( __builtin_constant_p(x) )
+ return __builtin_popcountl(x);
+
+#ifdef arch_hweightl
+ return arch_hweightl(x);
+#else
+ return generic_hweightl(x);
+#endif
+}
+
/* --------------------- Please tidy below here --------------------- */
#ifndef find_next_bit
diff --git a/xen/lib/Makefile b/xen/lib/Makefile
index a485415964..b6558e108b 100644
--- a/xen/lib/Makefile
+++ b/xen/lib/Makefile
@@ -6,6 +6,7 @@ lib-y += ctype.o
lib-y += find-next-bit.o
lib-y += generic-ffsl.o
lib-y += generic-flsl.o
+lib-y += generic-hweightl.o
lib-y += list-sort.o
lib-y += memchr.o
lib-y += memchr_inv.o
diff --git a/xen/lib/generic-hweightl.c b/xen/lib/generic-hweightl.c
new file mode 100644
index 0000000000..c242d4c2d9
--- /dev/null
+++ b/xen/lib/generic-hweightl.c
@@ -0,0 +1,49 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+
+#include <xen/bitops.h>
+#include <xen/init.h>
+#include <xen/self-tests.h>
+
+/* Value @b broadcast to every byte in a long */
+#if BITS_PER_LONG == 32
+# define BCST(b) ((b) * 0x01010101UL)
+#elif BITS_PER_LONG == 64
+# define BCST(b) ((b) * 0x0101010101010101UL)
+#else
+# error Extend me please
+#endif
+
+unsigned int generic_hweightl(unsigned long x)
+{
+ x -= (x >> 1) & BCST(0x55);
+ x = (x & BCST(0x33)) + ((x >> 2) & BCST(0x33));
+ x = (x + (x >> 4)) & BCST(0x0f);
+
+ if ( IS_ENABLED(CONFIG_HAS_FAST_MULTIPLY) )
+ return (x * BCST(0x01)) >> (BITS_PER_LONG - 8);
+
+ x += x >> 8;
+ x += x >> 16;
+#if BITS_PER_LONG > 32
+ x += x >> 32;
+#endif
+
+ return x & 0xff;
+}
+
+#ifdef CONFIG_SELF_TESTS
+static void __init __constructor test_generic_hweightl(void)
+{
+ RUNTIME_CHECK(generic_hweightl, 0, 0);
+ RUNTIME_CHECK(generic_hweightl, 1, 1);
+ RUNTIME_CHECK(generic_hweightl, 3, 2);
+ RUNTIME_CHECK(generic_hweightl, 7, 3);
+ RUNTIME_CHECK(generic_hweightl, 0xff, 8);
+
+ RUNTIME_CHECK(generic_hweightl, BCST(0x55), BITS_PER_LONG / 2);
+ RUNTIME_CHECK(generic_hweightl, BCST(0xaa), BITS_PER_LONG / 2);
+
+ RUNTIME_CHECK(generic_hweightl, 1 | (1UL << (BITS_PER_LONG - 1)), 2);
+ RUNTIME_CHECK(generic_hweightl, -1UL, BITS_PER_LONG);
+}
+#endif /* CONFIG_SELF_TESTS */
--
generated by git-patchbot for /home/xen/git/xen.git#master
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |