[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] count-leading-zeros: new module
From: |
Eric Blake |
Subject: |
Re: [PATCH] count-leading-zeros: new module |
Date: |
Sat, 11 Aug 2012 07:38:20 -0600 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120717 Thunderbird/14.0 |
On 08/11/2012 01:45 AM, Jim Meyering wrote:
> Eric Blake wrote:
>> I needed gcc's clz to determine the most significant bit of a
>> number (useful for things like truncating to a power of 2),
>> and was surprised it is not a standardized function
> Did you consider using a variant of the following?
> It looks like it would be more efficient.
>
> [From http://graphics.stanford.edu/~seander/bithacks.html]
>
> Find the log base 2 of an N-bit integer in O(lg(N)) operations
> with multiply and lookup
Pushed as follows:
From d22f151db0e5217913ec1667a3b4e354dd88a973 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 11 Aug 2012 07:34:00 -0600
Subject: [PATCH] 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 <address@hidden>
---
ChangeLog | 6 ++++++
lib/count-leading-zeros.h | 41 ++++++++++++++++-------------------------
2 files changed, 22 insertions(+), 25 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 80d1b61..2b7090b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+2012-08-11 Eric Blake <address@hidden>
+
+ 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 <address@hidden>
count-leading-zeros: new module
diff --git a/lib/count-leading-zeros.h b/lib/count-leading-zeros.h
index 4d7c291..cbb3264 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
--
1.7.11.2
--
Eric Blake address@hidden +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature