Mercurial > hg > octave-nkf > gnulib-hg
changeset 15426:60c6b6da0198
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.
Signed-off-by: Eric Blake <eblake@redhat.com>
author | Eric Blake <eblake@redhat.com> |
---|---|
date | Fri, 15 Jul 2011 14:26:43 -0600 |
parents | 8635f71da8d0 |
children | 2379b7a3f117 |
files | ChangeLog lib/ffs.c tests/test-ffs.c |
diffstat | 3 files changed, 34 insertions(+), 12 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2011-07-15 Eric Blake <eblake@redhat.com> + + 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 <bruno@clisp.org> pthread_sigmask: Rely on module 'threadlib'.
--- 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 @@ #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 }
--- a/tests/test-ffs.c +++ b/tests/test-ffs.c @@ -29,9 +29,9 @@ 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 @@ 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; }