[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] ffs: avoid undefined behavior
From: |
Eric Blake |
Subject: |
[PATCH] ffs: avoid undefined behavior |
Date: |
Fri, 15 Jul 2011 14:29:21 -0600 |
* lib/ffs.c (ffs): Provide fallback for non-32-bit int.
* tests/test-ffs.c (naive, main): Avoid signed shifts.
Reported by Bruno Haible.
Signed-off-by: Eric Blake <address@hidden>
---
ChangeLog | 7 +++++++
lib/ffs.c | 31 +++++++++++++++++++++++--------
tests/test-ffs.c | 8 ++++----
3 files changed, 34 insertions(+), 12 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 465e8d0..2a67a7e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2011-07-15 Eric Blake <address@hidden>
+
+ ffs: avoid undefined behavior
+ * lib/ffs.c (ffs): Provide fallback for non-32-bit int.
+ * tests/test-ffs.c (naive, main): Avoid signed shifts.
+ Reported by Bruno Haible.
+
2011-07-12 Bruno Haible <address@hidden>
pthread_sigmask: Rely on module 'threadlib'.
diff --git a/lib/ffs.c b/lib/ffs.c
index b23210b..b037d47 100644
--- a/lib/ffs.c
+++ b/lib/ffs.c
@@ -18,6 +18,8 @@
#include <strings.h>
+#include <limits.h>
+
int
ffs (int i)
{
@@ -26,13 +28,26 @@ ffs (int i)
#else
/* http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
gives this deBruijn constant for a branch-less computation, although
- that table counted trailing zeros rather than bit position. */
- static unsigned int table[] = {
- 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
- 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
- };
- unsigned int u = i;
- unsigned int bit = u & -u;
- return table[(bit * 0x077cb531U) >> 27] - !i;
+ that table counted trailing zeros rather than bit position. This
+ requires 32-bit int, we fall back to a naive algorithm on the rare
+ platforms where that assumption is not true. */
+ if (CHAR_BIT * sizeof i == 32)
+ {
+ static unsigned int table[] = {
+ 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
+ 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
+ };
+ unsigned int u = i;
+ unsigned int bit = u & -u;
+ return table[(bit * 0x077cb531U) >> 27] - !i;
+ }
+ else
+ {
+ unsigned int j;
+ for (j = 0; j < CHAR_BIT * sizeof i; j++)
+ if (i & (1U << j))
+ return j + 1;
+ return 0;
+ }
#endif
}
diff --git a/tests/test-ffs.c b/tests/test-ffs.c
index a7c615e..cfc4d0e 100644
--- a/tests/test-ffs.c
+++ b/tests/test-ffs.c
@@ -29,9 +29,9 @@ SIGNATURE_CHECK (ffs, int, (int));
static int
naive (int i)
{
- int j;
+ unsigned int j;
for (j = 0; j < CHAR_BIT * sizeof i; j++)
- if (i & (1 << j))
+ if (i & (1U << j))
return j + 1;
return 0;
}
@@ -45,8 +45,8 @@ main (int argc, char *argv[])
ASSERT (ffs (i) == naive (i));
for (i = 0; i < CHAR_BIT * sizeof i; i++)
{
- ASSERT (ffs (1 << i) == naive (1 << i));
- ASSERT (ffs (1 << i) == i + 1);
+ ASSERT (ffs (1U << i) == naive (1U << i));
+ ASSERT (ffs (1U << i) == i + 1);
}
return 0;
}
--
1.7.1