From 5c195762cfba7ef442f65df6cb5d05fdf7c7ffd1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 22 Sep 2005 20:44:51 +0000 Subject: [PATCH] Implemented ffs() and unified it with fls() to bitops.h. --- lib/Makefile | 4 ++- lib/bit-ffs.c | 46 +++++++++++++++++++++++++++++++++ lib/{log2.c => bit-fls.c} | 23 ++++++++++++++--- lib/bitops.h | 40 +++++++++++++++++++++++++++++ lib/bitops.t | 53 +++++++++++++++++++++++++++++++++++++++ 5 files changed, 161 insertions(+), 5 deletions(-) create mode 100644 lib/bit-ffs.c rename lib/{log2.c => bit-fls.c} (61%) create mode 100644 lib/bitops.h create mode 100644 lib/bitops.t diff --git a/lib/Makefile b/lib/Makefile index 734ef01a..73501c7b 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -17,7 +17,8 @@ LIBUCW_MODS= \ fb-file carefulio fb-mem fb-temp fb-mmap fb-limfd fb-buffer \ str_ctype str_upper str_lower unicode-utf8 stkstring \ wildmatch wordsplit ctmatch patimatch patmatch regex \ - prime random timer log2 randomkey \ + prime random timer randomkey \ + bit-ffs bit-fls \ db \ url \ mainloop exitstatus runcmd sighandler \ @@ -81,6 +82,7 @@ $(o)/lib/unicode-utf8.test: $(o)/lib/unicode-utf8-t $(o)/lib/hash-test.test: $(o)/lib/hash-test $(o)/lib/mempool.test: $(o)/lib/mempool-fmt-t $(o)/lib/mempool-str-t $(o)/lib/stkstring.test: $(o)/lib/stkstring-t +$(o)/lib/bitops.test: $(o)/lib/bit-ffs-t $(o)/lib/bit-fls-t INCLUDES+=$(o)/lib/.include-stamp $(o)/lib/.include-stamp: $(addprefix $(s)/lib/,$(LIBUCW_INCLUDES)) diff --git a/lib/bit-ffs.c b/lib/bit-ffs.c new file mode 100644 index 00000000..8a9198d1 --- /dev/null +++ b/lib/bit-ffs.c @@ -0,0 +1,46 @@ +/* + * UCW Library -- Find Lowest Set Bit + * + * (c) 2005 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#include "lib/lib.h" +#include "lib/bitops.h" + +/* Just a table, the rest is in bitops.h */ + +const byte ffs_table[] = { + 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 +}; + +#ifdef TEST + +#include + +int main(void) +{ + uns i; + while (scanf("%x", &i) == 1) + printf("%d\n", bit_ffs(i)); + return 0; +} + +#endif diff --git a/lib/log2.c b/lib/bit-fls.c similarity index 61% rename from lib/log2.c rename to lib/bit-fls.c index 8fedaf6b..6a6227dd 100644 --- a/lib/log2.c +++ b/lib/bit-fls.c @@ -1,21 +1,22 @@ /* - * UCW Library -- Binary Logarithm + * UCW Library -- Find Highest Set Bit * - * (c) 1997 Martin Mares + * (c) 1997-2005 Martin Mares * * This software may be freely distributed and used according to the terms * of the GNU Lesser General Public License. */ #include "lib/lib.h" +#include "lib/bitops.h" int -fls(u32 x) +bit_fls(u32 x) { uns l; if (!x) - return 0; + return -1; l = 0; if (x & 0xffff0000) { l += 16; x &= 0xffff0000; } @@ -25,3 +26,17 @@ fls(u32 x) if (x & 0xaaaaaaaa) l++; return l; } + +#ifdef TEST + +#include + +int main(void) +{ + uns i; + while (scanf("%x", &i) == 1) + printf("%d\n", bit_fls(i)); + return 0; +} + +#endif diff --git a/lib/bitops.h b/lib/bitops.h new file mode 100644 index 00000000..c1e63710 --- /dev/null +++ b/lib/bitops.h @@ -0,0 +1,40 @@ +/* + * UCW Library -- Bit Operations + * + * (c) 2005 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#ifndef _UCW_BITOPS_H +#define _UCW_BITOPS_H + +/* Find highest bit set (i.e., the floor of the binary logarithm) (bit-fls.c) */ + +int bit_fls(u32 x); /* bit_fls(0)=-1 */ + +/* Find lowest bit set, undefined for zero argument (bit-ffs.c) */ + +extern const byte ffs_table[256]; + +#ifdef __pentium4 /* On other ia32 machines, the C version is faster */ + +static inline uns bit_ffs(uns w) +{ + asm("bsfl %1,%0" :"=r" (w) :"rm" (w)); + return w; +} + +#else + +static inline uns bit_ffs(uns w) +{ + uns b = (w & 0xffff) ? 0 : 16; + b += ((w >> b) & 0xff) ? 0 : 8; + return b + ffs_table[(w >> b) & 0xff]; +} + +#endif + +#endif diff --git a/lib/bitops.t b/lib/bitops.t new file mode 100644 index 00000000..abf350ea --- /dev/null +++ b/lib/bitops.t @@ -0,0 +1,53 @@ +# Tests for bitops modules + +Run: obj/lib/bit-ffs-t +In: 1 + 2 + 3 + 4 + 5 + 6 + 12345678 + 23030300 + 23030000 + 23000000 + 40000000 + 80000000 +Out: 0 + 1 + 0 + 2 + 0 + 1 + 3 + 8 + 16 + 24 + 30 + 31 + +Run: obj/lib/bit-fls-t +In: 1 + 2 + 3 + 4 + 5 + 6 + 12345678 + 23030303 + 03030303 + 00030303 + 00000303 + 0fedcba9 +Out: 0 + 1 + 1 + 2 + 2 + 2 + 28 + 29 + 25 + 17 + 9 + 27 -- 2.39.5