From: Hongzhen Luo <hongz...@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 <jeffl...@linux.alibaba.com> [1]
[1] https://lore.kernel.org/r/20230802091750.74181-3-jeffl...@linux.alibaba.com
Signed-off-by: Hongzhen Luo <hongz...@linux.alibaba.com>
Signed-off-by: Gao Xiang <hsiang...@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
