Mercurial > hg > octave-kai > gnulib-hg
changeset 17038:86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
While this only affects non-gcc compilers, we can assume that
lookups are faster than conditionals, even if it results in
a slightly larger executable size.
* lib/count-leading-zeros.h (count_leading_zeros_32): Use an
alternate implementation, suggested by Jim Meyering.
Signed-off-by: Eric Blake <eblake@redhat.com>
author | Eric Blake <eblake@redhat.com> |
---|---|
date | Sat, 11 Aug 2012 07:34:00 -0600 |
parents | abd788a78228 |
children | e5d33904a8b2 |
files | ChangeLog lib/count-leading-zeros.h |
diffstat | 2 files changed, 22 insertions(+), 25 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2012-08-11 Eric Blake <eblake@redhat.com> + + count-leading-zeros: use a lookup table on non-gcc compilers + * lib/count-leading-zeros.h (count_leading_zeros_32): Use an + alternate implementation, suggested by Jim Meyering. + 2012-08-10 Eric Blake <eblake@redhat.com> count-leading-zeros: new module
--- a/lib/count-leading-zeros.h +++ b/lib/count-leading-zeros.h @@ -26,7 +26,7 @@ /* Expand the code which computes the number of leading zeros of the local variable 'x' of type TYPE (an unsigned integer type) and returns it from the current function. */ -#if 0 && __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) # define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \ return x ? BUILTIN (x) : CHAR_BIT * sizeof x; #else @@ -47,30 +47,21 @@ static inline int count_leading_zeros_32 (unsigned int x) { - int count = 0; - if (x & 0xffff0000U) - x >>= 16; - else - count += 16; - if (x & 0xff00) - x >>= 8; - else - count += 8; - if (x & 0xf0) - x >>= 4; - else - count += 4; - if (x & 0xc) - x >>= 2; - else - count += 2; - if (x & 2) - x >>= 1; - else - count++; - if (!(x & 1)) - count++; - return count; + /* http://graphics.stanford.edu/~seander/bithacks.html */ + static const char deBruijnLookup[32] = { + 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 + }; + + x &= 0xffffffffU; + if (!x) + return 32; + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; + return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27]; } #endif