On Sat, 24 Nov 2012, Theodore Ts'o wrote:
> Date: Sat, 24 Nov 2012 19:36:31 -0500
> From: Theodore Ts'o <tytso@xxxxxxx>
> To: Ext4 Developers List <linux-ext4@xxxxxxxxxxxxxxx>
> Cc: Theodore Ts'o <tytso@xxxxxxx>
> Subject: [PATCH 3/6] 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@xxxxxxx>
> ---
> lib/ext2fs/bitops.c | 35 +++++++++++++++++++++++++++++++++++
> lib/ext2fs/bitops.h | 1 +
> lib/ext2fs/tst_bitmaps.c | 1 +
> lib/ext2fs/tst_bitmaps_exp | 3 +++
> 4 files changed, 40 insertions(+)
>
> diff --git a/lib/ext2fs/bitops.c b/lib/ext2fs/bitops.c
> index 9322a35..7f5b66f 100644
> --- a/lib/ext2fs/bitops.c
> +++ b/lib/ext2fs/bitops.c
> @@ -116,3 +116,38 @@ 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 count)
> +{
> + const unsigned char *cp = addr;
> + const __u32 *p = addr;
> + unsigned int res = 0;
> +
Again it is assumed that 8 will always be aliquot of 'count', but
it might be worth having a check for that ?
Otherwise it looks good.
Reviewed-by: Lukas Czerner <lczerner@xxxxxxxxxx>
> + if ((((unsigned long) addr) & 3) == 0) {
> + while (count > 4) {
> + res += popcount32(*p++);
> + count -= 4;
> + }
> + cp = (const unsigned char *) p;
> + }
> + while (count > 0) {
> + res += popcount8(*cp++);
> + count--;
> + }
> + return res;
> +}
> diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
> index 526870f..17e707c 100644
> --- a/lib/ext2fs/bitops.h
> +++ b/lib/ext2fs/bitops.h
> @@ -686,6 +686,7 @@ extern int ext2fs_test_bit(unsigned int nr, const void * addr);
> extern int ext2fs_set_bit64(__u64 nr,void * addr);
> extern int ext2fs_clear_bit64(__u64 nr, void * addr);
> extern int ext2fs_test_bit64(__u64 nr, const void * addr);
> +extern unsigned int ext2fs_bitcount(const void *addr, unsigned int count);
>
> #ifdef NO_INLINE_FUNCS
> extern void ext2fs_fast_set_bit(unsigned int nr,void * addr);
> diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
> index 5da3693..2a76292 100644
> --- a/lib/ext2fs/tst_bitmaps.c
> +++ b/lib/ext2fs/tst_bitmaps.c
> @@ -270,6 +270,7 @@ void dump_bitmap(ext2fs_generic_bitmap bmap, unsigned int start, unsigned num)
> for (i=0; i < len; i++)
> printf("%02x", buf[i]);
> printf("\n");
> + printf("bits set: %u\n", ext2fs_bitcount(buf, len));
> free(buf);
> }
>
> diff --git a/lib/ext2fs/tst_bitmaps_exp b/lib/ext2fs/tst_bitmaps_exp
> index 2d406ce..893f315 100644
> --- a/lib/ext2fs/tst_bitmaps_exp
> +++ b/lib/ext2fs/tst_bitmaps_exp
> @@ -36,6 +36,7 @@ tst_bitmaps: testb 16
> Block 16 is set
> tst_bitmaps: dump_bb
> block bitmap: 00f80000000000000000000000000000
> +bits set: 5
> tst_bitmaps: ffzb 11 16
> First unmarked block is 11
> tst_bitmaps: ffzb 12 16
> @@ -64,6 +65,7 @@ tst_bitmaps: setb 12 7
> Marking blocks 12 to 18
> tst_bitmaps: dump_bb
> block bitmap: 00f80300000000000000000000000000
> +bits set: 7
> tst_bitmaps: seti 2
> Setting inode 2, was clear before
> tst_bitmaps: seti 5
> @@ -82,6 +84,7 @@ tst_bitmaps: testi 1
> Inode 1 is clear
> tst_bitmaps: dump_ib
> inode bitmap: 1e000000
> +bits set: 4
> tst_bitmaps: ffzi 1 6
> First unmarked inode is 1
> tst_bitmaps: ffzi 2 5
>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
