From ac493821ea0af9767a4c0f21a322133494bcdc48 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Wed, 4 Jul 2001 14:04:58 -0400 Subject: [PATCH] Add new functions to bitops.h to find quickly search for set bits in a bitmask. (In both C and i386 assembler). --- lib/ext2fs/ChangeLog | 6 +++ lib/ext2fs/Makefile.in | 35 +++++++++++++++- lib/ext2fs/bitops.h | 106 +++++++++++++++++++++++++++++++++++++++++++++++- lib/ext2fs/tst_bitops.c | 44 ++++++++++++++++++++ 4 files changed, 188 insertions(+), 3 deletions(-) create mode 100644 lib/ext2fs/tst_bitops.c diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog index 43e23f6..740df89 100644 --- a/lib/ext2fs/ChangeLog +++ b/lib/ext2fs/ChangeLog @@ -1,3 +1,9 @@ +2001-07-04 Theodore Tso + + * bitops.h (ext2fs_find_first_bit_set, ext2fs_find_next_bit_set): + Add new functions (C and in i386 assembler) which quickly + find bits set in a bitmask. + 2001-06-23 Theodore Tso * Makefile.in, ext_attr.c, ext2_attr.c, ext2fs.h: Add new files diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in index 948a873..d301d98 100644 --- a/lib/ext2fs/Makefile.in +++ b/lib/ext2fs/Makefile.in @@ -112,7 +112,12 @@ SRCS= ext2_err.c \ $(srcdir)/unlink.c \ $(srcdir)/valid_blk.c \ $(srcdir)/version.c \ - $(srcdir)/write_bb_file.c + $(srcdir)/write_bb_file.c \ + $(srcdir)/tst_badblocks.c \ + $(srcdir)/tst_bitops.c \ + $(srcdir)/tst_byteswap.c \ + $(srcdir)/tst_getsize.c \ + $(srcdir)/tst_iscan.c HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h HFILES_IN= ext2_err.h ext2_types.h @@ -188,6 +193,10 @@ tst_byteswap: tst_byteswap.o bitops.o $(STATIC_LIBEXT2FS) $(CC) -o tst_byteswap tst_byteswap.o bitops.o $(STATIC_LIBEXT2FS) \ $(LIBCOM_ERR) +tst_bitops: tst_bitops.o inline.o $(STATIC_LIBEXT2FS) + $(CC) -o tst_bitops tst_bitops.o inline.o \ + $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) + mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) $(CC) -o mkjournal $(srcdir)/mkjournal.c -DDEBUG $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) $(ALL_CFLAGS) @@ -309,6 +318,10 @@ expanddir.o: $(srcdir)/expanddir.c $(srcdir)/ext2_fs.h \ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +ext_attr.o: $(srcdir)/ext_attr.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2_ext_attr.h \ + $(srcdir)/ext2fs.h $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h fileio.o: $(srcdir)/fileio.c $(srcdir)/ext2_fs.h \ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ @@ -442,3 +455,23 @@ write_bb_file.o: $(srcdir)/write_bb_file.c $(srcdir)/ext2_fs.h \ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +tst_badblocks.o: $(srcdir)/tst_badblocks.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ + $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +tst_bitops.o: $(srcdir)/tst_bitops.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ + $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +tst_byteswap.o: $(srcdir)/tst_byteswap.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ + $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +tst_getsize.o: $(srcdir)/tst_getsize.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ + $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h +tst_iscan.o: $(srcdir)/tst_iscan.c $(srcdir)/ext2_fs.h \ + $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \ + $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \ + $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/bitops.h diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h index 3a3e275..176fc2f 100644 --- a/lib/ext2fs/bitops.h +++ b/lib/ext2fs/bitops.h @@ -105,11 +105,12 @@ extern void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map); #endif #endif -#if ((defined __GNUC__) && (defined(__i386__) || defined(__i486__) || \ - defined(__i586__))) +#if ((defined __GNUC__) && !defined(_EXT2_USE_C_VERSIONS_) && \ + (defined(__i386__) || defined(__i486__) || defined(__i586__))) #define _EXT2_HAVE_ASM_BITOPS_ #define _EXT2_HAVE_ASM_SWAB_ +#define _EXT2_HAVE_ASM_FINDBIT_ /* * These are done by inline assembly for speed reasons..... @@ -156,6 +157,60 @@ _INLINE_ int ext2fs_test_bit(int nr, const void * addr) return oldbit; } +#ifndef C_VERSIONS +_INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size) +{ + int d0, d1, d2; + int res; + + if (!size) + return 0; + /* This looks at memory. Mark it volatile to tell gcc not to move it around */ + __asm__ __volatile__( + "cld\n\t" + "xorl %%eax,%%eax\n\t" + "xorl %%edx,%%edx\n\t" + "repe; scasl\n\t" + "je 1f\n\t" + "movl -4(%%edi),%%eax\n\t" + "subl $4,%%edi\n\t" + "bsfl %%eax,%%edx\n" + "1:\tsubl %%ebx,%%edi\n\t" + "shll $3,%%edi\n\t" + "addl %%edi,%%edx" + :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2) + :"1" ((size + 31) >> 5), "2" (addr), "b" (addr)); + return res; +} + +_INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset) +{ + unsigned long * p = ((unsigned long *) addr) + (offset >> 5); + int set = 0, bit = offset & 31, res; + + if (bit) { + /* + * Look for zero in first byte + */ + __asm__("bsfl %1,%0\n\t" + "jne 1f\n\t" + "movl $32, %0\n" + "1:" + : "=r" (set) + : "r" (*p >> bit)); + if (set < (32 - bit)) + return set + offset; + set = 32 - bit; + p++; + } + /* + * No bit found yet, search remaining full bytes for a bit + */ + res = ext2fs_find_first_bit_set(p, size - 32 * (p - (unsigned long *) addr)); + return (offset + set + res); +} +#endif + #ifdef EXT2FS_ENABLE_SWAPFS _INLINE_ __u32 ext2fs_swab32(__u32 val) { @@ -354,6 +409,53 @@ _INLINE_ __u32 ext2fs_swab32(__u32 val) #endif /* !_EXT2_HAVE_ASM_SWAB */ +#if !defined(_EXT2_HAVE_ASM_FINDBIT_) +_INLINE_ int ext2fs_find_first_bit_set(void * addr, unsigned size) +{ + char *cp = (unsigned char *) addr; + int res = 0, d0; + + if (!size) + return 0; + + while ((size > res) && (*cp == 0)) { + cp++; + res += 8; + } + d0 = ffs(*cp); + if (d0 == 0) + return size; + + return res + d0 - 1; +} + +_INLINE_ int ext2fs_find_next_bit_set (void * addr, int size, int offset) +{ + unsigned char * p; + int set = 0, bit = offset & 7, res = 0, d0; + + res = offset >> 3; + p = ((unsigned char *) addr) + res; + + if (bit) { + set = ffs(*p & ~((1 << bit) - 1)); + if (set) + return (offset & ~7) + set - 1; + p++; + res += 8; + } + while ((size > res) && (*p == 0)) { + p++; + res += 8; + } + d0 = ffs(*p); + if (d0 == 0) + return size; + + return (res + d0 - 1); +} +#endif + /* These two routines moved to gen_bitmap.c */ extern int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap, __u32 bitno); diff --git a/lib/ext2fs/tst_bitops.c b/lib/ext2fs/tst_bitops.c new file mode 100644 index 0000000..fb4d3ad --- /dev/null +++ b/lib/ext2fs/tst_bitops.c @@ -0,0 +1,44 @@ +/* + * This testing program makes sure the bitops functions work + * + * Copyright (C) 2001 by Theodore Ts'o. + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +/* #define _EXT2_USE_C_VERSIONS_ */ + +#include +#include +#if HAVE_UNISTD_H +#include +#endif +#include +#include +#include +#include +#if HAVE_ERRNO_H +#include +#endif + +#include "ext2_fs.h" +#include "ext2fs.h" + +unsigned char bitarray[] = { + 0x80, 0xF0, 0x40, 0x40, 0x0, 0x0, 0x0, 0x0, 0x10, 0x20, 0x00, 0x00 + }; + +main(int argc, char **argv) +{ + int i, size; + + size = sizeof(bitarray)*8; + i = ext2fs_find_first_bit_set(bitarray, size); + while (i < size) { + printf("Bit set: %d\n", i); + i = ext2fs_find_next_bit_set(bitarray, size, i+1); + } +} -- 1.8.3.1