linux-kernel - [PATCH 1/2] bitmap: add bitmap_weight

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250720014146.432316-2-yury.norov@gmail.com>
Date: Sat, 19 Jul 2025 21:41:44 -0400
From: Yury Norov <yury.norov@...il.com>
To: Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>,
	Borislav Petkov <bp@...en8.de>,
	Dave Hansen <dave.hansen@...ux.intel.com>,
	"H. Peter Anvin" <hpa@...or.com>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Andrew Morton <akpm@...ux-foundation.org>,
	"Peter Zijlstra (Intel)" <peterz@...radead.org>,
	Ilpo Järvinen <ilpo.jarvinen@...ux.intel.com>,
	Fernando Fernandez Mancera <ffmancera@...eup.net>,
	"Xin Li (Intel)" <xin@...or.com>,
	x86@...nel.org,
	linux-kernel@...r.kernel.org
Cc: Yury Norov <yury.norov@...il.com>
Subject: [PATCH 1/2] bitmap: add bitmap_weight_from()

From: Yury Norov (NVIDIA) <yury.norov@...il.com>

bitmap_weight_from is useful in topo_unit_count() and potentially
more spots.

Signed-off-by: Yury Norov (NVIDIA) <yury.norov@...il.com>
---
 include/linux/bitmap.h | 11 +++++++++++
 lib/bitmap.c           | 28 ++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 595217b7a6e7..3cde3bd766b7 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -56,6 +56,7 @@ struct device;
  *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
  *  bitmap_weight_and(src1, src2, nbits)        Hamming Weight of and'ed bitmap
  *  bitmap_weight_andnot(src1, src2, nbits)     Hamming Weight of andnot'ed bitmap
+ *  bitmap_weight_from(src, start, nbits)       Hamming Weight starting from @start
  *  bitmap_set(dst, pos, nbits)                 Set specified bit area
  *  bitmap_clear(dst, pos, nbits)               Clear specified bit area
  *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
@@ -181,6 +182,8 @@ unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				 const unsigned long *bitmap2, unsigned int nbits);
 unsigned int __bitmap_weight_andnot(const unsigned long *bitmap1,
 				    const unsigned long *bitmap2, unsigned int nbits);
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int start, unsigned int nbits);
 void __bitmap_set(unsigned long *map, unsigned int start, int len);
 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
 
@@ -446,6 +449,14 @@ unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)
 	return __bitmap_weight(src, nbits);
 }
 
+static __always_inline
+unsigned int bitmap_weight_from(const unsigned long *src, unsigned int start, unsigned int nbits)
+{
+	if (small_const_nbits(start + nbits - 1))
+		return hweight_long(*src & GENMASK(start + nbits - 1, start));
+	return __bitmap_weight_from(src, start, nbits);
+}
+
 static __always_inline
 unsigned long bitmap_weight_and(const unsigned long *src1,
 				const unsigned long *src2, unsigned int nbits)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index b97692854966..eb9905071e3b 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -335,12 +335,40 @@ EXPORT_SYMBOL(__bitmap_subset);
 	w;									\
 })
 
+#define BITMAP_WEIGHT_FROM(FETCH, start, bits)					\
+({										\
+	unsigned long __start = (start), __bits = (bits);			\
+	unsigned int idx, w = 0;						\
+										\
+	if (unlikely(__start >= bits))						\
+		goto out;							\
+										\
+	idx = __start / BITS_PER_LONG;						\
+	w = (FETCH) & BITMAP_FIRST_WORD_MASK(__start);				\
+										\
+	for (++idx; idx < __bits / BITS_PER_LONG; idx++)			\
+		w += hweight_long(FETCH);					\
+										\
+	if (__bits % BITS_PER_LONG)						\
+		w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits));	\
+										\
+out:										\
+	w;									\
+})
+
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	return BITMAP_WEIGHT(bitmap[idx], bits);
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int start, unsigned int bits)
+{
+	return BITMAP_WEIGHT_FROM(bitmap[idx], start, bits);
+}
+EXPORT_SYMBOL(__bitmap_weight_from);
+
 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				const unsigned long *bitmap2, unsigned int bits)
 {
-- 
2.43.0