diff options
author | Eric Blake <eblake@redhat.com> | 2012-08-11 07:34:00 -0600 |
---|---|---|
committer | Eric Blake <eblake@redhat.com> | 2012-08-11 07:36:19 -0600 |
commit | d22f151db0e5217913ec1667a3b4e354dd88a973 (patch) | |
tree | 4301229ac796285acfeb83495f291f758c7f9c06 /lib/count-leading-zeros.h | |
parent | 0da76a94c8668319c68af5e8c2e71c80528db5de (diff) | |
download | gnulib-d22f151db0e5217913ec1667a3b4e354dd88a973.tar.gz |
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>
Diffstat (limited to 'lib/count-leading-zeros.h')
-rw-r--r-- | lib/count-leading-zeros.h | 41 |
1 files changed, 16 insertions, 25 deletions
diff --git a/lib/count-leading-zeros.h b/lib/count-leading-zeros.h index 4d7c291cf0..cbb3264e33 100644 --- 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 |