[PATCH 2/5] erofs-utils: lib: add some bit operations

[Gao Xiang]

From: Hongzhen Luo <hongzhen at linux.alibaba.com>

Introduce following bitmap helpers:
	erofs_test_bit
	__erofs_set_bit
	__erofs_clear_bit
	erofs_find_next_bit

Signed-off-by: Jingbo Xu <jefflexu at linux.alibaba.com> [1]
[1] https://lore.kernel.org/r/20230802091750.74181-3-jefflexu@linux.alibaba.com
Signed-off-by: Hongzhen Luo <hongzhen at linux.alibaba.com>
Signed-off-by: Gao Xiang <hsiangkao at linux.alibaba.com>
---
 include/erofs/bitops.h | 40 ++++++++++++++++++++++++++++++++++++++++
 include/erofs/defs.h   |  5 +++++
 lib/Makefile.am        |  3 ++-
 lib/bitops.c           | 30 ++++++++++++++++++++++++++++++
 4 files changed, 77 insertions(+), 1 deletion(-)
 create mode 100644 include/erofs/bitops.h
 create mode 100644 lib/bitops.c

diff --git a/include/erofs/bitops.h b/include/erofs/bitops.h
new file mode 100644
index 0000000..058642f
--- /dev/null
+++ b/include/erofs/bitops.h
@@ -0,0 +1,40 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 */
+#ifndef __EROFS_BITOPS_H
+#define __EROFS_BITOPS_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "defs.h"
+
+static inline void __erofs_set_bit(int nr, volatile unsigned long *addr)
+{
+	unsigned long mask = BIT_MASK(nr);
+	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
+
+	*p  |= mask;
+}
+
+static inline void __erofs_clear_bit(int nr, volatile unsigned long *addr)
+{
+	unsigned long mask = BIT_MASK(nr);
+	unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
+
+	*p &= ~mask;
+}
+
+static inline int __erofs_test_bit(int nr, const volatile unsigned long *addr)
+{
+	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
+}
+
+unsigned long erofs_find_next_bit(const unsigned long *addr,
+				  unsigned long nbits, unsigned long start);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/include/erofs/defs.h b/include/erofs/defs.h
index e462338..051a270 100644
--- a/include/erofs/defs.h
+++ b/include/erofs/defs.h
@@ -286,6 +286,11 @@ static inline u32 get_unaligned_le64(const void *p)
 	(n) & (1ULL <<  1) ?  1 : 0	\
 )
 
+static inline unsigned int ffs_long(unsigned long s)
+{
+	return __builtin_ctzl(s);
+}
+
 static inline unsigned int fls_long(unsigned long x)
 {
 	return x ? sizeof(x) * 8 - __builtin_clzl(x) : 0;
diff --git a/lib/Makefile.am b/lib/Makefile.am
index ef98377..9cddc92 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -20,6 +20,7 @@ noinst_HEADERS = $(top_srcdir)/include/erofs_fs.h \
       $(top_srcdir)/include/erofs/io.h \
       $(top_srcdir)/include/erofs/list.h \
       $(top_srcdir)/include/erofs/print.h \
+      $(top_srcdir)/include/erofs/bitops.h \
       $(top_srcdir)/include/erofs/tar.h \
       $(top_srcdir)/include/erofs/trace.h \
       $(top_srcdir)/include/erofs/xattr.h \
@@ -34,7 +35,7 @@ liberofs_la_SOURCES = config.c io.c cache.c super.c inode.c xattr.c exclude.c \
 		      namei.c data.c compress.c compressor.c zmap.c decompress.c \
 		      compress_hints.c hashmap.c sha256.c blobchunk.c dir.c \
 		      fragments.c dedupe.c uuid_unparse.c uuid.c tar.c \
-		      block_list.c rebuild.c diskbuf.c
+		      block_list.c rebuild.c diskbuf.c bitops.c
 
 liberofs_la_CFLAGS = -Wall ${libuuid_CFLAGS} -I$(top_srcdir)/include
 if ENABLE_LZ4
diff --git a/lib/bitops.c b/lib/bitops.c
new file mode 100644
index 0000000..bb0c9ee
--- /dev/null
+++ b/lib/bitops.c
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0
+/*
+ * erofs-utils/lib/bitops.c
+ *
+ * Copyright (C) 2025, Alibaba Cloud
+ */
+#include <erofs/bitops.h>
+
+unsigned long erofs_find_next_bit(const unsigned long *addr,
+				  unsigned long nbits, unsigned long start)
+{
+	unsigned long tmp;
+
+	if (__erofs_unlikely(start >= nbits))
+		return nbits;
+
+	tmp = addr[start / BITS_PER_LONG];
+
+	tmp &= ~0UL << ((start) & (BITS_PER_LONG - 1));
+	start = round_down(start, BITS_PER_LONG);
+
+	while (!tmp) {
+		start += BITS_PER_LONG;
+		if (start >= nbits)
+			return nbits;
+
+		tmp = addr[start / BITS_PER_LONG];
+	}
+	return min(start + ffs_long(tmp), nbits);
+}
-- 
2.43.5