From 048efdfbd59b00fe184c1cda7e9cf4af9b447156 Mon Sep 17 00:00:00 2001 From: Behdad Esfahbod Date: Wed, 3 Jan 2007 20:08:53 +0000 Subject: [PATCH] Fix bug in g_bit_nth_lsf (#371631) and use __builtin_clzl for 2007-01-03 Behdad Esfahbod * glib/gutils.h: Fix bug in g_bit_nth_lsf (#371631) and use __builtin_clzl for g_bit_storage if available (#371670). * tests/Makefile.am: * tests/bit-test.c: New test, to test g_bit_* operations against naive and builtin implementations. svn path=/trunk/; revision=5200 --- ChangeLog | 9 +++ glib/gutils.h | 20 ++++--- tests/Makefile.am | 2 + tests/bit-test.c | 145 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 168 insertions(+), 8 deletions(-) create mode 100644 tests/bit-test.c diff --git a/ChangeLog b/ChangeLog index 479f8bc0..e93a4519 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2007-01-03 Behdad Esfahbod + + * glib/gutils.h: Fix bug in g_bit_nth_lsf (#371631) and use + __builtin_clzl for g_bit_storage if available (#371670). + + * tests/Makefile.am: + * tests/bit-test.c: New test, to test g_bit_* operations against + naive and builtin implementations. + 2007-01-02 Behdad Esfahbod * configure.in: Avoid more warnings from running libtool --config. diff --git a/glib/gutils.h b/glib/gutils.h index 6a0ca478..06845b0b 100644 --- a/glib/gutils.h +++ b/glib/gutils.h @@ -250,10 +250,10 @@ gchar* g_find_program_in_path (const gchar *program); /* Bit tests */ G_INLINE_FUNC gint g_bit_nth_lsf (gulong mask, - gint nth_bit); + gint nth_bit) G_GNUC_CONST; G_INLINE_FUNC gint g_bit_nth_msf (gulong mask, - gint nth_bit); -G_INLINE_FUNC guint g_bit_storage (gulong number); + gint nth_bit) G_GNUC_CONST; +G_INLINE_FUNC guint g_bit_storage (gulong number) G_GNUC_CONST; /* Trash Stacks * elements need to be >= sizeof (gpointer) @@ -277,33 +277,36 @@ G_INLINE_FUNC gint g_bit_nth_lsf (gulong mask, gint nth_bit) { - do + if (G_UNLIKELY (nth_bit < -1)) + nth_bit = -1; + while (nth_bit < ((GLIB_SIZEOF_LONG * 8) - 1)) { nth_bit++; if (mask & (1UL << nth_bit)) return nth_bit; } - while (nth_bit < ((GLIB_SIZEOF_LONG * 8) - 1)); return -1; } G_INLINE_FUNC gint g_bit_nth_msf (gulong mask, gint nth_bit) { - if (nth_bit < 0) + if (nth_bit < 0 || G_UNLIKELY (nth_bit > GLIB_SIZEOF_LONG * 8)) nth_bit = GLIB_SIZEOF_LONG * 8; - do + while (nth_bit > 0) { nth_bit--; if (mask & (1UL << nth_bit)) return nth_bit; } - while (nth_bit > 0); return -1; } G_INLINE_FUNC guint g_bit_storage (gulong number) { +#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) + return number ? GLIB_SIZEOF_LONG * 8 - __builtin_clzl(number) : 1; +#else register guint n_bits = 0; do @@ -313,6 +316,7 @@ g_bit_storage (gulong number) } while (number); return n_bits; +#endif } G_INLINE_FUNC void g_trash_stack_push (GTrashStack **stack_p, diff --git a/tests/Makefile.am b/tests/Makefile.am index 601d9583..b8f9823b 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -65,6 +65,7 @@ test_programs = \ atomic-test \ array-test \ base64-test \ + bit-test \ $(CXX_TEST) \ child-test \ completion-test \ @@ -130,6 +131,7 @@ module_ldadd = $(libgmodule) $(G_MODULE_LIBS) $(progs_ldadd) atomic_test_LDADD = $(progs_ldadd) array_test_LDADD = $(progs_ldadd) base64_test_LDADD = $(progs_ldadd) +bit_test_LDADD = $(progs_ldadd) bookmarkfile_test_LDADD = $(progs_ldadd) child_test_LDADD = $(thread_ldadd) completion_test_LDADD = $(progs_ldadd) diff --git a/tests/bit-test.c b/tests/bit-test.c new file mode 100644 index 00000000..4fba905e --- /dev/null +++ b/tests/bit-test.c @@ -0,0 +1,145 @@ +#include + +#if defined(__GNUC__) && (__GNUC__ >= 4) +# define TEST_BUILTINS 1 +#else +# define TEST_BUILTINS 0 +#endif + +#if TEST_BUILTINS +static gint +builtin_bit_nth_lsf1 (gulong mask, gint nth_bit) +{ + if (nth_bit >= 0) + { + if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1)) + mask &= -(1<<(nth_bit+1)); + else + mask = 0; + } + return __builtin_ffsl(mask) - 1; +} + +static gint +builtin_bit_nth_lsf2 (gulong mask, gint nth_bit) +{ + if (nth_bit >= 0) + { + if (G_LIKELY (nth_bit < GLIB_SIZEOF_LONG * 8 - 1)) + mask &= -(1<<(nth_bit+1)); + else + mask = 0; + } + return mask ? __builtin_ctzl(mask) : -1; +} + +static gint +builtin_bit_nth_msf (gulong mask, gint nth_bit) +{ + if (nth_bit >= 0 && nth_bit < GLIB_SIZEOF_LONG * 8) + mask &= (1< GLIB_SIZEOF_LONG * 8)) + nth_bit = GLIB_SIZEOF_LONG * 8; + while (nth_bit > 0) + { + nth_bit--; + if (mask & (1UL << nth_bit)) + return nth_bit; + } + return -1; +} + +static guint +naive_bit_storage (gulong number) +{ + register guint n_bits = 0; + + do + { + n_bits++; + number >>= 1; + } + while (number); + return n_bits; +} + + + +#define TEST(f1, f2, i) \ + if (f1 (i) != f2 (i)) { \ + g_error (G_STRINGIFY (f1) " (%lu) = %d; " \ + G_STRINGIFY (f2) " (%lu) = %d; ", \ + i, f1 (i), \ + i, f2 (i)); \ + return 1; \ + } +#define TEST2(f1, f2, i, n) \ + if (f1 (i, n) != f2 (i, n)) { \ + g_error (G_STRINGIFY (f1) " (%lu, %d) = %d; " \ + G_STRINGIFY (f2) " (%lu, %d) = %d; ", \ + i, n, f1 (i, n), \ + i, n, f2 (i, n)); \ + return 1; \ + } + +int +main (void) +{ + gulong i; + gint nth_bit; + + /* we loop like this: 0, -1, 1, -2, 2, -3, 3, ... */ + for (i = 0; (glong)i < 1500 ; i = -(i+((glong)i>=0))) { + +#if TEST_BUILTINS + TEST (naive_bit_storage, builtin_bit_storage, i); +#endif + TEST (naive_bit_storage, g_bit_storage, i); + + for (nth_bit = -3; nth_bit <= 2 + GLIB_SIZEOF_LONG * 8; nth_bit++) { + +#if TEST_BUILTINS + TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf1, i, nth_bit); + TEST2 (naive_bit_nth_lsf, builtin_bit_nth_lsf2, i, nth_bit); +#endif + TEST2 (naive_bit_nth_lsf, g_bit_nth_lsf, i, nth_bit); + +#if TEST_BUILTINS + TEST2 (naive_bit_nth_msf, builtin_bit_nth_msf, i, nth_bit); +#endif + TEST2 (naive_bit_nth_msf, g_bit_nth_msf, i, nth_bit); + + } + } + + return 0; +} -- 2.34.1