libext2fs: add ext2fs_bitcount() function

This function efficiently counts the number of bits in a block of
memory.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Reviewed-by: Lukas Czerner <lczerner@redhat.com>

1 files changed, 40 insertions, 0 deletions

diff --git a/lib/ext2fs/bitops.c b/lib/ext2fs/bitops.c
index 9322a353..7c3f215f 100644
--- a/lib/ext2fs/bitops.c
+++ b/lib/ext2fs/bitops.c
@@ -116,3 +116,43 @@ int ext2fs_test_bit64(__u64 nr, const void * addr)
 	return (mask & *ADDR);
 }
 
+static unsigned int popcount8(unsigned int w)
+{
+	unsigned int res = w - ((w >> 1) & 0x55);
+	res = (res & 0x33) + ((res >> 2) & 0x33);
+	return (res + (res >> 4)) & 0x0F;
+}
+
+static unsigned int popcount32(unsigned int w)
+{
+	unsigned int res = w - ((w >> 1) & 0x55555555);
+	res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
+	res = (res + (res >> 4)) & 0x0F0F0F0F;
+	res = res + (res >> 8);
+	return (res + (res >> 16)) & 0x000000FF;
+}
+
+unsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes)
+{
+	const unsigned char *cp = addr;
+	const __u32 *p;
+	unsigned int res = 0;
+
+	while (((((unsigned long) cp) & 3) != 0) && (nbytes > 0)) {
+		res += popcount8(*cp++);
+		nbytes--;
+	}
+	p = (__u32 *) cp;
+
+	while (nbytes > 4) {
+		res += popcount32(*p++);
+		nbytes -= 4;
+	}
+	cp = (const unsigned char *) p;
+
+	while (nbytes > 0) {
+		res += popcount8(*cp++);
+		nbytes--;
+	}
+	return res;
+}