diff options
author | Eric Blake <eblake@redhat.com> | 2011-07-15 14:26:43 -0600 |
---|---|---|
committer | Eric Blake <eblake@redhat.com> | 2011-07-15 14:28:29 -0600 |
commit | d767af3634fa49b048bf073327092be19c7c7fd1 (patch) | |
tree | c1ad6b18f734d715d627463076b01803c95515b3 /lib/ffs.c | |
parent | bd399f07ee4f383fad038efad25a659fcdc0bbb0 (diff) | |
download | gnulib-d767af3634fa49b048bf073327092be19c7c7fd1.tar.gz |
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>
Diffstat (limited to 'lib/ffs.c')
-rw-r--r-- | lib/ffs.c | 31 |
1 files changed, 23 insertions, 8 deletions
@@ -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 } |